Computational Problems and its complexity

Any mathematical and computer problem could be classified according their inherent difficulty and its time necessary to solve the entire problem (Computational Time), this science area is called Computational Complexity Theory [1]. One computational problem could be viewed as a collection of instructions or equation, which is solved individually to find the entire solution of the problem; other people define one computational problem as some problem could be solved in a computer, both definitions are complementary to define a computational problem [2].

Computational and mathematical problem can divide in next groups:

• P Complexity: This group contains all problems can be solved in a deterministic machine and one polynomial time.
• NP Complexity: This group contains all problems can be solved in a non-deterministic machine and one polynomial time.
• NP Complete Complexity: This group contains all problems can be solved in a non-deterministic machine and not polynomial time.

On the other hand, there is other science area focused in resolving combinatorial problem by means of graph theory [3] [4], because any combinatorial problem could be converted to graph. In general, one graph can be defined as set of objects, where each object is connected with another object by links. Those connections are called edges and they can have direction or not inside of the path, making up directed or undirected graphs. On the other hand, each object is called vertex, as we said before, each vertex can join with other vertex by one or several edges with different vertex, inclusive itself. The graphs can have several classifications depending of different characteristics (weight edges, number of connections, direction, etc).

One pioneer inside of graph theory and topology was Leonard Euler, who in 1736 shows “the Seven Bridges of Königsberg problem” [5], highlight, in that period, Königsberg was Prussian city (now Kaliningrad, Russia) with seven bridges, over the Pregel River. The Euler’s problem formulates as one pedestrian is possible to walk through the city that would cross each bridge once and only once. This problem is an excellent combinatorial problem to convert in a graph form, because each part of the city is possible to represent as element of graph. Later, the Irish mathematician, William Rowan Hamilton and the British mathematician, Thomas Kirkman [6] formulated mathematically in 1800’s the Travelling Salesman Problem (next lines, we can called as TSP), in same time, it was formulated Hamiltonian Path Problem (following HPP), one of the most mathematical complex problems in graph theory, impossible to do in deterministic algorithm with huge number of elements.

In XX century, Edsger Wybe Dijkstra published one algorithm [7], which is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, making a shortest path tree, mainly this algorithm is often used in routing task or part of other graph algorithms. Later, Robert W. Floyd and Wharshall [8] [9] modified Dijkstra’s algorithm, which compares all possible paths through the graph between each pair of vertices to find shortest paths in weighted graph with positive or negative edge weights. Finally, From Dijkstra to now, there are lot algorithms or modifications of these algorithms to calculate shortest path or any route.

On the other hand, today the current computing systems are based on a sequential technology established by John Von Neumann [10] [11] in the middle of the last century. These sequential computers are good at resolving mathematical problems, because they have a powerful arithmetic unit inside, which can do complex operations with binary arithmetic. Also, these computers have difficulties with so-called turnkey problems, where all possible solutions should check to find a final solution, by this reason; these systems lost a huge time in the preparation all possible solution and later check one per one, being their computational time close to exponential or logarithmic order. One perfect example is HPP, which with a few nodes or cities, any system can solve it, but when the number or cities or nodes is huge, this problem cannot solve in polynomial time or similar, by this reason, there is not deterministic algorithm to solve the problem.

At the moment, scientific community can solve these problems with the construction of parallel computers or supercomputers, which divide and share each part of the problem between all different nodes of the system. This methodology can reduce the computing time close to polynomial, but finally, these solutions consume many resources in communications between a lot interconnected nodes, which are normally sequential computers. There are other initiatives to solve combinatorial problems, for example, using organic materials, we can find bacterial computer to solve HPP [12], on the other hand, using DNA to resolve HPP by Prof. Adleman [13], the 3-SAT problem using DNA [14], implementations in membrane computing [15] and others organic solutions.

In this way, using organic materials (in particular DNA), in 1994, Professor Adleman formulated a new alternative for programming with organic DNA, using huge mathematical knowledge about computation with DNA and last advances in DNA. He created a DNA computer to solve HPP with seven nodes, using organic material. Which this experiment, he demonstrated that NP-Complete problems could be resolved in a computational time very close to the polynomial, being very close to find one solution of universal problem of PNP.

