技術

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

あなたは今まで疑問に思ったことはありますか：あなたがこの記事を読んでいるデバイスは正確には何ですか？コンピューターとは何ですか？

計算科学は、これらの最新のコンピューティングデバイスが想像されるずっと前の時代にまでさかのぼります。よくある質問がプログラミング言語、フレームワーク、ライブラリを中心に展開している業界では、コンピュータを動かす基本的な概念を当然のことと思っていました。

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

計算可能性理論と複雑さ

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

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

計算可能性

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

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

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

判明数学的定義違います：

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

それはかなり一口でした。しかし、それは正確にはどういう意味ですか？

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

どうして？

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

C ++コードをコンパイルする方法

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

なぜなら、すべての関数をアルゴリズムとして説明できるわけではないからです。

ゲームのルール

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

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

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

承認-拒否コンピューター

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

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

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

可算性

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

より正確には、私たちの証明は、可能なプログラムのセットは数え切れないほど無限であるのに対し、アルファベット上の言語のセットは数え切れないほど無限であると主張しています。

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

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

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

可算数のプログラム

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

の証拠は簡単で、ここでは詳細を説明しません。重要なポイントは、自然数などと同じ数のコンピュータプログラムが存在することです。

繰り返しますが：

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

数え切れないほど多くの言語

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

アルファベット上のすべての言語のセットは数えられません。

繰り返しになりますが、の証拠ここに。

結果

それらはすぐには明らかにならないかもしれませんが、言語の数えられないこととすべてのコンピュータプログラムのセットの数えられないことの結果は深刻です。

どうして？

仮定しますに ASCII文字のセットです。 ASCII文字コンピュータプログラムを構成するために必要なものだけです。たとえば、JavaScriptプログラムを表す文字列のセットは、のサブセットであることがわかります。に* （ここで、*はクリーネ閉包演算子です）。 JavaScriptの選択は任意です。このプログラムのセットは可算集合のサブセットであるため、JavaScriptプログラムのセットは可算であることがわかります。

プロトタイプの設計方法

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

ここに重要なポイントがあります：

すべての有効なプログラムのセットは可算ですが、関数のセットはカウントできないため、プログラムを作成できない関数がいくつかあるはずです。
javascriptデザインパターンインタビューの質問

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

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

チューリングマシン

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

チューリングマシン

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

頭の下の現在の記号、および
マシンの内部状態。シンボルが書き込まれると更新されます。

それでおしまい。

普遍

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

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

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

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

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

チューリングが計算モデルとしてチューリングマシンを開発した一方で、アロンゾチャーチはラムダ計算として知られる計算モデルも開発しました。これらのモデルは強力です。どちらも計算を記述し、今日のどのコンピューターにも、さらに言えば、これまでのどのコンピューターにも匹敵する方法で計算を行うからです。これは、チューリングマシンを使用して、私たちが求めている解決できない問題を説明できることを意味します。私たちの調査結果は、過去、現在、およびそれ以降のすべての可能なコンピューターに当てはまることがわかっています。

認識可能性と決定可能性

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

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

そして

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

言語の認識機能を実現するには、チューリングマシンはその言語のすべての文字列を受け入れる必要があり、その言語以外のものを受け入れてはなりません。そのような文字列を拒否またはループする場合があります。決定者になるには、チューリングマシンは、受け入れるか拒否するかによって、常に入力を停止する必要があります。

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

決定不能性

コンピュータプログラムを作成したことがある場合は、プログラムの実行時にコンピュータが回転するのを見るだけで、そこに座っている感覚を知っている必要があります。プログラムに時間がかかっているだけなのか、コードに間違いがあり、無限ループが発生しているのかはわかりません。コンパイラがコードをチェックして、実行時にコードが停止またはループするかどうかを確認しないのはなぜか疑問に思われるかもしれません。

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

これはチューリングマシンを使用して証明できます。チューリングマシンは弦として説明できるので、数え切れないほどの数があります。 Mと仮定します₁、M₂、などがすべてのチューリングマシンのセットを構成します。次の関数を定義しましょう。

Mの場合f（i、j）= 1_私受け入れるj>、それ以外の場合は0

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

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

L = Mは受け入れません

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

M_L受け入れるL>>

または

M_L拒否しますL>>

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

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

停止問題

今説明した問題は関連性がないように見えるかもしれませんが、実際に重要な追加の解決できない問題に減らすことができます。停止性問題：

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

停止の問題は、コンパイラが以前の無限ループを検出できない理由の問題に当てはまります。プログラムが空の文字列で終了するかどうかを判断できない場合、その実行によって無限ループが発生するかどうかをどのように判断できるでしょうか。

この時点で、簡単な結論に達するために手を振ったように見えるかもしれません。しかし、実際には、チューリングマシンでは、コンピュータープログラムが停止するか、ループに永久に留まるかを判断できないことに気づきました。これは実際のアプリケーションでは重要な問題であり、チューリングマシンやその他の種類のコンピューターでは解決できません。 iPhoneではこの問題を解決できません。多くのコアを備えたデスクトップでは、この問題を解決できません。クラウドはこの問題を解決できません。誰かが量子コンピューターを発明したとしても、それでも停止性問題を解決することはできません。

概要

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

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

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

ポーターの5つの力のスイッチングコスト

複雑

遅いvs.速い

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

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

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

正式な定義

P は、多項式時間で解ける問題のセットです。つまり、計算ステップの数は、問題のサイズに関して多項式関数によって制限されます。「誰もがデートできますか？」質問、別名二部マッチング問題、にあります P 。

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

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

デザインの要素は何ですか

P対NP

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

扱いやすさの微妙さ

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

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

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

私たちは実際にはもっと微妙になることができます。最短経路（P）を求める代わりに、サイクルなしで最長経路を求めることができます。最長パスの問題もNP完全であることが判明しました。

この微妙な違いの例は他にもたくさんあります。たとえば、2部グラフと一般グラフの頂点被覆の識別や、句ごとに2つと3つのリテラルを使用したブール式の満足度などです。重要なのは、問題がPにあるのかNPにあるのかがすぐにはわからないため、実行時間分析が重要なスキルである理由です。設計しなければならないアルゴリズムがPの問題に対するものである場合、効率的な解決策があることがわかります。一方、問題がNPにある場合、アルゴリズムは一般に問題を解決するのに時間がかかりすぎるため、解決策を追求することに反対する強いケースがあります。

概要

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

PがNPと等しくないことを誰も証明できませんでした。これらの2つのクラスの問題が同等であるかどうかは、P vs. NP問題として知られており、すべての数学ではないにしても、今日の理論計算機科学で最も重要な未解決の問題です。実際、2000年に、クレイ数学研究所はP vs. NP問題を数学の7つの最も重要な未解決の質問の1つとして挙げ、この問題の解決策を決定する証拠として100万ドルの賞金を提供しました。