2010/12/28 by Algirdas Maknickas, Algirdas Antano Maknickas, Maknickas, Algirdas Antano
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.1012.5804
openalex publication_date 2010/12/28 · arxiv created 2016/10/19 · arxiv updated 2016/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By using of analytical multi-logic expresses in conjunction with non-deterministic Turing machine the proposition was proved that algorithm of deterministic Turing counter machine of polynomial time complexity can be decreased to the algorithm of linear time complexity in non-deterministic Turing counter machine. Furthermore, it was shown that existence of reduction of polynomial time complexity to the linear time complexity by switching from deterministic to non-deterministic Turing machine for string recognition imply P equals to NP. Analytical generation functions of higher order logic were used for finding of k value in Fagin's R. Theorem 24.