0
$\begingroup$

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?

$\endgroup$

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.