论文部分内容阅读
作为为 NP 难的问题的启发式的设计的一个重要工具,脊梁分析在最近的年里在理论计算机科学成为了一个热点。由于在关于脊梁的计算复杂性的研究的困难,许多研究人员由统计方法分析了脊梁。试图增加由存在方法通常很小的脊梁尺寸,唯一的最佳的答案例子构造(UOSIC ) 为图被建议划分双性人的问题(GBP ) 。另外,我们由使用获得脊梁是 NP 难的 UOSIC 证明,即没有算法存在在假设下面在多项式时间获得 GBP 的脊梁那 P *NP。我们的工作扩展脊梁的计算复杂性的研究区域。并且 UOSIC 为 NP 难的问题的