Hajim School Logo                                     URCS Mona Logo

Semi-Feasible Algorithms

UR-CS Participating Faculty: Lane A. Hemaspaandra (= Lane A. Hemachandra)

Project Description

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 $L$ for which there is a deterministic polynomial-time algorithm that, given as input any two strings, outputs the one in $L$ if exactly one is in $L$. 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.

References

1
This is a list of selected papers, from or related to this project, by University of Rochester authors. Links to essentially all Lane's conference and journal papers (and also his arXiv.org technical reports) can be found via the pointers from the related entries within Lane's entry at the DBLP project. Additionally, here is a link to Lane's complete publication list (note: that list does not itself have links to papers).
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. Denny-Brown, Y. Han, L. Hemaspaandra, and L. Torenvliet.
Semi-membership algorithms: Some recent advances.
SIGACT News, 25(3):12–23, 1994.
5
D. Eisenstat.
Simpler proofs of the power of one query to a P-selective set.
Technical Report TR-883, Department of Computer Science, University of Rochester, Rochester, NY, October 2005.
6
P. Faliszewski and L. Hemaspaandra.
Advice for semifeasible sets and the complexity-theoretic 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. Springer-Verlag 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 self-reducibility: 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 P-selective 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.
P-selectivity: 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 linear-nondeterminism, linear-sized, Karp–Lipton advice for the P-selective 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 top-Toda-equivalence-class 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 Semi-Feasible Algorithms.
Springer-Verlag, 2003.
24
L. Hemaspaandra and L. Torenvliet.
P-selectivity, 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. Springer-Verlag Lecture Notes in Computer Science #3881, January 2006.
25
L. Hemaspaandra, M. Zaki, and M. Zimand.
Polynomial-time semi-rankable 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.
CD-ROM ISSN 1201-8511/V2/#1.
$\begin{tabular}{l}
{}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\
\hline
\end{tabular}$

(Last modified: February 16, 2023.)


Lane A. Hemaspaandra