# Reductions weaker than polynomial-time for $\exists \mathbb{R}$

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) which addresses a similar issue. The difference is however that $$\exists \mathbb{R}$$ is closed under the reduction I defined above.

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).
• 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. Commented Apr 12, 2022 at 9:49
• 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}$. Commented Apr 12, 2022 at 16:30