Algorithms for solving NP problems

Август 21, 2022

Главная
Математика
Algorithms for solving NP problems

Содержание

2. The purpose of presentation is to acquaint the listeners with the example of the problem of
3. Cryptography is the art and science of protecting messages with encryption. A cryptographic algorithm (or cipher,
4. ALGORITHM RELIABILITY Unconditional reliability - recovery of the plaintext or key is impossible with any amount
5. COMPLEXITY THEORY «Information theory claims that almost all cryptographic algorithms can be broken. Complexity theory determines
6. COMPLEXITY THEORY DEFINES AND CLASSIFIES complexity of algorithms the complexity of the tasks themselves
7. P VS NP PROBLEM
8. PROPERTIES OF NP-HARD PROBLEMS: NP-hard problem cannot be solved by existing algorithms; if a polynomial solution
9. Picture 1 - Hamiltonian graph with a distinguished Hamiltonian cycle
10. Picture 2 - example of the knapsack problem
11. Picture 3 - brute force tree for solving the problem of packing a backpack with 3
12. TABLE 1 - CONDITION OF THE PROBLEM OF PACKING A BACKPACK
13. Picture 6 - coordinate system illustrating the implementation of the dynamic Objects Weight
15. Скачать презентацию

Слайд 2

The purpose of presentation is to acquaint the listeners with the

example of the problem of finding a Hamiltonian cycle in a graph and the «Knapsack problem»:
with the concept of «NP complexity problems»
with algorithms for solving these problems

Слайд 3

Cryptography is the art and science of protecting messages with encryption.
A

cryptographic algorithm (or cipher, or key) is a mathematical function or two mathematical related functions (one for encryption, the other for decryption).

Слайд 4

ALGORITHM RELIABILITY
Unconditional reliability - recovery of the plaintext or key is

impossible with any amount of cipher text received by the cryptanalyst.
The algorithm is reliable if it is cracked will cost more than the cost of encrypted data take longer than keeping the data private the amount of data required exceeds the amount of data encrypted with a key.

Слайд 5

COMPLEXITY THEORY
«Information theory claims that almost all cryptographic algorithms can be

broken. Complexity theory determines whether they can be hacked before the thermal death of the universe».
Bruce Schneier. Applied Cryptography. Protocols, Algorithms, and Source Code in C

Слайд 6