1
| Класс P — это класс проблем, которые могут быть разрешены за полиномиальное время на детерминированной машине Тьюринга, а класс NP — это класс проблем, для которых, когда дается доказательство того, что ответ — «да» (называемое свидетелем), правильность свидетеля может быть проверена за полиномиальное время (это называется верификацией). Поскольку проблемы, разрешимые за полиномиальное время, также проверяемы за полиномиальное время, очевидно, что P⊆NP, но неясно, является ли P строгим подмножеством NP. Хотя доказательства еще нет, многие исследователи верят, что P≠NP. Это предположение о том, что класс P и класс NP не равны, называется "проблемой P≠NP".
|