patternMinor
Complexity Classes UP and US
Viewed 0 times
andcomplexityclasses
Problem
According to complexity zoo:
Class UP (Unambiguous Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that
Class US (Unique Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that the answer is “yes” if and only if exactly one computation path accepts.
In contrast to UP, a US machine can legally have more than one accepting path that just means that the corresponding input is not in the language.
My question is:
but not in other? We know that UP $\cup$ coNP $\subseteq$ US.
that input is not in the language? (Maybe I am missing something
trivial here)
Class UP (Unambiguous Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that
- If the answer is “yes,” exactly one computation path accepts.
- If the answer is “no,” all computation paths reject.
Class US (Unique Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that the answer is “yes” if and only if exactly one computation path accepts.
In contrast to UP, a US machine can legally have more than one accepting path that just means that the corresponding input is not in the language.
My question is:
- Is there an example of a problem which is known to be in one class,
but not in other? We know that UP $\cup$ coNP $\subseteq$ US.
- It is known that class US is a subset of $P^{NP}$. A well-known example is USAT which is known to be US-hard (and coNP hard) but not known to be coNP. US is not known to be equal to coNP. Also, I know that coNP $\subseteq$ US. Can one give an intuitive reason for this?
- How can a machine have more than one accepting path, but
that input is not in the language? (Maybe I am missing something
trivial here)
Solution
Let me start with your third question. It seems that you don't quite understand the definitions of $\mathsf{UP}$ and $\mathsf{US}$, so let me repeat them here.
Definition of $\mathsf{UP}$. Property U. A non-deterministic Turing machine has property U if every input has at most one accepting path. The language accepted by such a machine consists of all inputs which do have an accepting path.
The class $\mathsf{UP}$ consists of all languages accepted by non-deterministic Turing machines having property U and running in polynomial time.
Definition of $\mathsf{US}$. U-acceptance. The language accepted by a non-deterministic Turing machine consists of all inputs which have an accepting path. In contrast, the language U-accepted by a non-deterministic Turing machine consists of all inputs having exactly one accepting path. Any input having either no accepting path or at least two accepting path does not belong to the language U-accepted by the machine.
The class $\mathsf{US}$ consists of all languages U-accepted by non-deterministic Turing machines running in polynomial time.
As for your second question, to show that $\mathsf{coNP} \subseteq \mathsf{US}$ it suffices to reduces $\mathsf{coSAT}$ to $\mathsf{US}$. Given a SAT instance $\phi = C_1 \land \cdots \land C_m$, let
$$\psi = (v \lor C_1) \land \cdots \land (v \lor C_m) \land (\lnot v \lor x_1) \land \cdots \land (\lnot v \lor x_n),$$ where $v$ is a new variable and $x_1,\ldots,x_n$ are the original variables. Then $\psi$ has a unique satisfying assignment (in which all variables are true) iff $\phi$ is unsatisfiable.
As for your first question, if $\mathsf{P} = \mathsf{NP}$ then $\mathsf{P} = \mathsf{UP} = \mathsf{US}$, so no unconditional separation is currently known. If you're interested in conditional separations, I suggest asking a new question focused just on that issue.
Definition of $\mathsf{UP}$. Property U. A non-deterministic Turing machine has property U if every input has at most one accepting path. The language accepted by such a machine consists of all inputs which do have an accepting path.
The class $\mathsf{UP}$ consists of all languages accepted by non-deterministic Turing machines having property U and running in polynomial time.
Definition of $\mathsf{US}$. U-acceptance. The language accepted by a non-deterministic Turing machine consists of all inputs which have an accepting path. In contrast, the language U-accepted by a non-deterministic Turing machine consists of all inputs having exactly one accepting path. Any input having either no accepting path or at least two accepting path does not belong to the language U-accepted by the machine.
The class $\mathsf{US}$ consists of all languages U-accepted by non-deterministic Turing machines running in polynomial time.
As for your second question, to show that $\mathsf{coNP} \subseteq \mathsf{US}$ it suffices to reduces $\mathsf{coSAT}$ to $\mathsf{US}$. Given a SAT instance $\phi = C_1 \land \cdots \land C_m$, let
$$\psi = (v \lor C_1) \land \cdots \land (v \lor C_m) \land (\lnot v \lor x_1) \land \cdots \land (\lnot v \lor x_n),$$ where $v$ is a new variable and $x_1,\ldots,x_n$ are the original variables. Then $\psi$ has a unique satisfying assignment (in which all variables are true) iff $\phi$ is unsatisfiable.
As for your first question, if $\mathsf{P} = \mathsf{NP}$ then $\mathsf{P} = \mathsf{UP} = \mathsf{US}$, so no unconditional separation is currently known. If you're interested in conditional separations, I suggest asking a new question focused just on that issue.
Context
StackExchange Computer Science Q#83997, answer score: 5
Revisions (0)
No revisions yet.