Пример НП - задачи

Рассмотрим задачу коммивояжера, заключающуюся в том, что он должен посетить всех покупателей, проживающих в различных городах, не превысив при этом установленной сметы. Таким образом, данная задача сводится к нахождению пути, суммарная протяжённость которого не превысит определённой величины.

Традиционное решение данной задачи заключается в систематическом рассмотрении возможных путей, сравнении их протяжённости с некоторым пределом, пока не будет найден приемлемый вариант или не будут рассмотрены все возможности.

Данный подход не имеет полиномиального временного решения следовательно, данное решение задачи коммивояжёра является непрактичным, особенно если необходимо посетить много городов.

Для решения этой задачи за разумное время необходимо найти более быстрый алгоритм. Мы можем получить последовательность задач которая не будет являться алгоритмом в техническом смысле. Говорят, что подобные команды недетерминированы, поэтому мы будем называть такой «алгоритм» недетерминированным алгоритмом. Но время, необходимое на выполнение недетерминированного алгоритма ограниченно кокой-то полиномиальной функцией. При использовании недетерминированного алгоритма появляется возможность решения задачи коммивояжёра за полиномиальное время.