Polynomial solving and polynomial verification differ.
Key knowledge
P contains decision problems solved by a deterministic algorithm in time polynomial in input length. NP contains problems whose yes instances admit polynomial-size certificates verified in polynomial time, with no accepted certificate for no instances. P⊆NP.
Conditions and scope
Fix a conventional discrete machine model and explicit finite input encoding.
NP does not mean non-polynomial; polynomial bounds are asymptotic rather than a practical speed guarantee.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
P contains decision problems solved by a deterministic algorithm in time polynomial in input length. NP contains problems whose yes instances admit polynomial-size certificates verified in polynomial time, with no accepted certificate for no instances. P⊆NP.
A decision problem B is NP-hard when every problem in NP has a polynomial-time reduction to B. B is NP-complete when it is also in NP. A polynomial algorithm for any NP-complete problem would give polynomial algorithms for all NP problems.
A fixed finite-tape deterministic Turing machine running in time t(n)≥n can be simulated by a single-tape machine in O(t(n)²) time by storing tape contents and head markers and scanning them for each simulated step. These models have the same decidable languages and polynomial-time class.
L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP, where EXP=⋃ₖ≥₁DTIME(2ⁿᵏ). A halting polynomial-space machine has only exponentially many configurations; a logspace configuration graph has polynomial size. P⊊EXP by deterministic time hierarchy.
Boolean satisfiability SAT is NP-complete under polynomial-time many-one reductions. For each language A∈NP and input x, a polynomial-size formula encodes a polynomial-time accepting computation tableau so that x∈A exactly when that formula is satisfiable; a satisfying assignment itself supplies the NP witness.
An interactive proof lets a polynomial-time randomized verifier exchange messages with a computationally unbounded prover. Completeness gives a successful honest prover on yes-instances; soundness bounds acceptance for every cheating prover on no-instances. Repetition/amplification must preserve the protocol model. An argument instead bounds only computationally restricted cheating provers, so its hardness assumptions and resource bounds must be declared.
Proof verification is a resource-defined decision procedure.
A reduction turns a successful scheme attacker into an attacker on a stated assumption, with explicitly related time, query count and success probability. A hybrid argument sums successive distinguishing gaps; a factor of q or additional failure probability can materially change finite-parameter security. Negligibility is an asymptotic condition, not an exact bit-strength certificate for one key size, and a random oracle is a model rather than a theorem that every hash function behaves randomly.
Worst-case complexity classes do not directly establish an average-case cryptographic assumption.