Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph.

It may be argued that the complexity of this problem is strictly greater than any co-NP problem. The idea is that it's perhaps impossible to come up with a counter-example, since we need e.g. an optimal tour candidate before we can consider a counterexample (but no optimal tour candidate is given in this problem statement).

On the other hand, it may be argued that the complexity of this problem is strictly smaller than any P-space-complete problem, as our problem may be seen as

$\exists$"a tour A containing x" $\forall$"tours B": (some formula stating that A <= B)

whereas some probably "minimal" P-space-complete problem has O(n) alternations of $\exists$ and $\forall$: the quantified boolean formula problem (QBF).

Based on this argument, is it reasonable to expect that there's a complexity class between co-NP and PSPACE? Does this particular class have a name? Can we expect to find arbitrarily more such classes by adding another one alternation of $\forall$ or $\exists$ to the previously found such class?

  • 1
    $\begingroup$ Are you familiar with the polynomial hierarchy? $\endgroup$ – Yuval Filmus Mar 26 '20 at 17:15
  • $\begingroup$ @YuvalFilmus I've seen that page a couple of times before and each time I got lost in the mathematical symbols. This time I think I'm starting to understand at least the definitions. The problem described here seems to be in $\Sigma^P_2$. Thanks! $\endgroup$ – Albert Hendriks Mar 26 '20 at 19:08

The complexity class $\Sigma_2^P$, which is the second level of the polynomial hierarchy, consists of all languages $L$ for which there exists a polytime predicate $f$ and a polynomial $p$ such that $$ x \in L \Longleftrightarrow \exists y \forall z \, f(x,y,z), \text{ where } |y|,|z| \leq p(|x|). $$ This is the natural location for your problem:

  • $x$ is a pair $(G,e)$, where $G$ is a graph and $e$ is an edge of $G$.
  • $y$ is a TSP tour.
  • $z$ is a TSP tour.
  • $f(x,y,z)$ holds if (i) $y,z$ are TSP tours of $G$; (ii) $e \in y$; and (iii) $w(y) \leq w(z)$.

More generally, $\Sigma_k^P$ is defined similarly with $k$ quantifier alternations, and $\Pi_k^P$ is defined the same but starting with a universal rather than an existential quantifier. For example, $\Sigma_1^P$ is NP and $\Pi_1^P$ is coNP. We also define $\Delta_k^P = \Sigma_k^p \cap \Pi_k^P$, generalizing the class NP∩coNP.

We define $\Sigma_k^P$-hard and $\Sigma_k^P$-complete in analog to NP-hard and NP-complete, using polynomial time reductions. The obvious question to ask in your case is whether your language is $\Sigma_2^P$-complete.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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