Complexity and structure

zbMath0589.03022MaRDI QIDQ1073788

Uwe Schoening

Publication date: 1986

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

Boolean functionpolynomial-time hierarchyrelativizationsword problemsself-reducibilityOraclesCircuit-Size Complexityexponential hierarchyhigh hierarchylow hierarchyNP-setspolynomial size circuitsProbabilistic Algorithmsselective setsSparse Sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity of proofs (03F20) Algorithms in computer science (68W99)

Related Items

Nondeterministic functions and the existence of optimal proof systems ⋮ On sparse oracles separating feasible complexity classes ⋮ Average-case intractability vs. worst-case intractability ⋮ On the lattices of NP-subspaces of a polynomial time vector space over a finite field ⋮ Autoreducibility, mitoticity, and immunity ⋮ On a theorem of Razborov ⋮ Complexity-theoretic algebra. II: Boolean algebras ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ New collapse consequences of NP having small circuits ⋮ On problems for which no oracle can help ⋮ On the contribution of backward jumps to instruction sequence expressiveness ⋮ Circuit size relative to pseudorandom oracles ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ On Toda’s Theorem in Structural Communication Complexity ⋮ Reducibilities on tally and sparse sets ⋮ Closure and nonclosure properties of the classes of compressible and rankable sets ⋮ On hiding information from an oracle ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ Graph isomorphism is low for PP ⋮ Sets with small generalized Kolmogorov complexity ⋮ Polynomial time samplable distributions

This page was built for publication: Complexity and structure