Некоторые реальные примеры задач, связанные с проблемой P и NP:

• Задача поиска клики. 2 Предположим, что в большой компании некоторые люди знакомы друг с другом. 2 Нужно найти размер максимальной группы людей, в которой все будут друг с другом знакомы. 2
• Задача коммивояжёра. 24 Дан набор городов и расстояний между ними, требуется найти кратчайший маршрут, следуя которому можно посетить все города. 2
• Задача о нахождении гамильтонова цикла в графе. 4 Задан граф на n вершинах, в котором некоторые пары вершин соединены рёбрами, а некоторые нет. 4 Нужно выяснить, найдётся ли такой циклический путь по рёбрам графа, который по разу проходит через все вершины. 4
• Задача пропозициональной выполнимости (SAT). 2 По заданной булевской формуле требуется определить, истинна ли она хоть при каких-нибудь значениях переменных. 2

Проблема P и NP связана с вопросом о том, совпадают ли два класса задач. 5 Класс P включает задачи, которые компьютер может решить эффективно, то есть за полиномиальное время, а класс NP содержит задачи, для которых можно быстро проверить правильность уже существующего решения. 5