Open Questions in the Theory of Semifeasible Computation

Details Open Questions in the Theory of Semifeasible Computation Open Questions in the Theory of Semifeasible Computation

2005-06-20

arxiv.org/abs/cs/0506082v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Open Questions in the Theory of Semifeasible Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Open Questions in the Theory of Semifeasible Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Open Questions in the Theory of Semifeasible Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293173