Cryptocomplexity and NP-completeness

DOI10.1007/3-540-10003-2_71zbMath0444.94013OpenAlexW1552419442MaRDI QIDQ3888962

Yacov Yacobi, Shimon Even

Publication date: 1980

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-10003-2_71

zbMATH Keywords

NP-completenessknapsack problemNP-hardnesscryptocomplexitycryptosystemscracking problem

Mathematics Subject Classification ID

Cryptography (94A60) Data encryption (aspects in computer science) (68P25)

Related Items (12)

NP is as easy as detecting unique solutions ⋮ Polynomial time quantum computation with advice ⋮ Promise problems complete for complexity classes ⋮ Mathematical problems in cryptology ⋮ Promise problems and access to unambiguous computation ⋮ The Shrinking Property for NP and coNP ⋮ The shrinking property for NP and coNP ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ Algebraic cryptography: new constructions and their security against provable break ⋮ Hard promise problems and nonuniform complexity

This page was built for publication: Cryptocomplexity and NP-completeness