A thirty Year old conjecture about promise problems

作者：Hughes Andrew^*; Mandal Debasis; Pavan A; Russell Nathan; Selman Alan L

来源：Computational Complexity, 2016, 25(4): 883-919.

DOI：10.1007/s00037-015-0107-6

• Promise problems
• ESY conjecture
• NP completeness
• truth-table reductions
• public-key cryptosystems

Even, Selman, and Yacobi (Even et al. in Inf Control 61(2):159-173, 1984, Selman and Yacobi in Proceedings of the 8th international colloquium on automata, languages, and programming, volume 140 of lecture notes in computer science. Springer, Berlin, pp 502-509, 1982) formulated a conjecture that in current terminology asserts that there do not exist disjoint NP-pairs all of whose separators are NP-hard via Turing reductions. In this paper, we consider a variant of this conjecture-there do not exist disjoint NP-pairs all of whose separators are NP-hard via bounded-truth-table reductions. We provide evidence for this conjecture. We also observe that if the original conjecture holds, then some of the known probabilistic public-key cryptosystems are not NP-hard to crack.

• 出版日期2016-12