# Tag Info

## New answers tagged np-complete

### Complexity of this variant of the Monotone(+,2−) -SAT problem?

It is in P. Suppose the first clause of $F^+$ has $k_1$ variables, and the second clause has $k_2$ variables. Then there are $k_1 k_2$ ways to pick one variable from the first clause, and one ...
• 149k

### Is this sorting problem NP-complete?

You can reduce from exact-cover by $3$-sets (X3C): given a set $X$ of $3n$ elements $x_1, \dots, x_n$, and a collection $S = \{S_1, \dots, S_m\}$ of $m$ sets each containing exactly $3$ elements, is ...
• 25.7k

### Possibly Tractable Variation of Suguru Puzzles

There is a simple linear-time algorithm that determines whether it is possible or find a possible way. The algorithm for the decision problem The idea is to collect the choices at the rightmost cell ...
• 36.8k
Accepted

### Strong NP-completeness of permuted kernel problem

Let $S_1,\dots,S_{3m}$ denote the integers that form the 3-partition instance. Let $T=(S_1+\dots + S_n)/m$, so that $T$ is the target sum for each triple. As noted on Wikipedia, without loss of ...
• 149k

### Show that a problem about permutations is NP-Complete

The decision version of the minimum feedback arc set problem is as follows: given a directed graph $G=(V,E)$ with no self-loops and an integer $k$, decide whether there is a set $F \subseteq E$ of ...
• 25.7k
1 vote
Accepted

### Complexity of deciding the satisfiability of quasi-monotone 3-SAT?

The answer to the question you linked already shows how to transform a quasi-monotone 3-SAT formula into a quasi-monotone formula in which each clause has either $2$ or $3$ literals. To get a formula ...
• 25.7k
Accepted

### Is checking whether a 3-SAT is satsifiable if and only if every clause has at least 2 or all three literal set to true an NP-complete problem?

It is not currently known whether your problem is $\mathsf{NP}$-complete, but it can definitely be solved in polynomial time since it can be reduced to 2-SAT. If we assume $\mathsf{P} \neq \mathsf{NP}$...
• 25.7k

### Is it possible to train a neural network to solve NP-complete problems?

So it would be a PROOF that P=NP, isn't it? IMHO worth checking and researching... Big prize ahead! 😉
Accepted

### Understanding the Strong Exponential Time Hypothesis

That can't happen. The maximum number of distinct possible clauses is $(2n)^k = O(n^k)$, which is polynomial in $n$ (since here $k$ is fixed). Here I imagine that there notation $O^*(c^n)$ probably ...
• 149k

### A sufficient condition for unsatisfiability

No. It is not significant. $\varphi'$ is a much weaker condition. $\varphi'$ allows each clause to have either 0 or 1 satisfied literals. It's much easier to satisfy that restriction. I don't ...
• 149k

### Ιf 3SAT reduces to its complement then NP=coNP

For $A \in \mathsf{NP}$ you have $A \le_p 3SAT \le_p \overline{3SAT} \in \mathsf{co{\text -}NP}$, which implies $A \in \mathsf{co{\text -}NP}$ and hence $\mathsf{NP} \subseteq \mathsf{co{\text -}NP}$....
• 25.7k
Hint 1: $Y\in \text{co}\mathsf{NP}$ if and only if $\overline{Y}\in\mathsf{NP}$. Hint 2: $A\leqslant B$ if and only if $\overline{A}\leqslant \overline{B}$.