this post was submitted on 12 May 2024
229 points (99.1% liked)
Asklemmy
43939 readers
493 users here now
A loosely moderated place to ask open-ended questions
Search asklemmy π
If your post meets the following criteria, it's welcome here!
- Open-ended question
- Not offensive: at this point, we do not have the bandwidth to moderate overtly political discussions. Assume best intent and be excellent to each other.
- Not regarding using or support for Lemmy: context, see the list of support communities and tools for finding communities below
- Not ad nauseam inducing: please make sure it is a question that would be new to most members
- An actual topic of discussion
Looking for support?
Looking for a community?
- Lemmyverse: community search
- sub.rehab: maps old subreddits to fediverse options, marks official as such
- !lemmy411@lemmy.ca: a community for finding communities
~Icon~ ~by~ ~@Double_A@discuss.tchncs.de~
founded 5 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
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.
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.
I think there's a ~~fighter~~ further* problem, it may be true and we just don't know the easy way to do it.
Thatβs actually the simplest and clearest description of the P/NP problem Iβve ever read.
I think my favorite troll statement to a mathematician/comp scientist is:
"Actually, P > NP - there exist problems where it's harder to verify a solution than to arrive at one"
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
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.
What if the sudoku is 1 milllion lines by 1 million lines? How about a trillion by a trillion? The answer is still easy to check, but it takes exponentially longer to solve the board as the board gets larger. That's the jist of the problem: Is there a universal solution to a problem like this that can solve any size sudoku before the heat death of the universe?
For the purposes of OPs problem (P v NP), it considers not particular solutions, but general algorithmic approaches. Thus, we consider things as either Hard (exponential time, by size of input), or Easy (only polynomial time, by size of input).
A number of important problems fall into this general class of Hard problems: Sudoku, Traveling Salesman, Bin Packing, etc. These all have initial setups where solving them takes exponential time.
On the other hand, as an example of an easy problem, consider sorting a list of numbers. It's really easy to determine if a lost is sorted, and it's always relatively fast/easy to sort the list, no matter what setup it had initially.
I disagree, I think most computer scientists believe that P != NP, at least when it comes to classical computers. If we believed that P = NP, then why would we bother with encryption?
EDIT: nvm, I misread it.
I think you've misunderstood π . Answering "no" to that question corresponds to P != NP (there are problems that are easy to verify but not easy to solve), while "yes" means P = NP (if a solution is easy to check, the problem must be easy to solve). So I am saying most people and most scientists believe P != NP exactly as you say.
Reading comprehension is hard my bad.
Edit: wait no, it's "easy" I'm just dumb.