2005/06/20 by Piotr Faliszewski, Faliszewski, Piotr, Lane A. Hemaspaandra +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0506082
arxiv created 2005/06/20 · openalex publication_date 2005/06/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) ∈ L ∩ \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.