New answers tagged

1

What is $K$? If $K$ is constant then this problem is in $P$. The number of paths with source s is less than $\binom{n-1}{K} \in O(n^K)$. So one can enumerate these paths in polynomial time. At first, we will construct an algorithm, that finds one path from s to t with length $\ge K$ function has_paths(G,s,t,K): { for all paths (s=v_1,v_2,...v_{K_1}) in G\{t}...


0

Here is a reduction from NAE3SAT to your problem. Given an instance $C_1 \lor \cdots \lor C_m$ of NAE3SAT, we construct an instance of your problem as follows: $S$ is the set of literals. $C$ consists of the sets $C_1,\ldots,C_m$ (considered as sets of literals) together with the sets $\{ x_i, \lnot x_i \}$ for each variable $x_i$. A valid solution to this ...


1

This problem is not in NP because it is not a decision problem. Instead it would lie in #P because you want it to output the number of accepting paths of a non-deterministic machine. You can look for some #P problems but I don't think each NP problem has a studied equivalent there. If you changed it into a decision problem of: 'Is there more (or less) than $...


0

Based on the review that I received, I fixed the second part of the proof. I would like to know if it's correct now, I would appreciate your input on this. Let us construct an NP machine M for $\overline{L}$ that gets the input x. Since we know L is accepted by a nice machine, let N be the nice machine for L. 2.1. The machine M guesses one particular path ...


0

Regarding your answer, here are some corrections. For part (1), your argument is partially correct but incorrectly stated. For part (2), your argument is not correct. Your biggest mistake is in the way you describe nondeterministic Turing machines. Remember that a nondeterministic Turing machine does not magically have access to all possible paths at once -- ...


0

Can I prove the first direction in the following way? Let us construct an NP machine for L that gets the input x. 1.1 The machine guesses all the possible paths for the given input. 1.2 The machine checks if any non-quit path exists. 1.3 The machine checks whether the value of all the 'Accepts' and 'Rejects' paths are equal. If both 1.2 and 1.3 are true, ...


1

The provided answer is not valid to the question, as far as I know. Your rebuttal that there could be some other clever certificate is totally reasonable. However, is it possible that you misunderstood the question? The question may be asking why this problem is not straightforwardly in NP-complete, in which case the "obvious" certificate would ...


2

To prove the reverse direction you need to show that if there exist a subsequence $S_1$ in $(a_1+K,a_2+K,\dotsc,a_n+K,K,\dotsc,K)$ that sums to $T+nK$, then there is a subsequence $S_2$ in $(a_1,\dotsc,a_n)$ that sums to $T$. The proof would become easy if we assume that $S_1$ only contains $n$ elements. If that happens, then the above statement holds. (hope ...


4

Instead of $\mathsf{TILING}$, I proved that $\mathsf{RectangleTILING}$ is $\mathsf{NP}$-complete by finding a reduction from $\mathsf{3SAT}$. Problem $\mathsf{RectangleTILING}$: Input: a set $T$ of tiles, two dimensions $M$ and $N$ (in binary or unary, it doesn't matter); Question: is it possible to cover a rectangle of size $N\times M$ with tiles of $T$? ...


1

Though your definition of $E$ is not clear. I am assuming that $E = \{(x,y) \mid x \in W \textrm{ and } y \in W'\} \, \cup \{(x,y) \mid x,y \in W \textrm{ and } (x,y) \notin F\}$. In other words, $E$ contain all edges between sets $W$ and $W'$, and the edges that are not in $F$. Proof Forward Direction: Suppose $H$ contains a clique of size at most $k$. Let ...


Top 50 recent answers are included