# NP Intermediate problems over Reals

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?

• 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. – Joshua Grochow Apr 18 '17 at 14:15