Back to Search Start Over

Complexity of Operators on Compact Sets

Authors :
Xishun Zhao
Norbert Th. Müller
Source :
Electronic Notes in Theoretical Computer Science. 202:101-119
Publication Year :
2008
Publisher :
Elsevier BV, 2008.

Abstract

Based on oracle Turing machines, we investigate the computational complexity of operators on compact sets. For the projection and convex hull we are able to show exponential upper and lower bounds as well as a connection to the P=NP problem for special settings.

Subjects

Subjects :
Discrete mathematics
operator complexity
Oracle Turing machines
General Computer Science
Computational complexity theory
DTIME
NP-easy
projection
Cook–Levin theorem
NP
Theoretical Computer Science
Combinatorics
Turing reduction
Time hierarchy theorem
Alternating Turing machine
compact sets
convex hull
Mathematics
Computer Science(all)

Details

ISSN :
15710661
Volume :
202
Database :
OpenAIRE
Journal :
Electronic Notes in Theoretical Computer Science
Accession number :
edsair.doi.dedup.....558dec12a65cd1527fad22818af07885
Full Text :
https://doi.org/10.1016/j.entcs.2008.03.011
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details