New answers tagged

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 ...
gnasher729's user avatar
  • 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.'s user avatar
  • 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 ...
Juho's user avatar
  • 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, ...
Pål GD's user avatar
  • 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 ...
Benjamin Smus's user avatar
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.'s user avatar
  • 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 ...
gnasher729's user avatar
  • 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 $...
Steven's user avatar
  • 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}$ ...
gnasher729's user avatar
  • 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.'s user avatar
  • 156k

Top 50 recent answers are included