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 …
[图书][B] Effective fractal dimension: foundations and applications
JM Hitchcock - 2003 - search.proquest.com
Lutz characterized Hausdorff dimension using gales, gambling functions which generalize
martingales. Imposing computability and complexity constraints on the gales in this …
martingales. Imposing computability and complexity constraints on the gales in this …
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 …
Complete sets and structure in subrecursive classes
H Buhrman, L Torenvliet - Proceedings of Logic Colloquium, 1998 - projecteuclid.org
Complete Sets and Structure in Subrecursive Classes Page 1 Complete Sets and Structure in
Subrecursive Classes Harry Buhrman2 &; Leen Torenvliet ABSTRACT In this expository …
Subrecursive Classes Harry Buhrman2 &; Leen Torenvliet ABSTRACT In this expository …
Small spans in scaled dimension
JM Hitchcock - SIAM Journal on Computing, 2004 - SIAM
Juedes and Lutz SIAM J. Comput., 24 (1995), pp. 279--295 proved a small span theorem for
polynomial-time many-one reductions in exponential time. This result says that for language …
polynomial-time many-one reductions in exponential time. This result says that for language …
Equivalence of measures of complexity classes
JM Breutzmann, JH Lutz - SIAM Journal on Computing, 1999 - SIAM
The resource-bounded measures of complexity classes are shown to be robust with respect
to certain changes in the underlying probability measure. Specifically, for any real number …
to certain changes in the underlying probability measure. Specifically, for any real number …
Results on resource-bounded measure
We construct an oracle relative to which NP has p-measure 0 but D p has measure 1 in EXP.
This gives a strong relativized negative answer to a question posed by Lutz [Lut96] …
This gives a strong relativized negative answer to a question posed by Lutz [Lut96] …
Equivalence of measures of complexity classes
JM Breutzmann, JH Lutz - STACS 97: 14th Annual Symposium on …, 1997 - Springer
The resource-bounded measures of complexity classes are shown to be robust with respect
to certain changes in the underlying probability measure. Specifically, for any real number …
to certain changes in the underlying probability measure. Specifically, for any real number …
[PDF][PDF] Resource-bounded measure bibliography
JM Hitchcock - Computer Science, 2003 - eecs.uwyo.edu
Resource-Bounded Measure Bibliography Page 1 Resource-Bounded Measure Bibliography
John M. Hitchcock jhitchco@uwyo.edu [1] E. Allender. Circuit complexity before the dawn of …
John M. Hitchcock jhitchco@uwyo.edu [1] E. Allender. Circuit complexity before the dawn of …
Measure theoretic completeness notions for the exponential time classes
K Ambos-Spies - … Symposium on Mathematical Foundations of Computer …, 2000 - Springer
The resource-bounded measure theory of Lutz leads to variants of the classical hardness
and completeness notions. While a set A is hard (under polynomial time many-one …
and completeness notions. While a set A is hard (under polynomial time many-one …