A Deterministic Polynomial-time Algorithm for the Clique Problem and the Equality of P and NP Complexity Classes

In this paper a deterministic polynomial-time algorithm is presented for the Clique problem. The case is considered as the problem of omitting the minimum number of vertices from the input graph so that none of the zeroes on the graph-s adjacency matrix (except the main diagonal entries) would remain on the adjacency matrix of the resulting subgraph. The existence of a deterministic polynomial-time algorithm for the Clique problem, as an NP-complete problem will prove the equality of P and NP complexity classes.

Authors:

• Zohreh O. Akbari

Keywords:

• Clique problem
• Deterministic Polynomial-time Algorithm
• Equality of P and NP Complexity Classes.

References:

[1] Richard E. Neapolitan and Kumarss Naimipour, "Foundations of
Algorithms using C++ Pseudocode", 3rd ed., Jones and Bartlett
Publishers, 2003, ch. 9.
[2] Michael Sipser, "Introduction to the Theory of Computation", 2nd ed.,
International Edition, Thomson Course Technology, p 270, definition
7.19 and theorem 7.20, 2006.
[3] Stephen A. Cook, "The complexity of theorem-proving procedures",
Proceedings of Third Annual ACM Symposium on Theory of
Computing, pages 151-158, 1971.
[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
Clifford Stein, "Introduction to Algorithms", 2nd ed., MIT Press and
McGraw-Hill, 2001, ch. 22 and ch. 34.
[5] Stephen A. Cook, "The P versus NP problem". Manuscript prepared for
the Clay Mathematics Institute for the Millennium Prize Problems, 2000.
[6] Richard M. Karp, "Reducibility among combinatorial problems", In R.
E. Miller and J. W. Thatcher (editors): Complexity of Computer
Computations, pages 85-103, New York: Plenum Press, 1972.