<p>I would argue that the main issue with using many-one <span class="math-container">$\mathrm{NP}$</span>-reduction to define completeness is that <span class="math-container">$\exists\mathbb{R}$</span>-hardness under many-one <span class="math-container">$\mathrm{NP}$</span> reductions no longer implies <span class="math-container">$\mathrm{NP}$</span>-hardness. We still do  not know whether <span class="math-container">$\mathrm{NP} \neq \exists\mathbb{R}$</span>, so if we define <span class="math-container">$\exists\mathbb{R}$</span>-hardness using many-one <span class="math-container">$\mathrm{NP}$</span>-reductions, one could conceivably have a world in which <span class="math-container">$\mathrm{P} &lt; \mathrm{NP} = \exists\mathbb{R}$</span>, but we cannot argue that <span class="math-container">$\exists\mathbb{R}$</span>-complete problems do not belong to <span class="math-container">$\mathrm{P}$</span>. This argument really applies to any complexity class above <span class="math-container">$\mathrm{NP}$</span>.</p>
<p>To give an example, the authors of <a href="https://link.springer.com/chapter/10.1007/978-3-540-77537-9_28" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007/978-3-540-77537-9_28</a> showed that simultaneous geometric graph embedding (SGE) is  hard for <span class="math-container">$\exists\mathbb{R}$</span> under  many-one <span class="math-container">$\mathrm{NP}$</span> reductions. So they could only conclude that if SGE lies in <span class="math-container">$\mathrm{NP}$</span>, then all of <span class="math-container">$\exists\mathbb{R}$</span> lies in <span class="math-container">$\mathrm{NP}$</span>. It was later shown that SGE is <span class="math-container">$\exists\mathbb{R}$</span>-complete under standard reductions (see <a href="https://link.springer.com/article/10.1007/s00454-010-9320-x" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s00454-010-9320-x</a>), so we now know that if SGE lies in any complexity class which is closed under the standard reduction (including <span class="math-container">$\mathrm{NP}$</span> and <span class="math-container">$\mathrm{P}$</span>), then all of <span class="math-container">$\exists\mathbb{R}$</span> lies in that class. A much stronger conclusion than the original result allowed.</p>
<p>That being said, if the focus is on precision issues rather than computational complexity, many-one <span class="math-container">$\mathrm{NP}$</span>-reductions are often sufficient and will be easier to come by (as the SGE example illustrates).</p>

