A Method For Solving Np-complete Problems By Use Of Graph Embodiment On A Quantum Computation Paradigm Using A Relational Database Query

Abstract

The relationship between the complexity class P and NP is one of the most fascinating and unresolved question in theoretical Computer Science. The classical computational paradigm, hedged on Turing thesis may be by itself the limiting factor. To investigate this relationship, a method for solving a query problem on a relational database on the classical and the new quantum computational paradigm has been developed. The method solves queries or database problems through the use of graphs. The relational database is converted into a directed labeled graph representing the set of the query solution space. The query problem is converted into a directed labeled graph representing the sub-set database solution space set. An association graph of the database and the query graphs is generated. The maximum clique (a known NP-Complete problem) of the association graph yields the solution to the query problem. Comparison of the maximum clique algorithm on both classical and quantum computation paradigms has yielded additional knowledge on the relationship between P vs NP problem. The results have indicated a substantial improvement on the algorithm efficiency on quantum computation but not sufficient enough to resolve the problem. The results indicate that the solution to the P vs NP cannot be resolved under the current computation paradigms and may requires a new computation paradigm to resolve it.