2011/06/27 by Koji Kobayashi, Kobayashi, Koji
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Neural Networks and Applications #cs.LO
paper · pdf · doi:10.48550/arxiv.1106.5470
openalex publication_date 2011/06/27 · arxiv created 2011/08/09 · arxiv updated 2011/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper talk about the influence of Connection and Dispersion on Computational Complexity. And talk about the HornCNF's connection and CNF's dispersion, and show the difference between CNFSAT and HornSAT. First, I talk the relation between MUC decision problem and classifying the truth value assignment. Second, I define the two inner products ("inner product" and "inner harmony") and talk about the influence of orthogonal and correlation to MUC. And we can not reduce MUC to Orthogonalization MUC by using HornMUC in polynomial size because HornMUC have high orthogonal of inner harmony and MUC do not. So DP is not P, and NP is not P.