A simplified NP-complete satisfiability problem

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

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
• 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)

• Parameterized complexity of MaxSat above average
• 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
• 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
• Further hardness results on rainbow and strong rainbow connectivity
• 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
• 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
• 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
• Tensor network contractions for \#SAT
• 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
• Generalizations of matched CNF formulas
• Arrays of distinct representatives --- a very simple NP-complete problem
• Scheduling Bidirectional Traffic on a Path
• Boundary properties of the satisfiability problems
• On Variables with Few Occurrences in Conjunctive Normal Forms
• On the minimum size of an identifying code over all orientations of a graph
• Max NP-completeness made easy
• Title not available (Why is that?)
• Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
• The Lovász Local Lemma and Satisfiability
• Topological implications of selfish neighbor selection in unstructured peer-to-peer networks
• Assigning times to minimise reachability in temporal graphs
• Finding disjoint paths in split graphs
• The computational difficulty of manipulating an election
• On the planar split thickness of graphs
• The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
• Complexity of rainbow vertex connectivity problems for restricted graph classes
• Algorithmic complexity of list colorings
• Computational complexity of some restricted instances of 3-SAT
• Power indices and easier hard problems
• On the optimality of exact and approximation algorithms for scheduling problems
• About some UP-based polynomial fragments of SAT
• Combinatorial voter control in elections
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
• Algorithms for the maximum satisfiability problem
• Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
• Title not available (Why is that?)
• On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
• Malicious Bayesian Congestion Games
• Reachability Switching Games
• Planar 3-SAT with a clause/variable cycle
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(k\)-majority digraphs and the hardness of voting with a constant number of voters
• Some Theorems Concerning the Core Function
• On the parameterized complexity of interval scheduling with eligible machine sets
• Title not available (Why is that?)
• Polynomial Time SAT Decision for Complementation-Invariant Clause-Sets, and Sign-non-Singular Matrices
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results
• On the generalized Helly property of hypergraphs, cliques, and bicliques
• Title not available (Why is that?)
• On the Fine-Grained Complexity of Rainbow Coloring
• Approximating Minimum Representations of Key Horn Functions
• 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
• Title not available (Why is that?)
• Complexity analysis and algorithms for the program download problem
• Hamiltonian problems in directed graphs with simple row patterns
• On the edge capacitated Steiner tree problem

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)