NP 证明不平凡的问题
Problem for which proof of NP is non-trivial
我正在寻找一个（可证明）属于 NP 的问题，但它属于 NP 的证明是 "not completely trivial/obvious"。有人知道这样的问题吗（最好是 "natural" 问题）？
我认为素数是一个很好的选择：
证明一个数字是合数很容易（给出一个因式分解），并且可以有效地检查它。
见证一个数是质数并不是那么明显。但自 80 年代以来，人们就知道这是可以做到的。所以很长一段时间以来，PRIMES 都是 "NP intersect coNP" 中的一种自然语言。
从 2004 年开始就知道 PRIMES 实际上在 P
我正在寻找一个（可证明）属于 NP 的问题，但它属于 NP 的证明是 "not completely trivial/obvious"。有人知道这样的问题吗（最好是 "natural" 问题）？
我认为素数是一个很好的选择：
证明一个数字是合数很容易（给出一个因式分解），并且可以有效地检查它。
见证一个数是质数并不是那么明显。但自 80 年代以来，人们就知道这是可以做到的。所以很长一段时间以来，PRIMES 都是 "NP intersect coNP" 中的一种自然语言。
从 2004 年开始就知道 PRIMES 实际上在 P