技術

計算可能性の理論と複雑さの紹介

あなたは今まで疑問に思ったことはありますか：あなたがこの記事を読んでいるデバイスは正確には何ですか？コンピューターとは何ですか？コンピュータサイエンスは、これらの最新のコンピューティングデバイスが考えられるずっと前の時代にまでさかのぼります。最もよくある質問がプログラミング言語、フレームワーク、およびライブラリを中心に展開している業界では、コンピュータを当然のこととして機能させる基本的な概念を採用することがよくあります。

しかし、無限の可能性を秘めているように見えるこれらのコンピューターには、何か制限がありますか？コンピューターでは解決できない問題はありますか？

計算可能性と複雑さの理論

この記事では、プログラミング言語とコンピューターアーキテクチャの詳細から離れて、これらの質問に対処します。コンピューターとアルゴリズムの能力と限界を理解することで、私たちはさまざまな戦略についての考え方とより良い推論を改善することができます。

コンピューティングの抽象的な見方は、1970年代に最初に開発されたときと同じように、今日の私たちにとって価値のある、時の試練に耐えてきた結果を生み出します。

Computabilidad

コンピューターとは何ですか？何が問題なのですか？

学校では、問題や機能のメンタルモデルを教えられることがよくあります。

関数は、出力f（x）を見つけるために入力xに適用するプロシージャです。

これは、ことが判明数学的定義違います：

関数は、各ペアの最初の要素がセットX（ドメインと呼ばれる）から来て、各ペアの2番目の要素がセットY（コドメインまたは範囲と呼ばれる）と各要素から来るように順序付けられたペアのセットです。ドメインのは、範囲の1つの要素とペアになっています。

それで十分でした。しかし、それは正確にはどういう意味ですか？

この定義は、コンピューターが関数を計算するためのマシンであることを示しています。

どうして？

コンピュータは任意の入力を何らかの出力に変換するからです。言い換えれば、彼らは問題を解決します。関数の2つの定義、私たちがよく知っているものと正式なものは、多くの実用的な目的で一致しています。

ただし、数学的な定義により、処理できない関数の存在（つまり、解決策のない問題）などの興味深い結論に達することができます。

すべての関数をアルゴリズムとして記述できないのはなぜですか。

ゲームのルール

私たちの議論を助けるために、コンピュータを入力を持ち、一連の操作を実行し、しばらくして出力を与えるマシンとして想像してみましょう。

入力マシンのアルファベットを呼び出しましょう。これは、ある有限集合からの文字シーケンスのセットです。たとえば、マシンのアルファベットは2進数（0と1）にすることも、ASCII文字セットにすることもできます。文字の有限シーケンスは文字列です（例：「0110」）。

また、マシンの結果を、マシンが（うまくいけば）計算を終了すると配信されるバイナリの受け入れと拒否の決定として表します。この抽象化は、上記の関数の数学的定義によく適合します。

コンピューターの受け入れ-拒否

これらのパラメータを考えると、もう1つのタイプ、つまり文字列のコレクションを特徴づけることが重要です。おそらく、マシンが受け入れる文字列のセットに関心があるか、特定のセットの文字列を受け入れ、他のセットを受け入れないマシンを構築しているのか、特定のすべてを受け入れるマシンを設計できるかどうかを尋ねているのかもしれません。セットであり、他ではありません。

これらすべての場合において、文字列のセットは言語と呼ばれます。たとえば、偶数を表すすべてのバイナリ文字列のセット、または偶数の文字を持つ文字列のセットです。数字のような言語は、オペレーターと取引連結、和集合、共通部分などのように。

重要な演算子は、正規表現でも使用されるクリーネ閉包演算子です。これは、言語のすべての可能な力の結合と見なすことができます。たとえば、私たちの言語の場合には文字列のセット{‘01’、 ‘1’}であり、その後のメンバーに* 文字列「0101111」です。

会計

