Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
A Structure with P = NP


Speaker: Christine Gaßner
Author(s): Christine Gaßner
Slot: Array, 14:50-15:10, col. 5

Abstract

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