Алгоритм Левина

Рассмотрим задачу, ответ к которой можно проверить просто и быстро, например судоку или составление расписания.
Можно ли такую задачу решить за полиномиальное время? За какое время решать оптимально?

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

Описание алгоритма весьма анекдотично. Если хотите весёлую короткую историю минут на 10-15, приходите.
