Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Toward combinatorial proof of P < NP. Basic approach

Speaker: Lev Gordeev
Author(s): Lev Gordeev, Tübingen University, Utrecht University
Slot: Array, 14:30-14:50, 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