runtime - np-完全だが「ハード」ではない

Question

NP完全であるが、「迅速な」アルゴリズムを知っている言語はありますか? ナップザックのように平均的にうまくいくという意味ではありません。最悪の場合でも、実行時間は 2^n^epsilon のようなものであり、結果は 0 より大きい任意の epsilon に対して保持されるため、任意に 0 に近づけることができます。

Answer 1

ウィキペディアによると、「停止問題など、NP 困難であるが NP 完全ではない決定問題もあります。」

「迅速な」アルゴリズムを知っている場合、NP 完全な言語はありません。そうしないと、NP 完全にはなりません。

Answer 2

この np 完全問題に対する「迅速な」アルゴリズムを見つけた場合、その P=NP を解決したことになり、ご存知のように、それはまだ未解決の問題です。