06Some Questions Have No Fast Answer — Ship Anyway

01Six questions, and your eye cannot tell which one is a wall

Page 5 ended with a lever that works on every problem it was pointed at, once the order was right. Here is a picture of ten junctions and fifteen roads, which is three roads at a junction on average 2 × 15 / 10 = 3. Get from A to J as cheaply as you can. Now wander from A to J as far as you can, never stepping on the same junction twice. Two questions on one picture, and each of them reads like the other one said backwards. One of the two is settled by your laptop before you look up, and the other has beaten every person who has ever seriously gone at it. That is not a statement about effort.

A second pair, drawn on the same roads, and one word apart. Walk every road exactly once, and come back to the junction you started from. Now visit every junction exactly once, and come back to the junction you started from. Roads in the first, junctions in the second. The third pair is a switch puzzle rather than a map, and it is printed small enough to satisfy by eye: five switches — A, B, C, D, E — and four rules, each naming two of them. At least one of (A off, C on) · at least one of (C off, A off) · at least one of (A on, B on) · at least one of (A on, B off). Switches D and E are named by no rule, so they are yours to set however you like. Satisfy all four rules at once, or show that no setting of the five switches can. Then the same puzzle with every rule naming three switches instead of two.

Notice that nothing in those six sentences is a name you have to look up first, which is the whole reason they were written that way. That matters more than it looks, because a guess made against unfamiliar vocabulary is not a guess at all. It is a coin flip wearing the clothes of judgement, and you would be right to distrust anything built on top of it. Every one of the six is a picture you already hold, so the guess is genuinely yours to make. Pick the harder one in each pair. Commit all three. No score arrives, and nothing is marked right or wrong while you are still guessing.

The picture carries all six questions and refuses to run anything until your three guesses are in. Then two solvers start on the same ten junctions, each with a tick counter you can watch. The left card claims there is a route from A to J costing at most 4. The right card claims there is a route from A to J visiting at least 8 junctions and repeating none. Same shape, same graph, same verb, and the counters part company inside the first second. Your own three answers come back last, after the counters have done the marking. One question in each pair is a wall, and nothing on the picture tells you which one.

02Finding is not checking, and the friend who may be lying

Look again at what your eyes actually did the moment each route appeared on screen. In both panels you confirmed two mechanical facts, and you confirmed them at a glance. First, that this is a legal walk from A to J which steps on no junction twice. Second, that the left route costs 4 and the right route touches 8 junctions. That is the whole of the checking, because both cards were threshold claims and nothing else was ever asked of you. Fifteen roads, one addition apiece, and you were done. The two panels differ in the finding, and in nothing else whatsoever.

Ask anyone what makes a problem hard and they say there are too many possibilities. That answer is a statement about finding, and it is also perfectly true of problems that are easy. A million records can be ordered in more ways than anyone could ever write down, and sorting them still finishes in under a second. School welded the two verbs together, because checking your answer there meant quietly doing the whole exercise again. Here they come apart. Everything that follows rests on the gap between them, so it is worth holding both words separately in your head.

So picture a friend who hands you a candidate answer, and you check it yourself, fast. That, and no machine, is what NP means. The letters stand for nondeterministic polynomial, a name built for a machine model we are not using. Two rules govern her card, and both are load-bearing. She may be lying, which is precisely why you check, because a friend you trusted would be an oracle and NP would swell to hold everything. And the card must be short. The graph on screen is ten junctions and fifteen roads, about forty numbers written out in full; a proposed route is ten numbers. That is the bar. Short in the size of the question as written, never short in the number of possibilities. A card the size of the search you were dodging is not a proof of anything — it is the search.

Now take a problem you can simply solve yourself, and keep the friend in the frame anyway. She hands you a blank card. You check it by ignoring it entirely and running your own fast method, and that check finishes fast. By the letter of the definition your problem is in NP, because nothing in the definition ever said the card had to be useful. So P sits inside NP, and it costs nothing at all to put it there. One thing has been quietly true of every card in this section, though, and it is worth saying out loud. You have only ever asked her for a card when the answer was yes.

