Open Questions in the Theory of Semifeasible Computation
| dc.creator | Faliszewski, Piotr | |
| dc.creator | Hemaspaandra, Lane A. | |
| dc.date | 2005-06-20 | |
| dc.date.accessioned | 2026-07-07T03:23:10Z | |
| dc.date.available | 2026-07-07T03:23:10Z | |
| dc.description | The study of semifeasible algorithms was initiated by Selman's work a quarter of century ago [Sel79,Sel81,Sel82]. Informally put, this research stream studies the power of those sets L for which there is a deterministic (or in some cases, the function may belong to one of various nondeterministic function classes) polynomial-time function f such that when at least one of x and y belongs to L, then f(x,y) \in L \cap \{x,y\}. The intuition here is that it is saying: ``Regarding membership in L, if you put a gun to my head and forced me to bet on one of x or y as belonging to L, my money would be on f(x,y).'' In this article, we present a number of open problems from the theory of semifeasible algorithms. For each we present its background and review what partial results, if any, are known. | |
| dc.identifier | https://arxiv.org/abs/cs/0506082 | |
| dc.identifier | http://arxiv.org/abs/cs/0506082 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32836 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Open Questions in the Theory of Semifeasible Computation | |
| dc.type | text |