すべての関数が計算可能であるとは限らないという私たちの主張を証明する前のパズルの最後のピースは、会計の概念です。直感的に、私たちのテストはより多くの言語があることを示します。つまり、それらを解決するための可能なプログラムよりも多くの問題があります。これは、文字列が言語に属しているかどうか（はい/いいえ）の問題自体が問題であるために機能します。

より正確には、私たちのテストでは、可能なプログラムのセットは無限に数えられるが、アルファベットの言語のセットは無限に数えられないと述べています。

この時点で、「無限大はそれ自体がかなり奇妙なアイデアです。今、私はそれらのうちの2つに対処する必要があります！」と考えているかもしれません。

まあ、それはそれほど悪くはありません。可算無限集合は、列挙できるものです。これは最初の要素、これは2番目の要素というように、最終的にセット内の各要素に番号を割り当てます。たとえば、偶数のセットを考えてみましょう。 2が最初、4が2番目、6が3番目というように言うことができます。そのような集合は、無限に可算または可算です。

ただし、実数のようないくつかのセットでは、あなたがどれほど賢いかは関係ありません。単に列挙はありません。これらのセットは無数の無限または数えられない。

多くの会計プログラム

まず、コンピュータプログラムのセットが可算であることを示したいと思います。私たちの目的のために、有限のアルファベット上のすべての文字列のセットが可算であることを観察することによってこれを行います。コンピュータプログラムは有限の文字列であるため、これは機能します。

の証拠これは簡単で、ここでは詳細を説明しません。重要な点は、たとえば自然数と同じ数のコンピュータプログラムがあるということです。

繰り返しますが：

Linuxはどのプログラミング言語を使用していますか

任意のアルファベットのすべての文字列のセット（たとえば、すべてのコンピュータープログラムのセット）は可算です。

無数の多くの言語

この結論を考えると、これらの文字列のサブセットはどうですか？別の方法で尋ねると、すべての言語のセットはどうですか？このセットは数えられないことがわかりました。

アルファベット上のすべての言語のセットは数えられません。
変換可能なノートとは何ですか

繰り返しますが、カバーしませんの証拠ここに。

結果

それらはすぐには明らかにならないかもしれませんが、無数の言語とすべてのコンピュータープログラムのアカウンティングの結果は深刻です。

どうして？

仮定しましょうに ASCII文字セットです。インクルード ASCII文字それらはコンピュータプログラムを作成するためにのみ必要です。たとえば、JavaScriptプログラムを表す文字列のセットはのサブセットであることがわかります。に* （ここで、*はクリーネのスター演算子です）。 JavaScriptの選択は任意です。このプログラムのセットは可算集合のサブセットであるため、JavaScriptのプログラムのセットは可算である必要があります。

また、どの言語でもそれを考慮しましょう L いくつかの関数を定義できます f 文字列がある場合は1と評価されますバツ入った L それ以外の場合は0。これらの機能はすべて異なります。すべての言語のセットと1：1の対応があり、すべての言語のセットは数えられないため、これらすべての関数のセットは数えられないことがあります。

詳細は次のとおりです。

すべての有効なプログラムのセットは可算ですが、関数のセットはカウントできないため、プログラムを作成できない関数がいくつかあるはずです。

これらの機能や問題がどのように見えるかはまだわかりませんが、存在することはわかっています。解決策のない問題がいくつかあるので、これは謙虚な認識です。私たちは、コンピューターは非常に強力で有能であると考えていますが、いくつかのことは手が届きません。

今の質問は、「これらの問題はどのようなものですか？」です。これらの問題の説明を続ける前に、まず一般化された方法で計算をモデル化する必要があります。

チューリングマシン

コンピューターの最初の数学モデルの1つは、AlanTuringによって開発されました。チューリングマシンと呼ばれるこのモデルは、計算可能性の概念を完全に捉えた非常にシンプルなデバイスです。

チューリングマシン

