From arXiv’s cs daily comes a theory paper that can be used to deal with matters of life and death. How could theory be any more practical than *that*? 
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).”
Full information:
Paper: cs.CC/0506082
Date: Mon, 20 Jun 2005 22:33:51 GMT (100kb,S)
Title: Open Questions in the Theory of Semifeasible Computation
Authors: Piotr Faliszewski and Lane A. Hemaspaandra
Report-no: URCS-TR-2005-872
Subj-class: Computational Complexity
ACM-class: F.1.3
\
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.
\ ( http://arXiv.org/abs/cs/0506082 , 100kb)
