Multicoloured Clique Is NP-Hard

Lax496464.WH_F5_MccNPHard · concepts/Lax496464/WH_F5_MccNPHard.lean · lax-496464

proven

Loading review…

Sign in with ORCID

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

    Multicoloured Clique is NP-hard: every language in NP reduces to it by a map computable in polynomial time by a Turing machine [FHRV09], [CFK+15, Theorem 13.7].

    Independent Set is NP-hard, as proved in the archive (Lax762056Lax762056). The reduction of WHF4IndependentSetToMccWH_F4_IndependentSetToMcc is computable in polynomial time on the word RAM, hence by a Turing machine (Lax759944Lax759944), and preserves the answer. Composing a reduction to Independent Set, the rewriting of its output bits as a word of numbers, and this reduction gives a reduction to Multicoloured Clique. The reduction to Independent Set always produces an instance, so the composite always produces the word of a Multicoloured Clique instance (mccnpHardinmcc_npHard_in), which is what a further reduction that is correct only on instances needs.

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

    Lean source view on GitHub

    1import Lax496464.WH_F3_NPHard
    2import Lax496464.WH_F4_IndependentSetToMcc
    3import Lax762056.IndependentSetHardness
    4
    5/-!
    6---
    7title: Multicoloured Clique Is NP-Hard
    8type: theorem
    9---
    10**Multicoloured Clique is NP-hard**: every language in NP reduces to it by a map computable in
    11polynomial time by a Turing machine [FHRV09], [CFK+15, Theorem 13.7].
    12
    13Independent Set is NP-hard, as proved in the archive (`Lax762056`). The reduction of
    14`WH_F4_IndependentSetToMcc` is computable in polynomial time on the word RAM, hence by a Turing machine
    15(`Lax759944`), and preserves the answer. Composing a reduction to Independent Set, the rewriting of
    16its output bits as a word of numbers, and this reduction gives a reduction to Multicoloured Clique.
    17The reduction to Independent Set always produces an instance, so the composite always produces the
    18word of a Multicoloured Clique instance (`mcc_npHard_in`), which is what a further reduction that is
    19correct only on instances needs.
    20
    21# Formalization Notes
    22
    23NP-hardness is `WH_F3_NPHard.NPHard`, for the problem without its parameter. The parameterized
    24statement is `WH_F4_IndependentSetToMcc.independentSet_le_mcc`.
    25-/
    26
    27namespace Lax496464.WH_F5_MccNPHard
    28
    29/-- **Multicoloured Clique is NP-hard.** -/
    30axiom mcc_npHard : WH_F3_NPHard.NPHard Lax888481.MulticolouredClique.problem
    31
    32/-- **Multicoloured Clique is NP-hard on its domain**: the reduction moreover always outputs the
    33word of an instance. -/
    34axiom mcc_npHard_in : WH_F3_NPHard.NPHardIn Lax888481.MulticolouredClique.problem
    35
    36end Lax496464.WH_F5_MccNPHard
    37
    Show ProofShow Proof
    Formalization Notes

    NP-hardness is WHF3NPHard.NPHardWH_F3_NPHard.NPHard, for the problem without its parameter. The parameterized statement is WHF4IndependentSetToMcc.independentSetlemccWH_F4_IndependentSetToMcc.independentSet_le_mcc.

    Discussion

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

    Loading discussion…