Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

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

Speaker: Lev Gordeev
Author(s): Lev Gordeev, Tübingen University, Utrecht University
Presentation: TowardShort.pdf
Slot: Sat, 14:30-14:50, Faraday E (col. 4)

Abstract

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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net