03The three cards

So ask her for the other card, and watch what happens on three different graphs. Each graph carries a claim card, and every claim on all three tables is true. Graph A has ten junctions and a round trip that visits each one exactly once. Its card says so, and the object that proves it is the trip itself. Click the route in, junction by junction, and the checker walks it. Ten roads light green as each is confirmed present and ten junctions tick over exactly once — 20 checks in all 10 + 10 — and the verdict lands while you are still watching.

Graph B also has ten junctions, and its card says the opposite: this graph has none. That is true as well, and the reason is small enough to hunt down yourself. Junction J is touched by a single road. A round trip has to arrive at J and it has to leave again, so it needs two roads there, and 1 < 2. One comparison settles it, and the card is a single sentence long. Drop that one-step card into the slot and the checker verifies it. A NO can be an object, and you just made one with your own hands.

Graph C is the Petersen graph. Ten junctions again, every junction wearing exactly three roads, so the road count is (3 × 10) / 2 = 15. Its card reads word for word like graph B's, and it is true too. Now adjudicate the tray yourself, against the two rules you were issued before the tray existed. The degree card refuses. The smallest degree on this graph is 3, and 3 is not below 2, so there is nothing to point at. That refusal is a fact about the graph rather than a ruling against you.

The card reading "I searched everything and found none" refuses as well, because checking that claim means redoing your search. The complete list of round trips to rule out is a genuine proof, and it dies on its own size counter: 181,440 lines (9! / 2) against a question written in 40 numbers, which is 4,536 times the question. Only the fourth item fits — and it is the best thing on the tray. A hand-built argument specific to this graph is accepted, and then it prints its fine print. It took a person, it works for this graph alone, and no recipe makes the next one.

Now set graph B beside graph C, and read the two tables together. Their cards say the same sentence. One of them has a one-step proof lying on the tray, and the other has nothing that fits, so the difference cannot be the claim. It is what there is to hand over, and nothing else. A certificate certifies one value of the answer, never the answer. That is why your solver can return a satisfying assignment in milliseconds and then grind for hours on the same formula's unsatisfiability, and why the proof of NO, when it finally lands, can run to gigabytes against a question you typed in 40 numbers. What graph C lacks is not the possibility of a proof but a general recipe, and whether one exists is unsettled. YES has a recipe, and nobody has ever found one for NO.

04The pairs, re-read

Now take both questions back to the three pairs you guessed on. Start with the routes. For the claim there is a route from A to J costing at most 4, the YES card is the route, and you have already checked one of those. The NO card is page 5 walking back through the door. Write a distance label on every junction, with label(A) = 0 and |label(u) − label(v)| ≤ cost(u,v) holding on every road |3 − 1| = 2 ≤ 2. A route may cross a road either way, so the check has to hold either way, which is why it is a distance and not a one-sided sum. Fifteen roads, fifteen checks, and the whole card is done. Those labels prove that nothing reaches J for less than label(J) = 4, so the twin claim at most 3 is settled NO by the same fifteen checks. Relaxation was a way to make progress on page 5. Here it is an object you hand over.

Now the hard twin, on the same ten junctions. For there is a route visiting at least 8 junctions and repeating none, the YES card is again the route: eight numbers, checked by walking it once. Ask for the NO card and you are standing on the third graph again. There is no label you can write on a junction that means no long route comes through here. Whether a route may use this junction depends on which junctions the rest of it already spent, and a label on a junction cannot know that. The easy twin has an object for both answers, and the hard twin has one only for yes.

