``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.''
I thought that most of these get disproved as time passes?
Did anyone challenge this one yet?
Personally, I'd like to think/hope that P=NP, but chances are that it's not true.
>>4
I just skimmed through it. If the mathematics are as rigorous and coherent as the grammar, then it's likely it will soon be disproved. In this paper, we mainly follows the official definition announced by Clay Math Institute in 2000.
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.
Anyone else read this part and just think laugh?
>>16
Efficient implementations of a large class of algos which are currently way too slow if you want to get a perfect solution? (less than perfect, but okay ones at reasonable performance can be usually done with the right heuristics).
Name:
Anonymous2010-05-18 16:14
[quote]The author would like to thank all the people who give him worm help and encouragement.[/quote]
>>17
'Efficient' is either incorrect or simply meaningless. Do you think that reducing NP to P means eliminating the possibility of prohibitive computation costs? I have some very bad news for you if you do.
>>21
You've made the mistake explicit now. Without a proof (at least) there is no guarantee that the PTIME solution will beat the EXPTIME solution at practical magnitudes, or even the magnitudes of interest.
>>24
No, that's what I meant all along. The worst-case scenario of the proof is not efficient in any meaningful sense, and it's just plain wrong to exclude it--which you just tried to do. I'm surprised you didn't catch on right away since this objection is common in any treatment of the issue. Oh right, you're 14, illiterate, and talking out of your ass. Never mind then.
>>33
(the guy cited as author in bright blue after following the link).
Name:
Anonymous2010-05-19 16:13
>>2 Personally, I'd like to think/hope that P=NP, but chances are that it's not true.
Me too, sir.
However, I see cranks posting their pages from arxiv on the Wikipedia talk page for P=NP all the time, and I doubt this "proof" is finally a correct one.
Name:
Anonymous2010-05-19 17:12
Let's just say that P does equal NP and be done with this conversation.
I don't see the benefit of proving P = NP on its own using some kind of template or archetype. Sure, yeah, we would have just proven a very complicated connection between the dynamics of different kinds of polynomial-time problems. On the other hand the binary solution to P = NP would not explain how to train a better salesman.
People have hopefully been trying to create better algorithms for these non-deterministic super-polynomial problems while we wait. In fact, I think an answer of "yes/true" would be disenchanting because it would imply we either already have the most efficient algorithms that can be codified for these problems (and they suck) or we lack the means or language for codifying any kind of elegant solution.
>>39
A polynomial time solution to an NP problem is proof that P = NP. An answer of "yes/true" would imply that we now have an elegant solution that can be specialized to all of these problems. It's a big fucking deal.
The `proof` in the OP, however, is based on an infinite sequence of TMs, and is therefore almost certainly shown false by diagonalization.
>>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.