A Structure of Finite Signature with Identity Relation and with P = NP - A Formal Proof

Christine Gaßner

Preprint series: Preprintreihe Mathematik 2005, 1

MSC 2000

68Q05 Models of computation

68Q10 Modes of computation

68Q15 Complexity classes

03D75 Abstract and axiomatic computability and recursion theory

03C10 Quantifier elimination, model completeness and related topics

Abstract
Here, we construct a simple structure of finite signature with identity relation and with P = NP respecting the uniform models of computation. So, a solution is also given for a problem that was put by Bruno Poizat in his work "Les petits cailloux". For the considered structure, we define an NP-hard problem and a problem which is decidable by a relation of this structure in constant time, and we give a polynomial time reduction of the first problem to the second problem.

The considered structure is constructed by means of a method introduced in Preprint 1, 2004 and presented in the Dagstuhl-Seminar in February, 2004 at the first time. In Preprint 1, 2004 and Preprint 13, 2004, structures were extended to structures of trees and expanded by means of a unary relation. In Preprint 14, 2004, the construction method is described directly and extensively for the simplest case. Here we shall give the first formal proof for this case. To simplify matters, we use strings over the alphabet {a,b}. The strings correspond to the non-branching trees without labeling nodes and with edges which are labeled by "a" and "b". Moreover, we shorten the proof by using a more familiar NP-hard problem derived from the classical Satisfiability Problem.

The ideas for the development of the used method resulted from investigations of computation paths and small guesses by Felipe Cucker, Pascal Koiran, M. Matamala, and Klaus Meer. The connections will be demonstrated shortly.