PSPACE
{{Infobox Complexity Class |class=PSPACE |image= |long-name=多项式空间 |description= |wheredefined= |external-urls=[https://complexityzoo.net/Complexity_Zoo:P#pspace Complexity Zoo] |dtime=n^{\Omega(1)}, 2^{n^{O(1)}} |complet…
标签：#复杂度类
共 4 篇文章
L (複雜度)
L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。 对数空间是指与输入规模成对数大小关系的可写的储存空间，大多数对数空间（LOGSPACE）算法以这种方式储存。 相关复杂度类 FL 和功能性問題相關的類別是FL，在计算复杂度理论，FL是一个复杂度类，是能被确定型图灵机在对数空间下解决的函数问题的集合。 依照同样的原理，可以定义相应的FP，FNP，TFNP。对数空间规约在定义NL-…
伪多项式时间
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。 一个具有伪多项式时间复杂度的NP完全问题称之为，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为。 例子 在素性测试}-中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数…
NC (复杂度)
在计算复杂度理论，NC（Nick's Class），是一个复杂度类，是能被并行计算机在多对数函数时间（O(logc n)）内以多项式空间（或者说O(nk)并行线程）下解决的判定问题的集合，最先由史提芬·古克提出。 正如P被认为是易解复杂度类一般，NC也被认为是在并行计算上易解的问题。明显的有NC ⊆ P，因为一切并行计算都可以以多项式空间依次的在确定型图灵机上运行。我们目前仍未知道的一个关键问题是，NC = P是否成立。大多数的研究人员…