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 79440
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
1
vote
Accepted
A NP-complete problem with difficult NP membership proof
Integer Linear Programming is such a problem.
Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$.
Question: is there a matrix $X\in \mathcal{M}_{n,1}(\mathb …
- 16.9k
1
vote
Reduction from Clique to IS degree at most 4
As you stated, this is not a correct reduction, because you would need to solve Clique for any graph (or prove that Clique with graphs of degree at most 4 is $NP$-complete). … I think the intention of the author for solving this exercice is to use the remark stated at the beginning of the exercice (which you cropped): "$\textsf{3SAT}$ remains $\textsf{NP}$-complete even when …
- 16.9k
1
vote
Accepted
K-Path-Problem is in $P$ or $NPC$
This problem is $\textsf{NP}$-complete. This is more or less the longest path problem. …
- 16.9k
1
vote
Accepted
NP-Complete Reduction
I think a reduction from $\texttt{Directed Hamiltonian Path}$ (not cycle) would work quite well.
Given a digraph $G = (V, E)$ where $V = \{v_1, …, v_n\}$, consider the digraph $G' = (V', E')$ where:
…
- 16.9k
1
vote
Accepted
Practicability of enumerating all Turing machines with fewer than $s$ states to find a poten...
There are a lot of Turing machines, so no, this idea is completely unpractical (I don't think there is really a loophole, since you are considering many restrictions). For example, there are roughly $ …
- 16.9k
2
votes
Accepted
Is the traveling salesman on a map NP-hard?
It was proved to be NP-complete by Garey, Graham and Johnson in 1976 and Papadimitriou in 1977.
Source: Computers and Intractability (Garey and Johnson) …
- 16.9k
2
votes
Accepted
Show that $PLANAR \in co-NP \cap NP$
Such an embedding is a $\mathsf{NP}$ certificate and is of polynomial size. It can be verified in polynomial time that no two edges cross. …
- 16.9k
1
vote
$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is NP- complete
I am sure that you can prove that $L_1\in \mathsf{NP}$. …
- 16.9k
2
votes
Accepted
If A reduces to B and B reduces to C, does that mean A reduces to C?
$A\in \mathsf{NP}$ because $\mathsf{P}\subset \mathsf{NP}$. … {NP}$-complete and $B\leqslant_m^p C$. …
- 16.9k
3
votes
Why does nondeterministically estimating a number have exponential time complexity?
That means that it is solving $\overline{\texttt{PRIME}}$ (the complement problem), and shows that $\texttt{PRIME}\in \text{co}\mathsf{NP}$, not that $\texttt{PRIME}\in \mathsf{NP}$. …
- 16.9k
1
vote
Clarification for binary search in solving optimal TSP when a polynomial algorithm with a bu...
A $NP$-complete problem is a $NP$-hard problem which also needs to be in $NP$. So when speaking about a $NP$-complete problem, it is not false to state that it is $NP$-hard. … However, $NP$ is a set of decision problems, therefore, TSP-OPT being an optimization problem cannot be in $NP$. …
- 16.9k
1
vote
How to reduce the hamiltonian path problem to 1/2 hamiltonian path problem
You just need to add $n$ (where $n$ is the order of the graph) vertices with no additional edges.
- 16.9k
2
votes
How can I prove the following problem is NP complete?
Since knapsack is $NP$-complete, this proves the $NP$-hardness of your problem. …
- 16.9k
0
votes
Accepted
Why is SET PACKING in NP?
Sure, $\mathsf{NP}$ is defined considering the executing time of a Turing machine, however we, human beings, are not made to think in TM. …
- 16.9k
1
vote
Karp's reduction strategy
$(3)\Rightarrow (1)$ should just be a consequence of the definition of $\textsf{NP}$-completeness. …
- 16.9k