Logical Approaches to Computational Barriers

A Structure with P = NP

Speaker:
| Christine Gaßner |

Author(s): |
Christine Gaßner |

Slot: |
Array, 14:50-15:10, col. 5 |

Several NP-complete problems for the BSS model are known which correspond to classical NP-complete problems. By analogy with the BSS model one can define some NP-complete problems for each structure of finite signature. Here, we supplement a structure of strings by some new relation by means of which it is possible to decide a unary variant of the Satisfiability Problem with respect to the uniform model of computation in constant time. The unary variant of the Satisfiability Problem is the result of padding the codes of formulae. The corresponding Satisfiability Problem is decidable in polynomial time such that we obtain P = NP for the new structure. Thus, a solution of a problem posed by Bruno Poizat in his book "Les petits cailloux" is presented.

websites: Arnold Beckmann | 2006-04-28 |