On the complexity of \(k\)-SAT
type: Item
instance of: scholarly article
title: On the complexity of \(k\)-SAT
zbMATH Open document ID: 0990.68079
author: Russell Impagliazzo
author: Ramamohan Paturi
published in: Journal of Computer and System Sciences
publication date: 2002-08-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1642222
zbMATH Keywords: \(k\)-SAT problem
zbMATH Keywords: critical clauses
zbMATH Keywords: Sparsification Lemma
Wikidata QID: Q56018875
MaRDI profile type: Publication
full work available at URL: jcss.2000.1727
OpenAlex ID: W1985572324
cites work: Q4004078
cites work: Q4252729
cites work: Experimental results on the crossover point in random 3-SAT
cites work: Which problems have strongly exponential complexity?
cites work: An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
cites work: A note on the complexity of the chromatic number problem
cites work: Solving satisfiability in less than \(2^ n\) steps
cites work: Algorithms for maximum independent sets
cites work: Q4283247
cites work: Finding a Maximum Independent Set
DOI: 10.1006/JCSS.2000.1727
description: scientific article; zbMATH DE number 1642222