Resource Bounds and Subproblem Independence |
| |
Authors: | Richard E Stearns Harry B Hunt III |
| |
Affiliation: | (1) Department of Computer Science, University at Albany – SUNY, Albany, NY 12222, USA |
| |
Abstract: | There are several reasons why some NP-hard problems can be solved
deterministically in 2O(n^a) time for some a,
0 < a < 1.
One reason is that the problem can be solved with a nondeterministic procedure
which uses only O(na) space. A second reason is that each instance of the problem
exhibits a high degree of "subproblem independence" (specifically O(na)
line channelwidth or treewidth).
A third is that each instance of the problem
can be solved using nondeterministic
straight-line programs where the number of variables is only O(na).
In this paper we show that, after imposing q-linear bounds
on the computation time and
obliviousness constraints on the nondeterminism,
these three reasons are essentially equivalent.
(q-Linear functions are similar to functions of the form n (log n)k.)
Specifically, the problem classes associated with these reasons
are interchangeable using reductions which are simultaneously polynomial time
and q-linear size-bounded.
We call these PQ-reductions.
The classes of problems solvable by these methods we call NQna.
Because these classes are defined in a very general way, they
include a rich variety
of problems.
We take this as evidence
that these classes have "power index" a
(i.e., that 2O(n^a) is also a lower time bound).
On the other hand, the easiness of all these problems
can be derived from "subproblem independence" considerations,
and thus the techniques associated with subproblem independence
are seen to be more widely applicable than
one might expect. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|