6
$\begingroup$

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.

$\endgroup$

1 Answer 1

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – sebastian
    Apr 12, 2022 at 9:49
  • $\begingroup$ 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}$. $\endgroup$
    – user66277
    Apr 12, 2022 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.