Counting classes
Lax366625.CountingClasses · concepts/Lax366625/CountingClasses.lean · lax-366625
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
A counting class is given by a membership predicate and a hardness predicate on counting problems over arbitrary relational vocabularies. The classes of this submission are built from their membership predicate: a problem is parsimoniously hard for the class when every member of the class reduces to by a relativized ordered parsimonious reduction, and parsimoniously complete when it is moreover a member.
Concept map
Lean source view on GitHub
| 1 | import Lax904597.Problems |
| 2 | import Lax366625.CountingProblems |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Counting classes |
| 7 | type: definition |
| 8 | --- |
| 9 | A counting class is given by a membership predicate and a hardness predicate |
| 10 | on counting problems over arbitrary relational vocabularies. The classes of |
| 11 | this submission are built from their membership predicate: a problem is |
| 12 | parsimoniously hard for the class when every member of the class reduces to |
| 13 | by a relativized ordered parsimonious reduction, and parsimoniously |
| 14 | complete when it is moreover a member. |
| 15 | -/ |
| 16 | |
| 17 | namespace Lax366625.CountingClasses |
| 18 | |
| 19 | open FirstOrder FirstOrder.Language |
| 20 | open Lax904597.Problems Lax366625.CountingProblems |
| 21 | |
| 22 | /-- A counting class: a membership predicate and a hardness predicate on |
| 23 | counting problems, over arbitrary relational vocabularies. -/ |
| 24 | structure CountingClass where |
| 25 | /-- The counting problems belonging to the class. -/ |
| 26 | Mem : ∀ {L : Language.{0, 0}} [L.IsRelational], CountingProblem L → Prop |
| 27 | /-- The counting problems every problem of the class reduces to. -/ |
| 28 | ParsimoniousHard : ∀ {L : Language.{0, 0}} [L.IsRelational], CountingProblem L → Prop |
| 29 | |
| 30 | /-- The class with the given membership, a problem being hard when every member |
| 31 | reduces to it by a relativized ordered parsimonious reduction. -/ |
| 32 | def CountingClass.ofMem |
| 33 | (Mem : ∀ {L₀ : Language.{0, 0}} [L₀.IsRelational], CountingProblem L₀ → Prop) : |
| 34 | CountingClass where |
| 35 | Mem C := Mem C |
| 36 | ParsimoniousHard C := ∀ {L'' : Language.{0, 0}} [L''.IsRelational] (D : CountingProblem L''), |
| 37 | Mem D → Nonempty (RelOrderedParsimoniousReduction D C) |
| 38 | |
| 39 | /-- A counting problem is parsimoniously complete for a class when it belongs |
| 40 | to it and is parsimoniously hard for it. -/ |
| 41 | def CountingClass.ParsimoniousComplete (K : CountingClass) {L : Language.{0, 0}} [L.IsRelational] |
| 42 | (C : CountingProblem L) : Prop := |
| 43 | K.Mem C ∧ K.ParsimoniousHard C |
| 44 | |
| 45 | end Lax366625.CountingClasses |
| 46 |
Used by
Lax175070.CountClassComplementsLax175070.CountClassInclusionsLax175070.CountClassMembershipLax175070.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.CountingRunsCompleteLax366625.CountingRunsValueLax366625.FPAndPTIMELax366625.FPByDigitsLax366625.FPClosureLax366625.FPCompleteLax366625.NumbersValueLax366625.QuantitativeLogicLax366625.SharpPAndNPLax366625.SharpPAsQuantitativeLogicLax366625.SharpPClosureLax366625.SharpSatCompleteLax366625.SharpSatValueLax366625.WitnessCountingLax794877.ExampleDatabaseProbabilityLax794877.H0CompleteLax794877.HierarchicalQueryInFPLax794877.ProbabilityRatioLax794877.WorldCountLax794877.WorldsInSharpPLax794877.WorldsValuesLax859101.AllSetsCompleteLax859101.AllSetsValuesLax859101.BipartiteCompleteLax859101.BipartiteValuesLax859101.ColoringCompleteLax859101.DnfCompleteLax859101.DnfValuesLax859101.NaeSatCompleteLax859101.NaeSatValuesLax859101.OneCallClosureLax859101.OneCallReductionsLax859101.RestrictedSatCompleteLax859101.RestrictedSatValuesLax859101.SubtractiveClosureLax859101.SubtractiveReductions
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments