Lax434930.NondeterministicPolynomialTime
The complexity class NP
concepts/Lax434930/NondeterministicPolynomialTime.lean · lax-434930
No public endorsements yet.
Loading review…
Sign in with ORCIDConcept map
Definition
A binary language belongs to if there are a verifier language and a polynomial such that precisely when some binary certificate with satisfies . The verifier is a single deterministic polynomial-time decider on the explicit pair encoding, and its running time is polynomial in the combined input and certificate lengths. The certificate bound depends only on the original input length. This is the standard certificate definition of NP.
Lean source view on GitHub
| 1 | import Lax434930.Certificates |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The complexity class NP |
| 6 | type: definition |
| 7 | --- |
| 8 | A binary language belongs to if there are a verifier |
| 9 | language and a polynomial such that |
| 10 | precisely when some binary certificate with |
| 11 | satisfies . |
| 12 | The verifier is a single deterministic polynomial-time decider on the |
| 13 | explicit pair encoding, and its running time is polynomial in the combined |
| 14 | input and certificate lengths. The certificate bound depends only on the |
| 15 | original input length. This is the standard certificate definition of NP. |
| 16 | -/ |
| 17 | |
| 18 | namespace Lax434930.NondeterministicPolynomialTime |
| 19 | |
| 20 | open PolynomialTime Certificates |
| 21 | |
| 22 | /-- Languages with polynomially bounded, polynomial-time verifiable certificates. -/ |
| 23 | def NP : Set Language := |
| 24 | {A | ∃ V : Language, V ∈ P ∧ ∃ p : Polynomial ℕ, ∀ x : Word, |
| 25 | x ∈ A ↔ ∃ y : Word, y.length ≤ p.eval x.length ∧ pair x y ∈ V} |
| 26 | |
| 27 | end Lax434930.NondeterministicPolynomialTime |
| 28 |
Community review
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.
0 comments