Reductions in circuit complexity: An isomorphism theorem and a gap theorem

DOI10.1006/jcss.1998.1583zbMath0921.68037OpenAlexW2046812405WikidataQ56610693 ScholiaQ56610693MaRDI QIDQ1276160

Manindra Agrawal, Steven Rudich, Eric W. Allender

Publication date: 29 September 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/22843a4e2a67cb11c03cb8e93e753b0a52d89b20

zbMATH Keywords

complete sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Comparing reductions to NP-complete sets ⋮ The isomorphism conjecture for constant depth reductions ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Local restrictions from the Furst-Saxe-Sipser paper ⋮ A lower bound for primality ⋮ Reductions to graph isomorphism ⋮ Strong Reductions and Isomorphism of Complete Sets ⋮ The non-hardness of approximating circuit size ⋮ Reductions to Graph Isomorphism ⋮ Unnamed Item ⋮ Investigations Concerning the Structure of Complete Sets ⋮ For completeness, sublogarithmic space is no space.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On one-way functions and polynomial-time isomorphisms
• One-way permutations in NC 0
• Collapsing degrees
• Rudimentary reductions revisited
• Space-bounded reducibility among combinatorial problems
• DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• On the isomorphism conjecture for weak reducibilities
• For completeness, sublogarithmic space is no space.
• Circuit lower bounds à la Kolmogorov
• On uniformity within \(NC^ 1\)
• Intersection Theorems for Systems of Sets
• Parity, circuits, and the polynomial-time hierarchy
• P-uniform circuit complexity
• A survey of one-way functions in complexity theory
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• A First-Order Isomorphism Theorem
• The isomorphism conjecture fails relative to a random oracle
• Computational Complexity and the Existence of Complexity Gaps

This page was built for publication: Reductions in circuit complexity: An isomorphism theorem and a gap theorem