A Gödel Theorem on Network Complexity Lower Bounds

DOI10.1002/MALQ.19860321912zbMATH Open0583.03045OpenAlexW1978889713MaRDI QIDQ3708019FDOQ3708019

Authors: Claus Peter Schnorr 

Publication date: 1986

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19860321912

Recommendations

• A Boolean function requiring 3n network size
• scientific article; zbMATH DE number 3867233
• scientific article; zbMATH DE number 139642
• On estimates on the complexity of restrictions of Boolean functions
• scientific article; zbMATH DE number 4208009

zbMATH Keywords

Boolean functionsincompletenesslower complexity boundsformal proof systemminimal proof length

Mathematics Subject Classification ID

Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (2)

• New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems
• The multiplicative complexity of quadratic boolean forms

This page was built for publication: A Gödel Theorem on Network Complexity Lower Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3708019)