Сложность проверки решений NP-сложных задач оптимизации?

Есть много задач оптимизации, которые, как известно, являются NP-сложными, например, задача коммивояжера, MAX-SAT или поиск минимального хроматического числа графа. Учитывая проблему подобного рода, мне интересно узнать о сложности следующей проблемы:

Учитывая NP-трудную задачу оптимизации и возможное решение S, является ли S оптимальным решением проблемы?

Интуитивно кажется, что это может быть сложной NP-сложной задачей, поскольку легко опровергнуть ответ на проблема оптимизации, угадав лучшее решение и используя его в качестве свидетеля, но я понятия не имею, как это показать. Фактически, я действительно не знаю, как рассуждать о сложности этой проблемы.

Кто-нибудь знает какие-либо хорошие нижние оценки сложности этой проблемы принятия решения? Было бы действительно интересно узнать, было ли это сложной совместной NP, сложной PSPACE и т. Д.