2
$\begingroup$

I have a very basic question. $\mathsf{P}$ is the class of decision problems solvable in polynomial time by a Turing machine. $\oplus \mathsf{P}$ is the class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes,' then the number of accepting paths is odd.
  2. If the answer is 'no,' then the number of accepting paths is even.

How do you show that $L \in \mathsf P \implies L \in \oplus \mathsf P$? i.e., that $\mathsf{P} \subseteq \oplus \mathsf{P}$.

$\endgroup$

1 Answer 1

4
$\begingroup$

You can think of a deterministic Turing machine as a nondeterministic Turing machine which doesn't make any nondeterministic choices, and so has a unique execution path. Consequently, a deterministic Turing machine has at most one accepting path. It accepts an input if there is an accepting path, and it doesn't accept an input if there is no accepting path. In particular, it accepts an input iff the number of accepting paths is odd.

$\endgroup$
3
  • $\begingroup$ Thank you! I still don't understand something though. If the input accepts, I understand that a deterministic Turing machine will accept in polynomial time by definition and that nondeterminstic TMs generalize deterministic ones. But how do we know that there aren't multiple accepting paths that aren't "seen" by the deterministic TM? I think there's something fundamental that I'm misunderstanding. $\endgroup$
    – jjaylon
    Feb 24, 2022 at 16:45
  • $\begingroup$ Deterministic Turing machines make no nondeterministic choices. There is a single run of the machine, which is either accepting or rejecting. $\endgroup$ Feb 24, 2022 at 16:47
  • $\begingroup$ Ah, I see. To decide if $x \in L$ for some $L \in \oplus P$, we are deciding if there exists any nondeterministic Turing machine such that the number of accepting paths is odd. In the case that $L \in \mathsf{P}$ we can just give the deterministic one which has one accepting path iff $x \in L$. And, $x \not\in L$ iff there are zero accepting paths (if that weren't the case, then the deterministic TM would have accepted). Thanks, your original answer makes perfect sense now. $\endgroup$
    – jjaylon
    Feb 24, 2022 at 17:07

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.