The polynomial hierarchy by alternating Turing machines

Lax564036.AlternatingMachineComplete · concepts/Lax564036/AlternatingMachineComplete.lean · lax-564036

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    For every k≥1k \ge 1, alternating machine acceptance with kk blocks is Σkp\Sigma_k^p-complete when the first block is existential and Πkp\Pi_k^p-complete when it is universal, under first-order reductions; and a decision problem is in Σkp\Sigma_k^p, respectively Πkp\Pi_k^p, if and only if it reduces to the corresponding acceptance problem by an ordered first-order reduction. Each level of the logically defined hierarchy is thus the corresponding level of the alternating-machine hierarchy of Chandra, Kozen and Stockmeyer; at one block these are the nondeterministic machine and its dual, the machine model of coNP. Membership reads a run as a game of kk rounds, each guessing one walk; hardness builds, inside the instance, the machine of a quantified Boolean formula, which sweeps the tape once per quantifier block.

    Concept map
    23 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    Lean source view on GitHub

    1import Lax904597.Problems
    2import Lax904597.Interpretations
    3import Lax904597.Relativized
    4import Lax904597.SecondOrder
    5import Lax904597.Classes
    6import Lax904597.Sat
    7import Lax904597.Machines
    8import Lax485149.Problems
    9import Lax485149.Complement
    10import Lax535992.ClassPTIME
    11import Lax564036.Hierarchy
    12import Lax564036.Difference
    13import Lax564036.Tautology
    14import Lax564036.ThreeDnfTautology
    15import Lax564036.SatUnsat
    16import Lax564036.QuantifiedBooleanFormulas
    17import Lax564036.AlternatingMachines
    18
    19/-!
    20---
    21title: The polynomial hierarchy by alternating Turing machines
    22type: theorem
    23---
    24For every k≥1k \ge 1, alternating machine acceptance with kk blocks is
    25Σkp\Sigma_k^p-complete when the first block is existential and
    26Πkp\Pi_k^p-complete when it is universal, under first-order reductions; and
    27a decision problem is in Σkp\Sigma_k^p, respectively Πkp\Pi_k^p, if and only
    28if it reduces to the corresponding acceptance problem by an ordered
    29first-order reduction. Each level of the logically defined hierarchy is thus
    30the corresponding level of the alternating-machine hierarchy of Chandra,
    31Kozen and Stockmeyer; at one block these are the nondeterministic machine
    32and its dual, the machine model of coNP. Membership reads a run as a game
    33of kk rounds, each guessing one walk; hardness builds, inside the instance,
    34the machine of a quantified Boolean formula, which sweeps the tape once per
    35quantifier block.
    36-/
    37
    38namespace Lax564036.AlternatingMachineComplete
    39
    40open FirstOrder FirstOrder.Language
    41open Lax904597.Problems Lax904597.Interpretations Lax904597.Relativized Lax904597.SecondOrder
    42open Lax904597.Classes Lax904597.Sat Lax904597.Machines
    43open Lax485149.Problems Lax485149.Complement Lax535992.ClassPTIME
    44open Lax564036.Hierarchy Lax564036.Difference Lax564036.Tautology Lax564036.ThreeDnfTautology
    45open Lax564036.SatUnsat Lax564036.QuantifiedBooleanFormulas Lax564036.AlternatingMachines
    46
    47/-- Alternating acceptance with `k + 1` blocks, existential first, is
    48`Σₖ₊₁ᵖ`-complete. -/
    49axiom atmAccept_sigmaP_complete : ∀ (k : ℕ),
    50 (SigmaP (k + 1)).Complete (ATMAccept (k + 1) true)
    51
    52/-- Alternating acceptance with `k + 1` blocks, universal first, is
    53`Πₖ₊₁ᵖ`-complete. -/
    54axiom atmAccept_piP_complete : ∀ (k : ℕ),
    55 (PiP (k + 1)).Complete (ATMAccept (k + 1) false)
    56
    57/-- `Σₖ₊₁ᵖ` is reducibility to alternating acceptance, existential first. -/
    58axiom mem_sigmaP_iff_le_atmAccept :
    59 ∀ {L : Language.{0, 0}} [L.IsRelational] (k : ℕ) (P : DecisionProblem L),
    60 (SigmaP (k + 1)).Mem P ↔ Nonempty (OrderedFOReduction P (ATMAccept (k + 1) true))
    61
    62/-- `Πₖ₊₁ᵖ` is reducibility to alternating acceptance, universal first. -/
    63axiom mem_piP_iff_le_atmAccept :
    64 ∀ {L : Language.{0, 0}} [L.IsRelational] (k : ℕ) (P : DecisionProblem L),
    65 (PiP (k + 1)).Mem P ↔ Nonempty (OrderedFOReduction P (ATMAccept (k + 1) false))
    66
    67/-- Acceptance with one existential block is NP-complete. -/
    68axiom atmAccept_one_NP_complete : NP.Complete (ATMAccept 1 true)
    69
    70/-- Acceptance with one universal block is coNP-complete. -/
    71axiom atmAccept_one_coNP_complete : coNP.Complete (ATMAccept 1 false)
    72
    73end Lax564036.AlternatingMachineComplete
    74
    Show ProofShow ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…