Theory of semi-feasible algorithms
From MaRDI portal
Publication:5959347
zbMath1021.68042MaRDI QIDQ5959347
Leen Torenvliet, Hemaspaandra, Lane A.
Publication date: 1 April 2002
Published in: Monographs in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)
03D15: Complexity of computation (including implicit computational complexity)
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Separating NE from Some Nonuniform Nondeterministic Complexity Classes, The communication complexity of enumeration, elimination, and selection, Dimension and the structure of complexity classes, Polynomial-time axioms of choice and polynomial-time cardinality, The consequences of eliminating NP solutions, Separating NE from some nonuniform nondeterministic complexity classes, Choosing, agreeing, and eliminating in communication complexity, Some connections between bounded query classes and non-uniform complexity., Closure and nonclosure properties of the classes of compressible and rankable sets, Fixed-parameter decidability: Extending parameterized complexity analysis, The Power of Self-Reducibility: Selectivity, Information, and Approximation