NP Complete 3rd Grade Math Problems (2018) | Hacker News Reader

NP Complete 3rd Grade Math Problems (2018)

leosstemhacks.wordpress.com

217 pointsrfw300182 comments

The reason so many people hate maths is because maths is taught so poorly: https://www.rangevoting.org/FeynTexts.html

>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!

Are there any books that aren't lousy or is it truly universal?

I did Art of Problem Solving in high school which has excellent textbooks. Certainly not for everyone though.

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...

There's also Life of Fred which is definitely different to anything else out there.

Israel Gelfand wrote a number of amazing books covering many areas of high school math.

I enjoyed Measurement [0]. I was unsurprised when I eventually learnt that its author had previously written Lockhart’s Lament [1].

[0] https://www.hup.harvard.edu/catalog.php?content=reviews&isbn...

[1] https://www.maa.org/external_archive/devlin/LockhartsLament....

The Singapore Math curriculum is fantastic.

https://www.greaterwrong.com/posts/xg3hXCYQPJkwHyik2/the-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".

Can you explain this?

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!)

What's wrong with the average temperature over many stars?

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.

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.

The really frustrating part is that a trivial edit--ask for the average temperature instead--could make it into a sensible question.

An average of an average does not yield any number that has any useful definition.

Could you elaborate?

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.

I may have overstated slightly. The mean of means is equivalent to the overall mean iff

> 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.

Yes, that's obviously how the math works out.

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

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

The story is in the page linked above. ctrl+f temperature

total... or mean? it's an intensive property (something that was "taught" to me many years ago, in school).

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.

If the values are small enough. The problem is that the length of the unary form grows exponentially

Here's that runs in O(√2^n) time and space. And with careful implementation it will never be significantly slower than the above DP algorithm.

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.

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))

No. Small n in only 21. You split the toys in a set of 10 and a set of 11. What I'm really describing is the Meet In The Middle algorithm:

https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-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'.

Did I miss something?

https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... calls it dynamic programming.

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.

For those interested, there is a trick to this. You successively add the first several items until the amount first exceeds 43.94. This occurs after summing up the first twelve items, with the sum being 46.81. The items are over the limit by 2.87.

You wish to decrease your spending by $2.87, so you check if there are any items you have not chosen that cost exactly $2.87 less than an item you have chosen. A smart fifth-grader would quickly find that the car ($5.18) can be replaced by Jacks ($2.31). This concludes the problem-solving process.

