POWER INDEXES AND EASIER HARD PROBLEMS

被引：21

作者：

STEARNS, RE

HUNT, HB

机构：

[1] Department of Computer Science, State University of New York at Albany, Albany, 12222, NY

来源：

MATHEMATICAL SYSTEMS THEORY | 1990年 / 23卷 / 04期

关键词：

D O I：

10.1007/BF02090776

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The concepts of power_index, satisfiability hypothesis (SH), and structure tree are introduced and used to make sharper hypotheses about a problem's complexity than "the problem is NP-complete." These concepts are used to characterize the complexities of a number of basic NP-complete problems, including both CLIQUE and PARTITION which are shown to have power-indices at most 1/2. Also, the problem 3SAT is shown to be solvable deterministically in time exponential only in the square root of v+c, where v is the number of variables and c is the number of "crossovers" needed to layout the formula in the plane. © 1990 Springer-Verlag New York Inc.

引用

页码：209 / 225

页数：17

共 30 条

[1]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[2]

ARNBORG S, 1987, UNPUB WHICH PROBLEMS

[3]

BODLAENDER HL, 1987, RUUCS8722 U UTR DEP

[4] SHORT PROPOSITIONAL FORMULAS REPRESENT NONDETERMINISTIC COMPUTATIONS [J].