2012/12/02 by Koji Kobayashi, Kobayashi, Koji
Computer Science · #Advanced Algebra and Logic #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1212.0191
openalex publication_date 2012/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This article provide new approach to solve P vs NP problem by using cardinality of bases function. About NP-Complete problems, we can divide to infinite disjunction of P-Complete problems. These P-Complete problems are independent of each other in disjunction. That is, NP-Complete problem is in infinite dimension function space that bases are P-Complete. The other hand, any P-Complete problem have at most a finite number of P-Complete basis. The reason is that each P problems have at most finite number of Least fixed point operator. Therefore, we cannot describe NP-Complete problems in P. We can also prove this result from incompleteness of P.