On the complexity of $k$-SAT

DOI10.1006/JCSS.2000.1727zbMath0990.68079OpenAlexW1985572324WikidataQ56018875 ScholiaQ56018875MaRDI QIDQ5943094

Russell Impagliazzo, Ramamohan Paturi

Publication date: 14 August 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2000.1727

zbMATH Keywords

$k$-SAT problem critical clauses Sparsification Lemma

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (only showing first 100 items - show all)

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Complexity of $C_k$-coloring in hereditary classes of graphs ⋮ Unnamed Item ⋮ The diameter of AT‐free graphs ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ A note on hardness of computing recursive teaching dimension ⋮ On the Complexity of String Matching for Graphs ⋮ Further improvements for SAT in terms of formula length ⋮ On the complexity of the storyplan problem ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ Inapproximability of positive semidefinite permanents and quantum state tomography ⋮ The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ Algorithms and complexity on indexing founder graphs ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Computing and listing avoidable vertices and paths ⋮ Solving cut-problems in quadratic time for graphs with bounded treewidth ⋮ A survey on rainbow (vertex-)index of graphs ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ DAG-$ \Sigma $: a DAG-based sigma protocol for relations in CNF ⋮ How to find a good explanation for clustering? ⋮ Non-interactive universal arguments ⋮ Disentangling the computational complexity of network untangling ⋮ FPT algorithms for packing $k$-safe spanning rooted sub(di)graphs ⋮ Counting Small Induced Subgraphs with Hereditary Properties ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ Computing and listing avoidable vertices and paths ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Unnamed Item ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Computing maximum matchings in temporal graphs ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Using a Geometric Lens to Find $\boldsymbol{k}$-Disjoint Shortest Paths ⋮ Unnamed Item ⋮ An FPT algorithm for bipartite vertex splitting ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Computing a partition function of a generalized pattern-based energy over a semiring ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ On computing large temporal (unilateral) connected components ⋮ $\mathrm{mR}_{\mathrm{LWE}}$-CP-ABE: a revocable CP-ABE for post-quantum cryptography ⋮ Communication and information complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Characterizing polynomial Ramsey quantifiers ⋮ Unnamed Item ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Many Visits TSP Revisited ⋮ A Polynomial Kernel for Line Graph Deletion ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ 1-extendability of independent sets ⋮ Semiring reasoning frameworks in AI and their computational complexity ⋮ Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs ⋮ Certified Core-Guided MaxSAT Solving ⋮ Proportionally Fair Matching with Multiple Groups ⋮ Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Planning and learning in partially observable systems via filter stability ⋮ The complexity of pattern counting in directed graphs, parameterised by the outdegree ⋮ Parameterized aspects of triangle enumeration ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Optimality program in segment and string graphs ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Parameterized complexity of min-power asymmetric connectivity ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ Graph square roots of small distance from degree one graphs ⋮ The perfect matching cut problem revisited ⋮ Fine-grained complexity of safety verification ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ The perfect matching cut problem revisited ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Parameterized complexity of diameter ⋮ Matching cut in graphs with large minimum degree ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Super Strong ETH ⋮ Computational Complexity of Computing Symmetries in Finite-Domain Planning ⋮ Unnamed Item ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Calculation of Discrepancy Measures and Applications ⋮ Maximal Common Subsequence Algorithms ⋮ Linear-Time Algorithm for Long LCF with k Mismatches ⋮ On miniaturized problems in parameterized complexity theory ⋮ An improved upper bound for SAT ⋮ Separating OR, SUM, and XOR circuits ⋮ A faster fixed parameter algorithm for two-layer crossing minimization ⋮ Efficiently approximating color-spanning balls ⋮ A substring-substring LCS data structure

Cites Work

This page was built for publication: On the complexity of $k$-SAT

On the complexity of \(k\)-SAT