Algorithms for solving NP problems

1.

ALGORITHMS FOR SOLVING
NP PROBLEMS

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.

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 to any such problem is found, then
all problems from the NP class will be quickly solvable.

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 items

12.

TABLE 1 - CONDITION OF THE PROBLEM OF PACKING A BACKPACK
Item number
Value
Weight
1
3
5
2
5
10
3
4
6
4
2
5

13.

Weight
Objects
Picture 6 - coordinate system illustrating the implementation
of the dynamic