Decision problems on finite structures
Lax904597.Problems · concepts/Lax904597/Problems.lean · lax-904597
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A decision problem over a relational vocabulary is an isomorphism-invariant property of -structures: for each universe carrying an -structure, whether is a yes-instance, with the requirement that isomorphic structures are both yes-instances or both no-instances. Invariance is part of the notion, as in finite model theory: a problem cannot tell apart two presentations of the same structure. Finiteness is not built in; it is a hypothesis of every statement that needs it, and every complexity-theoretic notion below reads a problem on its finite instances only.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.ModelTheory.Semantics |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Decision problems on finite structures |
| 6 | type: definition |
| 7 | --- |
| 8 | A decision problem over a relational vocabulary is an |
| 9 | isomorphism-invariant property of -structures: for each universe |
| 10 | carrying an -structure, whether is a yes-instance, with the |
| 11 | requirement that isomorphic structures are both yes-instances or both |
| 12 | no-instances. Invariance is part of the notion, as in finite model theory: a |
| 13 | problem cannot tell apart two presentations of the same structure. |
| 14 | Finiteness is not built in; it is a hypothesis of every statement that needs |
| 15 | it, and every complexity-theoretic notion below reads a problem on its |
| 16 | finite instances only. |
| 17 | -/ |
| 18 | |
| 19 | namespace Lax904597.Problems |
| 20 | |
| 21 | open FirstOrder FirstOrder.Language |
| 22 | |
| 23 | /-- A decision problem: an isomorphism-closed property of `L`-structures, |
| 24 | whose yes-instances are the `L`-structures satisfying it. -/ |
| 25 | structure DecisionProblem (L : Language.{0, 0}) [L.IsRelational] where |
| 26 | /-- The predicate: `P A` (through the function coercion) states that the |
| 27 | structure `A` is a yes-instance. -/ |
| 28 | Holds : ∀ (A : Type) [L.Structure A], Prop |
| 29 | /-- Decision problems do not distinguish isomorphic structures. -/ |
| 30 | iso_invariant : ∀ {A B : Type} [L.Structure A] [L.Structure B], |
| 31 | (A ≃[L] B) → (Holds A ↔ Holds B) |
| 32 | |
| 33 | namespace DecisionProblem |
| 34 | |
| 35 | variable {L : Language.{0, 0}} [L.IsRelational] |
| 36 | |
| 37 | instance instCoeFun : CoeFun (DecisionProblem L) fun _ => ∀ (A : Type) [L.Structure A], Prop := |
| 38 | ⟨Holds⟩ |
| 39 | |
| 40 | end DecisionProblem |
| 41 | |
| 42 | end Lax904597.Problems |
| 43 |
Builds on
none
Used by
Lax134656.AbiteboulVianuLax134656.AbiteboulVianuOrderedLax134656.ClassPSPACELax134656.HierarchyInPSPACELax134656.InflationaryInPartialLax134656.OrderFreeTransitiveClosureLax134656.PartialFixedPointLax134656.PartialFixedPointCaptureLax134656.PartialFixedPointClosureLax134656.PSPACEClosureLax134656.PSPACEEqCoPSPACELax134656.QsatLax134656.QsatInvarianceLax134656.QsatPSPACECompleteLax134656.SecondOrderTransitiveClosureLax134656.SpaceBoundedMachineInvarianceLax134656.SpaceBoundedMachinesLax134656.SpaceMachinesPSPACECompleteLax134656.SuccinctReachLax134656.SuccinctReachInvarianceLax134656.SuccinctReachPSPACECompleteLax134656.TransitiveClosureWithoutOrderLax175070.CountClassComplementsLax175070.CountClassInclusionsLax175070.CountClassMembershipLax175070.CountDefinabilityLax175070.CountingValuesLax175070.ParitySatCompleteLax175070.SelectedSatCompleteLax280166.CliqueCompleteLax280166.CliquesValuesLax280166.DirHamCircuitCompleteLax280166.DominatingSetCompleteLax280166.DominatingSetsValuesLax280166.ExactCoverCompleteLax280166.FeedbackArcSetCompleteLax280166.FeedbackSetsValuesLax280166.FeedbackVertexSetCompleteLax280166.HamCircuitCompleteLax280166.HamiltonCircuitsValuesLax280166.HittingSetCompleteLax280166.IndependentSetCompleteLax280166.KnapsackCompleteLax280166.KnapsacksValuesLax280166.OneInSATCompleteLax280166.SatVariantsValuesLax280166.SetCoverCompleteLax280166.SetFamiliesValuesLax280166.SetPackingCompleteLax280166.SteinerTreeCompleteLax280166.SteinerTreesValuesLax280166.ThreeSATCompleteLax280166.VertexCoverCompleteLax280166.ZeroOneIPCompleteLax366625.CountingClassesLax366625.CountingProblemsLax366625.CountingRunsCompleteLax366625.CountingRunsValueLax366625.FPAndPTIMELax366625.FPByDigitsLax366625.FPClosureLax366625.FPCompleteLax366625.NumbersValueLax366625.SharpPAndNPLax366625.SharpPAsQuantitativeLogicLax366625.SharpPClosureLax366625.SharpSatCompleteLax366625.SharpSatValueLax420092.ChandraMerlinLax420092.ContainmentInvarianceLax420092.ContainmentNPCompleteLax420092.DecodingAndWellFormedLax420092.EncodingFaithfulLax420092.EvaluationContainmentReductionsLax420092.EvaluationInvarianceLax420092.EvaluationNPCompleteLax480241.AlternatingSpaceValueLax480241.APSPACEIsEXPTIMELax480241.ExponentialCapturesLax480241.ExponentialClassesLax480241.ExponentialComplementsLax480241.ExponentialInclusionsLax480241.ExponentialMonotoneLax480241.SecondOrderFixedPointsLax485149.ClassLLax485149.ClassNLLax485149.ComplementLax485149.DeterministicReachabilityLax485149.DeterministicReachabilityInvarianceLax485149.DeterministicTransitiveClosureLax485149.FirstOrderDefinabilityLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.KromFragmentLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ProblemsLax485149.ReachabilityLax485149.ReachabilityInvarianceLax485149.ReachdLCompleteLax485149.ReachNLCompleteLax485149.TransitiveClosureLax485149.TransitiveClosureClosureLax485149.TwoSatLax485149.TwoSatInvarianceLax485149.TwoSatNLCompleteLax485149.UnreachdLCompleteLax485149.UnreachNLCompleteLax535992.CircuitValueLax535992.CircuitValueInvarianceLax535992.CircuitValuePTIMECompleteLax535992.ClassPTIMELax535992.DeterministicMachineInvarianceLax535992.DeterministicMachinePTIMECompleteLax535992.DeterministicMachinesLax535992.GameLax535992.GameInvarianceLax535992.GamePTIMECompleteLax535992.HornFragmentLax535992.HornIsLeastFixedPointLax535992.HornSatLax535992.HornSatInvarianceLax535992.HornSatPTIMECompleteLax535992.ImmermanVardiLax535992.InflationaryFixedPointLax535992.InflationaryIsLeastFixedPointLax535992.LeastFixedPointLax535992.LeastFixedPointComplementLax535992.NLSubsetPTIMELax535992.PTIMEClosureLax535992.PTIMEEqCoPTIMELax535992.PTIMESubsetNPLax564036.AlternatingMachineCompleteLax564036.AlternatingMachineInvarianceLax564036.AlternatingMachinesLax564036.CoNPClosureLax564036.DifferenceLax564036.DPClosureLax564036.DPInclusionsLax564036.HierarchyLax564036.HierarchyDualityLax564036.HierarchyInclusionsLax564036.PolynomialTimeInHierarchyLax564036.QbfCompleteLax564036.QuantifiedBooleanFormulasLax564036.QuantifiedBooleanFormulasInvarianceLax564036.SatUnsatLax564036.SatUnsatDPCompleteLax564036.SatUnsatInvarianceLax564036.TautCoNPCompleteLax564036.TautologyLax564036.TautologyInvarianceLax564036.ThreeDnfTautCoNPCompleteLax564036.ThreeDnfTautologyLax564036.ThreeDnfTautologyInvarianceLax604544.ClassesAsDegreesLax604544.DagIsomorphismLax604544.DegreeOfAProblemLax604544.DegreesLax604544.GraphIsomorphismLax604544.GraphIsomorphismDegreeLax604544.IsomorphismInNPLax604544.IsomorphismInvarianceLax604544.RelationIsomorphismSemanticsLax624099.ClassRELax624099.CodeHaltingInvarianceLax624099.CodehaltRECompleteLax624099.ConcreteInstancesLax624099.FiniteSatisfiabilityInvarianceLax624099.FinsatRECompleteLax624099.HaltingLax624099.HaltingInvarianceLax624099.HaltingUndecidableLax624099.HaltRECompleteLax624099.NPSubsetRELax624099.PcpRECompleteLax624099.PcpUndecidableLax624099.PostCorrespondenceInvarianceLax624099.ProblemsLax624099.REClosureLax624099.ReductionsComputableLax624099.REFiniteLax624099.REHardUndecidableLax624099.REIsRecursivelyEnumerableLax624099.RENeCoRELax624099.TrakhtenbrotLax624099.ValueInventionLax799700.ProblemsLax822549.TilingsCompleteLax822549.WideMachinesLax822549.WideMachinesCompleteLax822549.WideProblemsValuesLax822549.WideRegChannelLax822549.WideTilingsLax832283.StringProblemsLax859101.AllSetsCompleteLax859101.AllSetsValuesLax859101.BipartiteCompleteLax859101.BipartiteValuesLax859101.ColoringCompleteLax859101.DnfCompleteLax859101.DnfValuesLax859101.NaeSatCompleteLax859101.NaeSatValuesLax859101.OneCallClosureLax859101.RestrictedSatCompleteLax859101.RestrictedSatValuesLax859101.SubtractiveClosureLax895169.ACZeroComplementLax895169.ACZeroFiniteLax895169.ACZeroInLogSpaceLax895169.ACZeroInPTIMELax895169.ACZeroIsBitLogicLax895169.ACZeroIsLogTimeLax895169.ArithmeticLogicLax895169.BitLogicLax895169.FirstOrderInACZeroLax895169.LogTimeMachinesLax904597.ClassesLax904597.InterpretationsLax904597.MachinesLax904597.SatLax904597.SecondOrderLax945089.EhrenfeuchtMethodologyLax945089.EvenLax945089.EvenInvarianceLax945089.EvenNotFirstOrderLax945089.FirstOrderBelowACZeroLax945089.FirstOrderBelowTransitiveClosureLax945089.GamesOnLinearOrdersLax945089.GamesOnSetsLax945089.NoDefinableOrderLax945089.OrderFreeFirstOrderLax945089.OrderFreeInductionMissesPTIMELax945089.ParityLax945089.ParityInLogSpaceLax945089.PebbleInvarianceLax945089.ReductionsBelowLogSpaceLax945089.TransitiveClosureReductions
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments