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.