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
Lax485149.DeterministicReachabilityLax485149.DeterministicReachabilityInvarianceLax485149.FirstOrderInTransitiveClosureLax485149.ImmermanSzelepcsenyiLax485149.KromAndTransitiveClosureLax485149.LByAutomataLax485149.LClosureLax485149.LEqCoLLax485149.LSubsetNLLax485149.NLByAutomataLax485149.NLClosureLax485149.NLEqCoNLLax485149.NLIsTransitiveClosureLax485149.NLSubsetNPLax485149.ReachabilityLax485149.ReachabilityInvarianceLax485149.ReachdLCompleteLax485149.ReachNLCompleteLax485149.TransitiveClosureClosureLax485149.TwoSatLax485149.TwoSatInvarianceLax485149.TwoSatNLCompleteLax485149.UnreachdLCompleteLax485149.UnreachNLComplete
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments