# Tag Info

### 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 ...

### 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 ...

### 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., ). In such a problem, we want to color the ...

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, ... 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 ... 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 ... 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$...
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}$ ...