За решение этой задачки Марк Цукерберг учредил премию в размере 3.000.000 $

Да, это верно. Если положительный ответ на вопрос может быть быстро проверен с помощью сертификата, то это означает, что для данного входа существует корректный сертификат, который доказывает правильность ответа "да". И если такой сертификат существует, то его можно найти за полиномиальное время. Формально, это свойство называется верифицируемость в полиномиальное время и является ключевым свойством класса сложности NP (Nondeterministic Polynomial). В этом классе проблемы могут быть проверены за полиномиальное время, используя некоторый сертификат, но не обязательно могут быть решены за полиномиальное время без такого сертификата.