New answers tagged

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 ...
  • 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 ...
  • 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! 😉
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 ...
  • 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 ...
  • 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