The probability of being born a male is 0.466. The probability of being born in North America is 0.153846. The probability of being born in an urban location is 0.3571428. Find the exact probability that a baby will be born a male, in North America, in an urban location.
They obviously expect you to multiply those numbers (seven digit numbers with the quadratic algorithm -- poor kids), but the joint probability equals the product if and only if the random variables are independent, which in this case they are not.
Problem B (mentioned in the article) is probably not as bad as it looks: you can eyeball that the target sum is approximately half of the total, and you can probably match the final digit.
These things are marked by humans, and appealable (in the case of exams, if it's just homework who cares) - IME in the UK, if you write something like 'insufficient information in the question, given RVs are not independent' then you are not going to be marked down for it; if they find the question incorrect it'll likely be struck off entirely.
But more likely, everyone answers either wrong (not because they know better) or right, because they don't know to do anything but multiply them; at the stage this is a question they don't know there are dependent and independent RVs.
It's like if you draw something that looks near enough a square and show it to someone in primary school, asking for the angle in the corners. The correct answer is 90 degrees, it doesn't matter that it's not exactly drawn, that we didn't define a coordinate system or the units we wanted.
I'm glad these unwritten rules are all clearly expressed so that all 3rd graders understand them.
Because if you didn't realize all the things you were allowed to assume at the level of math you are doing, it might be really stressful to be given problem for homework tat's unsolvable in general, but solvable if you make the correct set of assumptions, and think you are expected to produce a solution for it.
Especially that part about 'if it's homework, who cares'. I'm sure kids are very clear on that one.
I don't doubt that what you say is true, but it strikes me as odd that they didn't sidestep the problem by picking an example where the variables are obviously uncorrelated.
It comes off as extremely sloppy: nobody expects kids in primary school to even understand what it means for variables to be independent, but certainly those writing the questions should know better!
Just because they don't know better, or it's a mistake. I'm not suggesting they knowingly thought 'but that doesn't matter here we want a specific technically wrong answer'.
That's not NP complete. There are two major differences:
1) it fits exactly.
2) you are told there is an answer
NP complete defines a generalization of a problem. Just because a general problem is hard doesn't mean every set of numbers is the same difficulty.
The problem of course is they are overthinking it using an adult brain. Just think stupid: add toys until you go over, then remove some. Start from largest to smallest. Etc.
By that logic no instance of an NP complete problem is NP complete because you can solve any NP complete problem in finite time, seeing as it's not undecidable.
It just might take longer than the universe will exist for you to get a solution.
If we are being technical (and I must assume that we are given that you are making a technical critique), then everything you are claiming is wrong.
1. The phrase “an NP Hard problem” refers to the computational complexity of a problem as the “scale” of the problem goes to infinity. Typically, an author would detail the problem, and what parameters go to infinity, but in this case the general problem “The subset sum problem (SSP)” is well known so explaining details is not necessary.
2. The homework question has two parts. The second part asks “(assume a solution exists) is the solution unique?” Clearly this decision problem reduces to SSP and is NP Hard
An NP complete problem is not any generalization but a problem where all solutions can be solved using brute force in polynomial time, also representing other problems in the same space. In actuality, an NP complete problem is defined as easy to find a single solution, not that it is difficult to find a solution.
No. If you want an intuitive but also theoretically correct definition of NP, it is the set of problems where it is easy to verify that a given solution is correct. NP - P then is the set of all problems for which it is easy to verify that a solution is correct, but hard to find any solution (this set may be empty, but we haven't proved either way).
Here 'easy' means 'in polynomial time', and the property of all NP problems is that they are solvable in polynomial time given an oracle which generates the solutions, and then verifying that each solution is correct. Equivalently, they are solvable in polynomial time given an infinite number of execution threads that each takes one candidate solution and verifies whether it is correct or not (in polynomial time).
I don't think there is any known class of problems in complexity theory where it is easy to find 1 solution but hard to find all solutions.
The thing is that it being an instance of an NP complete class of problems means that there isn't a guarantee that there is an easy way to find a solution. Meaning, you might have to check every combination - and even if you know there's a valid solution, there's no specific heuristic you can apply in searching the solution space that guarantees that it won't be the very last combination you try.
In particular, notice that the question asks 'is your solution the only one?'
Is there any way, in general, to know you've found all possible valid solutions to this problem without enumerating every single one?
You can prune entire sets of the combination space without needing to enumerate through all of them. One of the simplest such optimizations would be to set that if set S costs more than the target, then no superset of S is a valid solution.
Sure, but that doesn't change the fact that there is no polynomial time algorithm for solving this problem. Your observation makes the problem possible to solve using backtracking (as otherwise there would be an infinity of combinations to check, since we can take multiples of a toy), but does not guarantee it can be solved in a reasonable time.
The problem of finding all the subsets whose value exceeds the limit isn’t necessarily any easier than finding all the subsets whose value equals the limit, is it?
To be clear I think it’s neat that this guy is involved with their child’s schooling. I for one enjoyed it when my dad got involved—I usually learned way more from working with my dad than I did from the problem itself.
>The reason was that the books were so lousy. They were false. They were hurried. They would try to be rigorous, but they would use examples (like automobiles in the street for "sets") which were almost OK, but in which there were always some subtleties. The definitions weren't accurate. Everything was a little bit ambiguous – they weren't smart enough to understand what was meant by "rigor." They were faking it. They were teaching something they didn't understand, and which was, in fact, useless, at that time, for the child.
>[...] That's the way everything was: Everything was written by somebody who didn't know what the hell he was talking about, so it was a little bit wrong, always! And how we are going to teach well by using books written by people who don't quite understand what they're talking about, I cannot understand. I don't know why, but the books are lousy; UNIVERSALLY LOUSY!
There are many many wonderful math books, and many many wonderful math resources on youtube. (As well as, of course, many many terrible ones!) I second AOPS! They have a fantastic series for younger kids called "Beast Academy" (https://beastacademy.com), and their challenge problem sets are fantastic! The same blog has a couple of other posts about them: https://leosstemhacks.wordpress.com/2019/11/06/the-three-bes...
One memorable example of this was a book which said you could tell the temperature of a star by the wavelength of the light it emitted. It then asked you to calculate the temperature of stars in a depicted galaxy. I'm sure there are some subtleties that are not exactly perfect but good enough for a school textbook.
The part that made Feynman erupt in anger was the follow up question, "what is the total temperature of the galaxy".
The problem is incredibly ill defined. Do they want the sum of the temperatures calculated above? (Nonsensical) The temperature that the galaxy would have if you mixed everything together? (Insufficient information on star size and material composition) The average of the stars temperatures? (ALSO nonsensical!)
I haven't seen the source. But I am guessing the anger is temperature is a number that doesn't make since to blindly add. Example: 2 boiling pots are not 200 degrees C. Or more technically temperature is the mean molecular kinetic energy, an average not a total.
Both the overall mean and mean-of-means have sensible interpretations though.
Suppose you observe a random sample of stars and find their temperatures to be 6000, 6250, 6750, and 7000C. The best possible guess[0] for the temperature of a new star drawn from that population is 6500C. The average temperature of all the starstuff may be different if one star is larger than another, but that's an answer to a slightly different question.
In fact, I would argue that the mean-of-means is often a more appropriate summary statistic than the overall mean of the observations when there are repeated measurements.
It's an easy mistake to make, to have incorrect pedagogy around the concept of temperature, and Feynman was fanatical about correct pedagogy. This is always good: https://youtu.be/Q1lL-hXO27Q
… okay, I fail at presenting why this is interesting. Let me try again.
Ha, I tricked you. The thing I want to talk about is CHOOSE and FAIL.
There’s a certain kind of program that can solve this problem in remarkably little code: non-deterministic.
Imagine you had a JavaScript statement called fail;
if (foo) { fail; }
The program continuously restarts, trying all possible combinations such that fail never executes.
It’s like pretending the code (or incidentally, the start of my comment) has supernatural powers. It can “look into the future” and set up all the variables such that it just so happens never to fail;.
Therefore, you could solve the problem like this:
for each possibility {
if possibility doesn’t spend all the tokens {
fail
}
print(possibility)
}
The program will execute and perfectly print out every solution. And that’s all the code you need.
So with that intro, I encourage you to scroll back up and read the comment chain I linked, if you’re thirsty for details.
Now I sleep. Goodnight :) fail. Just kidding, I’m awake still.
EDIT: Bah, I really did a terrible job with this. Sorry. You’re probably wondering “why not just use continue instead of fail?” and “what about CHOOSE?”
Those are reasonable questions. The magic here is that the logic can be arbitrarily complicated. You can say “if x + y != 10, then fail; print(x,y)” and it will only print pairs like 1 and 9, 2 and 8, etc. But you’re probably still wondering “why not just loop x from 1 to 10, y from 1 to 10, and skip any x+y != 10? That’s like a Python one-liner.”
… I think this is a case where I should have thought a bit more carefully before commenting, so I’ll leave this as an actual fail. But, all I can say is, non-determinism really is delightfully fascinating, and I hope I sparked one person’s curiosity about it…
There are libraries based on this very concept. Instead of programming the solution, you program the "rules". And the library essentially a brute force (with branch trimming) until it finds a solution for you.
Somehow I doubt "Leo" actually understands anything about NP-completeness or the Lisp program written in the article. When I was in third grade I was learning times tables.
Anyway, the "trick" for me was to just group the toys together into small sets that make easily workable values. For example, I tried to find a small grouping of toys that ends in 94 cents. Boat + Racecar + Checkers = $19.94
After that I tried to find small groups of toys that added to whole numbers. For example, Bear ($4.89) + Xylophone ($7.11) = $12. Once you have a few of those, it's easy to find solutions:
So then 2x (Bear + Xylophone) + Boat + Racecar + Checkers = $12 + 12 + $19.94 = $43.94
Of course, knowing whether you've found all solutions is, as the article notes, an entirely different beast.
> Somehow I doubt "Leo" actually understands anything about NP-completeness
The parent is a Stanford professor that studies scientific reasoning. I would assume he is a good judge of what his kid understands. This article was 4 years into a series about teaching his child STEM concepts.
Also, I'm going to go ahead and say it. I don't buy it. The third grader with three different sets of handwriting who needs to write down carries in order to compute 2.16 + 0.87 and who 30 days earlier was still learning basic algebra suddenly has his own programming language in which he's doing implicit typecasting into bit vectors to enumerate a set of 2^n solutions?
You’re right, the handwriting depicting the “SnuffyCode” program is far neater than the handwriting enumerating basic arithmetic on the worksheet. Looks like Leo’s dad wrote the “SnuffyCode.” I guess Leo could have been dictating to his dad, but why not just write it himself? If he’s capable of coming up with his own programming language as a third grader, he’s definitely capable of writing ~10 lines of code in it himself. The handwriting on the worksheet is actually really neat for a third grader!
I can clear this up, at least a bit, since I was there. (Although I can’t say that I clearly remember every detail.) All the writing on the problem page is definitely Leo’s, and, yes, he wrote the misspelled “NP Complete”, and did (does) know what it means, at least in the sense of a problem that has an easy to check solution, but for which you have to try every possible combination to find them. As for Snuffycode, the writing is obviously mine, and the language is obviously nonsense. (I guess he wrote out the template.) I think that what was happening is that we were talking through an algorithm using a binary selection mechanism (APL-Like, as mentioned). As with the Lisp, I was “typing” but we were talking it through collaboratively. At least that’s my recollection.
It is hard, but only if you try to find the general solution. If instead you think in the way the problem designer (who had a target audience of 3rd graders in mind) intended the solution to be found, then it becomes easy to find a solution: one of each toy from the yo-yo to the car (inclusive). That gets you $5.18 from the goal of $43.94, so get another car (the problem doesn't state you can't have repeats).
Unfortunately that’s exactly the issue here. That justification puts more focus on training a (simplified and flawed) process rather than understanding the fundamental nature of the problem being presented.
I would argue that arithmetic is overvalued in early mathematics education. Category theory, as an example, has many more practical applications and leads into arithmetic. In my experience, early education in mathematics skips many of the prerequisites and you end up learning these things through rote-learning instead of building that knowledge from the fundamentals.
> Category theory, as an example, has many more practical applications and leads into arithmetic.
Now this is a sentence I never expected to read.
I aheb thought before about the fact that derivatives are a much simpler and more useful concept than exponentials and logarithms, but I very much fail to see how category theory is useful for anything other than researching the foundations of math.
Yes, which is most bizarre, since school-level arithmetic is the first kind of mathematics ever invented, far before writing, specifically for its practical uses.
Are you really claiming that it's of more practical use to understand the properties of monoids and rings than it is to understand that 2 + 2 = 4? Or are you actually talking about arithmetic beyond what is normally taught in school?
Arithmetic is just decategorified set theory. The main advantage of teaching arithmetic via set theory is that it allows for building intuitions about counting.
It shouldn't be surprising that two sheep plus two sheep is four sheep. We can go further. Suppose that we have lots of longhair sheep and shorthair sheep. If we choose some sheep, how many ways can we have some shorthair and some longhair? This gives exponentiation intuitively, so that we could ask how many ways we could choose zero sheep from a collection of zero sheep, or in other words, why zero to the zeroth power is one.
The parts of category theory that you're imagining, with the morphisms and natural transformations, doesn't have to be taught before arithmetic. It can be taught when lambdas are first introduced, when we write "f(x)" on the board for the first time.
But none of this modern theoretical understanding helps me see what is 131 + 121, or 2^10. Expressing arithmetic operations as set operations and counting elements is only useful for really small numbers - if you actually want to know the answer, you ignore the set-based or category based foundations and use an algorithm.
This is the major problem I have always had with examples of category theory use: they always sound nice and give very illuminating intuitions for certain mathematical structures, which is very useful for doing mathematics and furthering your understanding. But they never directly answer any practical questions - for those, you always abandon the abstractions and start getting into the nitty gritty of the specific domain. At best, they help you take a specific algorithm from domain 1 and apply it in domain 2.
Am I wrong? Is there some way to actually get the answer to how many ways you can combine longhair and shorthair sheep in sets of 10 sheep, other than simply counting all combinations, or using traditional arithmetic/geometry etc. (e.g. repeated multiplication, angle measurements)?
I think that you're overreacting a little to an imagined strawman. We already teach kids a decategorified set theory in order to give them an understanding of counting. We don't take the next step into category theory, which is to explain mappings between sets: If I can trade one sheep for two goats, and I have five sheep which I all trade for goats, how many goats do I get?
Remember: Sets are 0-categories, so set theory is 0-category theory.
It shows that tipping is not consistent with mathematics and pizza people should be formally compensated as to achieve this consistency. Perfectly congruent.
If you keep reading it asks if your solution was the only possible solution. This implies that you only have to give one solution and prove that there are no other solutions (very difficult) or find two solutions to show that there could be many more than just one.
When the son said that some people in the class got the problem exactly right, I doubt they spit out all 279 combinations.
Then it's a matter of luck whether you tried that pattern. I started with the highest prices items and didn't get far. It's mostly a lottery if it depends on people guessing that way.
I would start several approaches like writing a formula, bounding the number of toys (6 to 50?), looking for easy multiples, etc. the declare them all too hard and quit.
The easiest solution: Sort from largest to smallest. Then just do a DFS. Or, if you're so inclined, pay attention to the 1s digit. You know the digit has to add to exactly 4, because there is an exact fit. The search space is not 20^20, it's not even close.
One approach is to get close to the desired sum by buying a few of the more expensive toys, and then trying combinations of the cheaper ones.
Just by trial and error, I tried 5*7.11 (xylophone) to get 35.55, followed by 4.77 (chequers), 2.75 (doll) and 0.87 (pinwheel). First and second were just guesses, so the only "calculated" choices were the doll and pinwheel.
There are probably many other easy solutions that one might arrive at by guessing different values to start with.
Good job finding it
I've tried the problem myself and it seems it's possible to get exact answer without allowing repeats.
I got the answer, but not the method yet :(
There's actually 21 items in the set, so 2097151 non-empty zero-or-one combinations.
By the way, Leo says that some kids actually solved the problem exactly, so there may be a trick that wasn’t obvious to Leo or me, or maybe they just got lucky.
The AZSPCS Sums of Powers problem was similar [0]. I found the optimizations surprisingly convoluted for how little of a speed up they provide. Writing an efficient backtracking, depth-first search was fun though.
IT doesn't say you can only buy zero or one of each item - in fact, the setup is explicitly that the toys are to be donated, meaning that we aren't likely to care too much about buying duplicates.
Helicopter parenting, now with extra math! Don’t bore about this at the next PTA meeting, let the kid do his homework, it’s clearly intended to get them do some additions
One of the things that's rarely brought up in discussions about NP complete and NP hard problems is that they have input ranges where they require non-polynomial time solutions. It's difficult to speak in general, but for SSS problems, when the values are comparatively small or large, the you can use the LLL algorithm to find an exact answer in polynomial time.
3x3 tiles, after spending probably days on I gave up
a few years later I wrote some code to brute-force the solution, there were a total of two solutions out of ~20 billion possibilities (not including rotations)
and the box said "for kids ages 8+"...
I suspect the designers just drew it out and cut it up without realising quite how hard it was (NP complete)
Yes, you can prune that thing severely. I imagine nearly all branches can be discarded after 5 tiles are positioned and the initial set is invariant to rotations, what leads to "only" many tens of thousands of possibilities.
I hated with a passion those puzzles when I was a child, and the people that claimed that they measured intelligence. I had better things to do than mindlessly rearranging pieces in a board until they fit! Strangely, I have much more patience for that now.
~20bn sounds about right. 9! * 4^9 / 4 ~ 23.8bn. Divide by 4 due to rotational symmetry.
Absolutely mind-boggling to me that such a small, simple puzzle has such an extreme search space! Great example of P vs NP, time to build a Where’s Waldo matching game cryptosystem.
I think a naive tree search (start from one tile and try adding others with matching edges) might find a solution pretty fast, because most of the search space gets discarded early.
Good point! I think this heuristic works well if the edges between tiles in completed picture are uniquely identifiable or close to that. However from the images there seem to be only 4 "colors" of edges in the puzzle (8 if you count two orientations for each character), so I think this will prune the search space to "only" perhaps around 100k-500k. Still really good, this makes the search space 50k-250k times smaller.
There are 43 quintillion Rubik's cube arrangements, and only one of them is the right one. Of course, this hasn't stopped children from solving the cube and even developing their own algorithms ;)
IMO the cube has partial solutions that simplify the problem as you go.
This "game" seems more like a penrose tiling. Any mistake may not be apparent until you cannot put a piece, thus there is relatively little simplification and it may not be apparent how far you must undo the puzzle to make additional progress.
Just my gut feeling on the comparison of the two games.
This is a classic dynamic programming problem. You create an array of bools of length 4394+1, initialize to False, and fill it left to right with True on the specific amount of cents that can be covered (this is possible because nothing has a negative price). Then if the final element is True the solution exists, and all solutions can be generated by back-tracking. It's polynomial if the input is represented in unary form (like in the regex version down below), and exponential if the input is represented in binary.
BTW, if you want you can even express this as a certain regex+input combo:
Regex: (a^122|a^275|a^185|...)+
Input: a^4394
Where a^N means "a" repeated N times, and of course the regex must cover the entire string. And, if your regex engine can find all matches, then it would also find all solutions.
The lists L and M have to be O(2^N) in size, where N is the target sum. I fail to see how this is any faster. In fact I think it's a little slower, if N is the target sum and M is the number of toys this algorithm runs in O(2^N * M * log(M))
Interesting.. It's somehow tough for me to accept that a "NP complete" problem can be solved with a regular language.
You construct a DFA. Your start state has (string of toy length) transitions to every possible toy. Then these toys all have self edges looping to themselves (with a string of length toy), and edges to every other toy (with those edges being the length of the other toy)...
But what is your accepting state, do you have 2 "escape" transitions of "toy cost" and "other toy cost" from "toy" to a terminating, accepting state? (Does that work?)
It feels like an abuse of regular languages and automata, and I'm not sure it works...
This is like saying: the balanced parentheses problem can be solved by a regular language, *if you fix the balanced parentheses problem to strings of 2^5 length, and build a machine that accepts all balanced parentheses combinations of 2^5 length. Like yeah, you could hack together an automata to recognize all 2^5 strings, but is it a proper automata at that point?
This is a pseudopolynomial time algorithm: polynomial in the magnitude of an important number, not in the number of bits that it takes to write it down. Problems with those kind of algorithm available don't make P=NP because the problems that don't have known pseudopolynomial solutions, when reduced to problems that do, end up with numbers with logs (rather than magnitudes) polynomial in the size of the original problem.
In real life, numbers are often of human scale (rather than the kind you get from reducing a hard SAT instance to knapsack) and a pseudopolynomial algorithm is great.
Every state that means "a full toy has just been scanned" is a valid accepting state. In fact you don't need separate states for each toy, you only need self-loop of appropriate length.
(Also, this is an NFA, not a DFA)
The language of valid parentheses up to size 2^5 is obviously regular, it's even finite.
I'm not understanding the "fill it from left to right with true on the specific amount of cents [and if it fits perfectly, you found a solution]." Isn't finding that "specific amount of cents [e.g. which choice of items achieves that amount]" the crux of the problem here that is glossed over? How would you test each combination to fit this boolean array without trying all of them brute force?
Start by only considering the Yo Yo, that is easy to fill out. Now consider both the Yo Yo and Doll, that is also easy to fill out given the current array. Then continue.
Hmm, true, addition is commutative, so you can reorder the elements however you want. Though it doesn't change the O() complexity you may get some performance tuning by starting with the largest elements.
If we're at fine-tuning, one thing you can do is divide all numbers by the GCD of all numbers, assuming that the GCD is not just 1.
$0.00 is always achievable (choose nothing), and negative values are never achievable.
Is $0.01 achievable? Well, take all items, subtract their price from $0.01 and see if any of the results are achievable. If so, $0.01 is achievable.
Repeat for $0.02, $0.03, ... This works because by the time you're processing $X you already know the answers to all values smaller than $X (and no item has a negative price).
I understand your solution, but is it really "Dynamic Programming"? DP requires that the problem can be broken down into subproblems. Also your method requires just quadratic time, right? (It's still pseudo-polynomial though.)
I think it should take quadratic time because for every item you find, you loop through the entire array, and whenever you see a 'True', you add the current item's price in it and make that new entry 'True'. You do this for all 'N' items and then in the end, check whether the last index in the array is 'True'.
The integer version of knapsack one is considered dynamic programming (use cents to represent the dollar value). It's pseudo polynomial - it's effectively O(TotalWeight * Items) if the items can be added once only.
I also know this approach as Dynamic Programming. While the subproblem is not cleanly seperated it is present in the sense that you consider one element first and then deal with the rest later, never touching the first again.
And yes, the runtime here is polynomial, however it is polynomial in the price k, which only needs log k bits to encode in the input. Therefore it is exponential in the encoding length. These algorithms are called pseudo-polynomial.
The subproblem is covering $0.00 (always possible), then covering $0.01, then covering $0.02, then covering $0.03, ...
Yeah the time complexity is O(N*M), where N is the value of the target added up price (size of the unary representation), and M is the number of items.
Yep, except this is so small, you can look at all combinations.
Something like this would do it (without replacement).
from itertools import combinations
arr = [
("yoyo",1.22),("doll",2.75),("duckie",1.85),("tractor",5.97),("airplaine",6.47),
("ball",2.16),("racecar",7.13),("dog",4.57),("jumprope",1.46),("car",5.18),
("elephant",3.16),("bear",4.89),("xylophone",7.11),("tank",6.45),("checkers",4.77),
("boat",8.04),("train",6.71),("jacks",2.31),("truck",6.21),("whistle",0.98) ("pinwheel",0.87)
]
for r in range(1,len(arr)+1):
for thisset in list(combinations(arr, r)):
if 43.94==sum([tup[1] for tup in thisset]):
print ([tup[0] for tup in thisset])
You're correct... I must have made a mistake when pasting it into the HN edit box, since I performed slight edits to make it not jam into a single line. Thanks!
Yes, this would work. Hard to reason about LP solvers in complexity notation, but would probably be pretty quick.
You could also construct a graph, where every price is a node. Start at 0.00, and do a BFS until you find the desired price. Worst case scenario O(n) where n is the desired price. Could be optimised by using a path finding algorithm like A*, its heuristic would make it try a greedy algorithm at first and then do a more complex solve at the end.
Another possibility is by memoization (dynamic programming). Strictly worse than the graph algorithm in complexity terms, but in practice your computer is very good at working sequentially on a very big array of booleans.
Really many different approaches to solve this problem. In this specific case greedy worked as well.
Is there any proof that the solution must have an iterative approach?
For instance, say there was some extremely clever way of depicting the relationships that allowed a "single pass" computation in a way that abstractly solves it that can be reduced to the valid combinations without ever having to "guess" or backtrack or do some variation of a permutation map wherein you reduce a set of candidate solutions.
This novel method would solve it like say, one does with the process of algebra. Of course this would be in some rules and abstractions perhaps invented and defined solely for this problem - perhaps discarding all of arithmetic in the process.
I can imagine a proof could exist showing such an approach isn't possible and I realize coming up with such a novel system for this problem is so unlikely the inventor would be put in the league of Gauss and Maxwell, the question is setting that aside, has it been shown to be a futile effort?
Yep, that's kind of why I asked it. I've always been unhappy with the various solutions and I've felt that with some representations, abstractions, and relationships this class of problems would be as solvable as say, a geometry problem.
But it might be the geometry problem of squaring the circle and I can roughly see how a proof for it having to be iterative might work (by contradiction specifically). I am not enough of a mathematician in the field to know
Given that this problem is the knapsack problem, which is known to be NP-hard, your question amounts to asking if we know for sure that P!=NP, except that you're actually asking for a much tighter bound than polynomial complexity.
Right now there is no proof that there isn't a polynomial time algorithm for the problem. I'm not 100% sure, but there are probably proofs for lower bounds, forbidding something like the O(n) you're thinking about. For example, the minimum possible worse-case complexity for an algorithm sorting n numbers is proven to be O(n*log n) comparisons. You're not going to find a solution to the knapsack problem that's easier than that, I think that much is obvious.
The theorized solution could create a fissure between this and other problems that's not currently recognized. Showing that they're not actually as equivalent as we thought is one of the things that's on the table here.
If we were to introduce a new analytical dimensionality to things, new categories would form and there's no guarantee that the same relationships between problems would exist thereafter.
Unless, that is, this has been shown to be not possible here
The proof that knapsack is NP complete is constructive - there is a known way to translate any NP complete problem to an equivalent knapsack problem (in polynomial time). If you can then solve that knapsack problem using any method whatsoever, you can convert the result back into the result of the other NP problem you started out with, in polynomial time.
So no, there is no way to redefine Knapsack so that it is not NP complete. Finding an easy solution to knapsack, however you did it, would prove P = NP.
There is much more room for questions about particular classes of instances of Knapsack. Perhaps all versions of knapsack with certain physically plausible properties can in fact be solved in O(n), even if the general case can't. The Simplex algorithm is famous for having this property - in the general case it is not even NP (it is in EXP I believe), but there are whole classes of instances, including most instances found of practical interest, can be solved with a simple quadratic (?) algorithm.
There are no reasonable known lower bounds for knapsack beyond "you must at the very least spend Omega(n) time reading read the entire input".
For sorting too, actually. The famous n log n bound comes from the decision tree complexity, which in turn assumes that only comparison queries can be made ("is A > B?"). However, many domains give more flexibility than just comparison queries, and in particular there are known O(n log log n)-time sorting algorithms for integers (see, for example, https://dl.acm.org/doi/10.1145/509907.509993 ).
While one can come up with contrived domains with arbitrarily large lower bounds (all the way up to computability-centered shenanigans like "sort these Turing machines by how long they take to halt on the empty tape, with ties broken by a lexicographical ordering"), most useful ones not derived from EXPTIME-hard problems tend to have no known lower bound better than just linear.
> The famous n log n bound comes from the decision tree complexity, which in turn assumes that only comparison queries can be made ("is A > B?"). However, many domains give more flexibility than just comparison queries, and in particular there are known O(n log log n)-time sorting algorithms for integers (see, for example, https://dl.acm.org/doi/10.1145/509907.509993 ).
Sure, for specific subclasses of a problem there are sometimes known better algorithms than the more universal bounds, and there is nothing to say the same can't be true for knapsack. I said this in my other comment, but the most interesting example I am aware of is the Simplex algorithm, whose worse-case complexity is exponential, but which is (deterministically) polynomial for "most" classes of input.
Anyway, interesting to know that lower bounds for NP-complete problems are not known, thanks for explaining this. Thinking about it, it does make sense, especially if the correct lower bound actually has to be non-polynomial, but I had incorrectly assumed otherwise.
The simplex method is an algorithm for solving LPs; the comparison of a particular algorithm's running time to the complexity of a problem isn't exactly one-to-one. In this particular case, there are algorithms with polynomial-time worst-case guarantees for solving the same problem as simplex, including the classical ellipsoid method and a whole battery of interior point methods.
The only technique complexity theorists have at the moment for finding unconditional lower bounds for a problem's running time is diagonalization, as in the method used for proving the time hierarchy theorem. While this can be used to prove that some problems require exponential time to solve, it is provably too weak to separate P from PSPACE, let alone P from NP. But it is enough to separate P from EXPTIME, meaning that any EXPTIME-hard problem such as Generalized Chess is provably not in P.
The point you touch on with Simplex is interesting, because as you mentioned it works extremely well in practice despite the well-studied lower bounds. There is some line of work that tries to explain it with "Smoothed Complexity" analysis, but despite the polynomial bound the current results are still not terribly satisfying. More generally, I think you were hypothesizing something along the lines of Imagliazzo's "Heuristica" (see https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multi... ), where NP-hard problems are hard in the worst case but actually finding these hard instances is equally difficult. This is a very real scenario, with both pros (we can solve stuff!) and cons (hackers can too!), at least on a theoretical level where "solvable" is synonymous with "polynomial time solvable". I think this is considered the third most likely of the five hypothesized worlds after Cryptomania and Mini-crypt.
By the way, Leo says that some kids actually solved the problem exactly
Occam’s Razor suggests access to the answer as the simplest explanation. Given the level of parenting described in the article, the perceived academic stakes within the context would justify the proverbial file cabinets with answers to the professors’ tests moved down to primary school…I mean some parents have kids competing with the NP complete kid.
Given many here have shown it’s not hard to “stumble” onto a correct answer, your comment is a great example of how Occam’s Razor shows the probable, but there are many cases where the simplest explanation isn't correct.
If the question is asking how many possible solutions there are, it can be solved with generating functions. (This method was popularized by George Pólya but I learned it from Knuth.)
Let A(z) be the generating function for the number of ways to spend n cents using only the $1.22 yoyo. Then naturally we can only spend those n that are multiples of 122 cents. So we define
A(z) = 1 + z^122 + z^244 + z^366 + ...
In this formulation the coefficient represents the number of ways: that's why the coefficient is 1 if the power is a multiple of 122 but 0 otherwise. Next we realize this infinite sum can be transformed into
A(z) = 1 / (1 - z^122).
Next, we consider what happens if we are allowed to use both the $1.22 yoyo and $2.75 doll. We get
B(z) = 1 / (1 - z^275) * A(z).
We repeat this for all items, to arrive at the closed form solution
Now if we have a computer algebra system we just ask it to do a Taylor expansion and read off the solution at the z^4394 term. Mathematica can do it but sadly I can't get Wolfram Alpha to do it. The answer is 4794820.
(This allows repetitions, and I think the author didn't allow repetitions. The author also missed the third item, the $1.85 duckie which is apparent from the posted code and the fact that there are references to 2^20 not 2^21.)
If you don't have a computer algebra system you can of course solve it manually with dynamic programming: the coefficient of z^n for B(z) is equal to the coefficient of z^n for A(z) plus the coefficient of z^(n-275) for B(z). Just think about the distributive law for multiplication.
But then for Hacker News, I guess dynamic programming is more preferred then:
190 comments
[ 3.8 ms ] story [ 242 ms ] threadAlso, I wonder if posting a photo of the work with pencil annotations violates the CC NoDerivatives license.
Problem B (mentioned in the article) is probably not as bad as it looks: you can eyeball that the target sum is approximately half of the total, and you can probably match the final digit.
But more likely, everyone answers either wrong (not because they know better) or right, because they don't know to do anything but multiply them; at the stage this is a question they don't know there are dependent and independent RVs.
It's like if you draw something that looks near enough a square and show it to someone in primary school, asking for the angle in the corners. The correct answer is 90 degrees, it doesn't matter that it's not exactly drawn, that we didn't define a coordinate system or the units we wanted.
Because if you didn't realize all the things you were allowed to assume at the level of math you are doing, it might be really stressful to be given problem for homework tat's unsolvable in general, but solvable if you make the correct set of assumptions, and think you are expected to produce a solution for it.
Especially that part about 'if it's homework, who cares'. I'm sure kids are very clear on that one.
It comes off as extremely sloppy: nobody expects kids in primary school to even understand what it means for variables to be independent, but certainly those writing the questions should know better!
Using only independent examples is a good way to have a lot of very repetitive problems where you take marbles out of bags of marbles.
1) it fits exactly.
2) you are told there is an answer
NP complete defines a generalization of a problem. Just because a general problem is hard doesn't mean every set of numbers is the same difficulty.
The problem of course is they are overthinking it using an adult brain. Just think stupid: add toys until you go over, then remove some. Start from largest to smallest. Etc.
It just might take longer than the universe will exist for you to get a solution.
1. The phrase “an NP Hard problem” refers to the computational complexity of a problem as the “scale” of the problem goes to infinity. Typically, an author would detail the problem, and what parameters go to infinity, but in this case the general problem “The subset sum problem (SSP)” is well known so explaining details is not necessary.
2. The homework question has two parts. The second part asks “(assume a solution exists) is the solution unique?” Clearly this decision problem reduces to SSP and is NP Hard
Here 'easy' means 'in polynomial time', and the property of all NP problems is that they are solvable in polynomial time given an oracle which generates the solutions, and then verifying that each solution is correct. Equivalently, they are solvable in polynomial time given an infinite number of execution threads that each takes one candidate solution and verifies whether it is correct or not (in polynomial time).
I don't think there is any known class of problems in complexity theory where it is easy to find 1 solution but hard to find all solutions.
In particular, notice that the question asks 'is your solution the only one?'
Is there any way, in general, to know you've found all possible valid solutions to this problem without enumerating every single one?
Tell me about a time when you over-engineered a solution to your child’s homework or school project!
>The reason was that the books were so lousy. They were false. They were hurried. They would try to be rigorous, but they would use examples (like automobiles in the street for "sets") which were almost OK, but in which there were always some subtleties. The definitions weren't accurate. Everything was a little bit ambiguous – they weren't smart enough to understand what was meant by "rigor." They were faking it. They were teaching something they didn't understand, and which was, in fact, useless, at that time, for the child.
>[...] That's the way everything was: Everything was written by somebody who didn't know what the hell he was talking about, so it was a little bit wrong, always! And how we are going to teach well by using books written by people who don't quite understand what they're talking about, I cannot understand. I don't know why, but the books are lousy; UNIVERSALLY LOUSY!
[0] https://www.hup.harvard.edu/catalog.php?content=reviews&isbn...
[1] https://www.maa.org/external_archive/devlin/LockhartsLament....
The part that made Feynman erupt in anger was the follow up question, "what is the total temperature of the galaxy".
It gives you the best possible estimate (in a MSE sense) for the temperature of a new star for which you know nothing about.
It may not be a great estimate (e.g, the distribution is multimodal because stars come in various types), but it doesn't seem obviously nonsensical.
The average (over 24 hours) temperature yesterday was 25˚C. You could certainly ask how that compares to other August 29ths in different years.
This even has a name ("grand mean"), so I'm surprised that someone thinks it's never useful.
> the subsamples have the same number of data points
It's unlikely to be useful in any other situation. Certainly not for averaging the temperature of a galaxy.
Both the overall mean and mean-of-means have sensible interpretations though.
Suppose you observe a random sample of stars and find their temperatures to be 6000, 6250, 6750, and 7000C. The best possible guess[0] for the temperature of a new star drawn from that population is 6500C. The average temperature of all the starstuff may be different if one star is larger than another, but that's an answer to a slightly different question.
In fact, I would argue that the mean-of-means is often a more appropriate summary statistic than the overall mean of the observations when there are repeated measurements.
[0] Under L2 loss, with no prior, etc etc
… okay, I fail at presenting why this is interesting. Let me try again.
Ha, I tricked you. The thing I want to talk about is CHOOSE and FAIL.
There’s a certain kind of program that can solve this problem in remarkably little code: non-deterministic.
Imagine you had a JavaScript statement called fail;
The program continuously restarts, trying all possible combinations such that fail never executes.It’s like pretending the code (or incidentally, the start of my comment) has supernatural powers. It can “look into the future” and set up all the variables such that it just so happens never to fail;.
Therefore, you could solve the problem like this:
The program will execute and perfectly print out every solution. And that’s all the code you need.So with that intro, I encourage you to scroll back up and read the comment chain I linked, if you’re thirsty for details.
Now I sleep. Goodnight :) fail. Just kidding, I’m awake still.
EDIT: Bah, I really did a terrible job with this. Sorry. You’re probably wondering “why not just use continue instead of fail?” and “what about CHOOSE?”
Those are reasonable questions. The magic here is that the logic can be arbitrarily complicated. You can say “if x + y != 10, then fail; print(x,y)” and it will only print pairs like 1 and 9, 2 and 8, etc. But you’re probably still wondering “why not just loop x from 1 to 10, y from 1 to 10, and skip any x+y != 10? That’s like a Python one-liner.”
… I think this is a case where I should have thought a bit more carefully before commenting, so I’ll leave this as an actual fail. But, all I can say is, non-determinism really is delightfully fascinating, and I hope I sparked one person’s curiosity about it…
… sorry? runs away like an introvert
Anyway, the "trick" for me was to just group the toys together into small sets that make easily workable values. For example, I tried to find a small grouping of toys that ends in 94 cents. Boat + Racecar + Checkers = $19.94
After that I tried to find small groups of toys that added to whole numbers. For example, Bear ($4.89) + Xylophone ($7.11) = $12. Once you have a few of those, it's easy to find solutions:
So then 2x (Bear + Xylophone) + Boat + Racecar + Checkers = $12 + 12 + $19.94 = $43.94
Of course, knowing whether you've found all solutions is, as the article notes, an entirely different beast.
The parent is a Stanford professor that studies scientific reasoning. I would assume he is a good judge of what his kid understands. This article was 4 years into a series about teaching his child STEM concepts.
https://leosstemhacks.wordpress.com/about/
Also, I'm going to go ahead and say it. I don't buy it. The third grader with three different sets of handwriting who needs to write down carries in order to compute 2.16 + 0.87 and who 30 days earlier was still learning basic algebra suddenly has his own programming language in which he's doing implicit typecasting into bit vectors to enumerate a set of 2^n solutions?
First graders here get fill in the blank questions:
__ + 3 = 10
Years later they'll learn
x + 3 = 10
Filling in the blanks isn't that hard for most kids, but dealing with x can be.
Now this is a sentence I never expected to read.
I aheb thought before about the fact that derivatives are a much simpler and more useful concept than exponentials and logarithms, but I very much fail to see how category theory is useful for anything other than researching the foundations of math.
Are you really claiming that it's of more practical use to understand the properties of monoids and rings than it is to understand that 2 + 2 = 4? Or are you actually talking about arithmetic beyond what is normally taught in school?
It shouldn't be surprising that two sheep plus two sheep is four sheep. We can go further. Suppose that we have lots of longhair sheep and shorthair sheep. If we choose some sheep, how many ways can we have some shorthair and some longhair? This gives exponentiation intuitively, so that we could ask how many ways we could choose zero sheep from a collection of zero sheep, or in other words, why zero to the zeroth power is one.
The parts of category theory that you're imagining, with the morphisms and natural transformations, doesn't have to be taught before arithmetic. It can be taught when lambdas are first introduced, when we write "f(x)" on the board for the first time.
This is the major problem I have always had with examples of category theory use: they always sound nice and give very illuminating intuitions for certain mathematical structures, which is very useful for doing mathematics and furthering your understanding. But they never directly answer any practical questions - for those, you always abandon the abstractions and start getting into the nitty gritty of the specific domain. At best, they help you take a specific algorithm from domain 1 and apply it in domain 2.
Am I wrong? Is there some way to actually get the answer to how many ways you can combine longhair and shorthair sheep in sets of 10 sheep, other than simply counting all combinations, or using traditional arithmetic/geometry etc. (e.g. repeated multiplication, angle measurements)?
Remember: Sets are 0-categories, so set theory is 0-category theory.
You're not done when you've found one. Are you sure you can't buy ten yoyos, three cars and a pinwheel and hit the number too?
When the son said that some people in the class got the problem exactly right, I doubt they spit out all 279 combinations.
I would start several approaches like writing a formula, bounding the number of toys (6 to 50?), looking for easy multiples, etc. the declare them all too hard and quit.
Just by trial and error, I tried 5*7.11 (xylophone) to get 35.55, followed by 4.77 (chequers), 2.75 (doll) and 0.87 (pinwheel). First and second were just guesses, so the only "calculated" choices were the doll and pinwheel.
There are probably many other easy solutions that one might arrive at by guessing different values to start with.
By the way, Leo says that some kids actually solved the problem exactly, so there may be a trick that wasn’t obvious to Leo or me, or maybe they just got lucky.
Possibly they did something similar to https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... ?
[0]: http://azspcs.com/Contest/SumsOfPowers
(Checkers + boat + racecar) = 19.94 = 43.94.
There are probably other solutions. The trick is to get rid of the change, than fine something that adds up to 8
That said... holy smokes that is an awful problem.
yoyo, duckie to elephant (from left to right, then down), and checkers.
I'm trying to see if it's possible to get a more general solution rather than trial / error
https://i.etsystatic.com/17381496/r/il/440b0d/3124003935/il_...
3x3 tiles, after spending probably days on I gave up
a few years later I wrote some code to brute-force the solution, there were a total of two solutions out of ~20 billion possibilities (not including rotations)
and the box said "for kids ages 8+"...
I suspect the designers just drew it out and cut it up without realising quite how hard it was (NP complete)
Are you sure there was no way for a child to prune the search space?
https://imgur.com/a/ICIBZCw and https://imgur.com/a/JOWkTsp
have a go, though I think that was the strategy I was using as a child
(and the box actually says 6+... mean)
I hated with a passion those puzzles when I was a child, and the people that claimed that they measured intelligence. I had better things to do than mindlessly rearranging pieces in a board until they fit! Strangely, I have much more patience for that now.
Absolutely mind-boggling to me that such a small, simple puzzle has such an extreme search space! Great example of P vs NP, time to build a Where’s Waldo matching game cryptosystem.
This "game" seems more like a penrose tiling. Any mistake may not be apparent until you cannot put a piece, thus there is relatively little simplification and it may not be apparent how far you must undo the puzzle to make additional progress.
Just my gut feeling on the comparison of the two games.
BTW, if you want you can even express this as a certain regex+input combo:
Regex: (a^122|a^275|a^185|...)+
Input: a^4394
Where a^N means "a" repeated N times, and of course the regex must cover the entire string. And, if your regex engine can find all matches, then it would also find all solutions.
1. Spilt the toys in two sets (A and B) of similar size.
2. Generate a sorted list L of all the possible sums that can be made with the toys in set A. If two sums are equal, keep only one.
3. Generate a sorted list M of all the possible sums that can be made with the toys in set B. If two sums are equal, keep only one.
4. Iterate through L forwards and through M backwards looking for two sums that together make up the target amount.
https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-m...
You construct a DFA. Your start state has (string of toy length) transitions to every possible toy. Then these toys all have self edges looping to themselves (with a string of length toy), and edges to every other toy (with those edges being the length of the other toy)...
But what is your accepting state, do you have 2 "escape" transitions of "toy cost" and "other toy cost" from "toy" to a terminating, accepting state? (Does that work?)
It feels like an abuse of regular languages and automata, and I'm not sure it works...
This is like saying: the balanced parentheses problem can be solved by a regular language, *if you fix the balanced parentheses problem to strings of 2^5 length, and build a machine that accepts all balanced parentheses combinations of 2^5 length. Like yeah, you could hack together an automata to recognize all 2^5 strings, but is it a proper automata at that point?
In real life, numbers are often of human scale (rather than the kind you get from reducing a hard SAT instance to knapsack) and a pseudopolynomial algorithm is great.
(Also, this is an NFA, not a DFA)
The language of valid parentheses up to size 2^5 is obviously regular, it's even finite.
If we're at fine-tuning, one thing you can do is divide all numbers by the GCD of all numbers, assuming that the GCD is not just 1.
Is $0.01 achievable? Well, take all items, subtract their price from $0.01 and see if any of the results are achievable. If so, $0.01 is achievable.
Repeat for $0.02, $0.03, ... This works because by the time you're processing $X you already know the answers to all values smaller than $X (and no item has a negative price).
I think it should take quadratic time because for every item you find, you loop through the entire array, and whenever you see a 'True', you add the current item's price in it and make that new entry 'True'. You do this for all 'N' items and then in the end, check whether the last index in the array is 'True'.
Did I miss something?
And yes, the runtime here is polynomial, however it is polynomial in the price k, which only needs log k bits to encode in the input. Therefore it is exponential in the encoding length. These algorithms are called pseudo-polynomial.
Yeah the time complexity is O(N*M), where N is the value of the target added up price (size of the unary representation), and M is the number of items.
https://www.quora.com/How-do-you-find-the-positive-integer-s...
Maximize sum(x)
subject to constraint:
P•x = 43.94
where P is a vector of prices of each toy, and x is a vector of quantities purchased of each toy.
Then one can either plug this into an LP solver, or can solve it by hand using simplex or other algorithm.
[1] https://en.m.wikipedia.org/wiki/Knapsack_problem
If we add the constraint that x must be an integer vector, then it becomes an integer linear program. Solving integer linear programs is NP-complete.
You could also construct a graph, where every price is a node. Start at 0.00, and do a BFS until you find the desired price. Worst case scenario O(n) where n is the desired price. Could be optimised by using a path finding algorithm like A*, its heuristic would make it try a greedy algorithm at first and then do a more complex solve at the end.
Another possibility is by memoization (dynamic programming). Strictly worse than the graph algorithm in complexity terms, but in practice your computer is very good at working sequentially on a very big array of booleans.
Really many different approaches to solve this problem. In this specific case greedy worked as well.
https://en.wikipedia.org/wiki/Subset_sum_problem
For instance, say there was some extremely clever way of depicting the relationships that allowed a "single pass" computation in a way that abstractly solves it that can be reduced to the valid combinations without ever having to "guess" or backtrack or do some variation of a permutation map wherein you reduce a set of candidate solutions.
This novel method would solve it like say, one does with the process of algebra. Of course this would be in some rules and abstractions perhaps invented and defined solely for this problem - perhaps discarding all of arithmetic in the process.
I can imagine a proof could exist showing such an approach isn't possible and I realize coming up with such a novel system for this problem is so unlikely the inventor would be put in the league of Gauss and Maxwell, the question is setting that aside, has it been shown to be a futile effort?
But it might be the geometry problem of squaring the circle and I can roughly see how a proof for it having to be iterative might work (by contradiction specifically). I am not enough of a mathematician in the field to know
Right now there is no proof that there isn't a polynomial time algorithm for the problem. I'm not 100% sure, but there are probably proofs for lower bounds, forbidding something like the O(n) you're thinking about. For example, the minimum possible worse-case complexity for an algorithm sorting n numbers is proven to be O(n*log n) comparisons. You're not going to find a solution to the knapsack problem that's easier than that, I think that much is obvious.
If we were to introduce a new analytical dimensionality to things, new categories would form and there's no guarantee that the same relationships between problems would exist thereafter.
Unless, that is, this has been shown to be not possible here
So no, there is no way to redefine Knapsack so that it is not NP complete. Finding an easy solution to knapsack, however you did it, would prove P = NP.
There is much more room for questions about particular classes of instances of Knapsack. Perhaps all versions of knapsack with certain physically plausible properties can in fact be solved in O(n), even if the general case can't. The Simplex algorithm is famous for having this property - in the general case it is not even NP (it is in EXP I believe), but there are whole classes of instances, including most instances found of practical interest, can be solved with a simple quadratic (?) algorithm.
For sorting too, actually. The famous n log n bound comes from the decision tree complexity, which in turn assumes that only comparison queries can be made ("is A > B?"). However, many domains give more flexibility than just comparison queries, and in particular there are known O(n log log n)-time sorting algorithms for integers (see, for example, https://dl.acm.org/doi/10.1145/509907.509993 ).
While one can come up with contrived domains with arbitrarily large lower bounds (all the way up to computability-centered shenanigans like "sort these Turing machines by how long they take to halt on the empty tape, with ties broken by a lexicographical ordering"), most useful ones not derived from EXPTIME-hard problems tend to have no known lower bound better than just linear.
Sure, for specific subclasses of a problem there are sometimes known better algorithms than the more universal bounds, and there is nothing to say the same can't be true for knapsack. I said this in my other comment, but the most interesting example I am aware of is the Simplex algorithm, whose worse-case complexity is exponential, but which is (deterministically) polynomial for "most" classes of input.
Anyway, interesting to know that lower bounds for NP-complete problems are not known, thanks for explaining this. Thinking about it, it does make sense, especially if the correct lower bound actually has to be non-polynomial, but I had incorrectly assumed otherwise.
The only technique complexity theorists have at the moment for finding unconditional lower bounds for a problem's running time is diagonalization, as in the method used for proving the time hierarchy theorem. While this can be used to prove that some problems require exponential time to solve, it is provably too weak to separate P from PSPACE, let alone P from NP. But it is enough to separate P from EXPTIME, meaning that any EXPTIME-hard problem such as Generalized Chess is provably not in P.
The point you touch on with Simplex is interesting, because as you mentioned it works extremely well in practice despite the well-studied lower bounds. There is some line of work that tries to explain it with "Smoothed Complexity" analysis, but despite the polynomial bound the current results are still not terribly satisfying. More generally, I think you were hypothesizing something along the lines of Imagliazzo's "Heuristica" (see https://gilkalai.wordpress.com/2008/11/12/impagliazzos-multi... ), where NP-hard problems are hard in the worst case but actually finding these hard instances is equally difficult. This is a very real scenario, with both pros (we can solve stuff!) and cons (hackers can too!), at least on a theoretical level where "solvable" is synonymous with "polynomial time solvable". I think this is considered the third most likely of the five hypothesized worlds after Cryptomania and Mini-crypt.
Occam’s Razor suggests access to the answer as the simplest explanation. Given the level of parenting described in the article, the perceived academic stakes within the context would justify the proverbial file cabinets with answers to the professors’ tests moved down to primary school…I mean some parents have kids competing with the NP complete kid.
Let A(z) be the generating function for the number of ways to spend n cents using only the $1.22 yoyo. Then naturally we can only spend those n that are multiples of 122 cents. So we define
In this formulation the coefficient represents the number of ways: that's why the coefficient is 1 if the power is a multiple of 122 but 0 otherwise. Next we realize this infinite sum can be transformed into Next, we consider what happens if we are allowed to use both the $1.22 yoyo and $2.75 doll. We get We repeat this for all items, to arrive at the closed form solution Now if we have a computer algebra system we just ask it to do a Taylor expansion and read off the solution at the z^4394 term. Mathematica can do it but sadly I can't get Wolfram Alpha to do it. The answer is 4794820.(This allows repetitions, and I think the author didn't allow repetitions. The author also missed the third item, the $1.85 duckie which is apparent from the posted code and the fact that there are references to 2^20 not 2^21.)
If you don't have a computer algebra system you can of course solve it manually with dynamic programming: the coefficient of z^n for B(z) is equal to the coefficient of z^n for A(z) plus the coefficient of z^(n-275) for B(z). Just think about the distributive law for multiplication.
But then for Hacker News, I guess dynamic programming is more preferred then: