Докажи равенство p и np классов (информатика)

Классы сложности P и NP

⚠️

Доказать равенство P и NP пока невозможно: это открытая математическая задача.

Докажи равенство p и np классов

Решение

Известно, что : задачу, решаемую за полиномиальное время, можно также проверить за полиномиальное время. Однако не известно, верно ли обратное включение . Поэтому равенство пока ни доказать, ни опровергнуть не удалось.

Ответ

Равенство — открытая проблема; доказательства пока нет.

Помогло?