I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked.

So here goes:

Take the following problem for example:

Let $x[n]$ be a real valued discrete signal of length $N$.

It is known that the signal is of the form $$x[n] = sin(an) + sin(bn) + sin(cn)$$ where $a,b,c$ are some real valued constants.

We want to find $a,b,c$ , the 3 frequencies composing $x[n]$.

Now lets assume a parallel universe which somehow doesn't know of the Fourier transform. The only way they could propose to solve the problem (that I can think of) would be some form of grid search over $a,b,c$ which would seem to be exponentially hard.

Given the Fourier transform, one could solve the problem in poly-time.

So my question is: could some problems we think are NP-hard just seem that way because we haven't yet found the "magic" transform to change them into a basis which bring the problem to be solvable in poly-time?

I know that I haven't given the full formal formulation of the problem, and probably the catch is that even without Fourier the problem isn't NP hard.. but I'm still curious about how to refute the claim that there could exist a basis transform which would make an NP-hard problem solvable in poly time.

  • 1
    $\begingroup$ What does it mean to "think a problem is NP-hard"? NP-hardness is a matter of proof, not opinion. $\endgroup$ – David Richerby Mar 15 '15 at 23:49

The only way they could propose to solve the problem (that I can think of) ... would seem to be exponentially hard."

That's your core fallacy, and "that I can think of" is the answer. The complexity of the problem did not change, but the transformation made finding an efficient algorithm easier (as a tool).

Yes, it's certainly possible that we have yet to find a similar tool that, once we have it, allows even our feeble minds to easily find efficient algorithms for NP-hard problems. That would be a constructive and generalisable proof for P=NP, that is something like a holy grail.


An efficient change of basis doesn't change the hardness of a problem. Consider some decision problem $Q_1$, which consists of all objects $x$ of some type that satisfy some property. Now let $f$ be an efficient (polytime) transformation whose inverse $f^{-1}$ is also efficient, and consider the decision problem $Q_2$ = { f(x) : x \in Q_1 }$. Then:

  1. $Q_1$ is in P iff $Q_2$ is in P.

  2. $Q_1$ is in NP iff $Q_2$ is in NP.

  3. $Q_1$ is NP-hard iff $Q_2$ is NP-hard.

  4. $Q_1$ is NP-complete iff $Q_2$ is NP-complete.

The proofs are not too difficult and left as an exercise.

As a concrete example, (undirected) graphs can be represented either as adjacency matrices or as adjacency lists. Assuming the graphs in question are not abysmally sparse, there are efficient transformations going both ways, so that from the point of view of graph problems, both representations result in the same complexity (in the sense discussed above).

  • $\begingroup$ Ok, but if I understand correctly, that still doesn't rule out P=NP if there exists a "magic basis" for some NP-complete problem, right? $\endgroup$ – Ron Mar 16 '15 at 9:50
  • 1
    $\begingroup$ @Ron Sure. But if P=NP, the "ordinary basis" is already "magic". $\endgroup$ – David Richerby Mar 16 '15 at 12:45
  • $\begingroup$ @DavidRicherby Except that maybe we only know of a relevant algorithm for one base and not the other? $\endgroup$ – Ron Mar 16 '15 at 13:25
  • $\begingroup$ The point David is trying to make is that finding this magic basis is part of the algorithm. Many algorithms involve a reduction from the original problem to another one that we know how to solve efficiently. This is none other than your magic basis. $\endgroup$ – Yuval Filmus Mar 16 '15 at 13:49
  • $\begingroup$ So if I understand, we're saying essentially the same thing - my "magic basis transform" is for you a magic algorithm. $\endgroup$ – Ron Mar 17 '15 at 14:37

Could a problem we think is NP-hard actually be solvable in polytime? Sure. We could be wrong (we suspected/guessed it was NP-hard, but our suspicion/guess was wrong). Or, it could be NP-hard and solvable in polytime, if P = NP.

I think the root problem is that you're confusing "a NP-hard problem" with "a problem we think is NP-hard". Those two are not the same. We routinely think all sorts of things that later turn out not to be true. Hey, that's life.

This is one reason why theoretical computer science is so focused on proofs: to avoid (or minimize) the situation where we thought/guessed/suspected/assumed something was true, and then later discover it actually wasn't.


Not the answer you're looking for? Browse other questions tagged or ask your own question.