New problems complete for nondeterministic log space
New problems complete for nondeterministic log space
复制标题
不确定性日志空间的新问题已完成
DOI：
--
复制
发表时间：
1976
期刊：
影响因子：
--
通讯作者：
William T. Laaser
中科院分区：
文献类型：
--
作者：
Neil D. Jones;Y. Edmund Lien;William T. Laaser
结果表明，各种问题的计算复杂性相当于通过有向图找到一条路径。这些结果与Karp的结果在较低的复杂性水平上是平行的，涉及到每个子句有两个文字的命题公式的可满足性，通过一个结合的二元运算生成元素，每个方程有两个变量的线性方程的解，具有最终状态的广义序列机的等价性，以及决定上下文无关文法的LL（k）和LR（k）条件.最后，给出了几个等价于无向图可达性的问题，包括偶分性和具有“异或”连接符的公式的可满足性。
It is shown that a variety of problems have computational complexity equivalent to that of finding a path through a directed graph. These results, which parallel those of Karp at a lower complexity level, concern satisfiability of propositional formulas with two literals per clause, generation of elements by an associative binary operation, solution of linear equations with two variables per equation, equivalence of generalized sequential machines with final states, and deciding theLL(k) andLR(k) conditions for context-free grammars. Finally, several problems are shown equivalent to reachability in undirected graphs, including bipartiteness and satisfiability of formulas with the “exclusive or” connective.