New answers tagged np-hard
0
While Tom's answer is correct, I think there is more to be said. For example, there is a finite number of chess positions on an 8x8 board with the 50 moves rules, yet we can sometimes hear statements like "Chess is PSPACE-complete".
In order to study the complexity of such a problem, you have to generalize it, i.e. allow it to have arbitrarily ...
2
No. Bitcoin mining can be solved in $O(1)$ time. Unfortunately the hidden constant is quite large.
3
I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you don't have to make any restrictions on what inputs are allowed - i.e., every input string of bits represents a number that has a factorization. This is different ...
0
The problem you describe is exactly asymmetric TSP. As your reduction shows, asymmetric TSP generalizes the Hamiltonian circuit problem, which is known to be NP-hard.
Usually we consider metric versions of TSP, in which the triangle inequality $c(i,k) \leq c(i,j) + c(j,k)$ holds, and often the TSP instance is symmetric, $c(i,j) = c(j,i)$. Your reduction ...
0
This is not intended to be a full answer but rather to give a possible direction.
Assume $f_j$ are natural numbers. Then let $K = \sum_j f_j$.
Solve the following clustering problem for points $p_k$:
$$
\arg\min_k \sum_i \min_k |x_i - p_k|
$$
Then we need to assign each cluster a facility, such that facility $j$ is associated with $f_j$ clusters. Clearly, ...
1
The crux of the problem lies in worst to average case reductions. The standard construction of a function which is average case hard is taking a function which is worst case hard and applying all kinds of fancy error correcting codes on its truth table. See Ta-Shma's notes sketching the STV construction. As far as I know, we don't know how to do that for NP (...
Top 50 recent answers are included
