A thirty year old conjecture about promise problems

DOI10.1007/S00037-015-0107-6MaRDI QIDQ347124zbMATHOpenAlexWikidataFDO

Authors Debasis Mandal, Aduri Pavan, N. Russell, Andrew Hughes, Alan L. Selman

Publication date 30 November 2016

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-015-0107-6

zbMATH Keywords

NP-completenesspromise problemsESY conjecturepublic-key cryptosystemstruth-table reductions

Mathematics Subject Classification ID

Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A thirty year old conjecture about promise problems
• The complexity of promise problems with applications to public-key cryptography
• Complexity Measures for Public-Key Cryptosystems
• Disjoint NP-Pairs
• scientific article; zbMATH DE number 1834681

Cites work

• scientific article; zbMATH DE number 3811467 (Why is no real title available?)
• scientific article; zbMATH DE number 1302849 (Why is no real title available?)
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• scientific article; zbMATH DE number 1834681 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• A thirty year old conjecture about promise problems
• Bi-immunity separates strong NP-completeness notions
• Canonical disjoint NP-pairs of propositional proof systems
• Complexity Measures for Public-Key Cryptosystems
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Degrees of models
• Diagonalizations over polynomial time computable sets
• Disjoint NP-Pairs
• Fully homomorphic encryption using ideal lattices
• Genericity and measure for exponential time
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Probabilistic encryption
• Resource bounded randomness and weakly complete problems
• Separating NP-completeness notions under strong hypotheses
• Separation of NP-completeness notions
• The complexity of promise problems with applications to public-key cryptography

Cited in

(3)

• Some consequences of cryptographical conjectures for S 2 1 and EF
• A thirty year old conjecture about promise problems
• The complexity of promise problems with applications to public-key cryptography

This page was built for publication: A thirty year old conjecture about promise problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q347124)