论文部分内容阅读
该文就空间有界图灵机其细分非确定性问题作了讨论。这一讨论的直接背景耒源于LBA问题。指出了解决非确定与确定之间关系的困难程度,同时对能不能对LBA问题作出回答也作了一点探讨。结果表明,空间有界图灵机的非确定性与确定性之间的关系类似于时间有界图灵机非确定性与确定性之间的关系,解决它们是相当困难的。(珑摘)