A simplified NP-complete satisfiability problem
From MaRDI portal
Publication:790612
DOI10.1016/0166-218X(84)90081-7zbMATH Open0534.68028OpenAlexW2003979824WikidataQ127443560 ScholiaQ127443560MaRDI QIDQ790612FDOQ790612
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
NP-completenesspropositional logicsatisfiability problempolynomial-time decision algorithmsets of clauses
Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to mathematical logic and foundations (03-04)
Cites Work
Cited In (only showing first 100 items - show all)
- Malicious Bayesian Congestion Games
- Reachability Switching Games
- Planar 3-SAT with a clause/variable cycle
- \(k\)-majority digraphs and the hardness of voting with a constant number of voters
- The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results
- On the generalized Helly property of hypergraphs, cliques, and bicliques
- On the Fine-Grained Complexity of Rainbow Coloring
- 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
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding Temporal Paths Under Waiting Time Constraints.
- Title not available (Why is that?)
- Tight Lower Bounds for List Edge Coloring
- Solving the resolution-free SAT problem by submodel propagation in linear time
- Title not available (Why is that?)
- Coloring temporal graphs
- Parameterized complexity of finding a spanning tree with minimum reload cost diameter
- On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}
- Title not available (Why is that?)
- The \(k\)-SATISFIABILITY problem remains NP-complete for dense families
- The \textsc{red-blue separation} problem on graphs
- Tight Lower Bounds for the Complexity of Multicoloring
- 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
- 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?)
- On the parameterized complexity of \((k,s)\)-SAT
- Title not available (Why is that?)
- Finding temporal paths under waiting time constraints
- 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
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)
