New answers tagged np-complete
0
votes
What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?
A problem in NP with the answer “yes” can be solved by getting a clever hint followed by a polynomial time verification.
We could solve it very very slowly by enumerating all possible hints.
Which ...
- 28.4k
0
votes
Variant of Bounded Subset Product
The problem can be solved in polynomial time, using dynamic programming.
Let $A[k,s]$ be true if there exists a solution to your problem where $f_1 \cdots f_k = s$, or false otherwise. You can fill ...
D.W.♦
- 156k
0
votes
NP-hardness of modified distance-colouring of graphs
The problem you describe (for $r=1$) falls under the so-called $[\sigma,\rho]$-partitioning framework with several hardness results available (see e.g., [1]). In such a problem, we want to color the ...
- 22.5k
0
votes
NP-hardness of modified distance-colouring of graphs
I don't have an answer to your problem, but I have an answer for a different problem.
Let the Annotated Colorful Neighborhood-problem be as follows.
Annotated 2-Colorful 1-Neighborhood
Input: $G = (V, ...
- 15.5k
0
votes
Prove NP-completeness of deciding satisfiability of monotone boolean formula
IMO, it is intuitive to reduce Vertex-Cover to the problem that you are describing (which will show that the problem you are describing is at least as hard as Vertex-Cover). At the core of the problem ...
0
votes
NP completeness of closest vector problem
There is a mismatch in terminology in your question. The problem you specify is known as the shortest vector problem (SVP). You called it the closest vector problem (CVP), but the CVP is something ...
D.W.♦
- 156k
0
votes
3 Processor Scheduling
You should be able to do this in exponential time, but much faster than n^3 operations.
Get a quick upper bound by sorting the tasks in descending length, then scheduling each task in turn to the ...
- 28.4k
0
votes
Subset sum reducible to barter economy problem?
You can reduce from subset-sum as follows: given a set of $n$ positive integers $x_1, \dots, x_n$ and a positive integer target $T$, consider an instance with $2$ people $p_1, p_n$ and $n+1$ objects $...
- 28.4k
0
votes
( Soft question ) P vs NP - is such a situation possible?
Consider what happens if I find a polynomial time solution for an NP complete problem. Say a solution taking $n^{100}$ nanoseconds on my computer.
For n = 2 that’s $2^{100} \approx 10^{30}$ ...
- 28.4k
0
votes
( Soft question ) P vs NP - is such a situation possible?
Yes of course it is possible. Everything is possible. Such situations have been rare in mathematics, so I would not bet on it, but we have no way to rule out such a possibility. We do know that ...
D.W.♦
- 156k
Top 50 recent answers are included