Almost-natural proofs
type: Item
instance of: scholarly article
title: Almost-natural proofs
zbMATH Open document ID: 1215.68100
author: Timothy Y. Chow
published in: Journal of Computer and System Sciences
publication date: 2011-04-28T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 5882191
zbMATH Keywords: circuit lower bound
zbMATH Keywords: natural proof
MaRDI profile type: Publication
full work available at URL: j.jcss.2010.06.017
OpenAlex ID: W2110905926
cites work: Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds
cites work: Q4326630
cites work: A Boolean function requiring 3n network size
cites work: Circuit minimization problem
cites work: Explicit lower bound of 4.5n - o(n) for boolena circuits
cites work: Natural proofs
cites work: Q4231907
cites work: The number of Boolean functions computed by formulas of a given size
DOI: 10.1016/J.JCSS.2010.06.017
description: scientific article; zbMATH DE number 5882191