So I was reading the Wikipedia article on the Polynomial Hierarchy (http://en.wikipedia.org/wiki/Polynomial_hierarchy), and, like every other Wikipedia article on mathematics or computer science, it's only comprehensible to those who already know enough not to need to read it. I think I might have gotten the gist of it, however, and I'd like someone to tell me if what I think I know is correct. Please don't comment unless you're absolutely sure you understand PH. I don't need to be confused any further.
Here's what I think I know:
NP is the class of decision problems for which positive answers can be found by an NTM in polynomial time; co-NP is the analogous class for negative answers.
The class Δ(P2) (forgive me for incorrect formatting; there aren't supposed to be any parentheses before "P" or after "2", and "P" is supposed to be above "2", but if there's a way to do this on Dream.In.Code, I have no idea what it is) is the union of NP and co-NP. The class Σ(P2) is the class of decision problems for which positive answers can be found in polynomial time by an NTM with an oracle that can decide Δ(P2) problems. Π(P2) is the analogous class for negative answers. Δ(P3) is the union of Σ(P2) and Π(P2), and so on and so forth; this structure repeats for an infinite number of levels.
So am I completely off base, or what? Sorry if I'm inadvertently talking nonsense... I'm a Theatre major, not a math guy.
0 Replies - 2875 Views - Last Post: 09 August 2012 - 10:20 AM
Page 1 of 1