The problem with the proposed scheme is that a problem, say, that can only be solved in exponential time requires you to travel very close to the speed of light in order for you to see the problem complete in polynomial time, requiring an exponential expenditure of energy to accelerate/decelerate. So either way, you are stuck. Either you spend an exponential amount of effort building a superfast, superlarge computer or you spend an exponential amount of energy to zip around while a normal computer works on the problem.

No, because the computations that are carried out in relativistic vs. non-relativistic situations  are of the same complexity: they involve solving the equations of motion, that are differential equations in both cases, in classical physics and involve computing transition amplitudes in quantum physics. Incidentally,  if this were possible, it wouldn't be consistent with Lorentz invariance, since it would distinguish the frames-if in one the description were of polynomial complexity, whereas in another it were of exponential complexity that could not be reduced to polynomial complexity. Lorentz invariance implies that the complexity of calculation must be the same in all frames.  

What is a non-trivial issue in this context, however, pertains to the information processing in presence of black holes, when quantum effects become important.

I am going to claim that using time dilation effects or anything equivalent (like hibernation) violates unstated but implicit terms of the NP problems, unless the asymmetry between two participants can be reversed.  I will explain these terms.

First, I hypothesize that a problem solution is only useful in a context of a series of actions and problems.  Take this or leave it, it is my hypothesis.  Solving an NP problem in a vacuous context, I claim, is not solving it.

In a practical way, the series of actions of the universe at large constitute the relevant context.  The solution of the NP problem must be fed back into that series of actions in a reasonable period of time within that context. 

Now you see the problem using special relativity to do this.  One can slow down time for isolated objects (which relatively speeds up time for the rest of the universe).  But one cannot slow down time for the universe at large while speeding it up for a small subset (e.g. the computer solving the NP problem).

Therefore special relativity provides no mechanism for solving NP problems in a useful context.

The same arguments can be repeated for general relativity.  You can descend in your spaceship near the horizon of a black hole, wait just a short time, and return to find the problem solved.  But the entire history of the universe will have progressed billions of years and you will not be able to use the solution to affect the universe, only yourself.  If you have any interest in the rest of the universe, or see your life as meaningful in relation to it, then effectively you have killed yourself to find the solution to the problem.

If you can encapsulate all of the universe you are interested in, and take it near the horizon of a very large black hole, leaving only the computer outside, you can later return with your universe-of-interest in tow and read the answer from the computer and use it in the limited context you have decided is important. 

However, this completely conforms to the objection of Toth above.  You have traded one very hard problem for another which is if anything, even harder.

Roger -

Any idea concerning your first statement: "unless the asymmetry between two participants can be reversed"?

"The same arguments can be repeated for general relativity.  You can descend in your spaceship near the horizon of a black hole, wait just a short time, and return to find the problem solved.  But the entire history of the universe will have progressed billions of years and you will not be able to use the solution to affect the universe, only yourself"

Yes I agree, it would be useless. So the trick to slow down your own time rate  is right in principle but it might be really useless.

The above two comments, Doug : Any idea concerning your first statement: "unless the asymmetry between two participants can be reversed"? and Stefano: So the trick to slow down your own time rate is right in principle but it might be really useless, are related.

It happens that a geodesic (locally unaccelerated path) is the path of longest proper time, that is, the path on which the local clock runs the fastest.  See http://www.physicspages.com/2013/03/30/geodesics-paths-of-longest-proper-time/ for a short discussion.

That means if you do anything to your computer (accelerate it), you slow it down. 

My observation was that Doug's idea of slowing down yourself removes you from the context of the universe in which you needed the answer to the problem.  Unless you can isolate a small section of the universe that is all you care about, you are stuck, and you still have the high cost Toth mentioned.

So what about accelerating the bulk of the universe?  That is another way of saying "reverse the assymetry."  Of course, the energy to accelerate the bulk of the universe can't by definition be contained in the smaller fraction of the universe containing your computer.

Another way of looking at this is Mach's Principle.  Accelerating the bulk of the universe really means accelerating the smaller fraction, since the position of the universe is only relative to the bulk of it, so if Mach is correct you could wind up slowing the wrong clock.  In GR this is not necessarily the case, but then in GR there is no energy mechanism to accelerate something large with something very small.

This would make a possibly interesting plot for a Sci Fi novel.  A civilization that has reached the limit of its computing power needs to solve an NP-hard problem to develop star travel.  They live near a black hole, and put their whole planet on a trajectory to pass near it, leaving their computer at a distance. 

The whole universe also acts as a kind of computer with an infinite number of alien civilizations randomly trying to find star travel.  When our heroes return to their computer, they find this incidental biological computer of the universe has also solved the problem, and star traveling (and of course evil) aliens have confiscated the computer and are withholding the answer.

The brilliant scientists of our hero planet figure out that the evil alien civilization will collapse in a few billion years of its own corruption, so they take no action, leaving their planet on its orbit to go back near the black hole.

But when they emerge again, they find the universe is collapsing because of the presence of dark matter they couldn't see and didn't take into account.

To have the most time (and compute cycles) you have to not move.  It is a kind of catch 22.  Any civilization that develops (ordinary) star travel will find itself developing more slowly and will fall behind non-traveling civilizations.  Hmm, that also might make an interesting plot.

Robert,  Perhaps Research Gate is doing so well, they can fund your movie.

I think there is a problem with the design of a computer travelling at relativistic velocity: Electrons moving forward are going to need a huge potential to move faster than the spacecraft, and those moving aft will give off enough energy to burn up the spacecraft. It looks like this will have to be unmanned for similar reasons.  We need a 2-D computer.

Maybe it is better to stay at home and try to make this happen in wires with electrons. Groupings of electrons could be the initial state of the calculation and the answer is their structural relationship after they have been travelling around near the speed of light in Copper (or a superconductor). 

We've already gotten to the point where the best way to explain a space-time cone is showing that a supercomputer is calling for a read of data that hasn't yet been received by distant memory (a few feet away).

Sci Fi can make for good 102B.

In "SIGACT News Complexity Theory Column 36", John Kadvany says that one possible approach to PvNP includes: "... a characterization of complexity involving an analysis of relative numerical clocks, analogous to that in Einstein’s special theory of relativity..."  Robert - You are perfect for that job.

https://www.cs.umd.edu/~gasarch/papers/poll.pdf