マシンへの入力は、入力が書き込まれたテープです。読み取り/書き込みヘッドを使用して、マシンは一連のステップを通じて入力を出力に変換します。各ステップで、テープに書き込むかどうか、何を書き込むか、および右に移動するか左に移動するかが決定されます。この決定は、正確に2つのことに基づいています。

頭の下の現在のシンボルと
マシンの内部状態。記号が入力されると更新されます。

以上です。

普遍

1926年、アランチューリングはチューリングマシンを開発しただけでなく、彼の有名な記事「計算可能な数値について」を書いたときに、計算の性質についていくつかの重要なアイデアを持っていました。彼は、コンピュータープログラム自体がコンピューターへの入力と見なすことができることに気づきました。この観点から、彼はチューリングマシンがその入力をシミュレートまたは実行できるという美しいアイデアを持っていました。

今日、これらのアイデアは当然のことと考えていますが、チューリングの時代には、そのような万能チューリング機械のアイデアは、チューリングが解決できない問題を開発することを可能にした画期的なものでした。

チャーチチューリングテーゼ

先に進む前に、重要な点を調べてみましょう。チューリングマシンは計算モデルであることはわかっていますが、それで十分一般的ですか？この質問に答えるために、私たちはに目を向けますチャーチチューリングテーゼ、これは次のステートメントに信用を与えます：

計算可能なものはすべてチューリングマシンで計算できます。

チューリングが計算モデルとしてチューリングマシンを開発した一方で、アロンゾチャーチはラムダ計算として知られる微積分モデルも開発しました。これらのモデルは、コンピューティングを記述し、今日のどのコンピューターやどのコンピューターとも同等の方法で記述しているという点で強力です。これは、チューリングマシンを使用して、私たちが求めている解決できない問題を説明できることを意味します。私たちの調査結果は、考えられるすべてのコンピューターに当てはまることがわかっています。

認識と決定可能性

解決できない問題、つまり言語認識機能と言語決定要因の概念を具体的に説明する前に、もう少し背景を説明する必要があります。

言語を認識するチューリングマシンがあれば、その言語は認識できます。

Y

言語を決定するチューリングマシンがあれば、言語は決定可能です。

言語を認識するために、チューリングマシンはその言語の文字列をすべて受け入れる必要があり、その言語以外のものを受け入れてはなりません。これらの文字列を拒否または繰り返すことができます。決定要因となるために、チューリングマシンは常に受け入れまたは拒否することによって入力を停止する必要があります。

ここでは、エントリを停止するという考えが重要です。実際、決定要因は認識機能よりも強力であることがわかります。また、問題を解決することができます。つまり、関数によって記述される言語を決定するチューリングマシンが存在する場合にのみ、関数を決定できます。

判読不能

コンピュータプログラムを書いたことがあるなら、プログラムの実行中にコンピュータが車輪を回すのを見るだけで、そこに座っているとどんな感じかを知っている必要があります。プログラムに時間がかかるのか、コードに無限ループの原因となるエラーがあるのかは不明です。コンパイラがコードをチェックして、実行時にコードが停止したり、永久に繰り返されたりするかどうかを確認しないのはなぜか疑問に思われるかもしれません。

コンパイラーには、実行できないため、そのような制御はありません。コンパイルエンジニアが十分に賢くない、またはリソースが不足しているわけではありません。任意のコンピュータプログラムをチェックして、停止するかどうかを判断することは不可能です。

チューリングマシンを使用してこれをテストできます。チューリングマシンは文字列として記述できるため、数え切れないほどの数があります。 Mと仮定します₁、M₂、などがすべてのチューリングマシンのセットを構成します。次の関数を定義します。

f（i、j）= 1 si M_私あなたは受け入れるj>、反対に0

これが「M文字列エンコーディング」の構文であり、この関数はMの場合に1を生成する問題を表します。_私Mを受け入れると停止します_j逆に、入力および出力0として。 Mに注意してください_私停止する必要があります（つまり、取引のブレーカーになります）。これは、決定不可能な関数（つまり、解決策のない問題）を記述したいので必要です。

