https://arolstar52-zhtest.hf.space/index.php?action=history&feed=atom&title=PolyL 2026-07-04T03:46:05Z 在这个wiki上该页的修订历史 MediaWiki 1.43.8 https://arolstar52-zhtest.hf.space/index.php?title=PolyL&diff=784432&oldid=prev 2016-08-23T11:37:17Z

<p></p> <p><b>新页面</b></p><div>在[[計算複雜度理論]]內，&#039;&#039;&#039;PolyL&#039;&#039;&#039;是一個[[決定性問題]]的[[複雜度類]]， 可以使用決定型[[圖靈機]]使用被某個輸入大小的[[多对数函数]](polylogarithmic)函数所限制的空間。換句話說，polyL&amp;nbsp;=&amp;nbsp;[[DSPACE]]((log&amp;nbsp;&#039;&#039;n&#039;&#039;)&lt;sup&gt;O(1)&lt;/sup&gt;)，這裡的 [[大O符號|O]](1)代表一個常數。<br /> <br /> 相對於已知包含在[[P (複雜度)|P]]內的[[L (複雜度)|L]]，我們尚且不知道是否polyL是包含於P內，或者反過來。(PolyL已知包含於QP，或說，[[類多項式時間]](Quasi-polynomial time)之內)。 話說回來，我們知道polyL&amp;nbsp;≠&amp;nbsp;P，因為(舉例來說) polyL並沒有在[[多對一歸約|多對一]][[對數空間]][[歸約]]之下的[[完備 (複雜度)|完備]]問題。&lt;ref&gt;{{ComplexityZoo|polyL|P#polyl}}&lt;/ref&gt; 但是P則有這類問題。PolyL沒有對數空間之下的完備問題是因為[[空間譜系理論]](space hierarchy theory)保證了[[DSPACE]]((log&amp;nbsp;&#039;&#039;n&#039;&#039;)&lt;sup&gt;1&lt;/sup&gt;) ⊊ DSPACE((log&amp;nbsp;&#039;&#039;n&#039;&#039;)&lt;sup&gt;2&lt;/sup&gt;) ⊊ DSPACE((log&amp;nbsp;&#039;&#039;n&#039;&#039;)&lt;sup&gt;3&lt;/sup&gt;)…等等。如果polyL有完備問題，則這問題必然落在某個DSPACE((log&amp;nbsp;&#039;&#039;n&#039;&#039;)&lt;sup&gt;&#039;&#039;k&#039;&#039;&lt;/sup&gt;)內(&#039;&#039;k&#039;&#039;為某個常數)。這會令PolyL，也就是包含DSPACE((log&amp;nbsp;&#039;&#039;n&#039;&#039;)&lt;sup&gt;&#039;&#039;k+1&#039;&#039;&lt;/sup&gt;)以上所有空間複雜度內的問題，全部可以歸約為DSPACE((log&amp;nbsp;&#039;&#039;n&#039;&#039;)&lt;sup&gt;&#039;&#039;k&#039;&#039;&lt;/sup&gt;)，而違背了空間譜系理論。<br /> <br /> == 參考資料 ==<br /> {{reflist}}<br /> {{複雜度類}}<br /> <br /> [[Category:複雜度類]]</div>

imported>Edisonabcd