Conceptio › Archive › Stack Exchange
Stack Exchange open access CC BY-SA

Can one amplify P=NP beyond P=PH?

András Salamon · 2011
Stack Exchange · Datasets · License: CC BY-SA · 2011
Open Source ↗
In Descriptive Complexity, Immerman has Corollary 7.23. The following conditions are equivalent: 1. P = NP. 2. Over finite, ordered structures, FO(LFP) = SO. This can be thought of as "amplifying" P=NP to an equivalent statement over (presumably) larger complexity classes. Note that SO captures the polynomial-time hierarchy PH, and that FO(LFP) captures P, so this can be thought of as P=NP iff P=PH. (The interesting part of this is the statement that P=NP implies P=PH; it is trivial that P=CC implies P=NP for any class CC that contains NP. Immerman simply remarks "if P=NP then PH=NP", presumably because P=NP can be used with the oracle definition of PH to show inductively that the whole hierarchy collapses.) My question is: How much further can P=NP be amplified in this way? In particular, what is the largest known class CC' such that P=NP implies P=CC', and the smallest class CC such that P=NP implies CC=NP? This would allow P=NP to be replaced by the equivalent question CC=CC'. P appears to be a rather powerful class, which seems to provide little "wiggle room" for arguments trying to separate it from NP: how far can the wiggle room be amplified? I would of course also be interested in an argument that shows that P=PH is the limit of this approach. Edit: note the closely related question Why doesn't P=NP imply P=AP (i.e. P=PSPACE)? which focuses on the other direction, why we don't have proofs that P=PSPACE. Answers there by Kaveh and Peter Shor argue that the number of alternations being fixed is key. Another related question is A decision problem which is not known to be in PH but will be in P if P=NP which asks for a candidate problem; the answers there also can be used to construct answers for this question, although these classes are somewhat artificial (thanks to Tsuyoshi Ito for pointing this out). In a more general setting, Collapsing of exptime and alternation bounded turing machine asks whether a local collapse at any level in an alternation hierarchy in
Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

This document is indexed with metadata only: full text is not available in the archive for this record. Open the official source ↗

Related documents

Record · ID 787563
Retrieved via Conceptio: every document is proof-bundled with source, license, and retrieval metadata.
Bring this data into your agent: Connect via MCP or API · 20 free credits to start · no card required
Read the Docs → · View CLI source on GitHub · Conceptio Open Knowledge Archive