2001/06/25 by В. Г. Найденко, Naidenko, V. G.
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.0 #F.1.3 #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0106049
openalex publication_date 2001/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that there cannot be any algorithm that for a given nondeterministic polynomial-time Turing machine determinates whether or not the language recognized by this machine belongs to P