Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 73

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 80
CiE 2006 - Regular Talk: - Expansions of Structures with P = NP
Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Expansions of Structures with P = NP


Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 249
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
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135
2006-04-28 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net