yarvos · HackerTrans

Shor's algorithm absolutely does not reduce NP hard problems to P (or BQP). These kinds of problems with quantum speedups reside in an intermediate class of difficulty sometimes called NP-intermediate which may or may not already be in P, and which NP complete problems do not reduce to.

yarvos

4 anni fadiscuss

I am honestly shocked at the number of comments strongly asserting the impossibility of FTL based on simultaneity arguments from special relativity. Yes, faster than light travel through space is prohibited in both special and general relativity by simultaneity. But not so for sub light speed travel (or even being stationary) on a space which itself has the property where distances between the passenger and destination are decreasing faster than the speed of light, which is precisely the class of metric solutions that the paper is investigating.

The fact that certain galaxies are receding from us faster than the speed of light due to the expansion of the universe (again just changes in the metric) provides a clear example of this kind of 'FTL' travel that is permitted in general relativity.