Planar Formulae and Their Uses
Planar Formulae and Their Uses
复制标题
DOI：
10.1137/0211025
复制
发表时间：
1982-05
期刊：
影响因子：
--
通讯作者：
David Lichtenstein
中科院分区：
文献类型：
--
作者：
David Lichtenstein
定义了平面布尔公式集，证明了真量化平面公式集是多项式空间完全的，可满足平面公式集是np完全的。利用这些结果，我们能够提供平面节点覆盖、平面哈密顿电路和直线、几何连通支配集的np完备性，以及平面广义地理的多项式空间完备性的简单而几乎一致的证明。平面节点盖及平面哈密顿电路和直线的np -完备性在别处得到了首次证明[M]。R. gary和D. S. Johnson，线性Steiner树是np完全的，SIAM J.应用。数学。， 32(1977)，第826-834页。R. Garey， D. S. Johnson和R. E. Tarjan，平面Hamilton电路问题是np完全的，SIAM J. Comp, 5 (1976), pp. 704-714。
We define the set of planar boolean formulae, and then show that the set of true quantified planar formulae is polynomial space complete and that the set of satisfiable planar formulae is NP-complete. Using these results, we are able to provide simple and nearly uniform proofs of NP-completeness for planar node cover, planar Hamiltonian circuit and line, geometric connected dominating set, and of polynomial space completeness for planar generalized geography.The NP-completeness of planar node cover and planar Hamiltonian circuit and line were first proved elsewhere [M. R. Garey and D. S. Johnson, The rectilinear Steiner tree is NP-complete, SIAM J. Appl. Math., 32 (1977), pp. 826–834] and [M. R. Garey, D. S. Johnson and R. E. Tarjan, The planar Hamilton circuit problem is NP-complete, SIAM J. Comp., 5 (1976), pp. 704–714].