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). Or an analogue of Ladners theorem over the reals(or other algebraic structures). 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?

  • 2
    $\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
  • $\begingroup$ Any results that generalize the VNP intermediate problems to other algebraic structures(other than finite fields)? $\endgroup$ – user3483902 Jan 24 at 5:38
  • $\begingroup$ There is a technical issue with translating Ladner's theorem to BSS machines. Since the model allows for arbitrary real machine constants it is not possible to enumerate the machines (the model is in a sense nonuniform). $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 25 at 0:45
  • $\begingroup$ As for a candidate problem that is neither in $\mathrm{P}_\mathbb{R}$ nor $\mathrm{NP}_\mathbb{R}$-complete, any $\mathrm{DNP}_\mathbb{R}$ complete problem would be a natural candidate. Other good candidates would be TSP or Knapsack over the reals. $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 25 at 0:47
  • $\begingroup$ @Kristoffer $DNP_{R}$ complete problems would be good candidates for such an intermediate class - a proof that such $NPI_{R}$ problems exist without need for a Ladner like proof. $\endgroup$ – user3483902 Jan 25 at 7:35

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.