The switches split the same way, and this is the pair you can work by hand. A rule that mentions two switches is a pair of arrows in disguise. At least one of (A on, B off) says this: if A is off then B must be off, and if B is on then A must be on. Follow those arrows out of A on through the four printed rules. The first says C must be on, and the second says C must be off. Now follow them out of A off. The third says B must be on, and the fourth says B must be off. Both roads run into a contradiction, so no setting of the five switches satisfies all four rules. Look at what you are now holding. Two short chains, readable by anyone in a few seconds, proving NO. Add a third switch to a rule and the machinery dies at the first step. Knowing one of three is false leaves two possibilities open rather than one, so nothing turns into an arrow.

The third pair splits on a count. Use every road exactly once: count the junctions with an odd number of roads touching them. Zero of them and the round trip exists; any other count and it cannot, since a walk that enters a junction has to leave it again. The graph from the opening — ten junctions, fifteen roads — has ten junctions with an odd number of roads, which is every one of them each junction wears exactly three, so the answer is no, and the count is the proof either way. Use every junction exactly once, and you have just watched what the tray looks like on the Petersen graph when the answer is no. On the opening graph the answer is yes, and the round trip itself is the card. Three pairs, three easy twins, three objects that work on both answers — distance labels, implication chains, a parity count.

One objection arrives within four seconds for anyone who read page 5: just negate the weights and run Bellman-Ford. Negation turns a positive cycle into a negative one, and then shortest has no answer at all, because you can go round that cycle forever. Re-impose the rule that you never revisit a junction, and you are standing back on the hard problem. The real reason sits one level down, and it is about pieces. Shortest routes compose: a piece of a shortest route is itself a shortest route, which is exactly what let page 2's table collapse the tree. Longest non-repeating routes do not compose, because every piece must remember which junctions it already spent.

05Rewriting, where hardness starts, and what the label does not claim

You can now put a problem into NP, and you still own no way to call one hard. So build the only difficulty meter anyone has ever managed, which is a translation between two problems. Take any instance of my problem A, rewrite it as an instance of B, run B's solver, and read the answer off. That composite is a real method for A, and it costs the rewriting plus B's cost. So if B is easy, A is easy. Now say the contrapositive out loud, because it is the whole content of the idea: if A is hard, then B is hard. Hardness travels along the arrow and easiness travels against it, both on the same arrow.

Two imperative rules fall straight out of that, and you will need both within a month. To prove my problem hard, reduce a known-hard problem into mine. To borrow somebody's fast algorithm, reduce mine into theirs. The common wreck is the first rule run backwards. You want your scheduling problem declared hard, so you reduce it to 3-SAT, the famous one. What you have proved is that your problem is no harder than 3-SAT, which is the opposite of the claim you set out to make. The learner's private model is connect my problem to the hard one, and that phrase has no direction in it at all.

Watch the translation get built, on the two graphs you met a few paragraphs ago. A tour must be able to go from anywhere to anywhere. So every pair of junctions carries a price, and ten junctions make C(10,2) = 45 pairs 10 × 9 / 2. Fifteen of those pairs are the real roads, and they are priced at 1. The other 45 − 15 = 30 are missing pairs, priced at 21. That price is 2 × 10 + 1, and it comes back later carrying real weight. Now ask a question of a completely different problem: is there a tour costing at most 10? On graph A the round trip exists, so ten real roads at 1 each cost exactly 10. On the Petersen graph no round trip exists. Every tour is forced through at least one missing pair, so the cheapest costs 21 + 9 × 1 = 30. Same answer, new question, and the rewriting itself is 45 prices written out from a 40-number input.

The hopper drops those 45 pairs in one at a time, so you can watch the new instance assemble and read its answer back onto the old one. Then it hands you a direction toggle, and the interesting state is the broken one. Reverse the arrow and the pipe cracks, because there is genuinely nothing to carry. Along the arrow you can add up the rewriting plus B's cost and hold a method in your hand. Against it there is no sum to write down. That is worth doing with your fingers once, because the mistake is spatial, and spatial mistakes hide comfortably inside a sentence.

