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

Authors: Zohreh O. Akbari

Abstract:

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.

Keywords: Clique problem, Deterministic Polynomial-time Algorithm, Equality of P and NP Complexity Classes.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1334938

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.