Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31100
A Deterministic Polynomial-time Algorithm for the Clique Problem and the Equality of P and NP Complexity Classes

Authors: Zohreh O. Akbari


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):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1528


[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.