Short Notes on Cook's Theorem, Randomized Algorithms, and Bin Packing

These three topics occupy central positions in computational complexity, algorithm design, and approximation theory. Cook's theorem explains why SAT is historically foundational in NP-completeness; randomized algorithms show how randomization can improve performance or simplicity; and bin packing illustrates a classic NP-hard optimization problem where exact solutions are difficult but practical heuristics and approximation methods are powerful.3

A useful way to relate them is this: Cook's theorem establishes a framework for proving intractability via reductions, randomized algorithms provide alternative design strategies when deterministic methods are expensive or awkward, and bin packing is a canonical example of a hard problem that motivates approximation and heuristic approaches.3

3

Footnotes

1. Cook–Levin theorem - Wikipedia - Overview of the theorem stating SAT is NP-complete and explaining polynomial-time reductions. ↩ ↩² ↩³

2. Lecture 18: Randomized Algorithms - Harvard - Lecture notes defining Las Vegas and Monte Carlo algorithms, expected runtime, and error amplification. ↩ ↩² ↩³

3. Bin packing problem - Wikipedia - Overview of bin packing, hardness, heuristics, and approximation guarantees including FFD. ↩ ↩² ↩³

(a) Cook's Theorem

Cook's theorem—more precisely the Cook–Levin theorem—states that the Boolean satisfiability problem is NP-complete. This means two things hold:

1. SAT belongs to NP because, given a truth assignment, one can verify in polynomial time whether the Boolean formula is satisfied.
2. Every problem in NP can be reduced to SAT by a polynomial-time reduction.2

Formally, if $L \in \mathrm{NP}$, then there exists a polynomial-time computable function $f$ such that

$$x \in L \iff f(x) \in \mathrm{SAT}.$$

This is the key statement that makes SAT the first known NP-complete problem.2

The theorem is historically important because it launched the modern theory of NP-completeness and enabled thousands of later hardness proofs through chains of reductions.2 Once SAT was shown NP-complete, researchers could prove another problem hard by reducing SAT or another NP-complete problem to it.

The proof idea is to encode the computation of a nondeterministic Turing machine on an input as a Boolean formula.2 The formula describes a computation tableau ensuring:

• the initial configuration is correct,
• each step follows the machine's transition rules,
• and some accepting configuration is reached.2

Thus, the formula is satisfiable exactly when the original machine has an accepting computation path.2

Footnotes

1. Cook–Levin theorem - Wikipedia - Overview of the theorem stating SAT is NP-complete and explaining polynomial-time reductions. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

2. Introduction to Theoretical Computer Science: NP, NP completeness, and the Cook-Levin Theorem - Textbook-style explanation of encoding NP computations into SAT. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. NP Completeness - University of Virginia Slides - Slides summarizing NP-hardness, NP-completeness, and the significance of Cook/Levin. ↩

(b) Randomized Algorithms

A randomized algorithm is an algorithm that makes decisions using random bits during execution.2 Unlike deterministic algorithms, its behavior may vary across different runs on the same input. The analysis therefore studies both running time and probability of correctness.2

Two major classes are commonly distinguished:

Randomized algorithms are valuable because they can be simpler, faster in expectation, or easier to analyze than deterministic alternatives.2 They are especially useful in primality testing, hashing, matrix verification, minimum cut, load balancing, and geometric computation.2

A central concept is expected running time. If $T$ is a random variable for runtime, then one often studies $\mathbb{E}[T]$ rather than only the worst case.2 For example, randomized quicksort has expected complexity

$$\mathbb{E}[T(n)] = O(n \log n),$$

even though some unlucky pivot choices can still lead to quadratic behavior.2

For Monte Carlo algorithms, repeated independent trials can reduce the error probability, a technique called amplification. If a single trial fails with probability at most $1/2$, then after $k$ independent repetitions the failure probability can drop to at most

$$\left(\frac{1}{2}\right)^k.$$

