Proving SAT does not have small circuits with an application to the two queries problem
type: Item
instance of: scholarly article
title: Proving SAT does not have small circuits with an application to the two queries problem
zbMATH Open document ID: 1135.68022
author: Aduri Pavan
author: Samik Sengupta
author: Lance Fortnow
published in: Journal of Computer and System Sciences
publication date: 2008-03-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5246769
zbMATH Keywords: SAT
zbMATH Keywords: small circuits
zbMATH Keywords: two queries
MaRDI profile type: MaRDI publication profile
full work available at URL: j.jcss.2007.06.017
OpenAlex ID: W2013387708
cites work: A relationship between difference hierarchies and relativized polynomial hierarchies
cites work: Oracles and queries that are sufficient for exact learning
cites work: Two queries
cites work: More on BPP and the polynomial-time hierarchy
cites work: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
cites work: Foundations of Cryptography
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
cites work: The complexity of optimization problems
cites work: Symmetric alternation captures BPP
DOI: 10.1016/J.JCSS.2007.06.017
description: scientific article; zbMATH DE number 5246769