それでは、言語も定義しましょう L これは、独自の説明を受け入れないチューリングマシンの文字列エンコーディングで構成されています。

L =

たとえば、いくつかのマシンM₁入力用に0を出力できます1＆gt、他のマシンM₂入力に出力1を与えることができます2>。この言語が決定不可能であることを証明するために、Mは何をするのかを尋ねます_L、独自の説明が与えられたときに言語Lを決定するマシンL>入力として。 2つの機会があります：

M_Lあなたは受け入れるL>>

または

M_L拒否しますL>>

Si M_L独自のエンコーディングを受け入れるため、L>は言語Lではありません。ただし、その場合、M_Lそもそもあなたのエンコーディングを受け入れるべきではなかった。一方、Mの場合_L独自のエンコーディングを受け入れない場合L>は言語Lであり、次にM_L文字列エンコーディングを受け入れる必要があります。

どちらの場合も、L言語が決定不可能であることを示すパラドックス、または数学的には矛盾があります。したがって、最初の解決できない問題について説明しました。

問題を止める

今説明した問題は関連性がないように見えるかもしれませんが、実際に重要な追加の解決できない問題、特に拘禁問題：

空の文字列で停止するチューリングマシンエンコーディングの言語。

停止の問題は、コンパイラが無限ノットを早期に検出できない理由に当てはまります。プログラムが空の文字列で終了するかどうかを判断できない場合、その実行によって無限の結び目が生じるかどうかをどのように判断できますか？この時点で、私たちは簡単な結論に達するために手を振っていたように見えるかもしれませんが、チューリングマシンはコンピュータプログラムが停止するか、永遠に結び目にとどまるかを判断できないことに気付きました。これは実際のアプリケーションでは大きな問題であり、チューリングマシンやその他のタイプのコンピューターでは解決できません。 iPhoneではこの問題を解決できません。多くのコアを備えたデスクトップでは、この問題を解決できません。クラウドはこの問題を解決できません。誰かが量子コンピューターを発明したいと思ったとしても、彼らはそれでも停止問題を解決することができないでしょう。

概要

計算可能性理論の検討では、数え上げ引数によって、通常の意味では計算できない関数がどのようにあるかを確認しました。計算の意味を正確に定義し、チューリングマシンを形式化するための鉛筆と紙に関する彼自身の経験からのチューリングのインスピレーションに戻ります。このモデルが現在または将来のコンピューターで計算できるものをどのように計算できるかを見てきましたが、まったく計算できないクラスの問題に気づきました。

それでも、計算可能性には欠点があります。問題を解決できるからといって、すぐに解決できるとは限りません。結局のところ、太陽が何千万年も先に私たちに新星をもたらす前にその計算が終了しないのであれば、コンピューターは何が良いのでしょうか？

計算可能な関数と言語を残して、計算の複雑さについて説明し、効率的な計算と有名なP対を調べます。 NP。

複雑

遅い対。速い

コンピューター科学者はさまざまなクラスの問題を認識しており、私たちにとって重要な2つのクラスには、コンピューターが迅速または効率的に解決できる問題が含まれます。 P 解決策をすばやく検証できるが、すぐには取得できない問題。 例えば 。

たとえば、あなたがオンラインデートサービスのアルゴリズムを開発する責任があり、誰かが「誰もがデートをすることができますか？」という質問をしたとします。答えは、すべての人が一致するように、互換性のある個人を一致させることに要約されます。この問題を解決するための効率的なアルゴリズムがあることがわかりました。この問題はセットにあります P 。

さて、ユーザーの中で最大の兄弟関係を特定したい場合はどうでしょうか。兄弟愛とは、互いに互換性のある個人の最大のネットワークを意味します。ユーザー数が少ない場合、この問題は迅速に解決できます。たとえば、3人のユーザーがいるギルドを簡単に識別できます。しかし、より大きなソロリティを探し始めると、問題の解決はますます困難になります。この問題はセットにあります 例えば 。

