Problems given by a property of structures
Lax799700.Problems · concepts/Lax799700/Problems.lean · lax-799700
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 catalog 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 of the catalog is, this is the problem whose yes-instances are exactly the structures satisfying ; that equivalence is stated, problem by problem, next to each definition.
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 catalog the |
| 10 | bundling is done once and for all: the problem given by a property of |
| 11 | structures has as yes-instances the structures isomorphic to one satisfying |
| 12 | , which is invariant by construction. When is itself invariant, as |
| 13 | every property of the catalog is, this is the problem whose yes-instances are |
| 14 | exactly the structures satisfying ; that equivalence is stated, problem by |
| 15 | problem, next to each definition. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax799700.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 Lax799700.Problems |
| 31 |
Builds on
Used by
Lax117614.GraphCrawlingInvarianceLax117614.GraphCrawlingNPCompleteLax117614.GraphCrawlingProblemLax799700.CliqueFamilyLax799700.ColoringLax799700.CommonLax799700.DominatingSetLax799700.FeedbackLax799700.HamiltonLax799700.JobSequencingLax799700.KnapsackLax799700.MaxCutLax799700.NaeSatLax799700.NaeThreeSatLax799700.OneInSatLax799700.PartitionLax799700.SetFamilyLax799700.SteinerLax799700.SubgraphIsoLax799700.ThreeColorabilityLax799700.ThreeDimMatchingLax799700.ThreeSatLax799700.ZeroOneIP
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments