Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

A Proof for P vs. NP Problem

Name: Anonymous 2010-05-18 5:44

http://arxiv.org/abs/1005.3010

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

Name: Anonymous 2010-05-19 21:25

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.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List