When a problem exists, the need for a solution arises, and there has to be a way of working it out. Imagination, creative thinking, and a bit of artistic improvisation are the ingredients of what we call an elegant human thought - a human way of looking at a problem and finding a solution. The verb “to envision”. A challenge, an opportunity of surpassing one’s limits - of thinking beyond the norm.
Let me explain why I started with that thought. I don’t want my first blog post to just be about a tech subject or something hard-core implementation-wise. I want to write about our general approach to problems, here @Bugsense. After all, the road to reaching a destination, to visualizing and implementing it, is what matters most to us as developers. After all, we are just machine “imitations” trying to find our way in this “corner” of the galaxy. That said, be prepared for this post to be somewhat different than what you are accustomed to when reading tech blog posts.
I assume you are already familiar with the P and NP classes and what they represent in a greater algorithmic “landscape” (problems strictly in P have “efficient” solutions, according to the Cook-Karp thesis). NP-complete problems are “hard to solve” and don’t have “efficient” solutions that we know of. Let’s imagine how a future answer to the “P=NP” hypothesis might look like.
The problem lies in the definition of the Turing Machine input and state. When I was in high school I always tried to understand what a complex number may represent. Then I realized that a complex number is just a projection. Imagine for example an infinite set of numbers between 5 and 5. It’s not a typo. It’s something that contradicts reason, but, hey, why not? 5+5j, 5-6.9j, 5+j are just super-positions of the same projection. I say super-positions, because when we think of them as separate manifestations that exist at the same time, all of them have the same projection that our human perception “sees”: number 5.
Wanna go further? How about quaternions (that is, if the imaginary numbers are themselves a projection of something complex)? And we go on to dual quaternions, octonions, etc. Also, in signal theory, the Laplace and Z transforms are vital tools. They do an un-project operation from the real or complex domain to the complex one.
Now, imagine an input to the Turing Machine that’s just this: a superposition of different iterations of the same recursive algorithm, i.e. the input is not scalar; it’s a vector. The simultaneous processing of this complex input gives us the ability to solve the initial decision problem in polynomial time - let alone to also verify the answer in polynomial time. All of this just by using a brute force method. Don’t get confused with the formalizations. Encoding a complex number and passing it as an input is not what we want. We want the Turing Machine to be able to handle a superposition of inputs - a complex input in nature.
Some of you will wonder: "Isn’t this a concurrent machine that takes advantage of the parallel processing of inputs? So, it has nothing to do with the complexity reduction". The answer is "no". It has to do with the definition of the Turing Machine itself, as I said before, and the fact that the Turing Machine must retain its determinism in the verifying phase (Deterministic Turing Machines are used to verify the answer while Non-deterministic Turing Machines are used to solve the problem). Non-determinism is what makes a problem “hard” to solve. That’s why quantum computing will change the face of Informatics. Quantum mechanics rely on discrete values, probability, superposition and entanglement. These are some of the ideas that changed the way we think.
It all boils down to the Cook-Karp thesis. With the definition we currently use for the Turing Machine, P and NP are not likely to be equal (but we cannot prove that due to the initial definitions we have). With a different definition of the Turing Machine, we may see things in a very different way. What matters is what is thought to be a “hard” problem (that is, one that does not have an efficient solution) in terms of “practical computing”. Let’s take this to the extreme. What about the decidability property of a “harder” problem? “Halting problem" anyone?
Savitch's theorem basically states that we can move forward and backward in the space domain while we don't have this ability in the time domain. In the “real world” we live in, we believe that information cannot travel faster than the speed of light. This is a prerequisite for causality to stand (in other words, the effect follows the cause).
If FTL (faster than light) signaling is possible, the whole picture changes (this leads to “peculiar” situations where an answer “arrives” before the question). Let’s take a look at a particle that we can’t verify the existence of. Enter the tachyon. A superluminal particle that the Special Relativity Theory does not forbid to exist. In Special Relativity, the total energy E of a particle is:
where m is its rest mass, v its speed and c the speed of light. A particle that travels with increasing speed (accelerating from an initial speed) lower than the speed of light is forbidden to reach it, because the denominator would be equal to zero and thus the energy would be infinite. On the opposite side, a particle with an initial superluminal speed will yield an imaginary denominator (complex number - remember them?). Due to the fact that the energy is a real number, this would require its rest mass to be an imaginary number too. Well, this is the tachyon: a superluminal particle that has an imaginary rest mass. Say a warm “welcome” to complex numbers again! One interesting property of this particle is that it cannot decelerate to the speed of light; its energy would be infinite. So, if FTL communications are possible, then tachyons are one way of doing it.
This way, we can have an answer before the question. Which leads to solving undecidable problems (before they are stated!!) and even the hardest problem of them all: “A problem which we cannot formulate”. A problem we don’t know of. A problem we cannot even state or pose.
From a philosophical point of view, FTL should be possible. As a friend of mine once said:
"If we were bats, we would think of the speed of sound as the ultimate speed - this is exactly the case with light and how we perceive it".
Any intelligent manifestation of life with the willingness to communicate, as we conceive it in this universe, has the ultimate destination of achieving the un-achievable. The conquest of Everything. This is a universal standard. In terms of the Kardashev scale, a Type III (or above in the extended Kardashev scale) civilization is bound to use FTL methods in various situations.
We may think that something is impossible, but Physics teach us that the world is not the way we see it; there’s a whole lot bigger kind of picture, meaning that there’s ALWAYS a kind of solution, there’s always a WAY - direct or indirect. We just have to change our way of thinking.