Log-空间规约

维基百科,自由的百科全书
跳转至: 导航搜索

计算复杂性理论中,log-空间规约指仅使用对数阶空间的确定性图灵机(DTM)进行的规约。区别于常见的多项式时间规约,log-空间规约只允许DTM使用若干个log n(n是输入长度)空间。Log-空间规约在定义NL-完全问题时候起作用。