Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

DOI10.1070/IM1995v059n01ABEH000009zbMath0838.03045OpenAlexW2054013713MaRDI QIDQ4864743

Alexander A. Razborov

Publication date: 25 February 1996

Published in: Izvestiya: Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/im1995v059n01abeh000009

zbMATH Keywords

bounded arithmeticcircuit sizeSATISFIABILITYBoolean function complexitystrong pseudorandom generators

Mathematics Subject Classification ID

Related Items (28)

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ On the automatizability of resolution and related propositional proof systems ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Dag-like communication and its applications ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ A note on monotone real circuits ⋮ Some consequences of cryptographical conjectures for S 2 1 and EF ⋮ Towards NP-P via proof complexity and search ⋮ Circuit lower bounds in bounded arithmetics ⋮ Unnamed Item ⋮ A new proof of the weak pigeonhole principle ⋮ \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly ⋮ Resolution over linear equations and multilinear proofs ⋮ A form of feasible interpolation for constant depth Frege systems ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Natural proofs ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Adventures in monotone complexity and TFNP ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Some applications of propositional logic to cellular automata ⋮ Unnamed Item ⋮ A feasible interpolation for random resolution ⋮ Unprovability of circuit upper bounds in Cook's theory PV ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Reflections on Proof Complexity and Counting Principles

This page was built for publication: Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic