New answers tagged

2 votes
Accepted

This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?

I think that you cannot guarantee an unique sum, but the numbers for a counterexample must be taken at "the end of the universe". You can find primes $p_{i_j}$ and factors $k_j$ such that $\...
Marzio De Biasi's user avatar
5 votes

Bijection between NP-complete problems

To expand on Bruno and Emil's comments, the Berman-Hartmanis isomorphism theorem [1, p.312] says yes, provided $A$ and $B$ are paddable: If both $A$ and $B$ are paddable, there exists a polynomial-...
Neal Young's user avatar
  • 10.8k

Top 50 recent answers are included