Κεφάλαιο 3Adobe PDF
(280.19 kB)
| Title Details: | |
|
Computation Complexity Background |
|
| Authors: |
Pagourtzis, Aristeidis Zachos, Efstathios Grontas, Panagiotis |
| Reviewer: |
Poulakis, Dimitrios |
| Subject: | MATHEMATICS AND COMPUTER SCIENCE > > > MATHEMATICS AND COMPUTER SCIENCE > NATURAL SCIENCES AND AGRICULTURAL SCIENCES > PHYSICS > INDERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY > > ENGINEERING AND TECHNOLOGY > > > MATHEMATICS AND COMPUTER SCIENCE > > MATHEMATICS AND COMPUTER SCIENCE > > MATHEMATICS AND COMPUTER SCIENCE > MATHEMATICS > NUMBER THEORY > COMPUTATIONAL NUMBER THEORY |
| Description: | |
| Abstract: |
Analysis of algorithm execution time: O, Ω, Θ notation. Efficient algorithms. The complexity class P. Intractable problems and the class NP. The concept of NP-completeness. Method of constructing a public-key system from an NP-complete problem. The Merkle-Hellman knapsack cryptosystem. Computations with random choices, probabilistic algorithms. The classes RP, BPP, ZPP. One-way functions and the class UP. Hierarchy of complexity classes. Security proofs based on computational hardness assumptions, cryptographic reductions.
|
| Type: |
Chapter |
| Creation Date: | 2015 |
| Item Details: | |
| License: |
Attribution - NonCommercial - ShareAlike 4.0 International (CC BY-NC-SA 4.0) |
| Handle | http://hdl.handle.net/11419/5442 |
| Bibliographic Reference: | Pagourtzis, A., Zachos, E., & Grontas, P. (2015). Computation Complexity Background [Chapter]. In Pagourtzis, A., Zachos, E., & Grontas, P. 2015. Computational Cryptography [Undergraduate textbook]. Kallipos, Open Academic Editions. https://hdl.handle.net/11419/5442 |
| Language: |
Greek |
| Is Part of: |
Computational Cryptography |
| Publication Origin: |
Kallipos, Open Academic Editions |