CC BY-SA 4.0
2022-04-12T09:49:53.263Z
Thanks for your answer and in particular the link (it is twice the same link, is that on purpose?). I had not thought of that problem with NP-reductions. I guess in the end it is always a matter of taste: When defining $\exists \mathbb{R}$ completeness over NP-reductions we'd always have to prove NP-hardness of the studied problems separately but proving $\exists \mathbb{R}$-hardness  would be easier. On the other hand, using the established definition we get NP-hardness for free but we'll have to deal with results that might collaps $\exists \mathbb{R}$ via NP-reductions separately.
sebastian
CC BY-SA 4.0
2022-04-12T16:30:17.490Z
Fixed the first link, that was wrong, thanks for pointing that out. With NP-reductions, your notion of ∃R-hardness becomes weaker (and doesn't compare well to hardness for other complexity classes). If you take your proposal further, you could ask, why not define NP-hardness using NP-reductions? The answer here would be that this notion of NP-hardness does not allow you to draw any interesting conclusions. And, for all we know, $\exists\mathbb{R}$ could be the same as NP, so NP-reductions seem too generous for $\exists\mathbb{R}$.
user66277
CC BY-SA 4.0
2022-04-09T17:30:58.690Z
2022-04-12T16:20:44.390Z
2022-04-12T16:20:44.390Z
user66277
<p>I am currently studying the complexity class <span class="math-container">$\exists \mathbb{R}$</span> which contains all problems that are reducible in polynomial time to the existential theory of the reals. In the literature completeness for this complexity class is defined as follows: A problem <span class="math-container">$A \in\exists \mathbb{R}$</span> is called <span class="math-container">$\exists \mathbb{R}$</span>-complete if and only if the problem of deciding a sentence in the existential theory of the reals can be reduced in polynomial time to <span class="math-container">$A$</span>. My question concerns this definition of <span class="math-container">$\exists \mathbb{R}$</span>-completeness and also extends to other complexity classes outside of (larger than) <span class="math-container">$NP$</span>.</p>
<p>In particular, I was wondering why we are using polynomial-time reductions to define <span class="math-container">$\exists \mathbb{R}$</span>-completeness. Of course, I understand that polynomial-time reductions are nice and somehow using them seems to work reasonably well. But isn't the idea behind completeness to establish a group of problems such that showing one of them belongs to a smaller complexity class implies a collaps in the complexity hierarchy? For <span class="math-container">$\exists \mathbb{R}$</span>-completeness I would hence assume that we want to define it in such a way that the membership of any <span class="math-container">$\exists \mathbb{R}$</span>-complete problem <span class="math-container">$A$</span> in <span class="math-container">$NP$</span> implies that <span class="math-container">$\exists \mathbb{R}=NP$</span>. To achieve this, it would suffice to work with a kind of '<span class="math-container">$NP$</span>-reduction'.</p>
<p>I think such a reduction could be defined as follows:</p>
<p><span class="math-container">$A \leq_{NP} B$</span> if and only if there is a nondeterministic Turing machine that given  a YES-instance of <span class="math-container">$A$</span> computes a YES-instance of <span class="math-container">$B$</span> in polynomial-time (i.e. at least one of the nondeterministic choices leads to a YES-instance of <span class="math-container">$B$</span>) and given a NO-instance of <span class="math-container">$A$</span> cannot output a YES-instance of <span class="math-container">$B$</span> (i.e. no matter the nondeterministic choices, it will produce a NO-instance).</p>
<p>Note that if we knew both <span class="math-container">$A \leq_{NP} B$</span> and <span class="math-container">$B \in NP$</span> this would imply <span class="math-container">$A \in NP$</span>. Hence I think that such a type of reduction would be totally fine for the definition of <span class="math-container">$\exists \mathbb{R}$</span>-completeness. I understand that this would amount to proving weaker statements and we would lose the power to imply a collaps of <span class="math-container">$\exists \mathbb{R}$</span> directly to <span class="math-container">$P$</span> as <span class="math-container">$A \leq_{NP} B$</span> and <span class="math-container">$B \in P$</span> would not imply <span class="math-container">$A \in P$</span>. But this does not seem like a good argument for using polynomial-time reductions.</p>
<p>Note that I do not know of any problem that would become complete if we were using such a weaker reduction. But I recently read a paper about the <span class="math-container">$\exists \mathbb{R}$</span>-completeness of recognising segment graphs and one of the reductions would be significantly easier using a weaker reduction instead of a polynomial-time reduction. This is also pointed out by the author on top of page 24 (<a href="https://arxiv.org/abs/1406.2636" rel="noreferrer">https://arxiv.org/abs/1406.2636</a>).</p>
<p>My questions are:</p>
<ol>
<li>Have I overlooked/forgotten a good argument for using polynomial-time reductions over weaker reductions as the one I introduced above?</li>
<li>Do you know of any examples where using weaker reductions would make a problem complete for <span class="math-container">$\exists \mathbb{R}$</span> or <span class="math-container">$PSPACE$</span> or similar?</li>
</ol>
<p>Note that I found this thread (<a href="https://cstheory.stackexchange.com/questions/25316/nexptime-completeness-with-more-time-for-reductions">NEXPTIME-completeness with more time for reductions</a>) which addresses a similar issue. The difference is however that <span class="math-container">$\exists \mathbb{R}$</span> is closed under the reduction I defined above.</p>

<cc.complexity-theory><complexity-classes><definitions><existential-theory-of-the-reals>
Reductions weaker than polynomial-time for $\exists \mathbb{R}$
sebastian
# Reductions weaker than polynomial-time for $\exists \mathbb{R}$

(Asked by: username_0 on 2022-04-08)

I am currently studying the complexity class $\exists \mathbb{R}$ which contains all problems that are reducible in polynomial time to the existential theory of the reals. In the literature completeness for this complexity class is defined as follows: A problem $A \in\exists \mathbb{R}$ is called $\exists \mathbb{R}$-complete if and only if the problem of deciding a sentence in the existential theory of the reals can be reduced in polynomial time to $A$. My question concerns this definition of $\exists \mathbb{R}$-completeness and also extends to other complexity classes outside of (larger than) $NP$.

In particular, I was wondering why we are using polynomial-time reductions to define $\exists \mathbb{R}$-completeness. Of course, I understand that polynomial-time reductions are nice and somehow using them seems to work reasonably well. But isn't the idea behind completeness to establish a group of problems such that showing one of them belongs to a smaller complexity class implies a collaps in the complexity hierarchy? For $\exists \mathbb{R}$-completeness I would hence assume that we want to define it in such a way that the membership of any $\exists \mathbb{R}$-complete problem $A$ in $NP$ implies that $\exists \mathbb{R}=NP$. To achieve this, it would suffice to work with a kind of '$NP$-reduction'.

I think such a reduction could be defined as follows:

$A \leq\_{NP} B$ if and only if there is a nondeterministic Turing machine that given a YES-instance of $A$ computes a YES-instance of $B$ in polynomial-time (i.e. at least one of the nondeterministic choices leads to a YES-instance of $B$) and given a NO-instance of $A$ cannot output a YES-instance of $B$ (i.e. no matter the nondeterministic choices, it will produce a NO-instance).

Note that if we knew both $A \leq\_{NP} B$ and $B \in NP$ this would imply $A \in NP$. Hence I think that such a type of reduction would be totally fine for the definition of $\exists \mathbb{R}$-completeness. I understand that this would amount to proving weaker statements and we would lose the power to imply a collaps of $\exists \mathbb{R}$ directly to $P$ as $A \leq\_{NP} B$ and $B \in P$ would not imply $A \in P$. But this does not seem like a good argument for using polynomial-time reductions.

Note that I do not know of any problem that would become complete if we were using such a weaker reduction. But I recently read a paper about the $\exists \mathbb{R}$-completeness of recognising segment graphs and one of the reductions would be significantly easier using a weaker reduction instead of a polynomial-time reduction. This is also pointed out by the author on top of page 24 (<https://arxiv.org/abs/1406.2636>).

My questions are:

1. Have I overlooked/forgotten a good argument for using polynomial-time reductions over weaker reductions as the one I introduced above?
2. Do you know of any examples where using weaker reductions would make a problem complete for $\exists \mathbb{R}$ or $PSPACE$ or similar?

Note that I found this thread ([NEXPTIME-completeness with more time for reductions](https://cstheory.stackexchange.com/questions/25316/nexptime-completeness-with-more-time-for-reductions)) which addresses a similar issue. The difference is however that $\exists \mathbb{R}$ is closed under the reduction I defined above.

**Tags:** cc.complexity-theory, complexity-classes, definitions, existential-theory-of-the-reals

---

## 1 answers

### Answer by username_1 on 2022-04-09. Score: 6 | Accepted answer

I would argue that the main issue with using many-one $\mathrm{NP}$-reduction to define completeness is that $\exists\mathbb{R}$-hardness under many-one $\mathrm{NP}$ reductions no longer implies $\mathrm{NP}$-hardness. We still do not know whether $\mathrm{NP} \neq \exists\mathbb{R}$, so if we define $\exists\mathbb{R}$-hardness using many-one $\mathrm{NP}$-reductions, one could conceivably have a world in which $\mathrm{P} < \mathrm{NP} = \exists\mathbb{R}$, but we cannot argue that $\exists\mathbb{R}$-complete problems do not belong to $\mathrm{P}$. This argument really applies to any complexity class above $\mathrm{NP}$.

To give an example, the authors of <https://link.springer.com/chapter/10.1007/978-3-540-77537-9_28> showed that simultaneous geometric graph embedding (SGE) is hard for $\exists\mathbb{R}$ under many-one $\mathrm{NP}$ reductions. So they could only conclude that if SGE lies in $\mathrm{NP}$, then all of $\exists\mathbb{R}$ lies in $\mathrm{NP}$. It was later shown that SGE is $\exists\mathbb{R}$-complete under standard reductions (see <https://link.springer.com/article/10.1007/s00454-010-9320-x>), so we now know that if SGE lies in any complexity class which is closed under the standard reduction (including $\mathrm{NP}$ and $\mathrm{P}$), then all of $\exists\mathbb{R}$ lies in that class. A much stronger conclusion than the original result allowed.

That being said, if the focus is on precision issues rather than computational complexity, many-one $\mathrm{NP}$-reductions are often sufficient and will be easier to come by (as the SGE example illustrates).

> **Comments:**
> **username_0**: Thanks for your answer and in particular the link (it is twice the same link, is that on purpose?). I had not thought of that problem with NP-reductions. I guess in the end it is always a matter of taste: When defining $\exists \mathbb{R}$ completeness over NP-reductions we'd always have to prove NP-hardness of the studied problems separately but proving $\exists \mathbb{R}$-hardness  would be easier. On the other hand, using the established definition we get NP-hardness for free but we'll have to deal with results that might collaps $\exists \mathbb{R}$ via NP-reductions separately.  
> **username_1**: Fixed the first link, that was wrong, thanks for pointing that out. With NP-reductions, your notion of ∃R-hardness becomes weaker (and doesn't compare well to hardness for other complexity classes). If you take your proposal further, you could ask, why not define NP-hardness using NP-reductions? The answer here would be that this notion of NP-hardness does not allow you to draw any interesting conclusions. And, for all we know, $\exists\mathbb{R}$ could be the same as NP, so NP-reductions seem too generous for $\exists\mathbb{R}$.  

---