With this experiment, Prof Adleman shows the huge potential of DNA computing, breaking walls using organic material in computer science. Also, DNA Computing has huge potential to solve complex problems, but this methodology of computing contains certain barriers. For one side, implicit characteristics of material used (organic DNA), because is mainly perishable and long of time it dies. Other side, DNA machines are difficult to integrate in other environments as organics or silicon system, mainly in communication between them, by this reason, these systems are limited only for scientific environments and theoretical formulations.

Finally, in other field as optical, we can find works as solving HPP with light-based computer [16], on the other hand, using mathematical-theoretical equation for solving HPP [17], also with genetic algorithms to solve TSP [18] or by other systems or methodologies in different science areas.


References

[1] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

[2] Hopcroft John E., Motwan Rajeev, Ullman Jeffrey D, Introduction to Automata Theory, Languages, and Computation, Prentice Hall, 2007.

[3] A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.

[4] F. Harary, Graph Theory, Perseus Books, 1994.

[5] L. Euler, Solutio Problematis ad geometriam situs, 1736.

[6] E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, p. 269–271, 1959.

[7] R. W. Floyd, Algorithm 97: Shortest Path, Communications of the ACM 5 (6), p. 345, 1962.

[8] S. Warshall, A theorem on Boolean matrices, Journal of the ACM, p. 11–12. 1962.

[9] John von Neumann, First Draft of a Report on the EDVAC, 1945.

[10] J. D. Markgraf, The Von Neumann bottleneck, 2007.

[11] Jordan Baumgardner, Karen Acker, Oyinade Adefuye and Samuel Thomas Crowley, Solving a Hamiltonian Path Problem with a bacterial computer, Journal of Biological Engineering, 2009.

[12] Leonard Max Adleman, Molecular computation of solutions to combinatorial problems, Science, p. 1021–1024, 1994.

[13] Liu W, Gao L, Liu X, Wang S and Xu J, Solving the 3-SAT problem based on DNA computing, 2003.

[14] Gheorghe P˘aun, Introduction to Membrane Computing, 2009

[15] Mihai Oltean, Solving the Hamiltonian path problem with a light-based computer, Natural Computing, 2008

[16] Gerald L. Thompson and Shared Singhal, A probabilistic polynomial Algorithm for solving a directed Hamiltonian path problem, 1983

[17] Omar M. Sallabi and Younis El-Haddad, An Improved Genetic Algorithm to Solve the Traveling Salesman Problem, World Academy of Science, Engineering and Technology, pp. 403-406, 2009

[18] Frank Rubin, a Search Procedure for Hamilton Paths and Circuits, Journal of the ACM, p. 576–80, 1974

[19] Richard Bellman, on a routing problem, Quarterly of Applied Mathematics, p. 87–90, 1958

[20] L. R. Ford Jr., Network Flow Theory, 1956

[21] E. F. Moore, The shortest path through a maze, Proc. Internat. Sympos. Switching Theory 1957, Part II. Cambridge, Mass.: Harvard Univ. Press, p. 285–292, 1959

[22] J. Y. Yen, An algorithm for finding shortest routes from all source nodes to a given destination in general networks, Quarterly of Applied Mathematics, p. 526–530, 1970

[23] Silvia, Jose Daniel and Carlos Llopis, DNA based in silicon (Inchrosil), International Journal of Scientific & Engineering Research, pp. 728-732, 2014.

[24] Silvia, Jose Daniel and Carlos Llopis, Electronic System for emulating the chain of the DNA structure of a chromosome. Spain Patent WO 2009/022024 A1, 19 Febrary 2009.

[25] Foreman, Matthew and Akihiro Kanamori, Handbook of Set Theory, 2010.

[26] M. Morris Mano, Digital Logic and Computer Design, Prentice-Hall, 1979

[27] C. S. Wallace, A suggestion for a fast multiplier, IEEE Trans. on Electronic Comp, 1964.