2013/05/14 by Junichiro Fukuyama, Fukuyama, Junichiro
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1305.3218
openalex publication_date 2013/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Erdos 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 ≠ NP through the impossibility of a Boolean circuit with poly-log depth to compute cliques, based on the construction of (ii), and (iv) P ≠ 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,k (k=n1/4) 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 complexity of a Boolean function. We confirm that the proofs for (iii) and (iv) are not natural.