Average polynomial time complexity of some NP-complete problems (Q1091815)

Random graphs with n vertices are considered such that any edge occurs independently swith the same probability p. It is proved that the CLIQUE problem can be solved in average polynomial time for these graphs when \(p=n^{-\epsilon}\), where \(\epsilon >0\) is a constant. Besides, the problem CLIQUE(N(n)) is considered for the graphs with a number of edges less than N(n). It is shown that this problem can also be solved in average polynomial time for any function \(0\leq N(n)\leq n^{2-\epsilon}\), where \(0<\epsilon <2\). Provided that \(N(n)\geq n^{\epsilon}\), the latter problem is NP-complete.