This is one reason randomized methods are often practical despite allowing a tiny probability of error.

Footnotes

1. Lecture 18: Randomized Algorithms - Harvard - Lecture notes defining Las Vegas and Monte Carlo algorithms, expected runtime, and error amplification. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰

2. Notes on Randomized Algorithms - Yale - Notes discussing probabilistic analysis and the Las Vegas versus Monte Carlo distinction. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

(c) Bin Packing

The bin packing problem asks for the minimum number of bins of equal capacity needed to pack items of given sizes so that the total size in any bin does not exceed the capacity. In the standard one-dimensional version, if items have sizes $s_1,s_2,\dots,s_n$ with $0 < s_i \le 1$, the goal is to partition them into the fewest bins such that the sum in each bin is at most $1$.2

The decision version—whether all items can be packed into at most $k$ bins—is NP-complete, while the optimization version is NP-hard.2 Because of this, exact polynomial-time algorithms are not expected unless $P = NP$.

Bin packing has practical applications in memory allocation, cutting stock, cargo loading, scheduling, and resource consolidation.2 Its importance comes from the fact that it is easy to state, computationally hard, and rich in heuristic and approximation techniques.2

Several classical heuristics are used:

• Next Fit
• First Fit
• Best Fit
• First Fit Decreasing2

Among these, First Fit Decreasing (FFD) is especially important. It first sorts items in non-increasing order and then applies First Fit.2 It is fast and often near-optimal in practice. A classical bound states:

$$\mathrm{FFD}(I) \le \frac{11}{9}\mathrm{OPT}(I) + \frac{6}{9},$$

where $\mathrm{OPT}(I)$ is the minimum number of bins for instance $I$.

This illustrates a core theme of approximation algorithms: when exact optimization is hard, one seeks solutions that are provably close to optimal.2

2

Footnotes

1. Bin packing problem - Wikipedia - Overview of bin packing, hardness, heuristics, and approximation guarantees including FFD. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹

2. Approximation Algorithms for Multidimensional Bin Packing - Georgia Tech Thesis - Background on bin packing hardness, applications, and approximation context. ↩ ↩² ↩³

3. Approximation Algorithms for Bin Packing: A Survey - Survey covering classical heuristics such as FFD and their worst-case performance. ↩ ↩² ↩³ ↩⁴ ↩⁵

Concluding Note

In short, Cook's theorem is the foundational result proving that SAT is NP-complete and establishing the reduction-based framework of complexity theory.2 Randomized algorithms are algorithms that exploit random choices to obtain simplicity, speed, or bounded-error guarantees, usually analyzed through expectation and probability.2 Bin packing is a classical NP-hard optimization problem concerned with minimizing the number of fixed-capacity bins, and it is commonly addressed using heuristics such as First Fit and First Fit Decreasing, along with approximation analysis.2

Together, these topics represent three enduring ideas in computer science: proving hardness, designing with randomness, and coping with intractability through approximation.3

Footnotes

1. Cook–Levin theorem - Wikipedia - Overview of the theorem stating SAT is NP-complete and explaining polynomial-time reductions. ↩ ↩²

2. NP Completeness - University of Virginia Slides - Slides summarizing NP-hardness, NP-completeness, and the significance of Cook/Levin. ↩

3. Lecture 18: Randomized Algorithms - Harvard - Lecture notes defining Las Vegas and Monte Carlo algorithms, expected runtime, and error amplification. ↩ ↩²

4. Notes on Randomized Algorithms - Yale - Notes discussing probabilistic analysis and the Las Vegas versus Monte Carlo distinction. ↩

5. Bin packing problem - Wikipedia - Overview of bin packing, hardness, heuristics, and approximation guarantees including FFD. ↩ ↩²

6. Approximation Algorithms for Bin Packing: A Survey - Survey covering classical heuristics such as FFD and their worst-case performance. ↩