|
Semi-Feasible Algorithms
Adapted from the introduction of the
book “Theory of Semi-Feasible Algorithms,” by
Lane Hemaspaandra
and
Leen Torenvliet:
The focus of complexity theory is the computational complexity of
sets. However, it is an underappreciated
fact that sets may have various
types of complexity, and not all types are harmony
with each other. For example, sets that are
complex in terms of
deterministic time may nonetheless be simple in other natural
senses. Unifying and making more widely accessible a vibrant stream
of research--semi-feasible computation--that perfectly showcases
this point is the primary goal of this book.
The semi-feasible sets, which are most commonly referred to as the
P-selective sets, are those sets for which there is a
deterministic polynomial-time algorithm that, given as input any two
strings, outputs the one in if exactly one is in
.
The reason we say that the semi-feasible sets
showcase the above distinction is that it
is well-known that the semi-feasible sets are arbitrarily complex
in terms of the deterministic time it takes to recognize them, yet
they are
simple in a wide range of other senses. In
particular, they have small circuits, they are in the extended low
hierarchy,
and
they cannot be
NP-complete
unless P=NP.
We find the semi-feasible sets to be fascinating for many
reasons. First, as mentioned above, they
showcase the fact that mere
deterministic time complexity is not the only potential type of
complexity in the world of computation; sets that are complex in
terms of deterministic time may nonetheless be simple in many other
computationally natural senses.
A
second reason that the semi-feasible sets are interesting
is that they crisply
capture the complexity of (left cuts of) real
numbers, and
recently a refinement of the semi-feasible sets has
been shown to capture the
complexity of complexity-bounded
real numbers.
A third and more historical reason for interest in the semi-feasible
sets is that they are the
complexity-theoretic analog of
a key notion from recursive function theory; the semi-feasible sets
are exactly what one gets when one alters the definition of
the semi-recursive
sets
by changing the selector function from “recursive”
to “polynomial-time computable.”
In the late 1960s the semi-recursive sets yielded great insight into
distinguishing the power
of reductions in the recursion-theoretic context,
and in 1979 Selman launched
a program that used--successfully, in the
context of
structural connections to exponential time--semi-feasible sets to understand
the structure of polynomial-time reductions.
A fourth and somewhat surprising reason to
study semi-feasible sets is that
semi-feasible sets (in their recently-defined nondeterministic
version) have been shown to conditionally resolve
Selman's important question as to whether NP machines can
cull down to one the large number of potential solutions of
satisfiable formulas; in particular, it is now known that NP lacks
such “unique solutions” unless the polynomial hierarchy
collapses.
- 1
-
This is a list of selected journal (except when the work has not yet
appeared in journal/book form) papers, from or related to this project, by
University of Rochester authors. Essentially all the papers listed below can
be found, in their full technical report versions, in the
UR-CS Technical Report Archive's theory
section. Here is
Lane's complete publication
list
and links to
essentially all his conference and journal papers (and also his arXiv.org
technical reports) can be found via the “EE” (electronic edition) links at
Lane's entry at the DBLP
project.
- 2
-
R. Beigel, R. Chang, and M. Ogiwara.
A relationship between difference hierarchies and relativized
polynomial hierarchies.
Mathematical Systems Theory, 26(3):293-310, 1993.
- 3
-
L. Hemaspaandra and S. Jha.
Defying upward and downward separation.
Information and Computation, 121(1):1-13, 1995.
- 4
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
An introduction to query order.
Bulletin of the EATCS, 63:93-107, 1997.
- 5
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Query order in the polynomial hierarchy.
Journal of Universal Computer Science, 4(6):574-588, 1998.
- 6
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
R
(NP) distinguishes robust
many-one and Turing completeness.
Theory of Computing Systems, 31(3):307-325, 1998.
- 7
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
What's up with downward collapse: Using the easy-hard technique to
link boolean and polynomial hierarchy collapses.
SIGACT News, 29(3):10-22, 1998.
- 8
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
A downward collapse within the polynomial hierarchy.
SIAM Journal on Computing, 28(2):383-393, 1999.
- 9
-
L. Hemaspaandra, H. Hempel, and G. Wechsung.
Query order.
SIAM Journal on Computing, 28(2):637-651, 1999.
- 10
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Using the no-search easy-hard technique for downward collapse.
Technical Report TR-752, Department of Computer Science, University
of Rochester, Rochester, NY, June 2001.
- 11
-
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.
Extending downward collapse from 1-versus-2 queries to
-versus- queries.
SIAM Journal on Computing, 34(6):1352-1369, 2005.
(Last modified: February 15, 2020.)
Lane A. Hemaspaandra
|