加载中…
Any class of languages accepted in time has a counterpart accepted in nondeterministic time . It follows from the definition of nondeterministic languages that $ \subseteq $. This work shows that every sufficiently powerful language in contains a string corresponding to G"{o}del’s undecidable proposition, but this string is not contained in its nondeterministic counterpart. This inconsistency in the definition of nondeterministic languages shows that certain questions regarding nondeterministic time complexity equivalences are irrevocably ill-posed.

生成讲解博客的中文版本

生成AI智能校验的中文版本