A thirty year old conjecture about promise problems

DOI10.1007/s00037-015-0107-6zbMath1353.68102OpenAlexW1777658705WikidataQ123155226 ScholiaQ123155226MaRDI QIDQ347124

A. Pavan, Debasis Mandal, Nathan Russell, Andrew D. Hughes, Selman, Alan L.

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Canonical disjoint NP-pairs of propositional proof systems
• Probabilistic encryption
• Diagonalizations over polynomial time computable sets
• Genericity and measure for exponential time
• Resource bounded randomness and weakly complete problems
• Bi-immunity separates strong NP-completeness notions
• Separation of NP-Completeness Notions
• A Thirty Year Old Conjecture about Promise Problems
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Degrees of models
• The complexity of promise problems with applications to public-key cryptography
• Complexity Measures for Public-Key Cryptosystems
• A Pseudorandom Generator from any One-way Function
• Disjoint NP-Pairs
• Fully homomorphic encryption using ideal lattices
• Separating NP-completeness notions under strong hypotheses

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