A problem is complete for NP when it is in NP, and every problem in NP rewrites into it. Nothing inside NP sits above one of those. But every reduction compares two problems, so a chain of comparisons never bottoms out. You are owed an answer to a fair question. Where did the first hardness ever come from? A problem is in NP because a fixed, finite checking procedure exists, and a checking procedure is a machine of ANDs, ORs and NOTs. So write the checker down as a formula, and ask whether any input makes that formula say yes. That single question is now every question in NP at once.

That is the one theorem on this page we assert rather than build, and accepting it is safe, because you grant the step the moment you hear it. It is also how one problem comes to sit underneath everything, and every hardness proof since is a chain from that one. And it disposes of the quiet disbelief that a logic formula and a graph question could ever be the same object, by explaining why they are rather than showing that one is.

So hardness concentrates: everything rewrites into the complete ones, and one fast method for any single one of them collapses the whole class. Now two sharpenings, and the page is dishonest without either. None of this is proved. Nobody has shown that any of these problems needs exponential time. What has been shown is that they stand or fall together, and thousands of clever people have failed on all of them at once, from thousands of directions. That pooled failure is a far stronger engineering signal than any single failure, and it is the honest reason to act on the label. The second sharpening is narrower and it costs you more. NP-complete is a claim about the worst instance. It says nobody has a method that is fast on every input. It says nothing whatever about the instance sitting on your desk.

06The threshold, and the ruler nobody told you about

The theory answers yes-or-no questions, and the problems on your desk ask for the cheapest anything. Bolt a threshold on and the mismatch disappears. Instead of asking for the cheapest tour on those ten junctions, ask whether there is a tour costing at most 20. That is a claim your friend can hand across the table on a card. You have already checked two claims of exactly that shape, back when the two solvers raced. And the threshold gives the real number back whenever you want it, because binary search walks the answer down one yes-or-no question at a time. Twenty such questions pin any cost under a million (2²⁰ = 1,048,576). One number, twenty checkable claims, and the theory now covers the problem you actually have.

So put the knapsack into the theory, using nothing but the instruments already sitting on the bench. Your friend hands you the set of items she claims she packed, you add up the weights, and you add up the values. That is checkable in a few dozen additions, so the problem is in NP, and it is also one of the complete ones — borrowed from the chain, not proved here. Name the variant out loud: items go in whole or not at all. That is the table page 2 built for you, and not the fractional cousin that greedy settled in one pass. Your table has one row per item and one column per capacity, so filling it costs n·W steps. With 20 items and a capacity of 1,024 that is 20 × 1,024 = 20,480 cells, filled in well under a millisecond. Both of those letters look like ordinary inputs. It looks polynomial. And you have just been told that one fast method for a complete problem collapses the entire class. Did you break the world over lunch?

Before the floor drops, ask why the ruler you have been using all year never once bothered you. Sort n numbers: the input is those n numbers. The count of things and the length of what you typed agree to within a constant, so nobody ever needed to tell you which of the two the word polynomial was measuring. Knapsack's input is n items plus one capacity W. And W's magnitude is not W's length. One of those is what you typed, and the other is what your table quietly charges you for.

Now measure it, because the repair here is arithmetic and not a new word. Writing W down takes about lg W bits, while the table you fill has W cells. Four capacities, in two columns that are supposed to be the same ruler.

cells = 2^bits

The bottom row is the same n·W you priced a minute ago. With 20 items it now reads 20 × 1,073,741,824 = 21,474,836,480 cells, against 30 characters typed. That is an exponent in the length of the input, and an exponent is not a bad ratio you can out-engineer. Pseudo-polynomial is only the name we give the gap you just watched open.

So polynomial means polynomial in the characters you typed, and never in the quantity those characters denote. The two rulers part company at exactly one place, and it is worth learning to smell: the first time a magnitude is fed in rather than a count. Nothing collapsed, and your DP is still the right thing to run whenever the capacities in front of you are small. That is not a contradiction, and it is not a defeat. Ask one question of any fast-looking method: is its table indexed by a count, or by a value?

