I got riddled by the following problem: Wikipedia states (without citation)

Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution[Note 1] to an NP-complete problem such as 3-SAT would break most existing cryptosystems including:


  1. Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of $\mathcal{O}(N ^ 2)$ or better and a reasonable constant term would be disastrous. On the other hand, a solution that is $\Omega (N ^ 4)$ or worse in almost all cases would not pose an immediate practical danger.

(see https://en.wikipedia.org/wiki/P_versus_NP_problem)

How can you make such strong a statement about the whole class of NP-complete problems if by the very definition the reduction function and the growth of the input string caused by the reduction can have arbitrary polynomial constants?

For example, consider I have an algorithm A that solves some subclass C of NP-complete problems in time $\mathcal{O}(n)$. Further consider C is really weird, e.g. Super Mario Bros or something like that and my reduction function needs $\mathcal{O}(n ^ 8)$ time to reduce a problem p $\small{\in}$ 3SAT to p1 $\small{\in}$ C while it also grows the size of the input string by $\mathcal{O}(n ^ 8)$. So, to solve a problem p in 3SAT I would need to

  • reduce it to p1, needing $\mathcal{O}(n ^ 8)$ time
  • solve p1, needing $\mathcal{O}(n)$ time if n is the size of the input string p1, but $\mathcal{O}(n ^ 8)$ if n is the size of the input string p

In the end I would need to solve two problems in $\mathcal{O}(n ^ 8)$ if n is size of my original problem. And while being linear in the size of p1 (and in consequence be "disastrous" according to Wikipedias definition) it would be more like "impossible to do for big problems" in relation to the size of p.

Am I completely missing something?

Thanks in advance

  • $\begingroup$ You aren't missing anything. Wikipedia was just trying to make the point that some polynomial algorithms are practical and some aren't. $\endgroup$ – Yuval Filmus May 24 '17 at 20:51
  • $\begingroup$ So the article should be read like "Solving a 3SAT problem with polynomial constants XY", not like "Solving ANY NP-complete problem with constants XY" ? That would be pretty mistakable . And would also imply there are problems in NP-complete where linear runtime is superior, while it could be pretty poor on others, would'nt it ? $\endgroup$ – rndHard May 24 '17 at 22:06
  • $\begingroup$ If you don't find this Wikipedia paragraph useful, I suggest that you ignore it. $\endgroup$ – Yuval Filmus May 24 '17 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.