``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.