Multicoloured Clique Is NP-Hard
Lax496464.WH_F5_MccNPHard · concepts/Lax496464/WH_F5_MccNPHard.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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 (). The reduction of is computable in polynomial time on the word RAM, hence by a Turing machine (), 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 (), which is what a further reduction that is correct only on instances needs.
Concept map
Evidence
This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.
1 mcc_npHard proven
Lean source view on GitHub
| 1 | import Lax496464.WH_F3_NPHard |
| 2 | import Lax496464.WH_F4_IndependentSetToMcc |
| 3 | import Lax762056.IndependentSetHardness |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Multicoloured Clique Is NP-Hard |
| 8 | type: theorem |
| 9 | --- |
| 10 | **Multicoloured Clique is NP-hard**: every language in NP reduces to it by a map computable in |
| 11 | polynomial time by a Turing machine [FHRV09], [CFK+15, Theorem 13.7]. |
| 12 | |
| 13 | Independent 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 |
| 16 | its output bits as a word of numbers, and this reduction gives a reduction to Multicoloured Clique. |
| 17 | The reduction to Independent Set always produces an instance, so the composite always produces the |
| 18 | word of a Multicoloured Clique instance (`mcc_npHard_in`), which is what a further reduction that is |
| 19 | correct only on instances needs. |
| 20 | |
| 21 | # Formalization Notes |
| 22 | |
| 23 | NP-hardness is `WH_F3_NPHard.NPHard`, for the problem without its parameter. The parameterized |
| 24 | statement is `WH_F4_IndependentSetToMcc.independentSet_le_mcc`. |
| 25 | -/ |
| 26 | |
| 27 | namespace Lax496464.WH_F5_MccNPHard |
| 28 | |
| 29 | /-- **Multicoloured Clique is NP-hard.** -/ |
| 30 | axiom 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 |
| 33 | word of an instance. -/ |
| 34 | axiom mcc_npHard_in : WH_F3_NPHard.NPHardIn Lax888481.MulticolouredClique.problem |
| 35 | |
| 36 | end Lax496464.WH_F5_MccNPHard |
| 37 |
Formalization Notes
NP-hardness is , for the problem without its parameter. The parameterized statement is .
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments