中文
Sign in
AI tools
聊天
热门问题
时间线
Loading AI tools
全部
文章
字典
引用
地图
Immerman–Szelepcsényi theorem
来自维基百科,自由的百科全书
Found in articles
空间复杂度
hypothesis)猜想,对于时间复杂度而言,非确定型和确定型空间复杂度类之间的差距可能是指数级的。 根据
Immerman
–
Szelepcsényi
定理(英语:
Immerman
–
Szelepcsényi
theorem
),对于 f ∈ Ω ( log ( n ) ) {\displaystyle f\in \Omega
L (複雜度)
有时RL这个名称使用于使用对数空间不限时间能解决的问题其复杂度类。然而,根据
Immerman
–
Szelepcsényi
定理(英语:
Immerman
–
Szelepcsényi
theorem
),上述这个类别可以使用概率计数器证明RL' = NL,因此一般直接使用NL来代表。 我们也知道RL
哥德尔奖
5941 , ISSN 1095-7111, doi:10.1137/0217058, (原始内容存档 (PDF)于2012-02-07)
Szelepcsényi
, R., The method of forced enumeration for nondeterministic automata (PDF)
重复独立发现发明列表
Miller)(均1985年) 伊莫曼–塞莱普切尼定理(英语:
Immerman
–
Szelepcsényi
theorem
) – 尼尔·伊莫曼(英语:Neil
Immerman
);罗伯特·塞莱普切尼(英语:Róbert
Szelepcsényi
)(均1987年) 核酶 – 托马斯·切赫;西德尼·奥特曼(均1980年代)