An Elegant Argument that P is not NP

Abstract

In this note, we present an elegant argument that P is not NP by demonstrating that the Meet-in-the-Middle algorithm must have the fastest running-time of all deterministic and exact algorithms which solve the SUBSET-SUM problem on a classical computer.

2 pages; Version 14 is the published version, but this version is clearer

References in corpus (1)

• Complexity Science for Simpletons

Cited by in corpus (1)

• Critique of Feinstein's Proof that P is not Equal to NP