patternMinor
What is a Turing Machine in class coNP
Viewed 0 times
conpwhatmachineturingclass
Problem
On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy
it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B"
What is a "Turing machine in class A" for classes P, NP, and coNP?
I'm guessing a Turing machine in P is a deterministic Turing machine that can only run for polynomial time in the size of its input
and that a Turing machine in NP is a nondeterministic Turing machine that can only run for polynomial time in the size of its input
But I have no clue what is a Turing machine in class coNP ?
it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B"
What is a "Turing machine in class A" for classes P, NP, and coNP?
I'm guessing a Turing machine in P is a deterministic Turing machine that can only run for polynomial time in the size of its input
and that a Turing machine in NP is a nondeterministic Turing machine that can only run for polynomial time in the size of its input
But I have no clue what is a Turing machine in class coNP ?
Solution
The easiest way (for me) to understand co-NP is as the class of problems where certificates for "No" answers can be quickly verified (i.e. certificates of non-membership).
So if we look at NP as a class of nondeterministic Turing Machines which quickly (in polynomial time) determine that their input satisfies some property $\Pi$, co-NP is the class of nondeterministic Turing Machines that quickly determine that their input does not satisfy $\Pi$ (or equivalently satisfies $\neg\Pi$).
So if we look at NP as a class of nondeterministic Turing Machines which quickly (in polynomial time) determine that their input satisfies some property $\Pi$, co-NP is the class of nondeterministic Turing Machines that quickly determine that their input does not satisfy $\Pi$ (or equivalently satisfies $\neg\Pi$).
Context
StackExchange Computer Science Q#12466, answer score: 3
Revisions (0)
No revisions yet.