Remember that we are talking about decision problems.

An NP problem is a decision that can be solved on a NTM in polynomial time with the understanding that a HALT consitutes an answer of YES.  A non-halt (infinite loop) constitutes an answer of NO.

A co-NP problem is a decision problem whose COMPLEMENT is in NP.  In other words, this problem can be solved on a NTM where HALT means NO and NONHALT means YES.

SATISFIABILITY can be solved in polynomial time on a NTM. You just try all the possible boolean values in different threads.  If a certain thread determines a value of TRUE, it halts and SAT gives an answer of YES.  For SAT, you need only working choice of variables to show that it's true.  To show that it's false, everything you try must give false.  Finding one example of a boolean assignment that sets the expression to false is not good enough.  All boolean assignments must make the expression false, and this can't be done in polynomial time on a NTM, at least not in the same way that you can find one working boolean assignment.

(Nondeterministally, assign true and false values to the variables.  Plug 'em in, if it's true, YES, if not, oh, well, perhaps one of the other threads will find a true one.)  This strategy does not work for unsatisfiability because if I find a false one, that doesn't mean the answer is YES.  They all must be false for the answer to be YES.

However, I can more easily determine if unsatisfiability gives a NO answer.  If I try a boolean assignment to my variables and get a true answer, then the expression is certainly not unsatisfiable.  And the answer is NO.

P ^ ~P

P^Q = PQ,   PvQ = P+Q-PQ   P^2 = P   ~P = 1-P   True is 1 and false is 0.

P(1-P) = P - P^2 = P-P = 0, and so this expression is unsatisfiable.







In an alternating Turing Machine, some states are designated existential and some are designated universal.  This is part of the design of the ATM.  When you build it, you decide which states are universal and which are existential.

Now, some states are accept states and some states are reject states.  You don't get to decide those in advance, those are mathematically determined by the input.  An existential state is an accept state if one of its transitions (remember ATM's are nondeterministic, there is not necessarily only one next state).  If at least one of transitions is also to an accept state then this existential state is an accept state.
For a universal state ALL of its transitions must be to an accept state for it to be an accept itself.

A universal state with NO transitions is accept.
An existential state with no transitions is a reject state.

If the start state is an accept state, then the string is accepted.




Let's say my ATM can solve a problem.  As the machine moves through states while solving the problem, if it is guaranteed to switch between existential and universal states no more than m times, then the problem is in SIGMA(m) if the start state was existential  or in PI(m) if the start was universal.

PH :  this is the class of problems that is the union of all the deltas, all the sigmas, and all the pi's.  Everything in the hierarchy is in PH.

Let's say that I can solve a problem with an alternating Turing machine.  I can indeed solve it...but I don't have an upper limit for the number of times it transitions between existential and universal states.  (The classic example of this is QBF.  It's really easy to design an ATM to solve this...but it can bounce around between existential and universal states any number of times depending on the length of the fornula).  So, without a fixed maximum number of transitions, I cannot definitely put this problem on ANY specifi level of the hierarchy.  So, the problem might not be in PH at all!  But I can still solve it.

AP is that class of problems solvable with an ATM.  AP might contain PH or it might be equal to PH.

Any problem in PH can be solved with an ATM, so that problem is also in AP.

But is there a problem in AP that is not in PH?  Unknown.

QBF can be easily solved with an ATM that bounces between existential and universal states an unbounded number of times.  Suppose there is an algorithm that solves QBF but only bounces a fixed maximum (possibly a very large maximum) number of times.  Well, that would put QBF on a specific level of the hierarchy, which would put QBF in PH.