2010/12/28 by Maknickas, Algirdas Antano
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.1012.5804
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.