Dichotomy conjecture for root-finding in orders
Statement
Let be a separable polynomial. For an order , write for the zero set of in , and let denote the problem of deciding, given an order , whether is non-empty. The complexity classes and denote polynomial-time and NP-complete problems, respectively.
Dichotomy conjecture. lies in or in .
The paper places this conjecture in the study of the complexity of deciding whether polynomial equations have roots in orders. It is known that lies in for separable , 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.