Talk:Polynomial hierarchy

Mathematics Start‑class Mid‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-priority on the project's priority scale.

This page is awful. It's utterly incomprehensible to an average lay reader, because it doesn't define it's symbols, nor does it provide references to definitions of those symbols.

Wikipedia needs to take more emphatic measures against such incomprehensible morasses.

Er, as far as I can tell all symbols are either linked, defined in this article, or simple set builder notation. Is there anything specific that you think needs clarification? Deco 20:11, 11 June 2006 (UTC)[reply]

I think this article works pretty well for anyone who has had a basic grad-level class in theoretical computer science, which is about the level of expertise required to understand the polynomial hierarchy. If you know of an explanation of the polynomial hierarchy that the "average lay reader" would understand, then add it. That's why it's called a collaborative encyclopedia. Wikipedia is not a person that "needs to take measures". Wikipedia is you. You add more intuition to the article if you don't like it. Pexatus 02:33, 12 June 2006 (UTC)[reply]

Oracle definition of hierarchy

$\Sigma _{k}$ is ${\rm {P}}^{\Sigma _{k-1}}$ and ${\rm {P}}^{\Pi _{k-1}}$ . They are equivalent, since having an oracle for a language is the same as having an oracle for its complement. I reverted the previous change to reflect the "standard" definition. Pexatus 04:46, 3 August 2006 (UTC)[reply]

humor by scott aaronson

Terrible news, the polynomial hierarchy has collapsed.

http://www.scottaaronson.com/writings/phcollapse.pdf —Preceding unsigned comment added by 207.241.238.233 (talk) 06:45, 7 February 2008 (UTC)[reply]

Seen that before, it's very entertaining (and quite well-informed in its references to various complexity theory results). Might even be worth linking. Dcoetzee 19:45, 7 February 2008 (UTC)[reply]

Red Strings?

In the Definitions section, item (2) is the sentence "L represents a set of ordered (red) pairs of strings". What on earth is a red pair of strings? Does the polynomial hierarchy came in designer colours? Ross Fraser (talk) 18:24, 23 April 2010 (UTC)[reply]

No idea. I removed "red" from the article. --Robin (talk) 22:07, 24 April 2010 (UTC)[reply]