[图书][B] Theory of computational complexity
DZ Du, KI Ko - 2011 - books.google.com
A complete treatment of fundamentals and recent advances in complexity theory Complexity
theory studies the inherent difficulties of solving algorithmic problems by digital computers …
theory studies the inherent difficulties of solving algorithmic problems by digital computers …
[图书][B] The complexity theory companion
LA Hemaspaandra, M Ogihara - 2013 - books.google.com
Invitation Invitation Secret Secret 1 1 Algorithms Algorithms are are at at the the heart heart
of of complexity complexity theory. theory. That That is is the the dark dark secret secret of of …
of of complexity complexity theory. theory. That That is is the the dark dark secret secret of of …
Almost every set in exponential time is P-bi-immune
E Mayordomo - Theoretical Computer Science, 1994 - Elsevier
Abstract A set A is P-bi-immune if neither A nor its complement has an infinite subset in P.
We investigate here the abundance of P-bi-immune languages in linear exponential time …
We investigate here the abundance of P-bi-immune languages in linear exponential time …
An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality
HJ Böckenhauer, J Hromkovič, R Klasing… - STACS 2000: 17th …, 2000 - Springer
The traveling salesman problem (TSP) is one of the hardest optimization problems in NPO
because it does not admit any polynomial time approximation algorithm (unless P= NP). On …
because it does not admit any polynomial time approximation algorithm (unless P= NP). On …
Weakly hard problems
JH Lutz - SIAM Journal on Computing, 1995 - SIAM
A weak completeness phenomenon is investigated in the complexity class
E=DTIME(2^linear). According to standard terminology, a language H is ≦_m^P-hard for E if …
E=DTIME(2^linear). According to standard terminology, a language H is ≦_m^P-hard for E if …
Separation of NP-completeness notions
A Pavan, AL Selman - Proceedings 16th Annual IEEE …, 2001 - ieeexplore.ieee.org
We use hypotheses of structural complexity theory to separate various NP-completeness
notions. In particular, we introduce a hypothesis from which we describe a set in NP that …
notions. In particular, we introduce a hypothesis from which we describe a set in NP that …
Structural properties of complete problems for exponential time
S Homer¹ - Complexity Theory: Retrospective II, 1997 - books.google.com
The properties and structure of complete sets for exponential-time classes are surveyed.
Strong reductions, those implying many-one completeness, are considered as …
Strong reductions, those implying many-one completeness, are considered as …
Downward separation fails catastrophically for limited nondeterminism classes
R Beigel, J Goldsmith - SIAM Journal on Computing, 1998 - SIAM
The β hierarchy consists of classes \beta_k=\rmNPlogkn⊆\rmNP. Unlike collapses in the
polynomial hierarchy and the Boolean hierarchy, collapses in the β hierarchy do not seem to …
polynomial hierarchy and the Boolean hierarchy, collapses in the β hierarchy do not seem to …
Nonlocal quantum XOR games for large number of players
A Ambainis, D Kravchenko, N Nahimovs… - Theory and Applications …, 2010 - Springer
Nonlocal games are used to display differences between classical and quantum world. In
this paper, we study nonlocal games with a large number of players. We give simple …
this paper, we study nonlocal games with a large number of players. We give simple …
Autoreducibility of complete sets for log-space and polynomial-time reductions
C Glaßer, DT Nguyen, C Reitwießner… - … Colloquium on Automata …, 2013 - Springer
We investigate the autoreducibility and mitoticity of complete sets for several classes with
respect to different polynomial-time and logarithmic-space reducibility notions. Previous …
respect to different polynomial-time and logarithmic-space reducibility notions. Previous …