toc-beyond-np-space-and-distributed-limits
Use when the hardness question goes past NP or into distributed systems: the polynomial hierarchy, PSPACE and counting classes, fine-grained complexity and conditional lower bounds (SETH, 3SUM, APSP), space complexity, streaming and sublinear algorithms, and the distributed computing impossibility results — FLP, CAP and consensus — with their honest practical readings.
- License 许可
- MIT
- 最近更新
- 2026-11-15
- Stars
- ★ 5
- Forks
- 3
01 前言 Front Matter
- name
- toc-beyond-np-space-and-distributed-limits
- description
- Use when the hardness question goes past NP or into distributed systems: the polynomial hierarchy, PSPACE and counting classes, fine-grained complexity and conditional lower bounds (SETH, 3SUM, APSP), space complexity, streaming and sublinear algorithms, and the distributed computing impossibility results — FLP, CAP and consensus — with their honest practical readings.
03 SKILL.md 正文
Theory of Computation: Beyond NP, Space and Streaming, and Distributed Impossibility Results
Part 3 of 5 of the Theory of Computation reference (plugin
theory-of-computation), covering §8–§11. Sibling skills:toc-automata-regex-and-parsing(§0–§3),toc-computability-and-complexity(§4–§7),toc-type-systems-and-randomization(§12–§13),toc-reference(§14–§19). Section numbers are shared across the set; a reference written as §N →skillpoints into that sibling skill.Currency: Verified August 2026. See §16 →
toc-referencefor the currency snapshot and what goes stale first.
How to read this. Reference, not a course. Three markers:
- [DURABLE] — proven theorems and stable practice. This is most of the document, and it does not expire.
- [VERSIONED] — the small moving parts: recent results, solver capability, open problems.
- [CONTESTED] — genuine disagreement, mostly about pedagogy and practical relevance.
⚠️ GOTCHA boxes mark places where ignorance of the theory produces a specific, expensive production failure — which is the whole argument for learning it.
The three framings that organize everything below:
- This is the only branch of CS that tells you what you cannot do. Everything else teaches techniques. Theory tells you when to stop looking — and knowing a problem is undecidable or NP-hard is more valuable than any algorithm, because it redirects you from an impossible goal to a tractable approximation of it.
- You already use it; you may not know the names. Regex is finite automata. Your parser is a pushdown automaton. Your state machine is a DFA. Your build system's cycle detection is graph theory. The theory isn't an addition to your practice — it's a description of it, and knowing the description tells you where the edges are.
- "Hard" is not "impossible," and this is the most consequential practical point. NP-complete problems with thousands of variables are solved routinely (§9). The theory tells you no algorithm is fast on all inputs — it says nothing about your inputs, which are usually structured. Treating NP-hardness as a verdict rather than a warning is the single most common misapplication of this material.
§8. Beyond NP
[DURABLE] Worth knowing the landscape so you recognize when you're in worse trouble than NP.
PSPACE — solvable in polynomial space, any amount of time. PSPACE-complete problems include quantified Boolean formulas (QBF), most two-player games, and many planning problems. ⚠️ The tell: alternating quantifiers. "Is there a move such that for all responses there is a move such that…" That's QBF, that's PSPACE, and it is a qualitatively harder thing than a single existential search. If your problem has an adversary, you are probably here.
EXPTIME and above — provably harder than P (by the time hierarchy theorem, this one is not conjectural). Generalized games on n×n boards, some type-system and logic decision problems.
Undecidable — §4 → toc-computability-and-complexity.
[DURABLE] The hierarchy theorems are among the few unconditional separations we have:
more time and more space strictly buy you more. Almost everything else in §5 → toc-computability-and-complexity's map is open.
§9. Fine-Grained Complexity
[DURABLE, and under-taught relative to its practical value.] Classical complexity asks "polynomial or not." Fine-grained complexity asks: is my O(n²) algorithm actually optimal? — and it answers via conditional lower bounds.
The method: assume a hardness conjecture, then use fine-grained reductions — so tight that any improvement to the target implies an improvement to the source — to transfer hardness. The core conjectures: SETH (the Strong Exponential Time Hypothesis: for any ε > 0 there's a k such that k-SAT can't be solved in 2^((1-ε)n)), the Orthogonal Vectors hypothesis, 3SUM, and APSP.
[DURABLE] Why an engineer should care: it tells you when to stop optimizing. Well-known results in this line establish, under SETH, that Edit Distance and Longest Common Subsequence have no strongly subquadratic algorithm, that Orthogonal Vectors needs n², and that Bellman's classic O(nT) Subset Sum algorithm can't be substantially improved. Similar conditional bounds cover graph diameter approximation, dominating set, and a range of computational-geometry problems.
⚠️ The engineering translation: if your string-diff is quadratic, that is very likely not your fault, and no amount of profiling will fix it. The right move is to change the problem — restrict the input, exploit structure, approximate, or use a different similarity measure — not to keep optimizing the constant.
⚠️ These are conditional results. If SETH is false the bounds evaporate — but SETH has survived decades of attack and is treated as a working assumption.
[VERSIONED] Quantum analogues exist and are active (§16 → toc-reference): SETH itself fails quantumly
because Grover solves CNF-SAT in about 2^(n/2), so researchers built QSETH frameworks
to get meaningful quantum conditional lower bounds instead.
§10. Space and Memory
[DURABLE] Space is the resource engineers under-model. The classes: L (logarithmic space — you can hold a constant number of pointers, not a copy of the input), NL, PSPACE.
Two results worth carrying:
- Savitch's theorem: NSPACE(f) ⊆ SPACE(f²) — nondeterminism buys you much less in space than in time.
- Reingold's theorem (2005): undirected s-t connectivity is in log space — a genuinely surprising result, and the directed case remains the standing open challenge.
[DURABLE] Streaming and sublinear algorithms are the applied face of space complexity, and they're everywhere in production infrastructure: HyperLogLog (cardinality in kilobytes), Count-Min Sketch (frequency estimation), Bloom filters (membership with one-sided error), reservoir sampling. If you have a "count distinct over a firehose" problem, the theory already solved it — and the solution trades exactness for a bounded error you choose.
[VERSIONED — the one genuinely major recent theorem in this document.] In February 2025, Ryan Williams proved TIME[t] ⊆ SPACE[√(t log t)] — every multitape Turing machine running in time t can be simulated in O(√(t log t)) space. This replaced the Hopcroft–Paul–Valiant bound of t/log t that had stood since 1975, a near-quadratic improvement described in the field as "an earthquake of a result" and "a true classic complexity theorem." The proof reduces time-t computation to Tree Evaluation and applies the Cook–Mertz space-efficient algorithm from the catalytic-computing line.
⚠️ Read this correctly. It is a space simulation — it does not preserve the time bound, so it is not an algorithm you deploy tomorrow. Its significance is theoretical: it is a real step toward separating P from PSPACE, and it demolished a decades-old belief about what was possible. The engineering-adjacent lesson is epistemic: a 50-year-old "obvious barrier" fell, which is worth remembering whenever someone says something is known to be impossible when what they mean is that nobody has done it.
§11. Distributed Computing Impossibility Results
[DURABLE] Theory's most immediately actionable contribution to systems engineering. These are theorems, not architectural opinions, and violating them is not a design trade-off — it's a claim to have solved something proven impossible.
FLP impossibility (1985): in an asynchronous system with even one faulty process, there is no deterministic algorithm guaranteeing consensus. ⚠️ This is why every real consensus protocol uses timeouts, randomization, or a partial-synchrony assumption — Paxos and Raft don't refute FLP, they add an assumption FLP excludes. Anyone claiming deterministic asynchronous consensus is wrong.
CAP: under network partition, choose consistency or availability. ⚠️ CAP is routinely over-applied. It is about behaviour during a partition, not a general licence to be inconsistent, and the more useful modern framing is PACELC: under Partition, choose A or C; Else, choose Latency or Consistency — which is the trade-off you're actually making 99.9% of the time.
The Two Generals Problem: no protocol achieves guaranteed agreement over a lossy
channel. ⚠️ This is why exactly-once delivery does not exist, and why the achievable
target is at-least-once plus idempotency (which is why §3 → toc-automata-regex-and-parsing of a payments reference and this
paragraph are the same fact).
Byzantine fault tolerance: tolerating arbitrary (malicious) faults requires n > 3f nodes for f faults.
Linearizability, serializability, and the consistency zoo — these are formal definitions with precise meanings, and "eventual consistency" without specifying which model is not a specification.
[DURABLE] The practical instruction: when a design assumes reliable delivery, ordered delivery, synchronized clocks, or partition-free operation, name the assumption explicitly — because you have just chosen a side of one of these theorems, and it should be a decision rather than an accident.
04 同仓库更多 Skills
white-paper-writing
Use when writing white papers, technical reports, policy documents, thought leadership pieces, or any long-form authoritative document. Triggers on requests to write, structure, outline, or review white papers, technical reports, position papers, policy briefs, or evidence-driven arguments. Also use for B2B content marketing strategy, technical documentation requiring authority, academic-style reports, or any document that must educate while persuading. Use when someone asks "how should I structure this" for a long-form document.
prose-technical-mechanics
Use when editing or writing prose at a technical/mechanical level: choosing between Anglo-Saxon and Latinate diction, placing information in topic vs stress positions, writing periodic vs cumulative sentences, handling sentence rhythm, punctuation as logic, transitions, paragraph structure, or phonesthetics. Use when someone wants to understand WHY prose works or doesn't, not just surface-level style advice. Triggers on word choice, sentence structure, emphasis, rhythm, diction, or any deep writing mechanics question.
prose-mechanics
Use when writing, editing, or analyzing prose style; when trying to avoid generic AI-sounding writing; when applying specific prose styles such as journalistic, academic, narrative, KJV biblical, Hemingway plain, Latinate/Jamesian, Orwellian, Augustan, Victorian, Early Modern (Bacon, Browne, Milton), or free indirect discourse; or when coaching someone on writing voice and mechanics. Triggers on any request to improve, analyze, or write in a specific prose style, to fix "AI-sounding" writing, to make prose more vivid or concrete, to vary sentence rhythm, or to understand how a particular writer achieves their effects.
narrative-structure
Use when structuring stories, pitches, presentations, white papers, or any persuasive narrative; analyzing the hero's journey in fiction or non-fiction; applying StoryBrand for business communication; designing narrative arcs for thought leadership; or understanding Vogler, Snyder, Propp, or Campbell frameworks. Triggers on any narrative structure, storytelling, pitch structure, StoryBrand, hero's journey, three-act structure, Freytag, Save the Cat, narrative arc, or "how should I structure this story/pitch/presentation" request.
legal-brief-writing
Use when writing legal briefs, motions, or any court filing; when analyzing judicial cognition and persuasion; when applying elite brief-writing techniques from Roberts, Clement, Kagan, Garner; or when structuring legal arguments for maximum persuasion. Also use for autistic/neurodivergent advocates who need to understand how their natural communication style maps to elite legal advocacy. Triggers on any legal writing, brief drafting, motion preparation, or legal argument structuring request.
journal-publishability-criteria
Use whenever a research paper, article or preprint is being written, revised, reviewed or published, and specifically before every publication of docs/paper.md. Covers what legitimate journals actually gate on, in order of gating — the editor's desk screen (scope, novelty, package problems), what reviewers judge (methodological soundness, claims the evidence can carry, statistical and qualitative reporting), EQUATOR reporting guidelines, the ICMJE authorship criteria, COPE's view of text recycling, the near-universal generative-AI policy (no AI author, disclosure, author responsibility), TOP 2025 transparency standards, how to verify a journal is legitimate, submitting without an institution, and a pre-submission checklist. Triggers on requests to evaluate, review, prepare or submit a paper, to judge publishability, to write a declarations or data-availability section, to disclose AI use, or to check a journal.