Задача, для которой доказательство NP нетривиально

Question

Я ищу проблему, которая (доказуемо) лежит в NP, но для которой доказательство того, что она лежит в NP, "не совсем тривиально / очевидно". Кто-нибудь знает о такой проблеме (в идеале "естественная" проблема)?

Answer 1

Я думаю, что простота является хорошим кандидатом для этого:

Свидетельствовать, что число является составным, легко (дать факторизацию), и его можно эффективно проверить.

Свидетельствовать, что числопрост не так очевиден.Но с 80-х годов известно, что это можно сделать.Так что долгое время PRIMES был естественным языком в «NP intersect coNP».

Уже с 2004 года известно, что PRIMES фактически находится в P