2
$\begingroup$

According to complexity zoo: Class UP (Unambiguous Polynomial-Time) is defined as: The class of decision problems solvable by an NP machine such that

  1. If the answer is “yes,” exactly one computation path accepts.
  2. 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)
$\endgroup$
  • 1
    $\begingroup$ How do we ​ "know that UP ∪ coNP ⊆ US" ? ​ ​ ​ ​ $\endgroup$ – user12859 Nov 16 '17 at 6:56
  • $\begingroup$ You are asking three questions. The usual rule is one question per post. $\endgroup$ – Yuval Filmus Nov 16 '17 at 10:54
  • $\begingroup$ @RickyDemer UP is subset of US by definition. For coNP $\subseteq$ US, you can see the comments in this post. cs.stackexchange.com/q/77329 Essentially, it says that any coNP machine can be transformed to have exactly one accepting path. So, UP $\cup$ coNP $\subseteq$ US. $\endgroup$ – Pawan Kumar Nov 16 '17 at 14:07
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much. I had got the understanding of definitions of UP and US wrong. Now, it is clear to me. $\endgroup$ – Pawan Kumar Nov 16 '17 at 14:14

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.