「自然な」NP完全型probとは何ですか？

Question

私はNP-Complete、NP-Hardなどの一般的な知識はかなりあると思いますが、突然何らかの文献に間違いがありました。それらの引用符で。私は彼らが何を意味しているのか理解していなかったので、私はそれをグーグルにしようとしました - それは何度かポップアップしましたが、

「自然な」NP完全な問題を言うときに意味するものは何ですか？

Answer 1

CS理論の文脈では、誰かが実際に遭遇する可能性が高い高度に考案された問題を定義することによって、特定のプロパティに問題があることを証明する人がいることがよくあります。例えば、Ladner's theoremはP ≠ NP場合、Pにではなく、またNP -completeではなく、考案特定の問題は非常にあるNPに問題があることを示しています意図された特性を有する唯一の目的のために作られたものである。これらの問題は、主観的に、不自然な問題と呼ばれています。何故ならば、問題は何らかの性質を持つように発明されたからです。

「自然な」問題は、主観的には興味深い理論的性質を持つことが後で示される、それ自体が興味深い問題です。そのコンテキストでは、「自然」NP完全な問題は、実際に実際に発生するNP完全な問題です。たとえば、3色性、ハミルトニアンサイクル問題、またはブールの充足可能性などです。