Exercise 3: Why 1,000 and 2^10 Aren't the Same Kind of Problem — Possible Solution ==================================================================== WHY THE RAW NUMBERS LOOK SIMILAR ------------------------------ This chapter's own figures show 1,000 possibilities (a 3-digit PIN) and 2^10 = 1,024 possibilities (all subsets of a 10-item set) are genuinely close in magnitude - at that fixed size, checking either one exhaustively would take roughly the same, small amount of time, which this chapter's own measured rate would put at well under a millisecond for either. THE ACTUAL DIFFERENCE: HOW EACH SPACE RESPONDS TO GROWTH ------------------------------ The PIN search space is determined by a FIXED number of digits (3), and growing the search space means adding more digits, which multiplies the space by 10 per extra digit - a fixed, one-time choice, not something that grows automatically as some other quantity (like a list of items) grows. The subset-search space, by contrast, is DEFINED IN TERMS OF the input size n itself (2^n) - every single additional item added to the input set automatically DOUBLES the entire remaining search space, with no separate decision required. WHY THIS MAKES ONE PROBLEM SCALE SAFELY AND THE OTHER NOT ------------------------------ A PIN search's space only grows if someone deliberately chooses to add more digits - the underlying problem (checking a code against a target) doesn't force the space to grow on its own. This chapter's own verified numbers show that even after tripling the digit count from 3 to 6, the time only grew by the corresponding factor of 1,000, still well under a second. The subset-sum problem has no such freedom - the search space is mathematically tied to n, so simply having a somewhat larger real-world input (this chapter's own example used just 40 items) forces the search space through the exact same explosive doubling this chapter measured, growing to over a trillion candidates and, extrapolated from the chapter's own measured rate, nearly five days of exhaustive search. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation identifies the specific structural difference (a search space chosen independently of the input size, versus one mathematically defined by and forced to grow with the input size) rather than treating the similar raw numbers as evidence the two problems behave similarly, and connects the conclusion directly to this chapter's own verified linear-vs-exponential growth figures.