# An OO view of time travel

The Object:

According to physics, everything in this world is a unique stream of energy and matter. All energy and matter can be viewed constructed by a combination of wave and particle. Assume, we view this pattern as an Object, name P.

For each P, there are fields wave and particle to ensure its uniqueness. Also for each P, it has a real value entropy which has been proven (as far as I have leaned) non-static. Which means entropy changes as a function of time. let’s call it En(t).

For conclusion, each P has following structure:

Object P
{
Wave     w;
Matter   m;
Entopy  En(t);
}

The Space:

The space we are discussing in, mathematically, can be viewed as a vector space. Elements of the space are vectors from one state of P to another. Let’s denote Vij being the vector from state i of P to state j of P in the space. Thus, all components of the vector are functions of time t. Let’s also denote them as w(t), m(t) and En(t)(t) = En(t^2). Note that if we plot the functions in a matrix with each row and column numbered with state, we have a matrix representation of state machine for P. Let’s denote such space S and the state machine matrix Mstate. In this S, we define + being vector + and multiplication as vector multiplication.

Let’s also define a adjacent matrix for all objects P at time t. Let aij of the matrix be 1 if Pi has a connection to Pj. That is, like two person, if person i was talking to person j at some time t, then aij is 1 as Pi and Pj are connected at time t. Naturally, this matrix is also a function of time t, denoted as adjM(t).

The transformation:

Assume time travel is possible. That is, it is possible to calculate both Mstate and adjM(t) for some given t not consistent of current time t-current. The computation involves:
i)   For past time t<t-current. As table look consumes too much memory space, a reconstruction of adjM(t) from adjM(t-current). A reconstruction of Mstate from the current Mstate matrix. The construction of previous Mstate matrix means the recalculation of w(t), m(t), En(t)(t) from w(t-current), m(t-current), En(t-current^2) for some Object P.
ii)  For future time t>t-current. Predict adjM(t) from adjM(t-current) and predict all entities related to P for time t from time t-current.

As prediction with none given pattern is well studied and NP-hard, we can’t “calcualte” the future. The problem remains if it is possible to “calculate” the past.

It is natural for one to think of using dynamic programming and back-trace to time t from time t-current. Under the assumption that all choice we make are efficiency driven, it is possible to give the optimal solution of t-current based on some previous time slice t. This may grant the possibility of “reverse engineering” the dynamic programming algorithm and back-trace to the state at time t.

As a matter of fact, as the assumption does not always hold, most events in this world happens in a greedy algorithm fashion. Any choice we made are based on the information we were given and thus the optimal for time t+1 is just picking the best we can see at time t. Thus the back trace has to be in a greedy algorithm fashion. And, by nature, finding the optimal choice and back trace to previous time slice are equivalent to each other. Thus, if for some t-current, we can construct, from time t0 to t-current, states of all time slices using greedy algorithm regardless of correct matching of discrete events, we may very well have a traceable path to the past for some time t within range [t0, t-current].

As we’ve rejected dynamic programming, let’s focus on using reverse greedy algorithm to solve the problem. Note that if we have all possible choices for arbitrary time from t0 to tn shown as nodes. Define an edge exists between two nodes ni and nj, if and only if nj is choosable at state ni and ni can be back-traced from nj. Under this construction, we have a n-partite graph, that for all nodes at time ti they are naturally grouped and all nodes does not have any edge to any other nodes in the same group. Define the weight of an edge being it’s benifit one get by choosing this edge, we have a longest path problem from t0 to t-current between node n0 and n-current, which are both singleton and assumable known. This is an NP-hard problem and thus not calculable.

Thus, as we may have a polynomial time reduction from longest path problem to time slice reconstruction, the reconstruction problem is NP-hard. As a result, the equivalent back trace time problem is NP hard.

For conclusion, we have both time traveling to the past and future NP hard for computation. Thus, time travel is not possible for now.

The previous arguments are under following limitations:

a) All events we discussed here are restricted to human activities. We do not know how mother nature works. We do not know how to represent states… This sucks but this means we don’t talk about it here.

b) All discussion are restricted under modern computation capacity. If some genius figured a way to make it not NP hard, or even make NP hard problems solvable… Heck!!! I wanna see him!!!

c) All discussion are restricted to the author’s knowledge. After all, I’ve only finished undergraduate…

d) Please, be nice, this is wrote 5 in the morning…