cs-p-np-proof
Theorem: P ⊆ NP
Proof: Let (L \in \textbf{P}) with deterministic polynomial-time decider (M) running in time (p(|x|)). Construct verifier (V) that on input ((x, c)):
Completeness: If (x \in L), (M(x)) accepts → (V(x, c)) accepts for all certificates (c).
Soundness: If (x \notin L), (M(x)) rejects → (V(x, c)) rejects for all certificates (c).
Runtime: (O(p(|x|) + |x| + |c|)) — polynomial in (|x|).
Thus (L \in \textbf{NP}), and since (L) was arbitrary, (\textbf{P} \subseteq \textbf{NP}). ∎
Related result — Savitch's Theorem: (\text{NSPACE}(f(n)) \subseteq \text{DSPACE}((f(n))^2)), giving NPSPACE = PSPACE. No analogous time-bounded result is known (that's exactly the P vs NP problem).
Two Go implementations demonstrate the construction: - **Even language** (binary strings ending in '0') — O(n) decider → verifier - **PATH language** (directed graph reachability) — O(V+E) BFS decider → verifier All 30 test cases pass, covering: empty inputs, empty certificates, arbitrary certificates, trivial paths, disconnected graphs, completeness (members accepted with any cert), and soundness (non-members rejected with any cert).
{"model": "claude-sonnet-4-20250514", "problem_class": "cs-p-np-proof", "result": "passed", "tests": 30}