07The morning after — four exits

The label's real gift is that it tells you exactly where to stop digging. You are not going to find the fast exact method, and neither is the specialist you were about to hire. A chess engine has never solved chess and has never tried. It plays well inside its clock, and that is not a compromise on the product, that is the product. Your registrar wants a timetable on Friday, not the best timetable in principle. So the verdict is not a wall. It is a door with four exits, and three of them hand you a number before you write any code.

Exit one: n is small enough. Count the candidates before you write anything, which was page 1's move. Twenty items each go in or stay out, so the entire search is 2²⁰ = 1,048,576 subsets. That is about forty milliseconds, and the answer it returns is exact. Exit two: the instance you actually have is a special case. Your graph is a tree. Your rules mention two switches and never three. Your numbers are small — which is the knapsack DP you were examining a minute ago, so you have been standing in this exit the whole time without noticing.

Exit four makes no promise at all: hand the instance to a real solver and see. It is exit two's automated cousin, and you take it by betting there is structure without having to say which structure. Industrial SAT and ILP solvers swallow instances carrying millions of variables, because instances from the world carry regularity the worst case does not. That exit is legal for one reason, and it is the sharpening you were handed just before the knapsack went into the theory. The label is a claim about the worst instance, not about yours. Its defect belongs in the same breath: it guarantees nothing, so you can tell the registrar nothing until it returns, and it may never return. That leaves exit three, held back until now because it is the one that costs you something.

Exit three: accept an answer that is not the best one. It is the exit most people reach for first, and it is the one with a hole in it. That is the trade the fraction was built for. The denominator is the quality you can afford in the time you have, and the universe has capped it, so the numerator is the half that moves. You accept a bounded worse answer, and you know the bound before you ship. Both halves of that sentence are load-bearing, and only the first half is easy. Near-optimal is worthless until you can say how near.

08The floor you build yourself

A museum has corridors and junctions, and every corridor needs a guard at one of its ends. Post guards at junctions until that is true, use as few of them as you can, and you are holding the problem everybody calls cover. Exit three's number is at last on the table: within twice the best. Your gut should refuse that sentence on the spot. The best is precisely the quantity nobody can compute, and every ratio you have ever met divided two numbers you already had. You did not miss a step on the way in. The ratio is proved, and it is never computed.

The method is one motion, and that motion quietly does two separate jobs. Find a corridor with no guard at either end, and post guards at both of its ends. Two guards go on the board, and that half is the algorithm. One padlock also snaps shut, and that half is the floor. You keep going until no corridor is left unguarded, which is the only reason the thing you hand back is a legal cover at all. A ratio measured against an illegal answer would be worth nothing.

Twelve junctions and seventeen corridors are waiting with no guards anywhere on them, and the padlocks are yours to lock. Click a corridor that already has a guard at one end and the museum refuses you, in your own terms: that one costs you nothing new and proves you nothing new. That refusal is the mechanism, not a courtesy. Without it you could build a false proof with your own hands, inside the one figure whose entire purpose is that the proof is yours.

Say your run finishes with p = 4 padlocks, so the guards you placed number 2 x 4 = 8. Now read the padlocks. Those 4 corridors share no junction, because a corridor touching an earlier pick would already have been guarded, and you could never have picked it. Any legal cover therefore spends a guard on each of the 4, at 4 different junctions, so the optimum is at least 4. Your 8 is at most twice a number nobody computed. Only afterwards does the museum sweep all (2^12 =) 4,096 subsets of junctions and print the true minimum, which is 6. The bars read 4 < 6 < 8, exactly where your own padlocks said the optimum had to land. Your realised ratio was 8 / 6 = 1.33, and the ratio you proved was 2.

