Computational complexity of some restricted instances of 3-SAT
type: Item
instance of: scholarly article
title: Computational complexity of some restricted instances of 3-SAT
zbMATH Open document ID: 1111.68044
author: Piotr Berman
author: Marek Karpinski
author: Alex Scott
published in: Discrete Applied Mathematics
publication date: 2007-04-13T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 5142435
MaRDI profile type: Publication
full work available at URL: j.dam.2006.07.009
OpenAlex ID: W2038784300
cites work: The complexity of theorem-proving procedures
cites work: On the r,s-SAT satisfiability problem and a conjecture of Tovey
cites work: Q4375762
cites work: One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
cites work: Tricritical points in random combinatorics: the -SAT case
cites work: Determining computational complexity from characteristic ‘phase transitions’
cites work: A simplified NP-complete satisfiability problem
cites work: (2+\(f\)(\(n\)))-SAT and its properties.
DOI: 10.1016/J.DAM.2006.07.009
description: scientific article; zbMATH DE number 5142435