HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is a Turing Machine in class coNP

Submitted by: @import:stackexchange-cs··
0
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 ?

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$).

Context

StackExchange Computer Science Q#12466, answer score: 3

Revisions (0)

No revisions yet.