patternMinor
Query: Given a graph, is edge x in an optimal TSP tour?
Viewed 0 times
tourtspgraphoptimalqueryedgegiven
Problem
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?
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?
Solution
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:
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.
$$
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.
Context
StackExchange Computer Science Q#122188, answer score: 5
Revisions (0)
No revisions yet.