В 60-е годы прошлого века встал вопрос - все ли задачи теоретически имеют алгоритм для своего решения, который выполняется за "разумное" время?  
Для ответа на этот вопрос были введены **сложностные классы задач (классы сложности)**:  
1. Класс $P$ - к этому классу относятся все задачи, которые можно решить за полиномиальное время. Т. е., сложность алгоритма, решающего эту задачу - $O(n^k)$. В большинстве известных задач значение $k≤6$. Полиномы обладают тем свойством, что их сумма и произведение также полином. Считается, что все задачи, имеющие для своего решения полиномиальные алгоритмы, решаются за "разумное" время
2. Класс $NP$ - полиномиально-проверяемые задачи. Пусть имеется некоторое решение задачи. Если за полиномиальное время можно проверить, верно это решение или нет, то задача относится к классу $NP$. Очевидно, что все полиномиальные задачи класса $P$ одновременно принадлежат и к классу $NP$. А обратное утверждение (все $NP$ относятся к классу $P$) до сих пор стоит под вопросом. Более того, на сегодняшний день принята следующая картина:  
![Классы P и NP](../Pictures/11_01.%20Классы%20P%20и%20NP.png)  
Пример задачи, которая относится к классу $NP$, но для которой до сих пор неизвестен полиномиальный алгоритм решения: Дано множество чисел $a_1, a_2, ..., a_N$ и некоторое число $B$. Найти такой вектор $X = (x_1, x_2, x_3, ..., x_N)$, где $x_i=(0,1)$.  
$x_1∗a_1 + x_2∗a_2 + ... + x_N∗a_N=B$  
$P=NP???$ 
3. $NPC$ - $NP$ полные задачи. Понятие $NPC$-задачи было введено в начале 70-х годов прошлого века и напрямую связано с понятием сводимости одной задачи к другой. Под сводимостью понимается следующее: пусть имеется задача $Z1$ и решающий ее алгоритм $A1$ и задача $Z2$, алгоритм решения которой неизвестен. Если мы сможем переформулировать $Z2$ в терминах $Z1$, то будет возможно ее решить тем же алгоритмом $A1$. К классу $NPC$ относятся те задачи, к которым могут быть сведены все $NP$ (это доказано!)  
![Классы P, NP и NPC](../Pictures/11_02.%20Классы%20P,%20NP%20и%20NPC.png)  
Предыдущий пример относится к $NPC$-задачам.  
Если в классе $NPC$ найдется хоть одна задача, для которой будет найден полиномиальный алгоритм, значит $P=NP$