If the solution to a problem is easy to check for correctness, must the problem be easy to solve?
For instance, it is easy to check if a filled sudoku grid is a valid solution. Must it therefore be easy to solve sudokus?
Most people would probably intuitively answer “no”, and most computer scientists agree, but this has still not been proven, so we actually don’t know.
That’s actually the simplest and clearest description of the P/NP problem I’ve ever read.
Well, there’s counterfactual examples of this, so it must not be true.
In pretty much every single relationship worldwide, one person can very easily determine if the recommendation from the other for where to eat or what to watch is correct or not.
And yet successfully figuring out where to eat or what to watch is nigh impossible.
Isn’t it proof enough? Using the Sudoku example: there are certainly different levels of difficulties, depending on how many numbers are set in the beginning and other parameters. Checking if the solved answer is correct, is always the same “difficulty” - thus there is no correlation between the difficulty of the puzzle at the beginning and checking the Correctness. Some people might not be able to solve it, but they certainly can check if the solution is right
Isn’t it proof enough?
Unfortunately no. The question is a simplification of the P versus NP problem.
The problem lies in having to prove that no method exists that is easy. How do you prove that no matter what method you use to solve the sudoku, it can never be done easily? You’ll need to somehow prove that no such method exists, but that is rather hard. In principle, it could be that there is some undiscovered easy way to solve sudokus that we don’t know about yet.
I’m using sudokus as an example here, but it could be a generic problem. There’s also a certain formalism about what “easy” means but I won’t get into it further, it is a rather complicated area.
Interestingly, it involves formal languages a lot, which is funny as you wouldn’t think computer science and linguistics have a lot in common, but they do in a lot of ways actually.
You can solve any sudoku easily by trying every possible combination and seeing if they are correct. It’ll take a long time, but it’s fairly easy.
Well it just so happens that the definition of “easy” in the actual problem is essentially “fast”. So under that definition, checking every single possible solution is not an “easy” method.
I’m an IT auditor. “What the fuck?” is the main question, we ask it daily
I’m only a professional scientist in the loosest sense of the term but for years we’ve tried to figure out why Joe can’t leave the break room to fart and who the fuck does he think he is?
We still don’t understand quite how the brain works or how consciousness comes from neurons.
Trying to prevent bacteria from developing antimicrobial resistance. At these rates in 30 years antimicrobial resistant bacteria are projected to kill more people than cancer.
Clearly you need to figure out how to give antibiotic resistant bacteria cancer.
I feel inappropriate near all the very universal questions here, but as a paleontologist specialised in some reptilian groups, the question would probably be “where the fuck do turtles come from?!” The thing is that fossil evidence points to different answers when compared to genetic evidence, and thez separated long enough from other extant groups that we keep on having new “definitive” answers every year
My brother works in molecular biology; he tells me the field’s understanding of peptides have only just begun and it’s only through machine learning that they are now starting to make progress. 99% seem to be post-translational garbage, the other 1% is likely to be the basis of a revolution of treatment options.
I’m in the building sciences. The biggest unanswered question we come up against almost daily is “what the fuck was the last guy thinking?”. And we avoid, daily, admitting we were the last guy somewhere else.
This sounds like software engineering in a nutshell.
Probably not the most complex, but in programming, the salesman problem: intuitive for humans, really tough for programming. It highlights how sophisticated our brains are with certain tasks, and what we take for granted.
Also, related xkcd.
I once accidentally worked myself into trying to solve the traveling salesman problem. I was doing some work on a very specific problem, and I got to a point where I couldn’t figure out a way to efficiently link up a bunch of points. The funny thing is that I knew about the TSP, but I just didn’t realize that the problem I was trying to solve was a case of the TSP. After a couple of days trying to figure it out, I realized what it was, and that it was futile.
It was a good lesson to always try to find the most abstracted version of the problem you are trying to solve cause someone smarter has either tried and failed or tried and succeeded.
Is P, NP?
Guys I swear this actually makes sense…
I solved this in undergrad.
P = NP when N=1. I don’t understand what the big deal is.
I don’t think you passed
Also P is 0 when N is 0
How does immunology work?
Pro tip: nobody understands immunology and anyone who tells you otherwise is lying
After covid, this strikes me as a dangerous thing to say. Are you an immunologist and could you expound on this?