The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data

DOI10.1145/2688073.2688115zbMath1364.68193OpenAlexW2020189547MaRDI QIDQ2989039

Unnamed Author, R. Ryan Williams

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2688073.2688115

zbMATH Keywords

circuit complexitycomplexity theoryprogram testingnatural proofscircuit-input gamegray-box testing

Mathematics Subject Classification ID

Applications of game theory (91A80) Fault detection; testing in circuits and networks (94C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Unnamed Item ⋮ Natural Proofs versus Derandomization

This page was built for publication: The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data