On the complexity of \(k\)-SAT

From MaRDI portal

Publication:5943094

Jump to:navigation, search

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

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, Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails, On the copy complexity of width 3 Horn constraint systems, Structural parameterizations of clique coloring, Assigning channels via the meet-in-the-middle approach, On residual approximation in solution extension problems, Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases, The label cut problem with respect to path length and label frequency, Block interpolation: a framework for tight exponential-time counting complexity, Local reduction, Strong partial clones and the time complexity of SAT problems, Fixed-parameter tractability and lower bounds for stabbing problems, Covering problems for partial words and for indeterminate strings, Quantum one-way permutation over the finite field of two elements, An exponential time 2-approximation algorithm for bandwidth, Parameterized maximum path coloring, Parameterized complexity of MaxSat above average, On exact algorithms for the permutation CSP, Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis, Towards NP-P via proof complexity and search, Parameterized and subexponential-time complexity of satisfiability problems and applications, On the hardness of labeled correlation clustering problem: a parameterized complexity view, Convexity in partial cubes: the hull number, Dominating set based exact algorithms for \(3\)-coloring, Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis, Fixing improper colorings of graphs, Catalytic space: non-determinism and hierarchy, On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}, The P3 infection time is W[1-hard parameterized by the treewidth], Cliques enumeration and tree-like resolution proofs, Complexity and lowers bounds for power edge set problem, (2+\(f\)(\(n\)))-SAT and its properties., Computational complexity aspects of point visibility graphs, Fine-grained dichotomies for the Tutte plane and Boolean \#CSP, Limitations of semidefinite programs for separable states and entangled games, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs, \textsc{Max-Cut} parameterized above the Edwards-Erdős bound, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, Finding temporal paths under waiting time constraints, Coloring invariants of knots and links are often intractable, Refining complexity analyses in planning by exploiting the exponential time hypothesis, Fixed-parameter algorithms for DAG partitioning, On optimal approximability results for computing the strong metric dimension, An initial study of time complexity in infinite-domain constraint satisfaction, Dealing with 4-variables by resolution: an improved MaxSAT algorithm, A tight algorithm for strongly connected Steiner subgraph on two terminals with demands, Saving colors and max coloring: some fixed-parameter tractability results, Exact exponential algorithms to find tropical connected sets of minimum size, On the parameterized complexity of reconfiguration problems, On the approximability of robust network design, Scheduling partially ordered jobs faster than \(2^n\), A tight lower bound for planar Steiner orientation, Pattern matching and consensus problems on weighted sequences and profiles, The inverse Voronoi problem in graphs. I: Hardness, Temporal vertex cover with a sliding time window, Bounded-depth succinct encodings and the structure they imply on graphs, Stable matching games: manipulation via subgraph isomorphism, Complexity of token swapping and its variants, Approximability of clique transversal in perfect graphs, A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph, Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization, Parameterized counting of partially injective homomorphisms, On the computational complexity of vertex integrity and component order connectivity, A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Reducing graph transversals via edge contractions, Sliding window temporal graph coloring, A unifying model for locally constrained spanning tree problems, A linear edge kernel for two-layer crossing minimization, Boolean functional synthesis: hardness and practical algorithms, Hitting forbidden induced subgraphs on bounded treewidth graphs, Many-visits TSP revisited, Fine-grained complexity of rainbow coloring and its variants, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms, The complexity of dependency detection and discovery in relational databases, Structurally parameterized \(d\)-scattered set, Practical complexities of probabilistic algorithms for solving Boolean polynomial systems, A polynomial kernel for diamond-free editing, Learn to relax: integrating \(0-1\) integer linear programming with pseudo-Boolean conflict-driven search, Dual parameterization of weighted coloring, CNF satisfiability in a subspace and related problems, (Sub)linear kernels for edge modification problems toward structured graph classes, Colouring non-even digraphs, Moderate exponential-time algorithms for scheduling problems, Parameterized complexity of list coloring and max coloring, Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters, Fine-grained parameterized complexity analysis of graph coloring problems, Fine-grained complexity theory: conditional lower bounds for computational geometry, Algorithms and almost tight results for 3-colorability of small diameter graphs, \(k\)-approximate quasiperiodicity under Hamming and edit distance, Enumeration of maximal common subsequences between two strings, A fast algorithm for SAT in terms of formula length, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Simultaneous Approximation of Constraint Satisfaction Problems, Local Reductions, The Complexity of Problems in P Given Correlated Instances, Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, On the Equivalence among Problems of Bounded Width, Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks, Target Set Selection in Dense Graph Classes, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Known Algorithms for Edge Clique Cover are Probably Optimal, Improved MaxSAT Algorithms for Instances of Degree 3, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Counting Small Induced Subgraphs Satisfying Monotone Properties, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False), Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments, Interview with Don Knuth, The Time Complexity of Constraint Satisfaction, Unnamed Item, Unnamed Item, Tight Lower Bounds for the Complexity of Multicoloring, Unnamed Item, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Finding Points in General Position, Unnamed Item, Unnamed Item, Unnamed Item, Tight Hardness Results for Consensus Problems on Circular Strings and Time Series, Finer Tight Bounds for Coloring on Clique-Width, Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Beyond Outerplanarity, Approximate Clustering with Same-Cluster Queries, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, The Constant Inapproximability of the Parameterized Dominating Set Problem, On Algorithms Employing Treewidth for $L$-bounded Cut Problems, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Dual parameterization of Weighted Coloring, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, INCOMPLETENESS IN THE FINITE DOMAIN, A Polynomial Kernel for Diamond-Free Editing, On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Parameterized Complexity of the Workflow Satisfiability Problem, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Longest common substring made fully dynamic, Unnamed Item, Fast approximation of eccentricities and distances in hyperbolic graphs, Faster Pseudopolynomial Time Algorithms for Subset Sum, Finding Detours is Fixed-Parameter Tractable, Unnamed Item, Variable Influences in Conjunctive Normal Forms, k-SAT Is No Harder Than Decision-Unique-k-SAT, Testing the Complexity of a Valued CSP Language, Counting Answers to Existential Questions, Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs, Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems, Short Proofs Are Hard to Find, Fine-Grained Reductions and Quantum Speedups for Dynamic Programming., A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties, Imperfect gaps in Gap-ETH and PCPs, Fine-Grained Complexity Theory (Tutorial), The Orthogonal Vectors Conjecture for Branching Programs and Formulas, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, Path Contraction Faster Than 2^n, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Hardness of bounded distance decoding on lattices in lp norms, Unnamed Item, Comparing Degenerate Strings, Balanced Hashing, Color Coding and Approximate Counting, The Complexity of Satisfiability of Small Depth Circuits, An Exponential Time 2-Approximation Algorithm for Bandwidth, Time Complexity of Constraint Satisfaction via Universal Algebra, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy, Fine-Grained Complexity of Rainbow Coloring and its Variants., On the Complexity of Bounded Context Switching., Tight Lower Bounds for List Edge Coloring, More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints, Parameterized Approximation Algorithms for Bidirected Steiner Network Problems, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2, Unnamed Item, Unnamed Item, Unnamed Item, 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, Efficient algorithms for measuring the funnel-likeness of DAGs, 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, Length-bounded cuts: proper interval graphs and structural parameters, Quantum de Finetti theorems under local measurements with applications, Scheduling lower bounds via AND subset sum, Parameterized Maximum Path Coloring, Efficient computation of sequence mappability, A note on the complexity of computing the number of reachable vertices in a digraph, On the Fine-Grained Complexity of Rainbow Coloring, Streaming deletion problems parameterized by vertex cover, Completeness, approximability and exponential time results for counting problems with easy decision version, Parameterized Complexity and Subexponential-Time Computability, Fixed-Parameter Tractability of Treewidth and Pathwidth, Studies in Computational Aspects of Voting, On Directed Steiner Trees with Multiple Roots, Complexity and approximation results on the shared transportation problem, Local reduction and the algebraic cryptanalysis of the block cipher GOST, Partition into triangles on bounded degree graphs, Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis, On the complexity of finding shortest variable disjunction branch-and-bound proofs, Approximating the geometric edit distance, Graph searches and their end vertices, A note on the concrete hardness of the shortest independent vector in lattices, 1-extendability of independent sets, Learning from positive and negative examples: dichotomies and parameterized algorithms, A faster diameter problem algorithm for a chordal graph, with a connection to its center problem, The graph motif problem parameterized by the structure of the input graph, A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs, Finding a maximum minimal separator: graph classes and fixed-parameter tractability, Hitting forbidden subgraphs in graphs of bounded treewidth, Strong ETH and resolution via games and the multiplicity of strategies, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, On the satisfiability of quantum circuits of small treewidth, New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), On the Exact Complexity of Polyomino Packing, Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size, Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Longest common substring with approximately \(k\) mismatches, Mean isoperimetry with control on outliers: exact and approximation algorithms, A computation model with automatic functions and relations as primitive operations, A Dichotomy Result for Ramsey Quantifiers, A general purpose algorithm for counting simple cycles and simple paths of any length, The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds, Subquadratic algorithms for succinct stable matching, Fast exact algorithms for some connectivity problems parameterized by clique-width, Super-polynomial approximation branching algorithms, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, On the Variable Hierarchy of First-Order Spectra, On the complexity of restoring corrupted colorings, Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms, On the exact complexity of polyomino packing, On the optimality of pseudo-polynomial algorithms for integer programming, FPT and kernelization algorithms for the induced tree problem, A tight lower bound for edge-disjoint paths on planar DAGs, A multistage view on 2-satisfiability, On the complexity of detecting hazards, Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time, Exact capacitated domination: on the computational complexity of uniqueness, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, The complexity of LSH feasibility, Unnamed Item, Minimum label \(s\)-\(t\) cut has large integrality gaps, Parsimonious formulations for low-diameter clusters, Polynomial treedepth bounds in linear colorings, Path Contraction Faster than $2^n$, Waypoint routing on bounded treewidth graphs, On Variants of the Spanning Star Forest Problem, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, Satisfiability Certificates Verifiable in Subexponential Time, Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms, Approximation and hardness of shift-Bribery, Four decades of research on the open-shop scheduling problem to minimize the makespan, Hardness results for approximate pure Horn CNF formulae minimization, Edge deletion problems: branching facilitated by modular decomposition, Exact algorithms for the Hamiltonian cycle problem in planar graphs, On the parameterized complexity of the geodesic hull number, A fixed-parameter perspective on \#BIS, Tight conditional lower bounds for longest common increasing subsequence, On the Exact Complexity of Evaluating Quantified k-CNF, Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting, Domino sequencing: scheduling with state-based sequence-dependent setup times, A domination algorithm for {0,1}-instances of the travelling salesman problem, Subexponential algorithms for variants of the homomorphism problem in string graphs, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Computing a Nonnegative Matrix Factorization---Provably, Minimum fill-in: inapproximability and almost tight lower bounds, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers, \(H\)-colouring \(P_t\)-free graphs in subexponential time, Maximal common subsequence algorithms, Computing the chromatic number using graph decompositions via matrix rank, Fixed-parameter complexity and approximability of norm maximization, Pure Nash equilibria in graphical games and treewidth, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Hardness of approximation for knapsack problems, Sitting closer to friends than enemies, revisited, Faster exponential-time algorithms in graphs of bounded average degree, A complexity and approximation framework for the maximization scaffolding problem, A refined branching algorithm for the maximum satisfiability problem

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:5943094&oldid=12096981"