Problems given by a property of structures
Lax485149.Problems · concepts/Lax485149/Problems.lean · lax-485149
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The decision problems of the NP core are bundled with a proof that they do not distinguish isomorphic structures. For the problems of this submission the bundling is done once and for all: the problem given by a property of structures has as yes-instances the structures isomorphic to one satisfying , which is invariant by construction. When is itself invariant, as every property here is, this is the problem whose yes-instances are exactly the structures satisfying ; that equivalence is stated, problem by problem, in a lemma of its own.
Concept map
Lean source view on GitHub
| 1 | import Lax904597.Problems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Problems given by a property of structures |
| 6 | type: definition |
| 7 | --- |
| 8 | The decision problems of the NP core are bundled with a proof that they do |
| 9 | not distinguish isomorphic structures. For the problems of this submission |
| 10 | the bundling is done once and for all: the problem given by a property |
| 11 | of structures has as yes-instances the structures isomorphic to one |
| 12 | satisfying , which is invariant by construction. When is itself |
| 13 | invariant, as every property here is, this is the problem whose yes-instances |
| 14 | are exactly the structures satisfying ; that equivalence is stated, |
| 15 | problem by problem, in a lemma of its own. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax485149.Problems |
| 19 | |
| 20 | open FirstOrder FirstOrder.Language Lax904597.Problems |
| 21 | |
| 22 | /-- The decision problem whose yes-instances are the structures isomorphic to |
| 23 | one satisfying `P`. -/ |
| 24 | def DecisionProblem.ofPred {L : Language.{0, 0}} [L.IsRelational] |
| 25 | (P : ∀ (A : Type) [L.Structure A], Prop) : DecisionProblem L where |
| 26 | Holds := fun A _ => ∃ (B : Type) (i : L.Structure B) (_ : @Language.Equiv L B A i _), @P B i |
| 27 | iso_invariant := fun e => |
| 28 | ⟨fun ⟨B, i, f, h⟩ => ⟨B, i, e.comp f, h⟩, fun ⟨B, i, f, h⟩ => ⟨B, i, e.symm.comp f, h⟩⟩ |
| 29 | |
| 30 | end Lax485149.Problems |
| 31 |
Builds on
Used by
Lax134656.AbiteboulVianuLax134656.AbiteboulVianuOrderedLax134656.HierarchyInPSPACELax134656.InflationaryInPartialLax134656.PartialFixedPointCaptureLax134656.PartialFixedPointClosureLax134656.PSPACEClosureLax134656.PSPACEEqCoPSPACELax134656.QsatLax134656.QsatInvarianceLax134656.QsatPSPACECompleteLax134656.SpaceBoundedMachineInvarianceLax134656.SpaceBoundedMachinesLax134656.SpaceMachinesPSPACECompleteLax134656.SuccinctReachLax134656.SuccinctReachInvarianceLax134656.SuccinctReachPSPACECompleteLax134656.TransitiveClosureWithoutOrderLax175070.CountClassComplementsLax175070.CountClassInclusionsLax175070.CountClassMembershipLax175070.CountDefinabilityLax175070.CountingValuesLax175070.ParitySatCompleteLax175070.SelectedSatLax175070.SelectedSatCompleteLax480241.AlternatingSpaceLax480241.AlternatingSpaceValueLax480241.APSPACEIsEXPTIMELax480241.ExponentialCapturesLax480241.ExponentialClassesLax480241.ExponentialComplementsLax480241.ExponentialInclusionsLax480241.ExponentialMonotoneLax485149.DeterministicReachabilityLax485149.DeterministicReachabilityInvarianceLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ReachabilityLax485149.ReachabilityInvarianceLax485149.ReachdLCompleteLax485149.ReachNLCompleteLax485149.TransitiveClosureClosureLax485149.TwoSatLax485149.TwoSatInvarianceLax485149.TwoSatNLCompleteLax485149.UnreachdLCompleteLax485149.UnreachNLCompleteLax535992.CircuitValueLax535992.CircuitValueInvarianceLax535992.CircuitValuePTIMECompleteLax535992.DeterministicMachineInvarianceLax535992.DeterministicMachinePTIMECompleteLax535992.DeterministicMachinesLax535992.GameLax535992.GameInvarianceLax535992.GamePTIMECompleteLax535992.HornIsLeastFixedPointLax535992.HornSatLax535992.HornSatInvarianceLax535992.HornSatPTIMECompleteLax535992.ImmermanVardiLax535992.InflationaryIsLeastFixedPointLax535992.LeastFixedPointComplementLax535992.NLSubsetPTIMELax535992.PTIMEClosureLax535992.PTIMEEqCoPTIMELax535992.PTIMESubsetNPLax564036.AlternatingMachineCompleteLax564036.AlternatingMachineInvarianceLax564036.AlternatingMachinesLax564036.CoNPClosureLax564036.DPClosureLax564036.DPInclusionsLax564036.HierarchyDualityLax564036.HierarchyInclusionsLax564036.PolynomialTimeInHierarchyLax564036.QbfCompleteLax564036.QuantifiedBooleanFormulasLax564036.QuantifiedBooleanFormulasInvarianceLax564036.SatUnsatLax564036.SatUnsatDPCompleteLax564036.SatUnsatInvarianceLax564036.TautCoNPCompleteLax564036.TautologyLax564036.TautologyInvarianceLax564036.ThreeDnfTautCoNPCompleteLax564036.ThreeDnfTautologyLax564036.ThreeDnfTautologyInvarianceLax604544.ClassesAsDegreesLax604544.DagIsomorphismLax604544.DegreeOfAProblemLax604544.GraphIsomorphismLax604544.GraphIsomorphismDegreeLax604544.IsomorphismInNPLax604544.IsomorphismInvarianceLax604544.RelationIsomorphismSemanticsLax822549.TilingsCompleteLax822549.WideMachinesLax822549.WideMachinesCompleteLax822549.WideProblemsValuesLax822549.WideRegChannelLax822549.WideTilingsLax945089.EhrenfeuchtMethodologyLax945089.EvenLax945089.EvenInvarianceLax945089.EvenNotFirstOrderLax945089.FirstOrderBelowACZeroLax945089.FirstOrderBelowTransitiveClosureLax945089.GamesOnLinearOrdersLax945089.GamesOnSetsLax945089.NoDefinableOrderLax945089.OrderFreeInductionMissesPTIMELax945089.ParityLax945089.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