New answers tagged np
1
Suppose that $\mathsf{P}=\mathsf{NP}$. You can show that the contrapositive statement is true: If $A\neq \emptyset$ and $A \neq \Sigma^*$ then $A$ is $\mathsf{NP}$-hard.
Consider any language in $B \in \mathsf{NP}$. We will provide a poly-time computable function such that $x \in B \iff f(x) \in A$, thus showing $B \le_p A$. This will immediately imply that $...
0
To solve such a problem, you should have more of a "programming" point of view rather than a "Turing machine" point of view.
Sure, $\mathsf{NP}$ is defined considering the executing time of a Turing machine, however we, human beings, are not made to think in TM. You could think of it as the same difference between programming in a very ...
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
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, ...
0
NP is not the subset of co-NP unless we assume A be an NP-Complete problem and A∈ co-NP (which is not possible) then we can say all NP problems are a subset of co-NP problems since we can reduce all NP problems to problem A which is NP-complete it follows that for every problem in NP, we can construct a non-deterministic Turing machine that decides its ...
11
However, if P != NP then both NP and coNP are in exptime and not better.
This is not neccesarily true. It just means that some NP (and coNP) problems cannot be solved in polynomial time. This is not necessarily the same as requiring exponential time (e.g. $n^{\log n}$ is not polynomial but also not exponential).
If P != NP then it makes sense that NP = ...
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 ...
Top 50 recent answers are included