The polynomial hierarchy by alternating Turing machines
Lax564036.AlternatingMachineComplete · concepts/Lax564036/AlternatingMachineComplete.lean · lax-564036
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
For every , alternating machine acceptance with blocks is -complete when the first block is existential and -complete when it is universal, under first-order reductions; and a decision problem is in , respectively , 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 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
Evidence
This concept declares 6 statements. Each proof establishes one of them relative to its assumptions.
1 atmAccept_one_coNP_complete proven
2 atmAccept_one_NP_complete proven
3 atmAccept_piP_complete proven
4 atmAccept_sigmaP_complete proven
5 mem_piP_iff_le_atmAccept proven
6 mem_sigmaP_iff_le_atmAccept proven
Lean source view on GitHub
| 1 | import Lax904597.Problems |
| 2 | import Lax904597.Interpretations |
| 3 | import Lax904597.Relativized |
| 4 | import Lax904597.SecondOrder |
| 5 | import Lax904597.Classes |
| 6 | import Lax904597.Sat |
| 7 | import Lax904597.Machines |
| 8 | import Lax485149.Problems |
| 9 | import Lax485149.Complement |
| 10 | import Lax535992.ClassPTIME |
| 11 | import Lax564036.Hierarchy |
| 12 | import Lax564036.Difference |
| 13 | import Lax564036.Tautology |
| 14 | import Lax564036.ThreeDnfTautology |
| 15 | import Lax564036.SatUnsat |
| 16 | import Lax564036.QuantifiedBooleanFormulas |
| 17 | import Lax564036.AlternatingMachines |
| 18 | |
| 19 | /-! |
| 20 | --- |
| 21 | title: The polynomial hierarchy by alternating Turing machines |
| 22 | type: theorem |
| 23 | --- |
| 24 | For every , alternating machine acceptance with blocks is |
| 25 | -complete when the first block is existential and |
| 26 | -complete when it is universal, under first-order reductions; and |
| 27 | a decision problem is in , respectively , if and only |
| 28 | if it reduces to the corresponding acceptance problem by an ordered |
| 29 | first-order reduction. Each level of the logically defined hierarchy is thus |
| 30 | the corresponding level of the alternating-machine hierarchy of Chandra, |
| 31 | Kozen and Stockmeyer; at one block these are the nondeterministic machine |
| 32 | and its dual, the machine model of coNP. Membership reads a run as a game |
| 33 | of rounds, each guessing one walk; hardness builds, inside the instance, |
| 34 | the machine of a quantified Boolean formula, which sweeps the tape once per |
| 35 | quantifier block. |
| 36 | -/ |
| 37 | |
| 38 | namespace Lax564036.AlternatingMachineComplete |
| 39 | |
| 40 | open FirstOrder FirstOrder.Language |
| 41 | open Lax904597.Problems Lax904597.Interpretations Lax904597.Relativized Lax904597.SecondOrder |
| 42 | open Lax904597.Classes Lax904597.Sat Lax904597.Machines |
| 43 | open Lax485149.Problems Lax485149.Complement Lax535992.ClassPTIME |
| 44 | open Lax564036.Hierarchy Lax564036.Difference Lax564036.Tautology Lax564036.ThreeDnfTautology |
| 45 | open Lax564036.SatUnsat Lax564036.QuantifiedBooleanFormulas Lax564036.AlternatingMachines |
| 46 | |
| 47 | /-- Alternating acceptance with `k + 1` blocks, existential first, is |
| 48 | `Σₖ₊₁ᵖ`-complete. -/ |
| 49 | axiom 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. -/ |
| 54 | axiom atmAccept_piP_complete : ∀ (k : ℕ), |
| 55 | (PiP (k + 1)).Complete (ATMAccept (k + 1) false) |
| 56 | |
| 57 | /-- `Σₖ₊₁ᵖ` is reducibility to alternating acceptance, existential first. -/ |
| 58 | axiom 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. -/ |
| 63 | axiom 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. -/ |
| 68 | axiom atmAccept_one_NP_complete : NP.Complete (ATMAccept 1 true) |
| 69 | |
| 70 | /-- Acceptance with one universal block is coNP-complete. -/ |
| 71 | axiom atmAccept_one_coNP_complete : coNP.Complete (ATMAccept 1 false) |
| 72 | |
| 73 | end Lax564036.AlternatingMachineComplete |
| 74 |
Builds on
Lax485149.ComplementLax485149.ProblemsLax535992.ClassPTIMELax564036.AlternatingMachinesLax564036.DifferenceLax564036.HierarchyLax564036.QuantifiedBooleanFormulasLax564036.SatUnsatLax564036.TautologyLax564036.ThreeDnfTautologyLax904597.ClassesLax904597.InterpretationsLax904597.MachinesLax904597.ProblemsLax904597.RelativizedLax904597.SatLax904597.SecondOrder
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments