Computer Science
Algorithms, data structures, computation theory, and systems design
Cook–Levin Theorem
The Cook-Levin theorem proves that the Boolean satisfiability problem (SAT) is NP-complete: SAT is in NP and every NP problem reduces to it in polynomial time. Proved by Stephen Cook (1971) and independently Leonid Levin (1973), it founded the theory of NP-completeness.
Polynomial-Time Reduction
A polynomial-time reduction transforms instances of one problem into instances of another in polynomial time so that solving the second yields a solution to the first. Reductions are the core tool for proving NP-hardness and completeness, and they establish that problems are 'equally hard'.
NP-Completeness
An NP-complete problem is one that is both in NP and NP-hard, meaning every NP problem reduces to it in polynomial time. All NP-complete problems are interreducible, so an efficient algorithm for any one would solve them all and prove P = NP.
Boolean Satisfiability Problem (SAT)
SAT asks whether a Boolean formula can be made true by some assignment of true/false to its variables. It was the first problem proven NP-complete (Cook-Levin, 1971), and despite this worst-case hardness, modern solvers handle industrial instances with millions of constraints.
Complexity Class
A complexity class groups computational problems by the resources (time or space) they require on a model of computation such as the Turing machine. Key classes include P, NP, co-NP, PSPACE, and EXPTIME, related by the chain P subset of NP subset of PSPACE subset of EXPTIME, with P versus NP famously open.
What a Resolution of P versus NP Would Actually Look Like
A solution to P versus NP is not an algorithm for any single problem but a mathematical proof about the entire space of possible algorithms. This chunk distinguishes the constructive case (an explicit algorithm or reduction), the non-constructive case (proof that an efficient algorithm must exist without exhibiting it), and explains why 'polynomial' does not mean 'fast'.
The Sudoku-to-SAT Reduction: How to Translate One Problem Into Another
A worked example of a polynomial-time reduction: encoding a Sudoku puzzle as a Boolean satisfiability (SAT) instance. The reduction is a mechanical translator, not a solver — a fast SAT solver automatically becomes a fast Sudoku solver, illustrating why all NP-complete problems are interchangeable.
The Travelling Salesman Problem
The Travelling Salesman Problem asks for the shortest route that visits a set of cities exactly once and returns to the start. It is NP-hard (its decision version is NP-complete), so no known algorithm solves every instance efficiently and brute force scales factorially. In practice it is tackled with exact dynamic programming for small inputs and fast heuristics like nearest neighbor, Christofides, and Lin-Kernighan for large ones.
How SAT Solvers Actually Work: From DPLL to CDCL
Practical Boolean satisfiability solvers are built on backtracking search with constraint propagation. This chunk traces the lineage from unit propagation and pure-literal elimination through the 1962 DPLL algorithm to conflict-driven clause learning (CDCL, 1996), explaining why modern solvers handle millions of variables despite exponential worst cases.
The 2-SAT / 3-SAT Boundary: Where Tractability Ends
Boolean satisfiability is polynomial-time solvable when every clause has two literals (2-SAT) but becomes NP-complete the moment clauses may have three (3-SAT). This chunk explains implication graphs, why the branching at three literals defeats the graph method, the 4.27 phase-transition ratio, and why difficulty does not keep rising past 3-SAT.
Rowhammer: The DRAM Vulnerability That Flips Bits by Reading Memory
Rowhammer is a hardware vulnerability in DRAM where repeatedly accessing (hammering) one memory row causes electrical interference that flips bits in physically adjacent rows. Discovered in 2014 by Yoongu Kim et al. at CMU, it affects 85%+ of DRAM modules tested. Google Project Zero demonstrated it could be weaponized for privilege escalation — an unprivileged process flipping bits to gain kernel access.
Why Complexity Is Measured Asymptotically, Not by Counting Steps
Complexity theory measures how a problem's required work grows as a function of input size, deliberately ignoring constants, precomputation, and lookup tables. This chunk explains the abstract step model, why the 'pi contains the answer' and giant-lookup-table shortcuts fail, and why a valid hardness proof is timeless.
Vector Databases: How Embedding Search Powers Modern AI Applications
Vector databases are specialized storage systems optimized for similarity search on high-dimensional embedding vectors. They enable semantic search — finding items by meaning rather than keywords — by storing numerical representations (embeddings) of text, images, or other data and quickly finding the nearest neighbors to a query vector. Key implementations include pgvector (PostgreSQL extension), Pinecone, Weaviate, Chroma, Qdrant, and Milvus. They are the retrieval backbone of RAG (Retrieval-Augmented Generation) systems.
Reversing Pseudo-Random Number Generators: Why PRNGs Are Predictable and Hackable
Most computer-generated 'random' numbers come from deterministic formulas that are fully reversible. Linear Congruential Generators can be inverted with modular multiplicative inverses. XOR-shift generators can be unwound step by step. JavaScript's Math.random(), Minecraft's world generation, PHP, and Flash all use hackable PRNGs. Only cryptographically secure RNGs (CSPRNGs) are safe for security-sensitive applications.
CPU Cache Levels Explained: Why L1 Is Faster Than L3
CPU cache speed differences come from physical distance to the core and size tradeoffs. L1 (~1ns) is tiny but inside the core. L3 (~10-40ns) is larger but farther away. At 3 GHz, even millimeters matter.
Why Computers Aren't More Modular: The Interconnect Bottleneck
Hardware modularity is limited by interconnect speeds (inter-chip communication is ~100x slower than intra-chip), software parallelization difficulty, and Amdahl's Law. Apple's integrated SoC approach avoids the bottleneck.
P vs NP Problem: Fundamentals Explained
P = efficiently solvable, NP = efficiently verifiable. NP-complete problems are the hardest — solving any one efficiently would solve all NP problems. Proof must be mathematical, not algorithmic.