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 41
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
7
votes
How to show that problems are in NP?
The easiest way to prove some problem is in $\mathsf{NP}$ is using the certificate definiiton of $\mathsf{NP}$ mentioned in other answers. … The nondeterministic definition of $\mathsf{NP}$ is usually not very useful for showing a problem belongs to $\mathsf{NP}$. …
- 22.5k
5
votes
NP $\subsetneq$ EXP?
So what you are saying is
$$\mathsf{NP} \subsetneq \mathsf{ExpTime} \implies \mathsf{NP} \subsetneq \mathsf{ExpTime}$$
which is trivially true. … If you are asking if $\mathsf{NP}\subsetneq \mathsf{ExpTime} $ then the answer is: it is unknown. …
- 22.5k
9
votes
Are there are problems in NP that have been shown to be not NP-complete but it is still not ...
In other words if you show some problem is in $\mathsf{NP}$ but is not $\mathsf{NP}$ complete would imply that $\mathsf{P}$ is not equal to $\mathsf{NP}$. … In short, there is no problem in $\mathsf{NP}$ that we know it is not $\mathsf{NP}$-complete. …
- 22.5k
8
votes
Accepted
Problems that are Cook-reducible to a problem in NP $\cap$ co-NP
Stated in another way: $\mathsf{NP}$ is not closed under Cook reductions (assuming $\mathsf{P}\neq \mathsf{NP}$).
How about $\mathsf{NP}\cap\mathsf{coNP}$? … Is the only reason that $\mathsf{NP}$ is not closed under Cook reductions is because it is not closed under complement so if we take those $\mathsf{NP}$ problems whose complement is also $\mathsf{NP}$ …
- 22.5k
74
votes
Accepted
Are there subexponential-time algorithms for NP-complete problems?
It is closed under polynomials so no $\mathsf{NP}$-hard problem can be solved in this time without violating ETH.
III. … Take an $\mathsf{NP}$-complete problem like SAT. It has a brute-force algorithm that runs in time $2^{O(n)}$. …
- 22.5k
2
votes
Is $NP$ "minimal", i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?
E.g. the fact that a problem cannot be solved in polynomial nondeterministic time does not imply that it is NP-complete (i.e. universal for NP). … For NP:
if P=NP all problems except trivial ones will be complete for NP (under Karp reductions). So assume P is a proper subset of NP (or alternatively use a weaker notion of reduction like AC0). …
- 22.5k