A simplified NP-complete satisfiability problem

DOI10.1016/0166-218X(84)90081-7zbMATH Open0534.68028OpenAlexW2003979824WikidataQ127443560 ScholiaQ127443560MaRDI QIDQ790612FDOQ790612

Authors: Craig A. Tovey 

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

Recommendations

• The complexity of satisfiability problems
• A simplified NP-complete MAXSAT problem
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• scientific article; zbMATH DE number 152108
• scientific article; zbMATH DE number 515744

zbMATH Keywords

NP-completenesspropositional logicsatisfiability problempolynomial-time decision algorithmsets 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)

Cites Work

• Title not available (Why is that?)
• The Euclidean traveling salesman problem is NP-complete
• On the Complexity of Timetable and Multicommodity Flow Problems
• On Representatives of Subsets
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Malicious Bayesian Congestion Games
• Reachability Switching Games
• Tight lower bounds for the complexity of multicoloring
• Planar 3-SAT with a clause/variable cycle
• \(k\)-majority digraphs and the hardness of voting with a constant number of voters
• (2/2/3)-SAT problem and its applications in dominating set problems
• On the generalized Helly property of hypergraphs, cliques, and bicliques
• Sliding window temporal graph coloring
• Enforcing efficient equilibria in network design games via subsidies
• Optimality program in segment and string graphs
• Destroying Bicolored $P_3$s by Deleting Few Edges
• Complexity of Gröbner basis detection and border basis detection
• Domination problems with no conflicts
• Packing Arc-Disjoint Cycles in Tournaments
• Complexity analysis and algorithms for the program download problem
• Reversed resolution in reducing general satisfiability problem
• Hamiltonian problems in directed graphs with simple row patterns
• On the edge capacitated Steiner tree problem
• Distributed Evacuation in Graphs with Multiple Exits
• The \textsc{Red-Blue Separation} problem on graphs
• Finding Temporal Paths Under Waiting Time Constraints.
• Title not available (Why is that?)
• Solving the resolution-free SAT problem by submodel propagation in linear time
• Tensor network contractions for \#SAT
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• Title not available (Why is that?)
• Coloring temporal graphs
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• Title not available (Why is that?)
• The \(k\)-SATISFIABILITY problem remains NP-complete for dense families
• The \textsc{red-blue separation} problem on graphs
• Selecting and covering colored points
• Efficient exponential-time algorithms for edit distance between unordered trees
• Non-strict Temporal Exploration
• Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
• Tight complexity lower bounds for integer linear programming with few constraints
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• On the complexity of the partner units decision problem
• Errata for the paper ``Predecessor existence problems for finite discrete dynamical systems.
• Approximately fair cost allocation in metric traveling salesman games
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Title not available (Why is that?)
• The inequality-satisfiability problem
• Packing arc-disjoint cycles in tournaments
• Maximum reachability preserved graph cut
• Title not available (Why is that?)
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• On the fine-grained complexity of rainbow coloring
• On the parameterized complexity of \((k,s)\)-SAT
• Title not available (Why is that?)
• Finding temporal paths under waiting time constraints
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• On finding short resolution refutations and small unsatisfiable subsets
• A CNF Class Generalizing Exact Linear Formulas
• The Minimum Satisfiability Problem
• Discriminating Codes in Geometric Setups
• Deciding Relaxed Two-Colourability: A Hardness Jump
• Strong cliques and equistability of EPT graphs
• The minimum broadcast time problem for several processor networks
• Balanced independent and dominating sets on colored interval graphs
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Bounding the running time of algorithms for scheduling and packing problems
• On the complexity of role colouring planar graphs, trees and cographs
• The complexity of satisfiability problems
• Path-driven orientation of mixed graphs
• Title not available (Why is that?)
• DNF tautologies with a limited number of occurrences of every variable
• The Complexity of Very Simple Boolean Formulas with Applications
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• A perspective on certain polynomial-time solvable classes of satisfiability
• Scheduling bidirectional traffic on a path
• Further hardness results on rainbow and strong rainbow connectivity
• Deleting edges to restrict the size of an epidemic in temporal networks
• Deleting edges to restrict the size of an epidemic in temporal networks
• Scheduling tasks on two processors with deadlines and additional resources
• Nested satisfiability
• Recognition of \(q\)-Horn formulae in linear time
• A simplified NP-complete MAXSAT problem
• On the maximum disjoint paths problem on edge-colored graphs
• Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
• On variables with few occurrences in conjunctive normal forms
• An improved lower bound for rank four scheduling
• Rainbow graph splitting
• Clustering with lower-bounded sizes. A general graph-theoretic framework
• On the complexity of algorithms for detecting \(k\)-length negative cost cycles
• The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
• The complexity of the falsifiability problem for pure implicational formulas
• Complexity of partial satisfaction. II.
• Load balancing for redundant storage strategies: Multiprocessor scheduling with machine eligibility
• Disproof of the neighborhood conjecture with implications to SAT
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• Linear CNF formulas and satisfiability
• Computing an evolutionary ordering is hard
• It is difficult to tell if there is a Condorcet spanning tree
• Operads of finite posets
• A special planar satisfiability problem and a consequence of its NP- completeness
• Local optimization on graphs
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• Counting the number of solutions for instances of satisfiability

This page was built for publication: A simplified NP-complete satisfiability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q790612)