Talk:Polynomial hierarchy

Comment

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)

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)

BQP Result

In 2018 Tal and Raz published a proof using an oracle that BQP $\subsetneq$ PH. As BQP $\subseteq$ PSPACE and P $\subseteq$ BQP, this result presumably also has implications on other results on the main page, such as the relationship of P and PSPACE and PH and PSPACE. — Preceding unsigned comment added by 2A00:23C4:8585:7D01:244F:974F:E271:6C71 (talk) 12:43, 11 October 2021 (UTC)

Oracle definition of hierarchy

$\Sigma _{k}$ is ${\rm {NP}}^{\Sigma _{k-1}}$ and ${\rm {NP}}^{\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)

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)

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)

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)

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

Error in formular

This formular does not work:

$\Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{i}^{\rm {P}}}$

It would result in $\Sigma _{2}^{\rm {P}}:={\mbox{NP}}^{\Sigma _{1}^{\rm {P}}}={\mbox{NP}}^{\mbox{NP}}={\mbox{NP}}$

Instead it has to be:

$\Sigma _{i+1}^{\rm {P}}:={\mbox{NP}}^{\Pi _{i}^{\rm {P}}}$

This way the symmetrie in the PH is also more obvious to be seen. I know it is done wrong in some books, but using the definition of the oracle the error is quite obvious. --Maria Siebert 31.07.2010 16:58 —Preceding unsigned comment added by 78.52.234.189 (talk) 14:59, 31 July 2010 (UTC)

${\mbox{NP}}^{\mbox{NP}}$ is not the same as ${\mbox{NP}}$ (unless the polynomial hierarchy collapses). One easy way to see this is to first observe that ${\mbox{NP}}\subseteq {\mbox{P}}^{\mathrm {SAT} }$ and ${\mbox{coNP}}\subseteq {\mbox{P}}^{\mathrm {SAT} }$. This is because a SAT oracle can be used to decide SAT, complete for NP, and also it can be used to decide UNSAT, complete for coNP. Also, ${\mbox{NP}}\subseteq {\mbox{P}}^{\mathrm {SAT} }={\mbox{P}}^{\mbox{NP}}\subseteq {\mbox{NP}}^{\mbox{NP}}$. But if they are all equal, then since ${\mbox{coNP}}\subseteq {\mbox{P}}^{\mathrm {SAT} }$, this means ${\mbox{coNP}}\subseteq {\mbox{NP}}$, so the polynomial hierarchy collapses. Pexatus (talk) 00:07, 22 November 2010 (UTC)

Dubious claim $\Delta _{1}=\Delta _{0}$

I'm quite dubious if $\Delta _{1}=\Delta _{0}$. As I remeber from lectures asymmetric cryptography makes sense only if ${\mbox{NP}}\cap {\mbox{coNP}}\setminus {\mbox{P}}$ is not empty. Presented diagram claims contrarily. I could correct that if I'm right. Korektysta (talk) 16:40, 15 June 2016 (UTC)

I'm convinced that $\Delta _{1}=\Delta _{0}$ is indeed correct: by definition we can expand to $\Delta _{1}={\mathsf {P}}^{\Sigma _{0}^{\mathsf {P}}}={\mathsf {P}}^{\mathsf {P}}$, which is trivially just ${\mathsf {P}}$ because any polynomial-time algorithm can evaluate a polynomial amount of other polynomial-time functions, i.e. the ${\mathsf {P}}$ oracle is no help to the ${\mathsf {P}}$ machine, as it can answer itself the questions it has. Your statement about asymmetric cryptography sounds plausible, but I don't see the contradiction. --Empallio (talk) 15:06, 16 January 2022 (UTC)

The comment is quite old, so I'm not sure if Korektysta will reply or remember writing this, but I believe $\Delta _{1}=\Delta _{0}$ is trivial from the definition as you describe. Perhaps they are recalling an equivalent fact to $\Delta _{2}{\overset {?}{=}}\Delta _{1}$, though I'm not quite sure how to parse their condition (is it $({\mbox{NP}}\cap {\mbox{coNP}})\setminus {\mbox{P}}$ or ${\mbox{NP}}\cap ({\mbox{coNP}}\setminus {\mbox{P}})$?). — Bilorv (talk) 16:03, 16 January 2022 (UTC)

Thank you for both answers. It is very plausible that I was wrong. I don't remember much from this topic (lectures 7 years ago). My parsing would be $({\mbox{NP}}\cap {\mbox{coNP}})\setminus {\mbox{P}}$, but I don't remember much more. Korektysta (talk) 10:30, 17 January 2022 (UTC)

$({\mbox{NP}}\cap {\mbox{coNP}})\setminus {\mbox{P}}$ is empty if ${\mbox{P}}={\mbox{NP}}$, when the hierarchy collapses and $\Delta _{i}=\Delta _{0}$ for all i, so perhaps the condition needs negating as well. I'm sure you're remembering something relevant (when properly formulated) but I don't think it's a fact I'm aware of. — Bilorv (talk) 22:00, 17 January 2022 (UTC)

'Examples' subsection in Definitions section

My frustration with this article is the same as the user whose words appear at the top of this talk page. I came to this page for help understanding formal definitions as part of a homework assignment to write proofs regarding the PH, and did not find some of the formal notations that were introduced in the textbook, and other materials online, etc... In fact, what I noticed is that they are all different and as noted, what was true of a lot of the sources were "utterly incomprehensible to an average lay reader, because it doesn't define it's symbols".

I can imagine what would be helpful is to introduce a section into the main article, as a subsection to definitions, "Examples" and in there, for starters, write out the first three levels of the definitions. For the existential/universal definition (numbered '2' in the definition section), it could spell out that the class $\Sigma _{1}^{p}=\{L|\exists T\exists k{\text{ s.t. T runs }}\|x\|^{k},x\in L\iff \forall x\exists yT(x,y)\}$ where L is a language, T is a turing machine which can verify the result for a decision problem x, using certificate y.

Then do the same for \Pi_1^p, \Sigma_2^p, \Pi_2^p... No single source on the internet actually does this, but a reasonable midterm test problem is to prove membership in these classes -- and we wonder why its lonely in the ivory tower of academia. No self respecting person would actually go and slog through something like this when its not actually verifiable anywhere.

--Loraxcannon (talk) 13:50, 26 February 2019 (UTC)