So where do floors come from? Two generators, and both of them deserve a name. The first is disjoint obligations: separate places that any solution has to pay for separately, which is exactly the padlock set you just built by hand. The second is relaxation, last seen handing over distance labels and now manufacturing floors. Delete the constraint you cannot afford, and the easier problem's best answer cannot come out worse. Delete one edge from the optimal tour and what remains is a spanning tree. The MST is by definition the lightest spanning tree, so MST is no heavier than that tree, which is no heavier than the optimal tour. And the shape from the three cards survives both generators: a floor proves at least, and nothing will ever make it prove at most. Nothing forced you to find the biggest disjoint pick either, so a loose floor is still a floor. It weakens your promise and it never makes your promise wrong.

Sometimes one floor is thin, and the repair is a second floor of a different kind. Seven jobs, three machines. The longest single job runs 9 hours, so nobody finishes before 9. The total work is 30 hours split across 3 machines, and 30 / 3 = 10, so nobody finishes before 10. The floor is max(9, 10) = 10, and you took the better of two kinds rather than the sum. Hand each job to whichever machine frees up first, and you finish no later than the two floors added: 9 + 10 = 19 hours. A floor is not an answer, and turning one into an answer has a price.

09Where the guarantee actually rests

Walk the spanning tree, cross every edge exactly twice, and the meter reads exactly twice the tree. On six cities the tree holds five edges weighing 4 + 5 + 3 + 6 + 5 = 23, so the retrace parks the meter at 46. The retrace makes ten visits across six cities, so four of them are repeats 10 − 6 = 4. Now delete those four repeat visits, one at a time. The four deletions save 5, 4, 4 and 2, and the tour settles at 46 − 15 = 31. Brute force over (6 − 1)! / 2 = 60 tours puts the true optimum at 30, so the realised ratio is 31 / 30 = 1.03 against a bound of 2. The answer came in well under its own promise, which is pleasant and is not the lesson.

The lesson is not a quantity at all. It is a direction: the meter ticks down on every skip and never up. Watch the saving of 5, because that one skip is the whole guarantee in miniature. It drops the detour u → v → w, priced 6 + 5 = 11, and buys the direct hop u → w for 6. The saving is 11 − 6 = 5, and it comes out positive only because going direct is never worse than going round. That sentence is the triangle inequality, and the entire 2× is standing on it. Nothing in the setup marks it as load-bearing. So Fig. 5 gives you the meter, the three staged states, and then a toggle labelled BREAK THE TRIANGLE INEQUALITY.

Raise the direct hop u → w from 6 to 30, and press the same skip again. The saving is now 11 − 30 = −19, which is a saving that costs you money. So the meter climbs by 19, and the tour lands at 46 + 19 − 4 − 4 − 2 = 55. That is above 46, the ceiling you watched being built, breached by 9. Every link ran through that ceiling: the tour was under 2 × MST = 46, and 46 was under 2 × 28, the optimum doubled. Snap the first link and the second one is holding nothing at all. The guarantee did not soften. It died, and it died at the one step you were never told to guard. Airline fares break this rule every day, where a connection through a hub is routinely cheaper than flying direct. Carry the 2× into that setting and you are quoting a number nothing behind you supports.

There is a second assumption underneath, and it stays invisible because the first one covers for it. Deleting a repeat visit needs the direct hop to exist. Take one pair of cities off the map and the skip button refuses to press, and the reason it prints is not that this skip is expensive but that it is impossible. The argument never gets as far as needing the triangle inequality. So a tour wants a complete graph, where every pair carries a price, and where two cities with no road between them are priced at what the detour costs. Two assumptions, one guarantee, and each of them is holding up exactly one step. You will not read “assume X” again without asking which single step X is holding up.

10Manufacturing a gap, and reading the dial's fine print

You broke one guarantee with your own hands, so ask whether any weaker one survives. There is a claim on the other side that sounds unprovable: no constant-factor approximation for the cheapest tour exists at all. That sounds like a statement about infinitely many methods, and nobody can inspect infinitely many methods. So we inspect none of them. We take the instance you already built, and we let the promise convict itself. Ten junctions, every real road priced at 1, every missing pair priced at 21.

