diff 9506729..b34550f subset_sum_2_power_0_49n_v2.txt
diff --git a/subset_sum_2_power_0_49n_v2.txt b/subset_sum_2_power_0_49n_v2.txt
index a900efb..2d12bd6 100644
--- a/subset_sum_2_power_0_49n_v2.txt
+++ b/subset_sum_2_power_0_49n_v2.txt
@@ -3,24 +3,16 @@ SUBSET SUM IN TIME O(2^(0.49n))
A complete, self-contained proof
================================================================
-READER'S GUIDE
----------------
-Subset Sum is the question: given n positive whole numbers a_1,...,a_n
-and a target t, can we pick some of the numbers that add up exactly to t?
+OVERVIEW
+--------
+Subset Sum: given n positive whole numbers a_1,...,a_n and a target t,
+decide whether some subset sums exactly to t. Meet-in-the-middle solves
+it in ~2^(n/2); this paper decides it in O(2^(0.49n)) on every run,
+worst case over the input. The algorithm is randomized and answers
+correctly with probability at least 2/3 for every input; the time bound
+holds on every run.
-The dumb way tries all 2^n subsets. That is hopeless for large n.
-The classic clever way (meet in the middle) does about 2^(n/2) work,
-so doubling n squares the time. For decades everyone believed ~2^(n/2)
-was the wall. This paper breaks the wall: it decides Subset Sum in time
-O(2^(0.49n)), i.e. with exponent strictly below 1/2, on every random
-run, worst case over the input.
-
-It is a randomized algorithm: it flips coins, and with probability at
-least 2/3 it answers correctly, for EVERY input. The running-time bound
-holds on EVERY run, even unlucky ones.
-
-The proof has two engines that must be understood separately, then bolted
-together:
+The proof has two engines:
ENGINE A ("isolate"): add tiny random noise to make some target have
exactly ONE solution, so that a "fingerprint" of size 1 can detect it.
@@ -29,13 +21,12 @@ together:
solutions modulo a prime P, then subtract exactly the false positives
(the "aliases") created by taking things mod P.
-Everything else is bookkeeping (finite-precision arithmetic, bounded
-coin-flipping) and a numerical certificate that two specific circle
-integrals are small enough.
+The remainder is finite-precision arithmetic, bounded coin-flipping, and
+a numerical certificate that two specific circle integrals are small.
-Notation used throughout: [n] = {1,...,n}; for weights v_i and a subset I,
-write v(I) = sum_{i in I} v_i; the empty sum is 0. log means base 2
-unless it is ln (natural). "poly" means some fixed polynomial.
+Notation: [n] = {1,...,n}; for weights v_i and a subset I, write
+v(I) = sum_{i in I} v_i; the empty sum is 0. log means base 2 unless it
+is ln (natural). "poly" means some fixed polynomial.
================================================================