If Space-Time Is Discrete, It Could Be Possible to Solve NP-Complete Problems in Polynomial Time

摘要

Traditional physics assumes that space and time are continuous. However, a deeper analysis shows that this seemingly reasonable space-time model leads to some serious physical problems. One of the approaches that physicists have proposed to solve these problems is to assume that the space-time is actually discrete. In this paper, we analyze possible computational consequences of this discreteness. It turns out that in a discrete space-time, it is probably possible to solve NP-complete problems in polynomial time: namely, this is possible in almost all physically reasonable models of dynamics in discrete space-time (almost all in some reasonable sense).