A thirty year old conjecture about promise problems
DOI10.1007/S00037-015-0107-6zbMATH Open1353.68102OpenAlexW1777658705WikidataQ123155226 ScholiaQ123155226MaRDI QIDQ347124FDOQ347124
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
Recommendations
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
- Probabilistic encryption
- Fully homomorphic encryption using ideal lattices
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- A Pseudorandom Generator from any One-way Function
- Title not available (Why is that?)
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Complexity Measures for Public-Key Cryptosystems
- The complexity of promise problems with applications to public-key cryptography
- 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
- Degrees of models
- Title not available (Why is that?)
- Title not available (Why is that?)
- Disjoint NP-Pairs
- Title not available (Why is that?)
- Separating NP-completeness notions under strong hypotheses
- Canonical disjoint NP-pairs of propositional proof systems
Cited In (3)
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)
