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

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