Are there unambiguous analogues of $NP_{R}$ (using the BSS model, in all discussion)complete problems, and any results known about them? For instance, the canonical $NP_{R}$ complete problem $4FEAS$ ( ref. here but there could be a better reference ) could have an unambiguous version - $U4FEAS$ ( not allowing degenerate roots, for simplicity)in which there is only one zero or root for a system of degree 4 polynomial (for more about quantifiers over reals ). Of interest to study such unambiguous classes could be (loosely) Smales' 17th problem. How would the complexity differ (from say, $NP_{R}$, or higher in the $PH_{R}$ hierarchy) when we just have one root for a system of polynomials in the above context?

As the $PH$ can be defined over arbitrary structures - $K$, there is a $PH_{K}$, over that structure. We could have an Unambiguous Polynomial Hierarchy over the structure $K$- $UPH_{K}$- ( analogous Unambiguous Polynomial Hierarchy), are there any results of Unambiguous versions of classes over Reals?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.