HPL-2010-95
P ≠ NP - Deolalikar, Vinay
Keyword(s):P, NP, complexity theory
Abstract: We demonstrate the separation of the complexity class NP from its subclass P. Throughout our proof, we observe that the ability to compute a property on structures in polynomial time is intimately related to an atypical property of the space of solutions ...
Full Report
More...
