On Promise Problems (a survey in memory of Shimon Even)
Webpage for an article by Oded Goldreich
Abstract
The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion of ``unique solutions'',
the formulation of ``gap problems'' as capturing various
approximation tasks, the identification of complete problems
(especially for the class SZK), the indication of separations
between certain computational resources, and the enabling of
presentations that better distill the essence of various proofs.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.