On Circuit-Size Complexity and the Low Hierarchy in NP

DOI10.1137/0214003zbMath0562.68033OpenAlexW1999609654MaRDI QIDQ3675520

Uwe Schoening, Ker-I. Ko

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214003

zbMATH Keywords

sparse setp-selective setpolynomial size circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (30)

Space-efficient recognition of sparse self-reducible languages ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ On helping by robust oracle machines ⋮ Separating the low and high hierarchies by oracles ⋮ Graph isomorphism is in the low hierarchy ⋮ Self-reducible sets of small density ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ A refinement of the low and high hierarchies ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ The join can lower complexity ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Restricted relativizations of probabilistic polynomial time ⋮ P-selectivity: Intersections and indices ⋮ Turing machines with few accepting computations and low sets for PP ⋮ Logarithmic advice classes ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ Hard promise problems and nonuniform complexity ⋮ Probabilistic complexity classes and lowness ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ Sets with small generalized Kolmogorov complexity ⋮ Do there exist complete sets for promise classes? ⋮ On self-reducibility and weak P-selectivity ⋮ Tally NP sets and easy census functions. ⋮ On some natural complete operators ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

This page was built for publication: On Circuit-Size Complexity and the Low Hierarchy in NP