AComputing Cliques is Intractable

The class P is in fact a proper sub-class of NP. We explore topological properties of the Hamming space 2[n] where [n] = {1, 2,..., n}. With the developed theory, we show: (i) a theorem that is closely related to Erdös and Rado’s sunflower lemma, and claims a stronger statement in most cases, (ii) a new approach to prove the exponential monotone circuit complexity of the clique problem, (iii) NC 6 = NP through the impossibility of a Boolean circuit with poly-log depth to compute cliques, based on the conctruction of (ii), and (iv) P 6 = NP through the exponential circuit complexity of the clique problem, based on the construction of (iii). Item (i) leads to the existence of a sunflower with a small core in certain families of sets, which is not an obvious consequence of the sunflower lemma. In (iv), we show that any Boolean circuit computing the clique function CLIQUEn, 4√n has a size exponential in n. Thus, we will separate P/poly from NP also. Razborov and Rudich showed strong evidence that no natural proof can prove exponential circuit com-plexity of a Boolean function. We confirm that the proofs for (iii) and (iv) are not natural