Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem

1998/10/01 by Manindra Agrawal, Eric Allender, Steven Rudich · 1 citation
Computer Science · Mathematics · #Brouwer fixed-point theorem #Class (philosophy) #Combinatorics #Compactness theorem #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computable analysis #Computable function #Computer science #Discrete mathematics #Fixed-point theorem #Fundamental theorem #Gap theorem #Invertible matrix #Isomorphism (crystallography) #Isomorphism extension theorem #Mathematics #Pure mathematics #Structured program theorem

paper · doi:10.1006/jcss.1998.1583

crossref issued 1998/10/01 · crossref published 1998/10/01 · crossref published-print 1998/10/01 · openalex publication_date 1998/10/01 · crossref created 2002/10/07 · crossref deposited 2024/12/02 · openalex created_date 2025/10/10 · crossref indexed 2026/02/11 · openalex updated_date 2026/08/06

Citations

• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• A Pseudorandom Generator from any One-way Function
• Intersection Theorems for Systems of Sets
• On determinism versus non-determinism and related problems
• Parity, circuits, and the polynomial-time hierarchy
• On Isomorphisms and Density of NP and Other Complete Sets

Cited by

• Reducing the complexity of reductions
• Gadget (computer science) [wikipedia]