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

Question

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.

Answer 1

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).