Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with np
Search options answers only
not deleted
user 755
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
1
vote
Accepted
Does P not NP imply NP COMPLETE disjoint from RP?
If additionally $P \ne NP$, then it follows that $RP \ne NP$.
Yes, if $RP \ne NP$, then $NPC \cap RP = \emptyset$. …
D.W.♦
- 166k
2
votes
Is it incorrect too say that this function problem cannot be in $FNP$?
When we say that an algorithm runs in polynomial time, we mean that its running time is at most a polynomial of the length of the input. I assume the input is an integer $n$. The usual way to repres …
D.W.♦
- 166k
1
vote
Two transition functions def of NP
You can choose from among four options by first making one binary choice, then making a second binary choice; there are $2\times 2=4$ total possible outcomes, each of which can be mapped to one of tho …
D.W.♦
- 166k
1
vote
Accepted
A decision procedure for PCP
A decision procedure must always terminate. Your procedure never terminates if there is no possible way to make a match. If you run your procedure for a year and don't find any match, do you conclud …
D.W.♦
- 166k
2
votes
Accepted
"Given an algorithm, decide whether it runs in polynomial time" is this problem in NP?
No. If the problem was polynomial-time verifiable, it would be solvable in exponential time, and thus decidable; but we already know that is not decidable.
Why in exponential time? Because $V$ runs …
D.W.♦
- 166k
2
votes
Why is the difference of two NP-complete languages not in NP?
The difference between two $\mathsf{NP}$ languages is not necessarily in $\mathsf{NP}$. (It might be, but it might not be.) … there exists languages $A,B \in \mathsf{NP}$ such that $A\setminus B\notin \mathsf{NP}$. …
D.W.♦
- 166k
4
votes
Showing that CLIQUE can be verified in polynomial time
The latter problem is in NP. NP is a class of decision problems, so it doesn't make sense to ask whether an optimization problem is in NP; that's only meaningful for decision problems. … Any textbook or standard resource on NP should explain the difference between decision problems vs. optimization problems in more depth. …
D.W.♦
- 166k
5
votes
Accepted
If P = NP, then is NP = FNP?
No, it doesn't mean that FNP = NP. NP is a class of decision problems; FNP is a class of function problems. See the definition of FNP (e.g., on Wikipedia, or in any textbook). … Therefore, the elements of NP have a different type than the elements of FNP. …
D.W.♦
- 166k
1
vote
NP problems with exponentially complex average time solution?
It's possible that $P \ne NP$ but still all problems can be solved in subexponential time, as Yuval states. …
D.W.♦
- 166k
4
votes
Is finding all primes less than n, doable in polynomial time?
No, it doesn't. There are exponentially many primes less than $n$, so you can't enumerate them in polynomial time.
D.W.♦
- 166k
1
vote
Accepted
Karp hardness of digraph coloring without monochromatic dicycle
Yes, it is NP-complete. There appears to be a straightforward reduction from graph coloring. …
D.W.♦
- 166k
0
votes
If X is poly-time reducible to Y and X is in P, then Y is in P
Your argument is wrong. There is no guarantee that there exists a blackbox that runs in polynomial time.
If I had \$10, I could buy you a coffee. But that doesn't imply that I have \$10.
D.W.♦
- 166k
1
vote
1
vote
Accepted
Proof that nondeterministic TM runs in exponential time
Assuming $k$ is represented in binary, it takes $\lg k$ bits to represent $k$. So an algorithm whose running time is $\Theta(k)$ runs in time that is exponential in the length of the input. "Exponen …
D.W.♦
- 166k
2
votes
Superscript on complexity class?
That's referring to a complexity class defined in terms of oracle machines. See the Wikipedia article on that topic for more.
For example, $P^L$ means the class of all problems that can be solved in …
D.W.♦
- 166k