A very hard log space counting class
A very hard log space counting class
复制标题
一个非常难的日志空间计数类
DOI：
10.1109/sct.1990.113964
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Birgit Jenner
中科院分区：
文献类型：
--
作者：
Carme Àlvarez;Birgit Jenner
考虑到对数空间计数类哈希L，opt-L，和跨度L，这是类似于他们的多项式时间对应定义。完整的功能，得到这三类的图和有限自动机。结果表明，Hash L和opt-L都包含在NC/sup 2/中，但令人惊讶的是，span-L似乎比Hash L和opt-L更难计数类。证明了span-L-函数可以在多项式时间内计算当且仅当P=NP=PH=P（Hash P），即如果类P（Hash P）和多项式时间层次的所有类都包含在P中。散列P中包含的span-L，并且散列P中的任何函数都可以表示为span-L中两个函数的减法。然而，包含在span-L中的散列P将意味着NL=P=NP。还进行了调查类opt-L和span-L的各种限制，它是显示，例如，如果opt-L符合其限制版本之一，那么L=NL如下。<<ETX>>
Consideration is given to the logarithmic space counting classes Hash L, opt-L, and span-L, which are defined analogously to their polynomial-time counterparts. Complete functions are obtained for these three classes in terms of graphs and finite automata. It is shown that Hash L and opt-L are both contained in NC/sup 2/, but that, surprisingly, span-L seems to be much harder counting class than Hash L and opt-L. It is demonstrated that span-L-functions can be computed in polynomial time if and only if P=NP=PH=P( Hash P), i.e if the class P( Hash P) and all the classes of the polynomial-time hierarchy are contained in P. This result follows from the fact that span-L and Hash P are very similar: span-L contained in Hash P, and any function in Hash P can be represented as a subtraction of two functions in span-L. Nevertheless, Hash P contained in span-L would imply NL=P=NP. An investigation is also conducted of various restrictions of the classes opt-L and span-L, and it is shown, e.g that if opt-L coincides with one of its restricted versions, then L=NL follows.<<ETX>>