Computability in Europe 2006
Logical Approaches to Computational Barriers
Logical Approaches to Computational Barriers
Print this page
Regular Talk:
Expansions of Structures with P = NP
| Speaker: | Christine Gaßner |
| Author(s): | Christine Gaßner |
| Presentation: | GassnerExpansionsWithPNP.pdf |
| Slot: | Sat, 15:10-15:30, Faraday J (col. 5) |
Abstract
We introduce the uniform computation model over an arbitrary structure of finite signature which is analogous to the model of Blum, Shub, and Smale. We recursively construct an additional relation for an extension of this structure such that a unary variant of an NP-complete problem is decidable by means of this relation with respect to the uniform model of computation in constant time. This implies P = NP for the new structure.
| websites: Arnold Beckmann | 2006-04-28
|