I\'m aware that there must be something wrong with my reasoning, but I\'m not su

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.