This algorithm could solve NP Complete problem in P time
This article is the result of my work on algorithms and how they relate to classical parts of pure mathematics, as well as my research on the mathematical theory of computation. The following ideas represent a hypothetical thought experiment and not a real computer program.
What is the computational efficiency of a computer virus?
For the purpose of this thought experiment, imagine the following fake computer virus: for each computer infected by this “virus”, this computer will infect another computer over the internet once every T seconds.
Let’s take units where, by definition, T=1. Then we shall construct a fake “Command & Control Server” (C&C Server) (for this thought experiment), and the system consisting of the C&C Server + all infected computers constitutes a “single machine”.
First, assume we infect a single computer with this virus, say we infect the C&C server. Then the number of infected computers will double every unit of time T. After a total period of time t has passed, there will be 2^t infected computers. This means the “virus” spreads with a so-called “exponential efficiency”
For all practical purposes, it’s okay to assume that starting after time t=0, the computational power of the entire system grows exponentially in time. This is the basis of the entire algorithm, and why this is a thought experiment and not a real program.
The Algorithm
It’s a well known result in the theory of NP Complete that if there exists an algorithm to solve any single NP Complete problem in P time, then this algorithm can be used to solve any other problem in the family NP Complete in P time as well.
The basic idea is to make use of a practically infinite amount of computer power which grows exponentially in time. Let’s take as example NP Complete problem, the so-called SAT problem, which means the Boolean Satisfiability Problem, which can be stated as follows:
SAT PROBLEM: Decide whether or not the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE
Let B be any Boolean formula, and let N be the number of variables in B
1 — infect 2^N computers at an exponential rate in time with pre-defined instructions from the C&C server
2 —after a pre-determined amount of time, the pre-defined instructions execute their “payload”, which consists of checking the SAT problem
3 — if at any time, one of the infected computers gets the answer “True” when checking B, then it will send this message back to the C&C server
Then given any boolean expression B involving N variables, I can use this algorithm to solve the boolean satisfiability problem, on average, much faster than a normal program run on a finite network of computers.
Theoretical Computational Efficiency
In a scenario where the problem has no solution, it will take the C&C Server the maximum amount of time before concluding this problem cannot be solved; however, if B is solvable (by assumption, for the sake of argument), then it’s completely random what order each infected computer will send the C&C a True message. Sometimes you will get very lucky and the algorithm will complete very fast, other times, you will be unlucky and it will essentially take a worst case scenario amount of time, which would be the same as how much time it would take if B were unsolvable.
Heuristically, these types of arguments suggest there could be a logarithmic saving in theoretical computational efficiency, corresponding to the exponential increase in computing power, and that the efficiency of this algorithm would be O(N logN). I have at this time not rigorously proved this result.
