A simplified NP-complete satisfiability problem

DOI10.1016/0166-218X(84)90081-7zbMath0534.68028OpenAlexW2003979824MaRDI QIDQ790612

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(84)90081-7

zbMATH Keywords

propositional logic NP-completeness satisfiability problem polynomial-time decision algorithm sets of clauses

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to mathematical logic and foundations (03-04)

Related Items

Algorithmic complexity of list colorings, On finding short resolution refutations and small unsatisfiable subsets, Destroying Bicolored $P_3$s by Deleting Few Edges, A special planar satisfiability problem and a consequence of its NP- completeness, Scheduling tasks on two processors with deadlines and additional resources, Balanced independent and dominating sets on colored interval graphs, Recognition of $q$-Horn formulae in linear time, The maximum infection time of the $P_3$ convexity in graphs with bounded maximum degree, A simplified NP-complete MAXSAT problem, Scheduling Bidirectional Traffic on a Path, On the optimality of exact and approximation algorithms for scheduling problems, On the Fine-Grained Complexity of Rainbow Coloring, Hamiltonian problems in directed graphs with simple row patterns, Satisfiability with index dependency, Computing an evolutionary ordering is hard, It is difficult to tell if there is a Condorcet spanning tree, The \textsc{red-blue separation} problem on graphs, Computational complexity of some restricted instances of 3-SAT, Local optimization on graphs, Deleting edges to restrict the size of an epidemic in temporal networks, Packing arc-disjoint cycles in tournaments, On the complexity of the partner units decision problem, Disproof of the neighborhood conjecture with implications to SAT, Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy, Parameterized complexity of MaxSat above average, Tensor network contractions for \#SAT, Unnamed Item, On the complexity of role colouring planar graphs, trees and cographs, A CNF Class Generalizing Exact Linear Formulas, On the generalized Helly property of hypergraphs, cliques, and bicliques, Maximum reachability preserved graph cut, Can local optimality be used for efficient data reduction?, Further hardness results on rainbow and strong rainbow connectivity, On the maximum disjoint paths problem on edge-colored graphs, Topological implications of selfish neighbor selection in unstructured peer-to-peer networks, Assigning times to minimise reachability in temporal graphs, On the parameterized complexity of $(k,s)$-SAT, Efficient exponential-time algorithms for edit distance between unordered trees, The parameterized complexity of $k$-flip local search for SAT and MAX SAT, On the edge capacitated Steiner tree problem, Errata for the paper ``Predecessor existence problems for finite discrete dynamical systems., Manipulation can be hard in tractable voting systems even for constant-sized coalitions, Approximately fair cost allocation in metric traveling salesman games, Boundary properties of the satisfiability problems, On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}, Path-driven orientation of mixed graphs, Reachability Switching Games, Finding disjoint paths in split graphs, Finding temporal paths under waiting time constraints, The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles, The minimum broadcast time problem for several processor networks, Deciding Relaxed Two-Colourability: A Hardness Jump, On Variables with Few Occurrences in Conjunctive Normal Forms, Coloring temporal graphs, On the planar split thickness of graphs, Complexity of rainbow vertex connectivity problems for restricted graph classes, About some UP-based polynomial fragments of SAT, Domination problems with no conflicts, Operads of finite posets, On the minimum size of an identifying code over all orientations of a graph, Complexity of Gröbner basis detection and border basis detection, A Complexity Dichotomy for the Coloring of Sparse Graphs, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Computing unsatisfiable $k$-SAT instances with few occurrences per variable, Solving the resolution-free SAT problem by submodel propagation in linear time, Generalizations of matched CNF formulas, Rainbow graph splitting, Unnamed Item, Unnamed Item, Counting the number of solutions for instances of satisfiability, Malicious Bayesian Congestion Games, Unnamed Item, Unnamed Item, An improved lower bound for rank four scheduling, Clustering with lower-bounded sizes. A general graph-theoretic framework, Approximating the minimum clique cover and other hard problems in subtree filament graphs, Sliding window temporal graph coloring, Selecting and covering colored points, The Monotone Satisfiability Problem with Bounded Variable Appearances, On the complexity of algorithms for detecting $k$-length negative cost cycles, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Algorithms for the maximum satisfiability problem, Packing Arc-Disjoint Cycles in Tournaments, The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results, The Lovász Local Lemma and Satisfiability, Using clausal graphs to determine the computational complexity of $k$-bounded positive one-in-three SAT, Linear CNF formulas and satisfiability, On the r,s-SAT satisfiability problem and a conjecture of Tovey, The computational difficulty of manipulating an election, $k$-majority digraphs and the hardness of voting with a constant number of voters, Distributed Evacuation in Graphs with Multiple Exits, DNF tautologies with a limited number of occurrences of every variable, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Enforcing efficient equilibria in network design games via subsidies, Combinatorial voter control in elections, A perspective on certain polynomial-time solvable classes of satisfiability, Complexity analysis and algorithms for the program download problem, The $k$-SATISFIABILITY problem remains NP-complete for dense families, Strong cliques and equistability of EPT graphs, Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter, Non-strict Temporal Exploration, When removing an independent set is optimal for reducing the chromatic number, SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption, On the hull number on cycle convexity of graphs, Parameterized complexity of finding a spanning tree with minimum reload cost diameter, On finding the best and worst orientations for the metric dimension, Complexity and approximation for discriminating and identifying code problems in geometric setups, The Exact Subset MultiCover problem, Packing arc-disjoint cycles in oriented graphs, The \textsc{Red-Blue Separation} problem on graphs, On the complexity of minimum maximal acyclic matchings, Refined computational complexities of hospitals/residents problem with regional caps, Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles, Tight Lower Bounds for the Complexity of Multicoloring, Collaborative delivery on a fixed path with homogeneous energy-constrained agents, Discriminating Codes in Geometric Setups, Finding Temporal Paths Under Waiting Time Constraints., Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility, Optimality program in segment and string graphs, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Your rugby mates don't need to know your colleagues: triadic closure with edge colors, Unnamed Item, Planar 3-SAT with a clause/variable cycle, Tight Lower Bounds for List Edge Coloring, Approximating Minimum Representations of Key Horn Functions

Cites Work