ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let f∈Z[X]f \in \mathbb{Z}[X] be a separable polynomial. For an order AA, write ZA(f)Z_A(f) for the zero set of ff in AA, and let Πf\Pi_f denote the problem of deciding, given an order AA, whether ZA(f)Z_A(f) is non-empty. The complexity classes P\mathcal{P} and NPC\mathcal{NPC} denote polynomial-time and NP-complete problems, respectively.

Dichotomy conjecture. Πf\Pi_f lies in P\mathcal{P} or in NPC\mathcal{NPC}.

The paper places this conjecture in the study of the complexity of deciding whether polynomial equations have roots in orders. It is known that Πf\Pi_f lies in NP\mathcal{NP} for separable ff, and examples show that both polynomial-time and NP-complete cases occur; the general dichotomy remains unresolved.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.