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.
Publisher
School of Computing and Informatics