algorithm - 回路とは

Question

本Algorithmsは、「ワイヤ」を使用してデータを運ぶ「回路」による高速フーリエ変換を示しています。回路とは それは単にアルゴリズムをよりよく説明するために本の著者によって作成された概念ですか、それとも認識されているコンピューター サイエンスの概念ですか?

Answer 1

あなたの質問への答えは、はい、「回路」は、エレクトロニクスから関連する概念を利用して、理論的なコンピューター科学で認識されている概念です。ブール回路は、基本的には次のように聞こえます。ワイヤーでつながれたブール論理ゲートで構成される、バイナリ文字列に対する計算のモデルです。ウィキペディアで正式な定義を見つけることができます。

これらが役立つのは、これまで見てきたように、特定の問題の複雑さを判断する場合です。FFT の例はかなり分かりやすいですが、おそらく最も有名な例はクックの NP 完全性の定義です。これは、与えられたブール回路が充足可能かどうかを決定することが NP 完全であるという証明をオンにします。

Barrington と Maciel は、一連の計算の複雑さに関するレクチャー ノートを作成しており、最初のレクチャーで回路を紹介し、全体を通してその概念を使用し続けています。

Answer 2

簡単な問題もあれば、難しい問題もあります。何が問題を簡単にし、より多くのリグで難しくするかを言うために、私たちは一般的にコンピューターのモデルを使用し、それらのモデルに制約を置きます。

チューリング マシンは、問題のクラスを定義するために使用される一般的なモデルの 1 つです。たとえば、複雑度クラスPは、ある累乗 p (多項式時間) に対して O(n^p) 時間で問題を解決できるチューリング マシンが存在するような問題で構成されます。チューリング マシンの時間または空間の境界に他の制約がある他の複雑度クラスを取得できます。

非決定論的チューリング マシンは、コンピューターのもう 1 つのモデルです。 交互チューリングマシンは別のものです。コンピューターには多くのモデルが存在し、それぞれがさまざまな種類の問題を定義するのに役立ちます。 回路は、これらのコンピューター モデルの 1 つです。

シングルスレッド コンピューター プログラムのモデル化に役立つチューリング マシン。大規模な並列計算をモデル化する場合、回路が輝きます。たとえば、Nick のクラスまたはNCは、多項式数のプロセッサを使用して「迅速に」(poly-log 時間で) 解決できる問題で構成されています。