Computability in Europe 2006
Logical Approaches to Computational Barriers
|Author(s):||Lev Gordeev, Tübingen University, Utrecht University|
|Slot:||Sat, 14:30-14:50, Faraday E (col. 4)|
We present a plausibe “school-algebraic” condition C0 that infers, in Peano Arithmetic, the negative solution (abbr.: P < NP) to the familiar open problem P ?= NP. C0 expresses that a slight modification of the ordinary DNF conversion algorithm needs exponential size inputs in order to produce a certain big and complex output. This output is explicitly defined and its structure can be analyzed by standard methods of asymptotic combinatorics in order to achieve a desired proof of C0. C0 also admits purely combinatorial tree-presentation. We believe that our approach might accelerate fulfillment of Harvey Friedman’s prophecy: “2050, P != NP. Detailed combinatorial work on easier problems, leading up to the full result”.
|websites: Arnold Beckmann||2006-05-13|