It's easy to get a superficial understanding of the problem, and then very easy to subtly mis-understand it.
I've reviewed published papers by respectable people where they've made one of several easy mistakes:
* Be careful about how you encode your problem, it's easy to make it "too large", at which point your problem can be solved in P in the input size. For example, don't represent a sudoku as triples "x-pos,y-pos,value", where those 3 numbers are encoded in binary, because now if I give you a problem with only 2 filled in values, you can't take the solution as your 'certificate', as your input is about size 6 * log(n), but the solution will be n * n * log(n).
* It's also easy if you write your problem as a little language to accidentally make it impossible to check in P time.
* When proving a reduction (say turning SAT into a Sudoku, to prove Sudoku is NP-complete), it's (usually) easy to show how solutions map to solutions (so you show how the SAT instance's solution turns into a particular solution to the Sudoku). It's usually much harder, and easy to make mistakes, showing the Sudoku can't possible have any other solutions.
I've also seen people make the wrong direction of reduction.
Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.)
People make similar mistakes often when they want to show that a certain problem isn't solvable in linear time, and they try to show that sorting can solve your problem. But it's the wrong direction.
> Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.)
Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A. Which certainly means in this case that Sudoku is NP-hard. And it doesn't (without introducing additional facts) imply Sudoku is in NP either. I don't see anything wrong here, do you?
Reducing unknown-complexity to NP-complete means you can bound the complexity by above, but not by below. I can reduce binary integer addition to SAT, which means that binary integer addition is no harder than SAT... but we also know by other algorithms that it is in fact easier than SAT.
To bound by below, you have to reduce NP-complete (or NP-hard suffices) to unknown-complexity.
Oh gosh. I think I was so focused on the reduction direction that I think I misread the premise of the comment -- it seems somehow my brain parsed "use SAT to solve Sudoku" as "solve SAT using Sudoku". That's why I was saying that reducing SAT to Sudoku would imply Sudoku is at least as hard as SAT. It indeed would if they had actually done that, but they did the opposite. Not sure how my wires got crossed when reading, but thanks!
No, the GP is correct. If you use SAT to solve Sudoku, you have reduced Sudoku to SAT, not the other way around.
That is, you've shown that an oracle that solves any SAT problem in constant time can solve any Sudoku in polynomial time.
The more difficult side is to show that for any SAT instance, you can reduce it to a Sudoku.
Really proving that you can use SAT to solve Sudoku is not a great or interesting result; since Sudoku is a decision problem it is very clear that it is in NP. Or see that verifying that a Sudoku solution is correct is achievable in polynomial time.
> > they show that you can use SAT to solve Sudoku
> Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A.
Using SAT to solve Sudoku is a reduction of Sudoku to SAT. The order of the problems names switches depending on how you write it.
There's nothing subtle about the mistake in the paper at hand. The reason everybody expects proving P != NP to be difficult is that it's very hard to say anything at all about arbitrary programs. The authors just assume without justification that any program that solves SAT must operate in a certain recursive way -- obvious rubbish. It's hard to overstate how embarrassing this is for the Springer journal where this nonsense is published.
Algorithmic isomorphism practically ensures most CS approaches will fail to formally model the problem clearly. To be blunt, that million dollar prize will be waiting around a long time.
An infinite amount of Papers do not necessarily have to converge on a correct solution. =3
Gödel's Incompleteness Theorem has little to do with complexity theory. Complexity theorists routinely find out if two complexity classes are included in each other or not.
Why would Gödel's Incompleteness Theorem stop them for P=NP in particular?
Why is the current definition of P or NP insufficiently formal or clear?
PS: Citing YouTube Videos in mathematical discussions is a big red flag indicating you have not really understood things.
I would advise listening to Professor Thorsten Altenkirch brief introduction about the subject, and consider delaying argumentum ad hominem opinions a few minutes.
> "not really understood things"
Something currently impossible to prove is by definition confusing. lol =3
The ad-hominem was maybe unwarranted, sorry. Let's get back to the subject matter by me repeating the material question in my comment above, which you ignored: "Complexity theorists routinely find out if two complexity classes are included in each other or not. Why would Gödel's Incompleteness Theorem stop them for P=NP in particular?"
PS: I read through the transcript of the YouTube video you linked (and also know the material from my CS degree education) so I do in fact know what Gödel's Incompleteness Theorem is. Note that the video is really not about P=NP at all, not any more than it is about 1+1=2. The use of P=NP in the video was just to give an example of "what is a statement."
Personally I never saw degrees as an excuse to post nonsensical answers or troll people with personal barbs. P!=NP can be shown true for certain constrained sets, but P=NP was shown it can't currently be proven.
People can twist it anyway they like, but stating they can "sort of" disprove or prove P=NP is 100% obfuscated BS. That is why the million dollar prize remains unclaimed.
It's easy to get a superficial understanding of the problem, and then very easy to subtly mis-understand it.
I've reviewed published papers by respectable people where they've made one of several easy mistakes:
* Be careful about how you encode your problem, it's easy to make it "too large", at which point your problem can be solved in P in the input size. For example, don't represent a sudoku as triples "x-pos,y-pos,value", where those 3 numbers are encoded in binary, because now if I give you a problem with only 2 filled in values, you can't take the solution as your 'certificate', as your input is about size 6 * log(n), but the solution will be n * n * log(n).
* It's also easy if you write your problem as a little language to accidentally make it impossible to check in P time.
* When proving a reduction (say turning SAT into a Sudoku, to prove Sudoku is NP-complete), it's (usually) easy to show how solutions map to solutions (so you show how the SAT instance's solution turns into a particular solution to the Sudoku). It's usually much harder, and easy to make mistakes, showing the Sudoku can't possible have any other solutions.