This question was intended for fourth- and fifth-graders (https://www.insidemathematics.org/sites/default/files/materi...). Put yourself in the shoe of a smart fifth-grader who knows nothing about NP-completeness or knapsack problems. This problem is given to you, and you know it as solvable. This problem would look intimidating, but a good student would look for patterns, and the best way to start looking would be to sum the first few items (who knows, maybe the first items would sum up to exactly $43.94). After summing up to 46.81, a good student would "naturally" stop adding new items and ask himself "what can be done now?" All that he needs is now a mental "click".

Essentially, this problem tests students' intuition. It tests whether students can remain unintimidated in the face of difficult-looking questions. They need to start adding, and they need to have that one insight of replacing one of the items. Insights like these are extremely common and rewarding for young math learners.

I won't be surprised if many fifth-graders can solve the problem in five minutes.

That is... absurd. What an absolute waste of time, setting arbitrary patterns in interesting math questions- do we seriously want students, upon seeing a tough problem, to "just start adding"?

What rationale could anyone possibly have to teach this mindless nonsense to children, unless it was to prepare them for other standardized tests later in life, which are unanimously the product of mathematically impotent failed bureaucrats?

Oftentimes problems are hard, being able to come up with a useful heuristic (in this case greedy + fixer) is probably the most valuable thing one can do. Most math problems in real life aren’t solvable, you have to learn to approximate/bootstrap your way through.

Which I agree is an extremely useful skill to have, but I wouldn't call this problem "bootstrapping", I'd call it "a trick question". If the question had asked "provide a general solution to get you pretty close to the answer", I'd retract my criticism.

Write an essay on what the logic was to get you there - sure! I wish math classes were always taught that way!

I can only venture a guess. Many interesting mathematics results come from people simply observing patterns when doing adding, subtracting, etc. Many insights can come when people are not afraid of getting hands dirty. It's about getting rid of a fear of computation and developing a system for exploring unknown problems.

For example, consider this problem for geometric series: 1 + 2 + 4 + 8 + 16 + 32 + ... + 4096 = ?. This problem may look completely intractible and tedious without a calculator. But once you start adding: 1+2=3, 1+2+4=7, 1+2+4+8=15, 1+2+4+8=31, ..., even a child can spot the pattern. Now that they are amazed, they will be motivated to learn more about the cause of this pattern, etc, etc.

And I in turn can only venture a guess that you have entirely forgotten the brain-liquefying tedium of modern mathematics education, as shown by the fact that you immediately revert to actually interesting patterns that a properly-educated mathematician might think about.

The dollars-and-cents addition problem mapped onto the "fun" toy store narrative is not mathematically interesting until assigned the type of analytical firepower outlined in OP's blog post. It is a deliberately obtuse trick question posed as a learning tool; children labelled "gifted" will figure it out and feel the dull satisfaction of killing another "problem", and those without that benefit will simply experience more fear and boredom.

The word "label" is very important here.

"Smart" children are identified early. After that they are smart because everyone knows they are smart. It is very hard for a person who knows they are not smart to convince a society who knows they are not smart.

Dumb people are sometimes lucky and get something right. That doesn't make them smart. Smart people sometimes make mistakes. That doesn't re-label them as dumb. The important thing is the label you start with. Smart people will recognize the grammatical "mistake" in the previous sentence and understand that this post came from a dumb person.

But in the case of OP's problem, starting to sum from the first item is an arbitrary choice that "just happens" to need only one change for the sum to be exact. Where "just happens" means that it was artificially inserted by whoever wrote the problem.

Would the problem work if the student started summing backwards from the last item? How many items would the student have to swap in that case?. For how many random combinations of items would the problem "work" (i.e. require exactly one change?)

On the other hand, in your example you're not just trying random things until something works. Noticing that 1 + 2 = 3, etc is more analytical than adding members at random and hoping that the person who created the problem thought of the same random pattern you thought about.

..or down the columns instead of across the rows! It is indeed likely that the kids who got it (as claimed by the child) probably lucked into it in the afore-described way. But don’t you think that thinking about it first makes more sense than “just start summing”? And if you think about it, and know what an NP hard problem is (as this kid, shockingly! apparently did), you quickly realize that it’s impossible. Then, you need to have the meta-reflective insight that no one would give a third grader an NP hard problem, and that there must be a trick, so then, and only then, do you start to look for patterns, .. and then the bell rings and class is over and you spent the whole time meta-reflecting and looking for a trick in just one stupid problem. Sucks to be smart!

Sounds like you are a very smart mathematician who knows how to write a 4th grader math question which isn’t just „sum things up“.

In fact, this question is more than „just sum things up“, as described pretty well by the person above your comment.

I am a scientist. When I see a problem I have never seen before, I start to analyze it using the tools I know. This helps me to learn more about the given problem and supports me finding a „clever“ Solution in the next iteration.

This problem must be taken in the full context. This wasn't a free-form "explore the infinite bounds of mathematical expression" lesson, it was part of a worksheet. Worksheets are meant to be completed as proof of mathematical ability, and the relationship between one's ability to complete a worksheet and their intellectual potential is a poisonous lesson to teach to anyone. (Reference the past few pages of A Mathematician's Lament [1], or the whole thing if you have the time).

I am not opposing the idea that to do math, you must occasionally "get your hands dirty" as another commenter says; I am opposing the idea that it is useful to set this question in front of third graders in the form "find the solution and move onto another problem". As OP's article proved, there are many, many interesting implications that arise from this problem, and an investigation of those implications requires much more care, passion, and analysis than is implied by the form in which the problem is presented (as a solvable worksheet). For what it's worth: if you want to teach the lesson "sometimes you have to just start adding things up", just write that down in plain English and teach that. Put this question in a giant book of trick problems with an explanation of why each question is a trick, don't put this on a worksheet for of children who are required to attend class and then expect them to pick up on the subtleties of instruction after they write down the answer and get their grade back.

I am not a very smart mathematician; I am a middling intellect and have been my entire life. It was not until I was two years out of my engineering degree that I started investigating the world on my own and began to find out the true size and power of mathematics, and now it always angers me when I see the shallow imitations of real pedagogy and instruction passed off on the world's children as "useful math worksheets". My self-esteem and lifetime mathematical achievement were butchered by worksheets just like these.

[1] https://www.maa.org/external_archive/devlin/LockhartsLament....

I agree. GP explanation is no different than spotless guessing. I would probably start summing the most expensive ones in the hope that it would lead to less work to do.

>That is... absurd.

>unless it was to prepare them for other standardized tests later in life

yes, it teaches you how to understand standardized tests and to exploit them.

Unless standardized tests have changed radically for the better recently, I don't think this question is designed to teach someone how to score well on one.

This is a thinking problem that could be approached in a lot of different ways. It's really the opposite of a standardized test problem.

You can quickly determine that you need _at least_ seven items by summing the largest. It then happens that there are two possible seven-item solutions (468 solutions in total). To figure this out, I did in fact "just start adding."

That said, this problem isn't about mindlessly adding. It's about figuring out a way to systematically discover the answer. Most math challenge problems are designed with a method in mind; it's your job to figure that method out, and that's where the fun lies.

On the other hand, it teaches rapid prototyping and just trying out theories since each theory is fairly cheap to test out.

There's a somewhat popular TED talk on how kindergarteners frequently outcompete adults in the marshmallow challenge (tl;dr; build the tallest structure possible using assorted materials but a marshmallow must be on top) because, among other reasons, they're willing to just try out different approaches and fail fast rather than take a long time to think up of an approach that ultimately fails.

https://www.tanveernaseer.com/5-lessons-on-fostering-team-su...

https://www.marshmallowchallenge.com

You forgot the other half of the question - is your solution the only possible answer? - at which point you can really only evaluate all possible combinations. I agree it's one of several ways to test for a 'clever' student, though.

> at which point you can really only evaluate all possible combinations

You only need one counterexample, and in this case you can easily find it. E.g., you can note that the duckie in GP's solution can be swapped for the pinwheel+whistle without changing the solution's total cost, ergo the solution isn't unique.

I think a lot of people are looking at this like a coding interview, where it's assumed that your algorithm must work for all possible inputs, rather than just the inputs stated.

It’s easy to understand how a student at this level would approach it and give an answer.

Everybody’s problem here, mine included, is that this is a toxic way to teach math. One which has no use in math, which does not teach how to properly approach a problem and which in fact teaches and artificially rewards a bad approach: “just try it! It’ll work because all problems, even ridiculously difficult ones, are artificially customised to be easy for you to solve!”.

It’s bad. It’s awful. It’s not good. It’s everything math education shouldn’t be: boring, artificial, useless, constrained and a lie.

I don’t want children to solve this problem. I want children who can like math, to like and learn math. This is one of many drops in the jar of bullshit that will eventually overflow and turn them off.

No you don't. You only need to find a combination of toys in your answer that sum to another toy to easily see its not the only possible answer. If your solution involves the duckie for example that can be replaced by buying both the pinwheel and whistle. Or just find another combination of toys that works.

Some of this language: “a smart fifth grader would”, “a good student would”, stuck out to me. I have experienced people talking like this at work and I think it can be harmful. I watched a group humiliate one person by saying “how could you get a job here and not know that?” I also had a coworker once offer to help me solve a problem, during which they said something like “any competent engineer should be able to …” I had only been there a couple of weeks and it really undermined my confidence.

I don’t think recognizing a trick problem is necessarily about being good or smart. Is the author of the cited blog post dumber than a fifth grader?

>...and it really undermined my confidence

How is that a bad thing? I think the world needs less confidence in it right now, not more.

I think this approach is a bit backwards. The world needs more competence, and people should be encouraged to admit their gaps in knowledge and learn from others.

I really did appreciate the post, but I also felt weird about that language. Not offended or anything, but it stood out.

Not to detract from the nice explanation in that post, but I do think "smart" can be a bit of annoying term. It sort of implies an innate property. I'm pretty confident anyone can become really good at anything, given enough motivation and time. I'd prefer the term "experienced" or something to that effect.

> I'm pretty confident anyone can become really good at anything, given enough motivation and time.

And I'm pretty confident that some people can become really good at said thing faster, due to some form of innate talent. And as we all have finite time, that's a pretty important trait.

People, and their lives, are extremely high dimensionality objects, and most of those dimensions are essentially continuous. However, in terms of cognition, we are all quite close to one another along any given dimension. If we weren't, you'd really notice, like someone on the far end of "The Spectrum". However, small deltas in a high dimensionality space add up to a large vector length. Still, these are never so important as context: Where you grew up, whether you fell in love with someone early, whether you had access to the best schools for your target, etc. are much more important factors than the combinations of people's intrinsic features.

Perhaps the No true Scotsman fallacy?

https://en.m.wikipedia.org/wiki/No_true_Scotsman

The author has the “problem” of knowing too much. I’ve seen this myself where presented with a Singapore Math problem solvable easily by a 3rd grader I reach for more complex algebra because “I know that’s what the problem really is” when there are much easier ways to solve that kind of problem visually.

> I don’t think recognizing a trick problem is necessarily about being good or smart.

It goes a bit beyond that; this problem solving algorithm is pretty clearly unworkable. Even here where it can come to an answer in reasonable time it is questionable.

Any student that is happy to employ this algorithm is either extremely smart to the point where they can process a lot of arithmetic very quickly, or not very smart and setting themselves up for failure later on in life when the first guess at an answer doesn't work.

Ordinary garden-variety smart (as in, likely to be good at maths but not Euler or Gauss) should fail to answer this question on the basis that there is no technique beyond brute force, and brute force is impractical without a computer.

While that may be true, I consider it to be a lousy way of teaching and an even worse measure of mathematical competence, regardless of age.

I was fairly adept at math in fourth and fifth grade—well ahead of my peers. While I didn’t know terms like NP-Complete and NP-Hard, I would have immediately recognized that such a problem didn’t have a straightforward, timely solution for someone doing it by hand. I would have considered it a trap—in the sense that it’s a time sink—and moved onto the next problem.

If it later turned out that the solution to the problem required that I not actually understand it (from my perspective at the time), I would grow frustrated. I was the sort of asshole fifth grader who would not hesitate to chastise a teacher for giving us what I believed to be unrealistic, dumbed-down math problems. When in life am I going to encounter a knapsack problem that just happens to be quickly solvable that way? The chances of that are slim; the technique I’ve now learned has no application in the real world.

Take factoring, for example. I would regularly get frustrated with factoring assignments: how do you expect me to factor a collection of polynomials on a timed test if you cannot describe a deterministic algorithm for doing so? “If you’re having trouble, stay after school and I’ll help you.” After school, the teacher would helpfully demonstrate factoring several polynomials. I’d ask how the teacher knew how to guess the particular numbers they chose. What if the polynomial can’t be factored, and I waste time trying to find a solution? What if the numbers are large? The teacher would inevitably grow frustrated: “I won’t give you problems like that. Stop worrying about it.”

I’ll be the first to point out that I was never particularly nice to teachers who my judgmental 12-year-old brain considered incompetent, but I have little sympathy for this particular scenario. I wanted to understand the problems; I didn’t want canned solutions. My teachers knew I was perfectly capable of factoring the numbers with which we were presented, so they would get frustrated: why is an intelligent student stuck on a problem they’ve already solved?

Eventually, I found a book on prime numbers at a used book store and got the answers I needed.

Wow. Factoring quadratics were a similar pivotal moment in my maths education. Teacher couldn't explain how to do it in a way that fitted my brain. My confidence took a hit as did my love for the subject.

That happened to me too and directly influenced why I turned from math to programming, at least everything was deterministic.

> It tests whether students can remain unintimidated in the face of difficult-looking questions.

That's a very good goal. But for this problem, your success depends on whether you chose the same strategy that the teacher cherry-picked prices for - or just got lucky that another strategy happened to work.

"Intuition" implies that the student somehow understands the structure of the problem, but the prices in the problem could be adjusted ever so slightly in such a way that the strategy you outline would lead nowhere at all.

The only possible intuition to be found here is realizing that the only way to solve the problem is to throw shit on the wall until something sticks.

> I won't be surprised if many fifth-graders can solve the problem in five minutes.

A lot of fifth-graders could win on a scratch-off ticket in five minutes, too.

No rational human being would see this problem and just start adding the first few items. A smart student would skip the problem. It is counter-intuitive that just adding the first few items would be correct (why would they make it so obvious). If anything I would start with the last few items. Problems like this are the entire problem with math education in the U.S.

I was given an edge-matching puzzle as a kid, similar to this one:

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)

I remember those puzzles.

Are you sure there was no way for a child to prune the search space?

turns out it was a puzzle and OP is blind.

I found the pictures I took after beating my childhood nemesis

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)

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.

