科学者は、決して解決されない特定のアルゴリズムを知っているか、遭遇しましたか、それともこれは私たちがまだ直面していない理論的概念ですか？
現在のところ、解決できないことが証明されている既知のアルゴリズムはありませんが、効率的なアルゴリズムが知られていない多くの問題があります。実際、コンピューターサイエンスで最も有名なオープンな問題の1つは、多項式時間で巡回セールスマンの問題（TSP）を解決できるアルゴリズムが存在するかどうかです。つまり、アルゴリズムの実行時間は多項式に比例します。入力のサイズの関数。

TSPは、特定の都市セットを訪問し、出発点に戻る可能性が最も短いルートを見つけることを伴う最適化の問題です。TSPを解決できるアルゴリズムがありますが、一般的に非常に遅いため、より大きな問題サイズに最適なソリューションを見つけることは保証されていません。

効率的なアルゴリズムが知られていない問題の他の例には、ナップサックの問題、グラフの着色の問題、最大派の問題が含まれます。これらはすべてNPハードの問題です。つまり、それらに対する解決策は多項式時間で検証できますが、解決策を見つけるには指数関数的な時間が必要になる場合があります。

理論的には、あらゆるアルゴリズムによって解決できない問題がある可能性がありますが、そのような問題が存在するかどうかは現在知られていません。しかし、解決できない問題の概念は、コンピューターサイエンスと数学の重要な問題であり、これらの問題の研究は、計算と複雑さの性質に関する多くの重要な洞察をもたらしました。