``This paper proposes a theoretic proof for P vs. NP problem. The central idea of this proof is a recursive definition for Turing machine (shortly TM). By the definition, an infinite sequence of TM is constructed and it is proved that the sequence includes all TM. Based on these TM, the class D that includes all decidable languages is defined. By proving P=D, the result P=NP is proved.''
>>39 already have the most efficient algorithms that can be codified for these problems (and they suck)
Knowing for sure that we can't do better than O(n2) isn't the same as knowing our O(n2) algorithm is the best we can do. A* and plain BFS are both O(n2) algorithms that tackle the same problem, but one will outperform the other pretty much every time.
Name:
Anonymous2010-05-20 8:09
What kind of mentally retarded motherfucker would spend his time writing false crap like this?
Name:
Anonymous2010-05-20 16:03
What kind of mentally retarded motherfucker would spend his time writing false crap like this?
>>47
You moron. These posts get damn wide, and you passed up the one chance to use a fake "post truncated" that /prog/ has ever seen.
Name:
Anonymous2010-05-27 11:42
there are so many things wrong with that paper. the nigger should have stopped and killed himself when he proved all recursive languages can be solved in P.
One can (assuming the [formal] consistency of classical
mathematics) even give examples of propositions (and
indeed of such a type as Goldbach and Fermat) which are really contextually [materially] true but improvable in the
formal system of classical mathematics.
There are two possible answers to the P =? NP question: P = NP and P != NP.
There are another answer: P = NP is unanswerable. Thus, this proof only proves faggotry.
Name:
Anonymous2011-08-14 4:34
Do you have a bicycle? Does it have a lock? If not, nag your parents to get you one, those cheap bastards.
If I told you the combination, how hard would it be for you to check if I was right? It's quick. Use the numbers I gave you and see if the lock opens. Easy! People have found a whole bunch of jobs that are easy like checking lock combinations and grouped them together and called them "P". It's a terrible name, really. Let's call them "Easy problems".
Now, what about the problem of finding out the combination? That's hard. Unless it's a bad lock, it's a HUGE job to try and figure it out. You're going to sit all day and fiddle with the lock and hopefully you'll figure it out in the end. If you're clever, you'll try every single combination one after the other. That's called "brute force". Maybe it'll take 1 day to open your little bicycle lock, but I've got a lock which has got 20 numbers on it. Trying every combination would take you far too long.
People have taken all those types of problems and put THEM into a group too. They called that group "NP". Another dumb name. Let's call them "NP hard problems". I need to leave the "NP" in their name because NP hard problems are special. Not every hard problem is NP hard.
So here's the thing. We know that "easy problems" are easy, because we can solve them easily. But we don't actually KNOW that "NP hard problems" are hard. We strongly suspect it. We think that "Easy Problems" are different from "NP hard problems". Mathematicians write this like P != NP.
So, we've got this group of "easy problems", and this other group of "NP hard problems". What happens if someone comes up with a wild and brilliant way of solving the NP hard problems? If they did that, they would instantly all become easy problems. We could say that "NP hard problems" are the same as "easy problems". Mathematicians write it like P = NP.
So there's 2 different possibilities. We've never solved an NP problem, but nobody has been able to show exactly why NP problems can't be solved easily. So that's the big unsolved mystery. Are they really hard? And why.
What does it matter? Well, it matters for 2 reasons. First of all, all NP problems are the same. And there's a LOT of them. What do I mean they're the same? It means that if you find a way to solve one, you can use that way to solve them all.
The second reason is because a lot of what makes humans different to computers is being able to look at an NP hard problem and make some progress even though it's "unsolvable" for a computer. Proving something is like an NP hard problem. Checking the proof is like a P easy problem. Often, only humans can write proofs, and then computers can check the proofs.
If we discover that P=NP, that all these hard problems are really easy, we will very very quickly be able to ask computers to do things that today seem totally impossible. We're not just talking about faster and better computers. Compared to what computers do today, they would be able to do stuff that would look like magic.
But don't get too excited just yet. 9 out of every 10 scientists think that P!=NP, which means that hard problems are really very hard, and there's no easy shortcut to solving them. And the other scientist is on LSD and basically has no clue what he's talking about.
I haven't read the entire paper thoroughly but it seems to me there is an obvious error in it.
He shows a way to iterate some TMs and names the set of these TMs Q. He claims that D (the set of all deciders) is a subset of Q even though all TMs in Q only accept the encodings of other TMs in Q.
What about the decider that accepts the input 'foo' (which is not an encoding of a TM) and rejects in all other cases? That TM will never be reached by the sequence, so obviously Q is not the set of all TMs of some alphabet.
As it has been pointed out in >>8 this proof implies that even EXP-TIME problems can be done in P time which is nonsense.