SemiFeasible Algorithms
Adapted from the introduction of the
book “Theory of SemiFeasible 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—semifeasible computation—that perfectly showcases
this point is the primary goal of this book.
The semifeasible sets, which are most commonly referred to as the
Pselective sets, are those sets for which there is a
deterministic polynomialtime algorithm that, given as input any two
strings, outputs the one in if exactly one is in
.
The reason we say that the semifeasible sets
showcase the above distinction is that it
is wellknown that the semifeasible 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
NPcomplete
unless P=NP.
We find the semifeasible 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 semifeasible sets are interesting
is that they crisply
capture the complexity of (left cuts of) real
numbers, and
recently a refinement of the semifeasible sets has
been shown to capture the
complexity of complexitybounded
real numbers.
A third and more historical reason for interest in the semifeasible
sets is that they are the
complexitytheoretic analog of
a key notion from recursive function theory; the semifeasible sets
are exactly what one gets when one alters the definition of
the semirecursive
sets
by changing the selector function from “recursive”
to “polynomialtime computable.”
In the late 1960s the semirecursive sets yielded great insight into
distinguishing the power
of reductions in the recursiontheoretic context,
and in 1979 Selman launched
a program that used—successfully, in the
context of
structural connections to exponential time—semifeasible sets to understand
the structure of polynomialtime reductions.
A fourth and somewhat surprising reason to
study semifeasible sets is that
semifeasible sets (in their recentlydefined 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, plus in some cases some conference articles)
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 URCS 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

E. Allender and L. Hemachandra.
Lower bounds for the low hierarchy.
Journal of the ACM, 39(1):234–251, 1992.
 3

J.Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.
Competing provers yield improved Karp–Lipton collapse results.
Information and Computation, 198(1):1–23, 2005.
 4

D. DennyBrown, Y. Han, L. Hemaspaandra, and L. Torenvliet.
Semimembership algorithms: Some recent advances.
SIGACT News, 25(3):12–23, 1994.
 5

D. Eisenstat.
Simpler proofs of the power of one query to a Pselective set.
Technical Report TR883, Department of Computer Science, University
of Rochester, Rochester, NY, October 2005.
 6

P. Faliszewski and L. Hemaspaandra.
Advice for semifeasible sets and the complexitytheoretic
cost(lessness) of algebraic properties.
International Journal of Foundations of Computer Science,
16(5):913–928, 2005.
 7

P. Faliszewski and L. Hemaspaandra.
Open questions in the theory of semifeasible computation.
SIGACT News, 37(1):47–65, 2006.
 8

P. Faliszewski and L. Hemaspaandra.
The consequences of eliminating NP solutions.
Computer Science Review, 2(1):40–54, 2008.
 9

E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe.
On the complexity of kings.
In Proceedings of the 16th International Symposium on
Fundamentals of Computation Theory, pages 328–340. SpringerVerlag Lecture
Notes in Computer Science #4639, August 2007.
 10

E. Hemaspaandra, L. Hemaspaandra, T. Tantau, and O. Watanabe.
On the complexity of kings.
Theoretical Computer Science, 411(4–5):783–798, 2010.
 11

L. Hemaspaandra.
Beautiful structures: An appreciation of the contributions of Alan
Selman.
SIGACT News, 45(3):54–70, 2014.
 12

L. Hemaspaandra.
Complexity classes.
In K. Rosen, editor, Handbook of Discrete and Combinatorial
Mathematics, pages 1308–1314. CRC Press, 2nd edition, 2018.
 13

L. Hemaspaandra.
The power of selfreducibility: Selectivity, information, and
approximation.
In D.Z. Du and J. Wang, editors, Complexity and Approximation,
pages 19–47. Springer, 2020.
 14

L. Hemaspaandra, H. Hempel, and A. Nickelsen.
Algebraic properties for selector functions.
SIAM Journal on Computing, 33(6):1309–1337, 2004.
 15

L. Hemaspaandra, A. Hoene, A. Naik, M. Ogiwara, A. Selman, T. Thierauf, and
J. Wang.
Nondeterministically selective sets.
International Journal of Foundations of Computer Science,
6(4):403–416, 1995.
 16

L. Hemaspaandra, A. Hoene, and M. Ogihara.
Reducibility classes of Pselective sets.
Theoretical Computer Science, 155(2):447–457, 1996.
Erratum appears in the same journal, 234(1–2):323.
 17

L. Hemaspaandra and Z. Jiang.
Pselectivity: Intersections and indices.
Theoretical Computer Science, 145(1–2):371–380, 1995.
 18

L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman.
Computing solutions uniquely collapses the polynomial hierarchy.
SIAM Journal on Computing, 25(4):697–708, 1996.
 19

L. Hemaspaandra, C. Nasipak, and K. Parkins.
A note on linearnondeterminism, linearsized, Karp–Lipton
advice for the Pselective sets.
Journal of Universal Computer Science, 4(8):670–674, 1998.
 20

L. Hemaspaandra, M. Ogihara, and G. Wechsung.
Reducing the number of solutions of NP functions.
Journal of Computer and System Sciences, 64(2):311–328, 2002.
 21

L. Hemaspaandra, M. Ogihara, M. Zaki, and M. Zimand.
The complexity of finding topTodaequivalenceclass members.
Theory of Computing Systems, 39(5):669–684, 2006.
 22

L. Hemaspaandra and L. Torenvliet.
Optimal advice.
Theoretical Computer Science, 154(2):367–377, 1996.
 23

L. Hemaspaandra and L. Torenvliet.
Theory of SemiFeasible Algorithms.
SpringerVerlag, 2003.
 24

L. Hemaspaandra and L. Torenvliet.
Pselectivity, immunity, and the power of one bit.
In Proceedings of the 32nd International Conference on Current
Trends in Theory and Practice of Computer Science, pages 323–331.
SpringerVerlag Lecture Notes in Computer Science #3881, January 2006.
 25

L. Hemaspaandra, M. Zaki, and M. Zimand.
Polynomialtime semirankable sets.
In Journal of Computing and Information, 2(1), Special
Issue: Proceedings of the 8th International Conference on Computing and
Information, pages 50–67, 1996.
CDROM ISSN 12018511/V2/#1.
(Last modified: February 28, 2021.)
Lane A. Hemaspaandra
