New answers tagged np-complete
0
votes
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 ...
D.W.♦
- 149k
0
votes
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
2
votes
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
2
votes
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 ...
D.W.♦
- 149k
2
votes
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
2
votes
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
-1
votes
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! 😉
- 1
2
votes
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 ...
D.W.♦
- 149k
0
votes
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 ...
D.W.♦
- 149k
0
votes
Ι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
0
votes
Ιf 3SAT reduces to its complement then NP=coNP
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}$.
- 11.5k
1
vote
EXACT INDSET is DP-complete
Hint: show that $\texttt{EXACT INDSET} = \texttt{INDSET}\cap L$ with: $$L = \{\langle G, k\rangle \mid G \text{ has no independent set of size }\geqslant k + 1\}$$ and show that $L$ is $\text{co}\...
- 11.5k
0
votes
$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is NP- complete
There is a somewhat trivial reduction from $L$ to $L_1$…
Consider $x\in \Sigma^*$. Then $x\in L \Leftrightarrow 0x\in L_1$. Clearly this reduction is polynomial.
I am sure that you can prove that $L_1\...
- 11.5k
Top 50 recent answers are included