Two numbers do the whole job, and each one comes from a different instrument. Start with the guarantee. Graph A does have a round trip through all ten junctions, so its cheapest tour costs exactly 10. A method promising twice optimal must therefore hand back something costing at most 20 there. Now switch instruments and use the instance, with the guarantee touched nowhere. The Petersen graph has no such round trip, so every tour it admits is forced across at least one missing pair. Nine real roads plus one missing pair (9 + 21 = 30) is the cheapest that can possibly be. Whatever the method does on that graph, its output is at least 30.

Now read the two bands together. Anything at most 20 came from graph A, and anything at least 30 came from Petersen, and 20 < 30 leaves no overlap for the reading to fall into. So you run the approximation, glance at its meter, and you have decided the round-trip question. That is not yet a contradiction, and saying so is the point rather than a caveat. It becomes one only if no fast decider for the round trip exists, which you were already warned is a belief and not a theorem. The construction also widens on demand: price the missing pairs at ρ·n + 1, which for ρ = 2 and n = 10 is the 21 you have been using. The yes case still costs n and the no case exceeds ρ·n, so the two bands never touch for any ρ you choose.

Sometimes no constant is available at all. When one is, the next question is the exchange rate, and the clearest place to ask it is the algorithm you watched blow up. Your knapsack table blew up because it is indexed by a value, so index it the other way round. For each achievable total value, keep only the least weight that reaches it. That list of achievable values is now the thing that grows, and here is the move. If you only need the answer to within ten percent, you do not need every distinct value, only one representative per band. Keep one entry per (1 + δ) band and the list stops doubling. Relative accuracy needs only relative resolution.

Then comes the fine print, which is the actual lesson. You spend that (1 + δ) factor once per item, so split the error budget by how many times you will spend it. Trim at δ = ε/2n. With ε = 0.1 and n = 50 items that is δ = 0.001, a tenth of a percent per item, and fifty rounds multiply your answer by 1.001⁵⁰ = 1.051 — inside the 1.1 you promised. The band you trim by is a hundred times finer than the promise it buys. Now look at what the dial itself costs here: the work grows like 1/ε, so halving ε doubles it. Page 4's sampling estimate needed about 1/ε² samples, where halving ε quadruples the work instead. Same dial, same label, two different prices — which is why you look before you turn one.

11The honest coda — two tiers of hardness

Every guarantee on this page has rested on a proof that runs one way only, and the hardness your bank account rests on has less behind it than anything else here. The complete ones are all tied together by the friend's card, so a break anywhere is a break everywhere. Nobody has proved that any single one of them needs exponential time. What stands behind them is everyone's failure, pooled: thousands of clever people, coming from thousands of directions, all stuck on the same wall at once. That is a far stronger signal than any one person's failure, and it is why you are entitled to act on the label. Factoring, the problem your bank actually runs on, has no such company.

So ask factoring the two questions, on a number small enough to check by hand. Is 8,051 composite? YES: someone hands you 83, you multiply it by 97, the product is 8,051, and the whole check is one multiplication. And the card for the other answer, the one the Petersen graph refused to give up, exists here too. Ask whether 8,053 is composite, and the answer is no, because it is prime. A short primality certificate can be handed over for that, and checking one is arithmetic anyone can do. Both answers have a recipe, and neither recipe runs out on hard instances. Factoring is two-sided.

Now hold that beside the three cards you filled in by hand. The complete problems are believed to have one side only, and the missing side is the whole reason this page exists. Factoring has both. You can therefore predict, without being told, that factoring is probably not one of the complete ones. That is what almost everyone in the field believes, and you just derived it from an instrument you built ten minutes ago.

