The complement of a decision problem
Lax485149.Complement · concepts/Lax485149/Complement.lean · lax-485149
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
The complement of a decision problem over a relational vocabulary has as yes-instances the structures that are no-instances of . It is a decision problem: a property and its negation are invariant under the same isomorphisms.
Concept map
Lean source view on GitHub
| 1 | import Lax904597.Problems |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The complement of a decision problem |
| 6 | type: definition |
| 7 | --- |
| 8 | The complement of a decision problem over a relational vocabulary |
| 9 | has as yes-instances the structures that are no-instances of . It is a |
| 10 | decision problem: a property and its negation are invariant under the same |
| 11 | isomorphisms. |
| 12 | -/ |
| 13 | |
| 14 | namespace Lax485149.Complement |
| 15 | |
| 16 | open Lax904597.Problems |
| 17 | |
| 18 | open FirstOrder |
| 19 | |
| 20 | open Language |
| 21 | |
| 22 | /-- The complement of a decision problem: its yes-instances are the |
| 23 | no-instances of `P`. -/ |
| 24 | def DecisionProblem.compl {L : Language.{0, 0}} [L.IsRelational] |
| 25 | (P : DecisionProblem L) : |
| 26 | DecisionProblem L where |
| 27 | Holds := fun A inst => ¬@DecisionProblem.Holds L _ P A inst |
| 28 | iso_invariant := fun e => not_congr (P.iso_invariant e) |
| 29 | |
| 30 | end Lax485149.Complement |
| 31 |
Builds on
Used by
Lax134656.AbiteboulVianuLax134656.AbiteboulVianuOrderedLax134656.ClassPSPACELax134656.HierarchyInPSPACELax134656.InflationaryInPartialLax134656.PartialFixedPointCaptureLax134656.PartialFixedPointClosureLax134656.PSPACEClosureLax134656.PSPACEEqCoPSPACELax134656.QsatInvarianceLax134656.QsatPSPACECompleteLax134656.SpaceBoundedMachineInvarianceLax134656.SpaceMachinesPSPACECompleteLax134656.SuccinctReachInvarianceLax134656.SuccinctReachPSPACECompleteLax134656.TransitiveClosureWithoutOrderLax175070.CountClassComplementsLax175070.CountClassInclusionsLax175070.CountClassMembershipLax175070.CountingValuesLax175070.ParitySatCompleteLax175070.SelectedSatCompleteLax480241.AlternatingSpaceValueLax480241.APSPACEIsEXPTIMELax480241.ExponentialCapturesLax480241.ExponentialClassesLax480241.ExponentialComplementsLax480241.ExponentialInclusionsLax480241.ExponentialMonotoneLax485149.ClassLLax485149.ClassNLLax485149.DeterministicReachabilityLax485149.DeterministicReachabilityInvarianceLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ReachabilityLax485149.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.DPClosureLax564036.DPInclusionsLax564036.HierarchyDualityLax564036.HierarchyInclusionsLax564036.PolynomialTimeInHierarchyLax564036.QbfCompleteLax564036.QuantifiedBooleanFormulasInvarianceLax564036.SatUnsatDPCompleteLax564036.SatUnsatInvarianceLax564036.TautCoNPCompleteLax564036.TautologyInvarianceLax564036.ThreeDnfTautCoNPCompleteLax564036.ThreeDnfTautologyInvarianceLax895169.ACZeroComplementLax895169.ACZeroFiniteLax895169.ACZeroInLogSpaceLax895169.ACZeroInPTIMELax895169.ACZeroIsBitLogicLax895169.ACZeroIsLogTimeLax895169.FirstOrderInACZero
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments