[dragontamer]

NP-hard problems commonly come up as human-solvable puzzles. Like Sudoku... or perhaps a more applicable problem... layout and routing of electronic components on a PCB and/or chip. Or even assembly-language register allocation (coloring and packing problem).

Trained Humans are surprisingly good at these problems, far better than expected given how much computational power we have today. So its clear we don't understand something fundamental with regards to NP-hardness. And that's why the research continues, to bring human-like intuition into these problems and provide more automation to these tasks.

[mistercow]

I’m not sure there’s necessarily going to be a satisfying general answer to find here though. I can invent an NP-complete problem with very easy instances by combining a linear time problem with an NP-complete problem, e.g. “Does this list of cities have a complete route shorter than X OR is one of the cities New York?”

All of the “yes New York” solutions are easy, but there’s no deep, satisfying reason for that. It’s just a hard problem glued onto an easy problem. For all we know, a lot of NP-hard problems could be like that, and the structure of the easy instances could be essentially unrelated between problems.

[foota]

Maybe the answer then is to find what these hard cases are and use them in heuristics or approximate algorithms? If we could tell when part of the problem is hard, and maybe bound the error for them, and use an exact algorithm for other parts of the problem, you could get a better result in most cases without it blowing up on you.

[kaba0]

Well, you can just start an exact solver on the problem in one thread, and an approximate algorithm on another. If the former doesn’t finish in n seconds, you cancel it and use the result of the latter.

[foota]

The advantage of combining them though is that you might be able to treat different subparts of the problem differently (which is the hard part), so that you could use an approximate algorithm for the hard part of it, and an exact algorithm for the easy part.

Thi of course assumes the problem can be divided in this way, which is fairly speculative.

[kaba0]

> Trained Humans are surprisingly good at these problems

Are we? I don’t think we would even start working on problems with big enough `n` where the complexity actually ramps up.

Like, optimally scheduling even just a couple of things will have a shitton of combinations, and I really doubt we would be good at it.

Good at iteratively decreasing a cost function? Yeah, I guess with a good interface we could move around tasks to be scheduled on a timeline and optimize it. Finding the optimum? No chance.

[hinkley]

Our monkey brains can get within a few % of optimal on written TSP problems.

For a lot of these problems, having a tight upper bound lets you narrow the search space, regardless of whether you're looking for the ideal answer or simply a less-bad one (Would you turn down saving $500,000 on fuel and labor in a year just because someone thinks $613,000 is the maximum savings achievable?)

The more we can get automation to do approximations as well as humans, the better.

[sacado2]

It's often a modeling issue. Modeling languages are so abstract and general they give up a part of the problem's structure.

The most famous example is the pigeonhole problem, when given to SAT solvers. Definition of the problem is: I have n pigeons and m pigeonholes, with n = m + 1. Can I put all n pigeons in a different pigeonhole? The answer is obvious to a human. If I have 20 pigeons and only 19 pigeonholes, I won't make it. But even state of the art SAT solvers will fail at solving this in a reasonable amount of time. Because of the way the problem is represented (a conjunction of boolean clauses). With just a slightly more expressive modeling language (such as pseudo-boolean representation / reasoning), you solve it with the blink of an eye.

We humans are efficient because we recognize the underlying structure of the problem. You'll solve the pigeonhole problem in a split second. But if I encode the problem in CNF (the language of SAT solvers) and give it to you without more information, you won't be able to do it anymore.

[azornathogron]

I do find this interesting...

> Trained Humans are surprisingly good at these problems

Surprising why, and by what metric? (speed? Or quality of solution?)

[codeflo]

A problem is NP hard if there are instances that other hard problems reduce to. That is, only some instances of the problem have to be hard. NP hardness says nothing about "average" problem instances and even less about hand-picked ones.

And that's what Sudoku puzzles are. They are made for humans to solve. They are specifically crafted to contain challenging, but possible, solution paths.

[azornathogron]

I was asking about why specifically it's surprising that humans are good at such problems. I think that to be surprising there must be some prior expectation about how good humans should be and then evidence that they're actually better than that. Both sides of that are interesting and I'd like to know more about it: What is the prior expectation of human capabilities here (and why), and how does it compare to actual observed capabilities.

I'm not sure sudoku is a good example since the problem size there is so small that I don't have any intuitive sense that it should be something humans can't do.

[imtringued]

Computers have to solve hard exact problems. You don't seem to understand that heuristics can significantly speed up NP hard problems, especially if you are willing to give up exact solutions.

[cyberax]

Hmm.... A neural network for register allocation? Might be an interesting experiment to try.

[sp332]

Sudoku puzzles are usually set by humans.

[verve_rat]

Not really, as I understand it. The big blow up of sudoku books full of puzzles came about because some guy figured out how to create them with a program, rather than by hand. Earned the guy millions I believe.

Edit: Wayne Gould https://en.m.wikipedia.org/wiki/Wayne_Gould

[mrloba]

People who are more into it usually prefer human made puzzles since they often have a logical path that you're supposed to find, which can be quite satisfying. Generating sudoku puzzles is actually quite easy. Just put random numbers on the board until you have a unique solution. It runs surprisingly fast. The tricky part is deciding on the difficulty. I made a program that would identify all the different sudoku techniques needed to solve each puzzle (x wings, pairs, all the way up to chains), then set the difficulty based on what techniques were required. Code is here for anyone interested: https://github.com/magnusjt/sudoku/ Sadly I don't think anyone would pay millions for this anymore