正式な定義

P は、多項式時間で解くことができる一連の問題です。つまり、計算ステップの数は、問題のサイズに関する多項式関数によって制限されます。「誰もがデートできますか？」という質問は、二部一致問題、入った P 。

例えば は、多項式時間で検証可能な一連の問題です。もちろん、これにはPのすべての問題が含まれます。ただし、この封じ込めが厳格かどうかはわかりません。効率的に検証できるが効率的に解決できない問題はわかっていますが、問題が本当に解決できないかどうかはわかりません。兄弟愛の問題はそれらの問題の1つです。解決策を効率的に検証できることはわかっていますが、問題を効率的に解決できるかどうかはわかりません。

最後に、 NP完全 で最も難しい問題である問題のセットです 例えば 。で問題が発生したため、最も難しいと言われています 例えば 効率的に変換することができます NPC 。その結果、誰かが問題の効率的な解決策を特定した場合 NPC 、あらゆる種類 例えば によって吸収されます P 。兄弟愛の問題も NPC

P対NP

したがって、私たちはの問題になります P に対して 例えば 。多くのコンピュータ科学者や数学者は、 P Y 例えば それらは同じではありません。もしそうなら、その影響は深遠ではありません。今日のデジタルインフラストラクチャの多くは、に問題があるという事実に基づいています 例えば にない P 。そうでない場合、たとえば暗号化方式は一夜にして崩壊し、問題の効率的な解決策を持っている人が NPC 最も厳しいセキュリティプロトコルでさえ破壊する可能性があります。

トレーサビリティの微妙さ

コンピュータ初心者にとって、マッチメイキングとギルドの問題の違いは大したことではないようです。実際、問題の違いは P との問題 例えば それは非常に微妙な場合があります。違いを見分けることができることは、現実の世界でアルゴリズムを設計する人にとって重要です。

最短経路問題を考えてみましょう。 2つの場所が与えられた場合、目標はそれらの間の最短経路を特定することです。 iPhoneはこれをミリ秒単位で計算します。これは計算上処理可能な問題です。

Python3にアップグレードする方法

一方、ホーカーの問題を考えてみましょう。目標は、可能な限り最短距離を移動しながら、原点で終わる可能性のある目的地のサブセットを訪問することです。この問題は最短経路問題に似ていますが、NP完全です。また、サプライチェーンロジスティクスが10億ドル規模の産業である理由についても説明します。

実際、私たちはさらに微妙になる可能性があります。最短経路（P）を求める代わりに、結び目のない最長経路を求めることができます。最長パスの問題もNP完全であることがわかります。

この微妙な違いには、2部グラフとの頂点カバレッジの識別など、さらに多くの例があります。句ごとに2つおよび3つのリテラルを持つ一般的または満足のいくブール式。重要なのは、問題がPにあるのかNPにあるのかがすぐにはわからないため、ランタイム分析の理由は重要なスキルです。設計しなければならないアルゴリズムがPの問題に対するものである場合、効率的な解決策があることがわかります。一方、問題がNPにある場合、アルゴリズムは一般に問題を解決するのに時間がかかりすぎるため、解決策を探すことに反対する強いケースがあります。

概要

この複雑さのテストでは、問題クラスPとNPを定義します。 Pは非公式にコンピューターで効率的に解決できる問題を表し、NPは効率的に検証できる問題を表します。

PがNPと等しくないことを示すことができた人は誰もいません。これらの2つのクラスの問題が同等である場合、それはP対として知られているものです。 NPは、数学のすべてではないにしても、今日の理論計算で最も重要な未解決の問題です。実際、2000年に、クレイ数学研究所は問題をPvsと名付けました。 NPは、数学における7つの最も重要な未解決の質問の1つであり、この問題の解決策を決定するテストに対して100万ドルの報酬を提供しています。