Logical Approaches to Computational Barriers

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 C_{0}
that infers,
in Peano Arithmetic, the negative solution (abbr.: P < NP) to the familiar
open problem P ?= NP. C_{0} 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
C_{0}. C_{0} 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 |