2
$\begingroup$

While studying ${\bf NP}$ complete problems we have from Ladners' theorem - if ${\bf P}$ $\neq$ ${\bf NP}$-there are ${\bf NP}$ problems not in the class ${\bf P}$ nor ${\bf NP}$-complete. Ladners' theorem is well known in the setting of ${\bf NP}$ completeness. The analog in the setting of real computation using the Blum-Shub-Smale model, that ${\bf P}$$_{\mathbb{R}}$ $\neq$ ${\bf NP}$$_{\mathbb{R}} \Rightarrow$ there are ${\bf NP}$$_{\mathbb{R}}$ problems not in the class ${\bf P}$$_{\mathbb{R}}$ nor are they ${\bf NP}_{\mathbb{R}}$ complete should hold. So it is natural to think of ${\bf NP}$ intermediate problems over reals, or ${\bf NPI}$$_{\mathbb{R}}$ in the context of ladners theorem holding over reals (using the Blum Shub Smale model). Are there any candidate problems for this class ${\bf NPI}$$_{\mathbb{R}}$. Is it natural to think of the class ${\bf NPI}$$_{\mathbb{R}}$ - even to think of problems in this class of ${\bf NPI}$$_{\mathbb{R}}$, or even any known?

$\endgroup$
  • $\begingroup$ Are you really only interested in the BSS model, or algebraic computation more generally? For example, there are problems that are VNP-intermediate (not in VP nor VNP-complete) over finite fields, assuming PH doesn't collapse to the second level (see Mahajan-Saurabh and references to Burgisser therein). There are also algebraic problems over finite fields that might be NP-intermediate in the usual Boolean sense. $\endgroup$ – Joshua Grochow Apr 18 '17 at 14:15

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.