The consequences are not decoration. Proving P ≠ NP would not make your bank safe, because factoring could still fall to a clever method the next morning. Breaking RSA would not collapse NP either, because the break need not travel to anything else. The hardness your money rests on is a smaller and lonelier conjecture than the famous one — its only evidence is that this single door has held. Saying which direction your proof runs is the same discipline as writing the bound beside the answer.

12The course's last move

Your university has 180 exams, and two of them cannot share a day if one student sits both. Each exam collides with about 26 others, so the schedule carries 2,340 colliding pairs 180 × 26 / 2. Fit them into as few days as you can. Nobody wrote a page about this problem, and page 1's reflex fires anyway: count the candidates first. Packing 180 exams into 9 days gives 9¹⁸⁰ timetables, a number 172 digits long 180 × 0.954243 = 171.76. Four boxes sit in the figure below, and nothing is revealed until all four are shut. Your colleague says the exams fit in 8 days: what does she hand you, and how long do you take to check it? Then she says 8 days is impossible: what does she hand you now? Whatever you write in that second box, I must be able to verify it in a few thousand comparisons, without redoing your search. Name both halves of the fraction, then say which half you could buy and what buying it would get you. Last, pick an exit, build the floor by hand on a twelve-exam slice, and say what you promise the registrar. Commit all four. Everything after this paragraph is an answer.

She hands you one day number per exam, 180 of them, against an input of 180 exams and 2,340 conflicts. Same order of size, so the card is short. Checking it means walking every colliding pair and confirming the two days differ. That is 2,340 comparisons, instant, and the problem is in NP before anyone names it. Now the other card, and the asymmetry you met on three graphs arrives on material nobody prepared you for. Sometimes an object does come across the desk. Nine exams that all collide with each other need nine separate days, and 9 is more than 8. Checking that group costs 36 comparisons 9 × 8 / 2, with no solver anywhere in the room. Sometimes the largest such group holds only seven exams. Then 21 comparisons 7 × 6 / 2 buy you a floor of 7 days, and seven is under eight, so that group says nothing whatever about 8. Same problem, same instrument, same reader — and which card you get was never something you chose.

Now the fraction, named before you spend a day of anyone's time. The numerator is the quality you demand, meaning the true minimum number of days. The denominator is the quality you can afford, meaning the fewest days any method you can actually run before Friday will find. Friday is a deadline, not a quality. You can buy the denominator, and it is worth pricing that purchase exactly once. A hundred times the machines divides a 9¹⁸⁰ sweep by 100, which strikes off two digits and leaves a 170-digit search. A constant cannot catch an exponent, so the half that moves is the numerator. The obvious method is to take the exams one at a time and give each one the first day nothing on it conflicts with. That is page 5's lever verbatim, where the order is the reason the timetable comes out legal. Take the fourth exit instead and hand the instance to a real solver. It returns a legal 9-day timetable in seconds, checkable by the same 2,340 comparisons you already own. Ask it to prove 8 impossible. Sometimes it answers within a second, and sometimes it never comes back at all. The timetable on your screen looks identical either way.

So build the floor yourself, by hand, on a slice of twelve exams holding 66 possible pairs 12 × 11 / 2. The padlock refuses any exam that fails to collide with every exam already picked, and it prints the reason in your own terms: exam 7 can share a day with exam 3, so it locks no extra day. The largest mutually colliding group in that slice holds five exams, confirmed in 10 comparisons 5 × 4 / 2. Those five need five separate days — and any timetable for all 180 exams is also a timetable for those twelve, so five days is a floor on the whole thing, not just on your slice. Widen the hunt past the slice and the best group you find by hand holds seven, which lifts the floor to 7. Finding the largest group is itself hard, and it does not matter here. A floor only has to be true, never best, so a weaker group is a weaker promise rather than a wrong one. Your floor says 7, the solver's timetable says 9, so 7 ≤ best ≤ 9. Both of those numbers are objects you can put in somebody's hand. Ship the timetable, hand over the floor beside it, and say which one you proved.