Any class of languages $\mathbf{L}$ accepted in time $\mathbf{T}$ has a counterpart $\mathbf{NL}$ accepted in nondeterministic time $\mathbf{NT}$. It follows from the definition of nondeterministic languages that $\mathbf{L} \subseteq \mathbf{NL}$. This work shows that every sufficiently powerful language in $\mathbf{L}$ 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.
翻译:任何类型的语言 $\ mathbf{L}$\ mathbf{T}$ 被接受的时间 $\ mathbf{NL}$ $\ mathbf{NL}$ 有对应的 $\ mathbf{NL}$。 从非确定性语言的定义来看, $\ mathbf{L}\ subseteq \ mathbbf{NL}$ 。 这项工作显示, $\ mathbf{L}$ 中每个足够强大的语言都包含一个与 G\ “ { o}del 不可确定性主张相对应的字符串, 但这个字符串没有包含在非确定性对应的字符串中。 非确定性语言定义中的这种不一致性表明, 与非确定性时间复杂性等同有关的某些问题不可撤销。