#compsci 

## Введение
Бывают ли такие задачи, сложность которых настолько велика, что ставит под сомнение практическую ценность применения ЭВМ для их решения?

Пример: "задача о рюкзаке"
![[Pasted image 20260224004411.png]]
![[Pasted image 20260224005438.png]]

## Определения (для задачи о рюкзаке)
P-задача:
![[Pasted image 20260224005505.png]]

NP-задача:
![[Pasted image 20260224005538.png]]

**NP-полными** (NP-complete) называются такие задачи, к которым может быть сведена любая NP задача за полиномиальная время, полиномиальное время:
![[Pasted image 20260224005841.png]]

Класс P содержится внутри NP, но неизвестно, совпадают ли они полностью.
Если бы классы полностью совпали (P = NP), тогда наличие полиномиального алгоритма для задачи верификации гарантировало бы, что существует полномиальный алгоритм для решения задачи разрешимости.
Если же классы не совпадают (P ≠ NP), то существуют задачи, для которых не может существовать полиномиального алгоритма для задачи решимости