Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-018 | 6th February 2005 00:00

On Promise Problems (a survey in memory of Shimon Even [1935-2004])



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.

ISSN 1433-8092 | Imprint