Более того — решение десятой проблемы Гильберта как "любое перечислимое множество диофантово" устроено очень похоже на сведение к 3-SAT: чтобы нас убедить, что алгоритм -- машина Тьюринга, или, лучше, машина со счётчиками -- на данном входе хоть когда-нибудь останавливается, он приходит со справкой-сертификатом-протоколом своего выполнения, где (помимо всего прочего) записаны (в системе счисления с огромным основанием, "чтобы влезло") все состояния во все моменты времени. А многочлен проверяет, что все переходы действительно сделаны правильно (и для этого нужны ещё дополнительные переменные — они работают "справкой", удостоверяющей, что протокол-справка заполнен правильно).