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?
$\begingroup$
$\endgroup$
5
-
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 GrochowApr 18, 2017 at 14:15
-
$\begingroup$ Any results that generalize the VNP intermediate problems to other algebraic structures(other than finite fields)? $\endgroup$– user3483902Jan 24, 2021 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 HansenJan 25, 2021 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 HansenJan 25, 2021 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$– user3483902Jan 25, 2021 at 7:35
Add a comment
|