New answers tagged

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