The puzzle performed exactly as desired by giving your parents a few days off! They were the customer, not you haha!

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 problem looks really familiar to me. I went to an experimental elementary school - actually a large-scale psych experiment run by psychologists - where these kinds of NP-hard problems were parceled out in each class to supposedly find the most talented students, and where the problems ranged from those with geometric or visual solutions to purely mathematical ones (some of which even the teachers couldn't solve). It's impressive (if true, which I doubt) that the child wrote NP-COMPLETE on the paper. And I wouldn't argue it's good exercise for a child's mind to try to solve things like this; in fact, an 8-year-old may be a lot faster at doing it than any known algorithm, for reasons we don't fully understand. But in fact these tests had nothing to do with getting the answer right. No one expects them to get it right. It's a way of measuring whether or not a child becomes frustrated with hard problems - or whether they try to do all the math one step at a time - or whether they try to invent some logic to solve them. Technically, mathematically, whatever shortcut they invent to solve can't possibly shortcut the NP-Hard nature of the problem, but the array of ways they'll come up with to try to do that is what's fascinating.

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.

But that's how you build to to the learning about the eventual general solution.

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.

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 has many more practical applications than arithmetic?

Certainly, see Haskell. It enables reasoning about interfaces, easy as algebra.

> 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.

I specifically mentioned arithmetic, which is often confused for mathematics.

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.

Can you explain how category theory can be used to figure out how much to tip a pizza delivery person?

It shows that tipping is not consistent with mathematics and pizza people should be formally compensated as to achieve this consistency. Perfectly congruent.

The question doesn't ask you to find a solution - it says "what combinations" can you find - plural.

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?

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.

All of which is just more evidence in the column of 'this is a terrible question, ill-posed, and pedagogically invalid'

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 PDF linked to in the post: https://web.archive.org/web/20181123120243/www.insidemathema... (the original link is dead)

Also, I wonder if posting a photo of the work with pencil annotations violates the CC NoDerivatives license.

Problem E of that set is hilariously wrong:

    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'.

Eh. My teacher just wrote "assume all probabilities are independent" at the top of the test.

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.

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 :(

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

    U(z) = 1 / ((1 - z^122) * (1 - z^275) * (1 - z^185) * ... * (1 - z^87))

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:

    #include <array>
    #include <stdio.h>
    
    int main() {
      static constexpr std::array<int, 21> kItemPrices = {
          122, 275, 185, 597, 647, 216, 713, 457, 146, 518, 316,
          489, 711, 645, 477, 804, 671, 231, 621, 98,  87};
      static std::array<std::array<int, 4395>, kItemPrices.size()> dp = {};
    
      // Base case
      for (int j = 0; j <= 4394; j += kItemPrices[0])
        dp[0][j] = 1;
    
      // Recurrence
      for (int i = 1; i < kItemPrices.size(); ++i) {
        for (int j = 0; j <= 4394; ++j) {
          dp[i][j] = dp[i - 1][j] +
                     (j - kItemPrices[i] < 0 ? 0 : dp[i][j - kItemPrices[i]]);
        }
      }
    
      printf("%d\n", dp[20][4394]);
    }

>The answer is 4794820 how do we get the answer from here?

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.

Using Julia and it's LLLplus library

  using LLLplus
  show(IOContext(stdout, :limit=>false), MIME"text/plain"(), subsetsum([122,275,185,597,647,216,713,457,146,518,316,489,711,645,477,804,671,231,621,98,87],4394))
  ([1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1], true)

Giving a yo-yo, doll, ball, racecar, car, bear, tank, checkers, jacks, truck, pinwheel as an answer

Isn't this a knapsack problem [1]? It looks like it can be represented as a linear program:

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

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 missing a comma before the pinwheel one, but otherwise this finds the same 686 solutions as mine.

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!

The LP solver might find a solution with fractional toys.

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.

Good point regarding ILP—that had slipped my mind.

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.

it's subset sum, isn't it?

https://en.wikipedia.org/wiki/Subset_sum_problem

My solver found 351 solutions without repeating items. But the article says there are 279. What is wrong?

  #include <stdio.h>
  
  #define N_ITEMS 21
  
  int prices[] = {122,275,185,597,647,216,713,457,146,518,316,489,711,
                  645,477,804,671,231,621,98,87};
  
  int sol[N_ITEMS] = {0};
  
  void show_sol(void) {
    printf("[");
    for(int i = 0; i < N_ITEMS; i++)
      printf("%d%c", sol[i], i != N_ITEMS - 1 ? ',' : '\0');
    printf("]\n");
  }
  
  void solve(int limit, int depth)
  {
    if(depth == N_ITEMS)
      return;
  
    if(limit == 0){
      show_sol();
      return;
    }
  
    solve(limit, depth+1);
    sol[depth]++;
    limit -= prices[depth];
    solve(limit, depth+1);
  
    sol[depth] = 0;
  }
  
  int main(void) {
    solve(4394, 0);
    return 0;
  }

The author forgot to add the "duckie" item in the list.

The OP wrote in Lisp. The Lisp compiler reflects on the code, and realizing that it’s trying all combinations, cross-compiled it to a quantum computer which produced an approximate answer.

There are actually 686 solutions. The problem is you're exiting the solve function before showing the ones that include the last price. Swapping the order of the two if statements fixes it.

Thanks!

Note that this line only initializes element 0, not all elements:

  int sol[N_ITEMS] = {0};

Did you mean {}?

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.

The code snippet in the made-up language is certainly interesting. You know, with more judicious use of the graph paper, sprinkle in some OCR and you might could run the hand-written version one day. The typed version maybe something like

      0   PRICE=$10.02
      1   MAT A[20]
      2   BIN L
      3   DEC N
  /   4   FOR N FROM 1 to 2^20
  |   5   L = N
  |   6   /*******/
  |   7   (/\A[L])?=PRICE 10
  \   8   NEXT N
      9   
      10  PRINT A[L]
      20  END
      30  /SNUFFYRUN
      40  ((NIL))
      50  
      60  
      70  
      80  
      90  
      100
      200 
      300 
      400 
      500
          END

Here's how I did it by hand (assuming you can buy multiple of a given item):

Work in cents, modulo 87 (the cost of the cheapest item, the pinwheel).

The total we want is 4394 (or 44 mod 87). Write down the price of every item modulo 87.

The whistle is 98 (or 11 mod 87) so you can buy 4 whistles and make up the rest in pinwheels (46).

The dog is 457 (or 22 mod 87) so you can buy 2 dogs and make up the rest in pinwheels (40).

Lots of other combinations.

However, the paper doesn't seem to suggest that buying multiple is okay.

I'm glad others mentioned the dynamic programming solution. That one feels elegant. Should've thought of that.

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.

Possibly they did something similar to https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-poly... ?

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.

[0]: http://azspcs.com/Contest/SumsOfPowers

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.

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.

Here's a much more efficient algorithm that runs in O(n*√2^n) time and space:

1. Spilt the toys in two sets (A and B) of similar size.

2. Generate a list L of all the possible sums that can be made with the toys in set A.

3. Sort the list.

4. Generate all the possible sums that can be reached with the toys in B and binary search L for a sum that will solve the problem.

Here's one answer I got from randomly picking. Each toy is either bought or passed (no repeats). I got the exact answer by getting:

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

Although finding the specific partitions might be tricker, existence is easy, this is the classic change making problem. Expand prod_i 1/(1-x^p_i) and check if you have terms = total value. Should tell you the number of possible partitions right away.

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?

This is a variation on the Knapsack problem. I'm not familiar with the common proofs used, but it is a well studied problem.

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.

Reminds me of

https://www.quora.com/How-do-you-find-the-positive-integer-s...

Solution in SageMath:

from sage.numerical.knapsack import knapsack knapsack([122, 275, 185, 597, 647, 216, 713, 457, 146, 518, 316, 489, 711, 645, 477, 804, 671, 231, 621, 98, 87], max=4394)

Note that this only finds a solution, not all solutions.

There’s a trick... the answer is (yoyo + ball + elephant + jump rope)3 = 83 = 24 +

(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

Covered in https://xkcd.com/287/

I don't like the title, NP problems do not have to be hard, it only means they get hard if you scale up the problem. Like traveling salesmen with 3 destinations is easy, not hard. I also agree the problem posed is ridiculous, but NP hard does not alway mean hard.

I wish somebody had taught me like Leo is being. seems so much fun

Fun fact, that problem is NOT NP-complete. It's a finite-sized instance of a class of NP-complete problems. It can be solved in constant time.

That said... holy smokes that is an awful problem.

Sort the list descending and apply a DFS.

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.

https://leosstemhacks.wordpress.com/about/

I love seeing that I’m literally mentally challenged compared to this third grader. Christ I hate myself.

An adjunct*.

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.

I wish I had the energy to dive in to a delightful segue. But: https://news.ycombinator.com/item?id=26804484

… 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…

… sorry? runs away like an introvert

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.

Peak parenting right here.

Tell me about a time when you over-engineered a solution to your child’s homework or school project!

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.

Sort desc first then it is pretty easy and can be stored as a bitmask.

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

How many additions? There are 21 prices on there. Are they doing... 2^21 different sums for their homework?

add them all and then one on top.

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?

Reply on news.ycombinator.com