Lax Lean Archive

While this submission is a draft, it cannot be used by other submissions.

The isomorphism problems are in NP

Lax604544.IsomorphismInNP · concepts/Lax604544/IsomorphismInNP.lean · lax-604544

proven

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    Digraph Isomorphism, Graph Isomorphism and DAG Isomorphism are in NP, by an existential second-order sentence guessing the bijection, with no order and no counting; and every problem of GI is in NP.

    Concept map
    28 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    1 dagIso_mem_NP proven

    2 digraphIso_mem_NP proven

    3 GI_subset_NP proven

    4 graphIso_mem_NP proven

    Lean source view on GitHub

    1import Lax904597.Problems
    2import Lax904597.Interpretations
    3import Lax904597.Relativized
    4import Lax904597.Classes
    5import Lax904597.Sat
    6import Lax799700.SubgraphIso
    7import Lax485149.Problems
    8import Lax485149.TwoSat
    9import Lax485149.ClassNL
    10import Lax535992.HornSat
    11import Lax535992.ClassPTIME
    12import Lax564036.Hierarchy
    13import Lax564036.Tautology
    14import Lax624099.ClassRE
    15import Lax624099.FiniteSatisfiability
    16import Lax604544.Degrees
    17import Lax604544.RelationIsomorphism
    18import Lax604544.GraphIsomorphism
    19import Lax604544.DagIsomorphism
    20
    21/-!
    22---
    23title: The isomorphism problems are in NP
    24type: theorem
    25---
    26Digraph Isomorphism, Graph Isomorphism and DAG Isomorphism are in NP, by an
    27existential second-order sentence guessing the bijection, with no order and
    28no counting; and every problem of GI is in NP.
    29-/
    30
    31namespace Lax604544.IsomorphismInNP
    32
    33open FirstOrder FirstOrder.Language
    34open Lax904597.Problems Lax904597.Interpretations Lax904597.Relativized Lax904597.Classes
    35open Lax904597.Sat Lax799700.SubgraphIso
    36open Lax485149.Problems Lax485149.TwoSat Lax485149.ClassNL Lax535992.HornSat Lax535992.ClassPTIME
    37open Lax564036.Hierarchy Lax564036.Tautology Lax624099.ClassRE Lax624099.FiniteSatisfiability
    38open Lax604544.Degrees Lax604544.RelationIsomorphism
    39open Lax604544.GraphIsomorphism Lax604544.DagIsomorphism
    40
    41/-- Digraph Isomorphism is in NP. -/
    42axiom digraphIso_mem_NP : NP.Mem DigraphIso
    43
    44/-- Graph Isomorphism is in NP. -/
    45axiom graphIso_mem_NP : NP.Mem GraphIso
    46
    47/-- DAG Isomorphism is in NP. -/
    48axiom dagIso_mem_NP : NP.Mem DagIso
    49
    50/-- GI is contained in NP. -/
    51axiom GI_subset_NP : ∀ {L : Language.{0, 0}} [L.IsRelational] (P : DecisionProblem L),
    52 GI.Mem P → NP.Mem P
    53
    54end Lax604544.IsomorphismInNP
    55
    Show ProofShow ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…