The Complexity of Satisfiability of Small Depth Circuits
type: Item
instance of: scholarly article
title: The Complexity of Satisfiability of Small Depth Circuits
zbMATH Open document ID: 1273.68159
DOI: 10.1007/978-3-642-11269-0_6
author: Chris Calabro
author: Russell Impagliazzo
author: Ramamohan Paturi
published in: Parameterized and Exact Computation
publication date: 2010-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q12
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 5658361
MaRDI profile type: Publication
full work available at URL: 978-3-642-11269-0 6
OpenAlex ID: W1576180980
cites work: The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
cites work: Theory and Applications of Satisfiability Testing
cites work: Q4228473
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: An improved exponential-time algorithm for k -SAT
cites work: Q4484662
cites work: Exponential lower bounds for depth three Boolean circuits
cites work: An algorithm for the satisfiability problem of formulas in conjunctive normal form
cites work: Q4164821
description: scientific article