<p>While studying <span class="math-container">${\bf NP}$</span> complete problems we have from Ladners' theorem - if <span class="math-container">${\bf P}$</span> <span class="math-container">$\neq$</span> <span class="math-container">${\bf NP}$</span>-there are <span class="math-container">${\bf NP}$</span> problems not in the class <span class="math-container">${\bf P}$</span> nor <span class="math-container">${\bf NP}$</span>-complete.  Ladners' theorem is well known in the setting of <span class="math-container">${\bf NP}$</span> completeness. The analog in the setting of real computation using the Blum-Shub-Smale model, that  <span class="math-container">${\bf P}$$_{\mathbb{R}}$</span> <span class="math-container">$\neq$</span> <span class="math-container">${\bf NP}$$_{\mathbb{R}} \Rightarrow$</span> there are <span class="math-container">${\bf NP}$$_{\mathbb{R}}$</span> problems not in the class <span class="math-container">${\bf P}$$_{\mathbb{R}}$</span> nor are they <span class="math-container">${\bf NP}_{\mathbb{R}}$</span> complete should hold. So it is natural to think of <span class="math-container">${\bf NP}$</span> intermediate problems over reals, or <span class="math-container">${\bf NPI}$$_{\mathbb{R}}$</span> 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 <span class="math-container">${\bf NPI}$$_{\mathbb{R}}$</span>. Is it natural to think of the class <span class="math-container">${\bf NPI}$$_{\mathbb{R}}$</span> - even to think of problems in this class of <span class="math-container">${\bf NPI}$$_{\mathbb{R}}$</span>, or even any known?</p>

CC BY-SA 3.0
2017-04-18T14:15:16.780Z
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](http://dx.doi.org/10.1007/s00224-016-9740-y) 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
CC BY-SA 4.0
2021-01-24T05:38:40.440Z
Any  results that generalize the VNP intermediate problems to other algebraic structures(other than finite fields)?
user3483902
CC BY-SA 4.0
2021-01-25T00:45:06.673Z
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).
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-01-25T00:47:59.937Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-01-25T07:35:39.800Z
@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.
user3483902
<cc.complexity-theory><computing-over-reals>
NP Intermediate problems over Reals
user3483902
# NP Intermediate problems over Reals

(Asked by: username_0 on 2016-02-02)

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?

**Tags:** cc.complexity-theory, computing-over-reals
> **Comments:**
> **username_1**: 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](http://dx.doi.org/10.1007/s00224-016-9740-y) and references to Burgisser therein). There are also algebraic problems over finite fields that might be NP-intermediate in the usual Boolean sense.  
> **username_0**: Any  results that generalize the VNP intermediate problems to other algebraic structures(other than finite fields)?  
> **username_2**: 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).  
> **username_2**: 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.  
> **username_0**: @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.  

---

## 0 answers

