On Circuit-Size Complexity and the Low Hierarchy in NP
From MaRDI portal
Publication:3675520
DOI10.1137/0214003zbMATH Open0562.68033OpenAlexW1999609654MaRDI QIDQ3675520FDOQ3675520
Authors: Ker-I Ko, Uwe Schöning 
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
Recommendations
- On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
- On the (non) NP-hardness of computing circuit complexity
- On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
- scientific article; zbMATH DE number 806749
- Lower bounds for the size of nondeterministic circuits
- On the NP-Completeness of the Minimum Circuit Size Problem.
- On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results
- On the complexity of circuit satisfiability
- Circuit size lower bounds and \#SAT upper bounds through a general framework
- scientific article; zbMATH DE number 987472
Cited In (38)
- \(\mathrm{UP}\) and the low and high hierarchies: a relativized separation
- New Collapse Consequences of NP Having Small Circuits
- Hard promise problems and nonuniform complexity
- On proving circuit lower bounds against the polynomial-time hierarchy: positive and negative results
- Tally NP sets and easy census functions.
- Upper bounds for the complexity of sparse and tally descriptions
- Self-reducible sets of small density
- Sparse selfreducible sets and nonuniform lower bounds
- Turing machines with few accepting computations and low sets for PP
- Circuit-size lower bounds and non-reducibility to sparse sets
- Logarithmic advice classes
- P-selectivity: Intersections and indices
- UP and the low and high hierarchies: A relativized separation
- On helping by robust oracle machines
- The join can lower complexity
- Do there exist complete sets for promise classes?
- On some natural complete operators
- Complexity and structure
- On self-reducibility and weak P-selectivity
- Locating \(P\)/poly optimally in the extended low hierarchy
- Separating the low and high hierarchies by oracles
- Boolean operations, joins, and the extended low hierarchy
- In Memoriam: Ker-I Ko (1950–2018)
- Restricted relativizations of probabilistic polynomial time
- Lower bounds for the low hierarchy
- Nonuniform lowness and strong nonuniform lowness
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality
- On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
- A refinement of the low and high hierarchies
- Space-efficient recognition of sparse self-reducible languages
- Graph isomorphism is in the low hierarchy
- Probabilistic complexity classes and lowness
- Sets with small generalized Kolmogorov complexity
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
This page was built for publication: On Circuit-Size Complexity and the Low Hierarchy in NP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3675520)
