Small progress measures for solving parity games
M Jurdziński - Annual Symposium on Theoretical Aspects of …, 2000 - Springer
In this paper we develop a new algorithm for deciding the winner in parity games, and hence
also for the modal μ-calculus model checking. The design and analysis of the algorithm is …
also for the modal μ-calculus model checking. The design and analysis of the algorithm is …
[PDF][PDF] The complexity zoo
S Aaronson, G Kuperberg, C Granade - 2005 - cse.unl.edu
What is this? Well its a PDF version of the website www. ComplexityZoo. com typeset in
LATEX using the complexity package. Well, what's that? The original Complexity Zoo is a …
LATEX using the complexity package. Well, what's that? The original Complexity Zoo is a …
The quantitative structure of exponential time
JH Lutz - [1993] Proceedings of the Eigth Annual Structure in …, 1993 - ieeexplore.ieee.org
Recent results on the internal, measure-theoretic structure of the exponential time
complexity classes E= DTIME (2/sup linear/) and E/sub 2/= DTIME (2/sup polynomial/) are …
complexity classes E= DTIME (2/sup linear/) and E/sub 2/= DTIME (2/sup polynomial/) are …
Resource-bounded measure and randomness
K Ambos-Spies, E Mayordomo - Complexity, logic, and recursion …, 2019 - taylorfrancis.com
We survey recent results on resource-bounded measure and randomness in structural
complexity theory. In particular, we discuss applications of these concepts to the exponential …
complexity theory. In particular, we discuss applications of these concepts to the exponential …
On the power of nonlinear secret-sharing
A secret-sharing scheme enables a dealer to distribute a secret among no parties such that
only some predefined authorized sets of parties will be able to reconstruct the secret from …
only some predefined authorized sets of parties will be able to reconstruct the secret from …
Cook versus Karp-Levin: Separating completeness notions if NP is not small
JH Lutz, E Mayordomo - Theoretical Computer Science, 1996 - Elsevier
Under the hypothesis that NP does not have p-measure 0 (roughly, that NP contains more
than a negligible subset of exponential time), it is shown that there is a language that is⩽ TP …
than a negligible subset of exponential time), it is shown that there is a language that is⩽ TP …
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 …
Genericity and measure for exponential time
K Ambos-Spies, HC Neis, SA Terwijn - Theoretical Computer Science, 1996 - Elsevier
Recently, Lutz [14, 15] introduced a polynomial time bounded version of Lebesgue measure.
He and others (see eg [11, 13–18, 20]) used this concept to investigate the quantitative …
He and others (see eg [11, 13–18, 20]) used this concept to investigate the quantitative …
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 …
Hausdorff dimension in exponential time
In this paper we investigate effective versions of Hausdorff dimension which have been
recently introduced by Lutz. We focus on dimension in the class E of sets computable in …
recently introduced by Lutz. We focus on dimension in the class E of sets computable in …