On Circuit-Size Complexity and the Low Hierarchy in NP

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
Hard promise problems and nonuniform complexity
New Collapse Consequences of NP Having Small Circuits
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
Sparse selfreducible sets and nonuniform lower bounds
Turing machines with few accepting computations and low sets for PP
Self-reducible sets of small density
Logarithmic advice classes
Circuit-size lower bounds and non-reducibility to sparse sets
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
Space-efficient recognition of sparse self-reducible languages
Graph isomorphism is in the low hierarchy
A refinement of the low and high hierarchies
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.
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
Complexity classes between $\Theta _k^P$ and $\Delta _k^P$

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)