Complexity classes, cofinal hardness, and NP
Lax904597.Classes · concepts/Lax904597/Classes.lean · lax-904597
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A complexity class is given by a membership predicate and a hardness predicate on decision problems over arbitrary relational vocabularies. The classes of this development are built from their membership predicate alone, with hardness read cofinally: a problem is hard when every member of the class reduces, by a relativized ordered first-order reduction, to every problem that itself reduces to. This is equivalent to the usual “every member reduces to ” (stated in NP is a complexity class), and is the form the library this submission comes from uses. A problem is complete for a class when it belongs to it and is hard for it.
NP is the class whose members are the -definable problems, by Fagin's theorem; more generally the level of the polynomial hierarchy has the -definable problems as members. The library this submission comes from makes closure under first-order reductions part of the definition of a class; that NP is closed is stated separately, in NP is a complexity class.
Concept map
Lean source view on GitHub
| 1 | import Lax904597.Problems |
| 2 | import Lax904597.Interpretations |
| 3 | import Lax904597.Relativized |
| 4 | import Lax904597.SecondOrder |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Complexity classes, cofinal hardness, and NP |
| 9 | type: definition |
| 10 | --- |
| 11 | A complexity class is given by a membership predicate and a hardness |
| 12 | predicate on decision problems over arbitrary relational vocabularies. The |
| 13 | classes of this development are built from their membership predicate |
| 14 | alone, with hardness read *cofinally*: a problem is hard when every |
| 15 | member of the class reduces, by a relativized ordered first-order reduction, |
| 16 | to every problem that itself reduces to. This is equivalent to the |
| 17 | usual “every member reduces to ” (stated in *NP is a complexity |
| 18 | class*), and is the form the library this submission comes from uses. A |
| 19 | problem is complete for a class when it belongs to it and is hard for it. |
| 20 | |
| 21 | NP is the class whose members are the -definable problems, by |
| 22 | Fagin's theorem; more generally the level of the polynomial |
| 23 | hierarchy has the -definable problems as members. The |
| 24 | library this submission comes from makes closure under first-order |
| 25 | reductions part of the definition of a class; that NP is closed is stated |
| 26 | separately, in *NP is a complexity class*. |
| 27 | -/ |
| 28 | |
| 29 | namespace Lax904597.Classes |
| 30 | |
| 31 | open FirstOrder FirstOrder.Language |
| 32 | open Lax904597.Problems Lax904597.Interpretations Lax904597.Relativized Lax904597.SecondOrder |
| 33 | |
| 34 | /-- A complexity class: a membership predicate and a hardness predicate on |
| 35 | decision problems, over arbitrary relational vocabularies. -/ |
| 36 | structure ComplexityClass where |
| 37 | /-- The problems belonging to the class. -/ |
| 38 | Mem : ∀ {L : Language.{0, 0}} [L.IsRelational], DecisionProblem L → Prop |
| 39 | /-- The problems every problem of the class reduces to. -/ |
| 40 | Hard : ∀ {L : Language.{0, 0}} [L.IsRelational], DecisionProblem L → Prop |
| 41 | |
| 42 | variable {L : Language.{0, 0}} [L.IsRelational] |
| 43 | |
| 44 | /-- Cofinal hardness for a collection of problems: every problem of the |
| 45 | collection reduces to every relational problem that `P` reduces to. -/ |
| 46 | def CofinalHard (Mem : ∀ {L₀ : Language.{0, 0}} [L₀.IsRelational], DecisionProblem L₀ → Prop) |
| 47 | (P : DecisionProblem L) : Prop := |
| 48 | ∀ {L' : Language.{0, 0}} [L'.IsRelational] (S : DecisionProblem L'), |
| 49 | Nonempty (RelOrderedFOReduction P S) → |
| 50 | ∀ {L'' : Language.{0, 0}} [L''.IsRelational] (Q : DecisionProblem L''), |
| 51 | Mem Q → Nonempty (RelOrderedFOReduction Q S) |
| 52 | |
| 53 | /-- The class with the given membership and cofinal hardness. -/ |
| 54 | def ComplexityClass.ofMem |
| 55 | (Mem : ∀ {L₀ : Language.{0, 0}} [L₀.IsRelational], DecisionProblem L₀ → Prop) : |
| 56 | ComplexityClass where |
| 57 | Mem P := Mem P |
| 58 | Hard P := CofinalHard Mem P |
| 59 | |
| 60 | /-- A problem is complete for a class if it belongs to it and is hard for |
| 61 | it. -/ |
| 62 | def ComplexityClass.Complete (C : ComplexityClass) (P : DecisionProblem L) : Prop := |
| 63 | C.Mem P ∧ C.Hard P |
| 64 | |
| 65 | /-- The level `Σₖ₊₁ᵖ` of the polynomial hierarchy: the problems definable with |
| 66 | `k + 1` alternating blocks of second-order quantifiers, existential first. -/ |
| 67 | def sigmaLevel (k : ℕ) : ComplexityClass := |
| 68 | .ofMem fun P => SigmaSODefinable (k + 1) P |
| 69 | |
| 70 | /-- NP is `Σ₁ᵖ`: by definition, the existential-second-order definable |
| 71 | problems (Fagin's theorem). -/ |
| 72 | def NP : ComplexityClass := sigmaLevel 0 |
| 73 | |
| 74 | end Lax904597.Classes |
| 75 |
Used by
Lax117614.CrawlDecodingLax117614.GraphCrawlingInvarianceLax117614.GraphCrawlingNPCompleteLax117614.GraphCrawlingProblemLax134656.AbiteboulVianuLax134656.AbiteboulVianuOrderedLax134656.ClassPSPACELax134656.HierarchyInPSPACELax134656.InflationaryInPartialLax134656.PartialFixedPointCaptureLax134656.PartialFixedPointClosureLax134656.PSPACEClosureLax134656.PSPACEEqCoPSPACELax134656.QsatInvarianceLax134656.QsatPSPACECompleteLax134656.SpaceBoundedMachineInvarianceLax134656.SpaceMachinesPSPACECompleteLax134656.SuccinctReachInvarianceLax134656.SuccinctReachPSPACECompleteLax134656.TransitiveClosureWithoutOrderLax175070.CountClassComplementsLax175070.CountClassInclusionsLax175070.CountClassMembershipLax175070.CountDefinabilityLax175070.CountingValuesLax175070.ParitySatCompleteLax175070.SelectedSatCompleteLax366625.CountingRunsCompleteLax366625.CountingRunsValueLax366625.FPAndPTIMELax366625.FPByDigitsLax366625.FPClosureLax366625.FPCompleteLax366625.NumbersValueLax366625.SharpPAndNPLax366625.SharpPAsQuantitativeLogicLax366625.SharpPClosureLax366625.SharpSatCompleteLax366625.SharpSatValueLax420092.ChandraMerlinLax420092.ContainmentInvarianceLax420092.ContainmentNPCompleteLax420092.DecodingAndWellFormedLax420092.EncodingFaithfulLax420092.EvaluationLax420092.EvaluationContainmentReductionsLax420092.EvaluationInvarianceLax420092.EvaluationNPCompleteLax420092.PackagedInstancesLax420092.QueryPairsLax480241.AlternatingSpaceValueLax480241.APSPACEIsEXPTIMELax480241.ExponentialCapturesLax480241.ExponentialClassesLax480241.ExponentialComplementsLax480241.ExponentialInclusionsLax480241.ExponentialMonotoneLax485149.ClassLLax485149.ClassNLLax485149.DeterministicReachabilityInvarianceLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ReachabilityInvarianceLax485149.ReachdLCompleteLax485149.ReachNLCompleteLax485149.TransitiveClosureClosureLax485149.TwoSatInvarianceLax485149.TwoSatNLCompleteLax485149.UnreachdLCompleteLax485149.UnreachNLCompleteLax535992.CircuitValueInvarianceLax535992.CircuitValuePTIMECompleteLax535992.ClassPTIMELax535992.DeterministicMachineInvarianceLax535992.DeterministicMachinePTIMECompleteLax535992.GameInvarianceLax535992.GamePTIMECompleteLax535992.HornIsLeastFixedPointLax535992.HornSatInvarianceLax535992.HornSatPTIMECompleteLax535992.ImmermanVardiLax535992.InflationaryIsLeastFixedPointLax535992.LeastFixedPointComplementLax535992.NLSubsetPTIMELax535992.PTIMEClosureLax535992.PTIMEEqCoPTIMELax535992.PTIMESubsetNPLax564036.AlternatingMachineCompleteLax564036.AlternatingMachineInvarianceLax564036.CoNPClosureLax564036.DifferenceLax564036.DPClosureLax564036.DPInclusionsLax564036.HierarchyLax564036.HierarchyDualityLax564036.HierarchyInclusionsLax564036.PolynomialTimeInHierarchyLax564036.QbfCompleteLax564036.QuantifiedBooleanFormulasInvarianceLax564036.SatUnsatDPCompleteLax564036.SatUnsatInvarianceLax564036.TautCoNPCompleteLax564036.TautologyInvarianceLax564036.ThreeDnfTautCoNPCompleteLax564036.ThreeDnfTautologyInvarianceLax604544.ClassesAsDegreesLax604544.DegreeOfAProblemLax604544.DegreesLax604544.GraphIsomorphismLax604544.GraphIsomorphismDegreeLax604544.IsomorphismInNPLax604544.IsomorphismInvarianceLax604544.RelationIsomorphismSemanticsLax624099.ClassRELax624099.CodeHaltingLax624099.CodeHaltingInvarianceLax624099.CodehaltRECompleteLax624099.FiniteSatisfiabilityLax624099.FiniteSatisfiabilityInvarianceLax624099.FinsatRECompleteLax624099.HaltingInvarianceLax624099.HaltingUndecidableLax624099.HaltRECompleteLax624099.NPSubsetRELax624099.PcpRECompleteLax624099.PcpUndecidableLax624099.PostCorrespondenceLax624099.PostCorrespondenceInvarianceLax624099.REClosureLax624099.ReductionsComputableLax624099.REFiniteLax624099.REHardUndecidableLax624099.REIsRecursivelyEnumerableLax624099.RENeCoRELax624099.TrakhtenbrotLax799700.CliqueFamilyLax799700.ColoringLax799700.CommonLax799700.DominatingSetLax799700.FeedbackLax799700.HamiltonLax799700.JobSequencingLax799700.KnapsackLax799700.MaxCutLax799700.NaeSatLax799700.NaeThreeSatLax799700.OneInSatLax799700.PartitionLax799700.SetFamilyLax799700.SteinerLax799700.SubgraphIsoLax799700.ThreeColorabilityLax799700.ThreeDimMatchingLax799700.ThreeSatLax799700.ZeroOneIPLax822549.TilingsCompleteLax822549.WideMachinesCompleteLax822549.WideProblemsValuesLax832283.LogicalBridgeLax895169.ACZeroComplementLax895169.ACZeroFiniteLax895169.ACZeroInLogSpaceLax895169.ACZeroInPTIMELax895169.ACZeroIsBitLogicLax895169.ACZeroIsLogTimeLax895169.FirstOrderInACZeroLax904597.CookLevinLax904597.MachineFormLax904597.NPClassLax945089.EhrenfeuchtMethodologyLax945089.EvenInvarianceLax945089.EvenNotFirstOrderLax945089.FirstOrderBelowACZeroLax945089.FirstOrderBelowTransitiveClosureLax945089.GamesOnLinearOrdersLax945089.GamesOnSetsLax945089.NoDefinableOrderLax945089.OrderFreeInductionMissesPTIMELax945089.ParityInLogSpaceLax945089.PebbleInvarianceLax945089.ReductionsBelowLogSpace
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments