P = BPP if E requires exponential circuits

1997/01/01 by Russell Impagliazzo, Avi Wigderson · 10 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Quantum Computing Algorithms and Architecture

paper · doi:10.1145/258533.258590

crossref issued 1997/01/01 · crossref published 1997/01/01 · crossref published-print 1997/01/01 · openalex publication_date 1997/01/01 · crossref created 2003/11/25 · crossref deposited 2025/06/18 · openalex created_date 2025/10/10 · crossref indexed 2026/06/10 · openalex updated_date 2026/07/29

Cited by

• The status of the P versus NP problem
• Parallel Identity Testing for Skew Circuits with Big Powers and Applications
• Cosmological lower bound on the circuit complexity of a small problem in logic
• Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
• Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors
• Guest Column: NP-complete problems and physical reality
• The Nature of Computation
• Arthur–Merlin protocol [wikipedia]
• BPP (complexity) [wikipedia]
• Russell Impagliazzo [wikipedia]