Bitte wählen Sie ihr Lieferland und ihre Kundengruppe
A 'promise problem' is a formulation of a partial decision problem. Complexity issues about promise problems arise from considerations about cracking problems for public-key cryptosystems. Using a notion of Turing reducibility between promise problems, this paper disproves a conjecture made by Even and Yacobi (see Lecture Notes in Computer Science, vol.85, p.195-207, Springer/Verlag, Berlin/New York, 1980), that would imply nonexistence of public-key cryptosystems with NP-hard cracking problems. In its place a new conjecture is raised having the same consequence. In addition, the new conjecture implies that NP-complete sets cannot be accepted by Turing machines which have at most one accepting computation for each input word.