The complexity theory companion
From MaRDI portal
Publication:5925718
zbMath0993.68042MaRDI QIDQ5925718
Hemaspaandra, Lane A., Ogihara, Mitsunori
Publication date: 19 February 2001
Published in: Texts in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Nonnumerical algorithms (68W05)
Related Items (39)
A note on VNP-completeness and border complexity ⋮ The isoperimetric spectrum of finitely presented groups ⋮ Time hierarchies for cryptographic function inversion with advice ⋮ Unnamed Item ⋮ Complexity results in graph reconstruction ⋮ On the connection between interval size functions and path counting ⋮ On the relative power of reduction notions in arithmetic circuit complexity ⋮ Complexity of exclusive nondeterministic finite automata ⋮ Towards implementation of a generalized architecture for high-level quantum programming language ⋮ The consequences of eliminating NP solutions ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ The Boolean hierarchy of NP-partitions ⋮ Rationalizations of Condorcet-consistent rules via distances of Hamming type ⋮ Out of order quantifier elimination for standard quantified linear programs ⋮ Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ Inverse monoids associated with the complexity class NP ⋮ On a decision procedure for quantified linear programs ⋮ Computation in generalised probabilisitic theories ⋮ The complexity of two problems on arithmetic circuits ⋮ Robustness among multiwinner voting rules ⋮ On the asymmetric complexity of the group-intersection problem ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ Infinitely generated semigroups and polynomial complexity ⋮ Quantum and classical complexity classes: Separations, collapses, and closure properties ⋮ On the autoreducibility of functions ⋮ Lower bounds and the hardness of counting properties ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ Structural properties of oracle classes ⋮ Polynomial-time right-ideal morphisms and congruences ⋮ Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets ⋮ On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ Bernoulli measure on strings, and Thompson-Higman monoids. ⋮ Theory of one-tape linear-time Turing machines ⋮ All superlinear inverse schemes are coNP-hard ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy
This page was built for publication: The complexity theory companion
