(57)【特許請求の範囲】
【請求項１】
ＮＰ−プロセッサであって、コンピューティング環境を含み、前記コンピューティング環境は、行列状に論理ゲートが配置されたゲートアレイであり、前記論理ゲートは論理値「ＴＲＵＥ」または「ＦＡＬＳＥ」のいずれか１つを保持するトリガー要素であり、列方向に配線で接続された前記トリガー要素の集合は複数要素トリガーであり、前記複数要素トリガーはフリップフロップを形成し、前記複数要素トリガーの前記トリガー要素のうちの一つだけが安定的アクティブ状態にあることができ、前記アクティブ状態は論理値「ＴＲＵＥ」に対応し、各前記複数要素トリガーの前記トリガー要素のすべては複数のアクティブ状態へのセッティングを禁止する入力を有しており、前記アクティブ状態へのセッティングを禁止する入力に対して非アクティブ信号が出されるとき、前記トリガー要素は論理値「ＦＡＬＳＥ」を保持して非アクティブ状態になり、前記複数要素トリガーごとのアクティブ状態にある前記トリガー要素の配分が与えられた問題の解となり、
ＮＰ−問題を解くためのＮＰ−プロセッサ回路に干渉モジュールが取り付けられており、前記干渉モジュールの入力が複数要素トリガーのトリガー要素の出力に接続されており、解くべき問題の初期データが前記干渉モジュールのデータ入力へと供給され、前記初期データがグループに分かれており、前記グループがビットの集合からなっており、各前記ビットが前記干渉モジュールの個別の入力に供給され、前記干渉モジュールの個別の出力が、各個別の前記複数要素トリガーの各個別の前記トリガー要素のアクティブ状態へのセッティングを禁止する入力へとそれぞれ接続され、前記接続は前記干渉モジュールが各個別のトリガー要素に対してアクティブ状態へのセッティングの禁止を設定するものであり、前記干渉モジュールは前記与えられた問題のグラフ表現において、辺で接続されていない頂点に対応するトリガー要素が同時にアクティブ状態となることがないように制御し、
各前記複数要素トリガーにおけるトリガー要素が非アクティブ状態からアクティブ状態へ状態遷移するタイミングを制御するために、ＮＰ−プロセッサ回路に動的環境要素活動レべリングモジュールが取り付けられており、前記動的環境要素活動レベリングモジュールは各個別の複数要素トリガーの各個別のトリガー要素に対して負帰還を行うものであり、前記負帰還は非アクティブ信号の代わりに前記トリガー要素のアクティブ状態へのセッティングを禁止する入力へと供給され、前記個別の複数要素トリガーの前記アクティブ状態の総和が少なくとも一つの他の複数要素トリガーの前記アクティブ状態の総和よりも大きいという条件において、前記負帰還は前記個別の複数要素トリガーの前記トリガー要素のアクティブ状態の総和によって決定されるものであり、前記動的環境要素活動レベリングモジュールの各個別の出力は、非アクティブ信号の代わりに、各個別の前記複数要素トリガーのすべてのトリガー要素のアクティブ状態へのセッティングを禁止する入力に一緒に接続されており、前記トリガー要素のアクティブ状態へのセッティングを禁止する入力は各前記トリガー要素から一つずつ接続されており、前記動的環境要素活動レベリングモジュールでは、各前記複数要素トリガーのすべてのトリガー要素の出力に対応する入力が、アナログ加算器または論理加算器の入力に接続されており、前記加算器は、トリガー要素のアクティブ状態の総和を演算するために各個別の前記複数要素トリガーのために取り付けられており、各個別の前記加算器の出力は、超過信号の値を演算するために二入力超過比較器の第一入力に接続されており、前記超過信号は、前記複数要素トリガーのために演算された総和が、前記超過比較器の第二入力に供給される他の複数要素トリガーのために他の加算器で演算された総和に対して超過するものであり、前記超過比較器の出力は、前記個別の複数要素トリガーのための超過加算器の入力に接続されており、前記超過加算器の出力は動的環境要素活動レベリングモジュールの出力であり、前記動的環境要素活動レベリングモジュールの出力が、非アクティブ信号の代わりに、前記複数要素トリガーのすべてのトリガー要素のアクティブ状態へのセッティングを禁止する入力に負帰還として一緒に接続されており、前記トリガー要素のアクティブ状態へのセッティングを禁止する入力が各前記トリガー要素から一つずつ接続されており、前記動的環境要素活動レベリングモジュールの出力値に従って前記トリガー要素の状態遷移を抑制することを特徴とする、ＮＰ−プロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータテクノロジに関し、かつ入力データの総計の多項式関数である時間における指数関数的複雑性問題（ＮＰ−問題）を解決するためのプロセッサまたはコプロセッサとして使用されることができる。本発明の主目的は、その上に基づく人工知能システムを構築することである。
【背景技術】
【０００２】
アルゴリズム的原理に基づく現代コンピュータは、アルゴリズムがプログラムの形式で開発される全ての問題を効果的に解決する。しかし、アルゴリズム的に解決できる問題は別として、入力データの総計の指数より遅く増大する多くの計算に対して何のアルゴリズムもない幅広いクラスの問題がある；これらは、ＮＰ−問題（非決定論的多項式問題）である。それらの中の特別なクラスがＮＰ完全問題であり、および全ての他のＮＰ−問題はそれらのいずれかに変形される。このために、ＮＰ完全問題の１つを解決するプロセッサが、汎用ＮＰ−プロセッサである。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第２００５００１３５３１号明細書
【特許文献２】米国特許第３，７６４，９１９号明細書、１９７３年１０月９日、１９７２年１２月２２日出願、図９
【非特許文献】
【０００４】
【非特許文献１】「同形問題の変形およびグラフの非密度を見いだす課題への同形参入」、Ｐｒｏｃ．  ３ｒｄ  Ａｌｌ−Ｕｎｉｏｎ  Ｃｏｎｆ．  Ｐｒｏｂｌｅｍｓ  ｏｆ  Ｔｈｅｏｒｅｔｉｃａｌ  Ｃｙｂｅｒｎｅｔｉｃｓ、１９７４、ｐ．  １２４
【非特許文献２】「Ｖｙｄｅｌｅｎｙｅ  ｃｈａｓｔｅｙ  ｖ  ｇｒａｆｅ  ｏｔｎｏｓｈｅｎｙ，  ｉｚｏｍｏｒｆｎｙｋｈ  ｄａｎｎｏｍｕ  ｇｒａｆｕ」［規定されたグラフに同形である関係グラフ内の部分の識別］、Ｒｅｓｐｕｂｌｉｋａｎｓｋｉｙ  ｍｅｚｈｖｅｄｏｍｓｔｖｅｎｎｙｙ  ｎａｕｃｈｎｏ−ｔｅｋｈｎｉｃｈｅｓｋｉｙ  ｓｂｏｒｎｉｋ  “Ｐｒｏｂｌｅｍｙ  Ｂｉｏｎｉｋｉ”、Ｎｏ．２１、“Ｖｙｓｓｈａｙａ  ｓｈｋｏｌａ”  Ｐｕｂｌｉｓｈｉｎｇ  Ｈｏｕｓｅ、１９７８、ｐ．  １２９
【非特許文献３】Ｋａｒｐｏｖ，Ｙｕ．Ｇ．、２００３、「Ｔｅｏｒｉｙａ  ａｖｔｏｍａｔｏｖ」  ［オートマトンの理論］、Ｐｅｔｅｒ、２０８  ｐｐ．
【非特許文献４】Ｃｈｒｉｓｔｏｓ  Ｈ．  Ｐａｐａｄｉｍｉｔｒｉｏｕ、１９９４、計算の複雑性、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ
【発明の概要】
【発明が解決しようとする課題】
【０００５】
予め設定されたグラフに同形である部分をグラフ内に見いだすＮＰ完全問題を解決するためのＮＰ−プロセッサを提供することが、本発明の一目的である。
【０００６】
ＮＰ−プロセッサを構築するための数学的基礎は、Ｖｉｚｉｎｇ，Ｖ．Ｇによって最初に提唱されたグラフの積である（非特許文献１）。類似した結果が、パターン認識の問題に対して独立してＮｏｖｉｋｏｖ  Ａ．Ａ．によって得られた（非特許文献２）。同じ出典が、グラフの積が集団内の神経系連結を決定する場合、完全グラフによってその連結が決定される一組の神経細胞が、より刺激に誘発されやすく、それが神経細胞レベルで上述の問題を解決するための機構の存在の証拠であることができるという示唆を含む。
【０００７】
多項式時間内にＮＰ−問題を解決する抽象装置が、非決定性チューリングマシンである（非特許文献３）。（特許文献１）が、並列光学的演算に基づく非決定性チューリングマシンの実現を請求する。しかしながら、完全に機能する電子的実現はこれまでのところ何も達成されていない。
【課題を解決するための手段】
【０００８】
本発明に従うＮＰ−プロセッサは、非決定性チューリングマシンに類似して、有限集合の要素を、それらを組み合わせることによって備える仮想マシンである、各問題経路に対する個々のマシンを作り出す。仮想マシンの数はさらに、入力データの総計に関するＮＰ−問題を解決するための計算の範囲の依存関係に類似した集合内の要素数に指数関数的に依存する。仮想マシンを構築するのに必要な要素数は、入力データの総計の多項式関数である。
【０００９】
指数関数的数の仮想マシンが、多項式時間内に指数関数的複雑性問題を解決する。
【００１０】
仮想マシンは、相互の重合せで競争する（互いに干渉する）。解は、指定された要素数をアクティブ状態に保持するマシンである。このアプローチだけが、アルゴリズムの複雑性の理論の根本的な結果を犯すことなく多項式時間内にＮＰ−問題を解決することを可能にする（非特許文献４）。
【００１１】
本発明は、ＮＰ−Ｋ点を備えた部分グラフのＮ点を備えた完全グラフ内の完全検索課題、を解決するＮＰ−プロセッサ実現の特定の場合における、既知のＮｘＫ−要素（Ｎ＞Ｋ）行列トリガーに基づく（特許文献２）。可能なＮｘＫ行列トリガー状態のいずれかが、完全Ｎ−点グラフのＮ−点上のＫ−完全点グラフのＫ−点の配置として代表されることができる。次に、行列トリガーは複数ユニットトリガーからなる装置の全クラスに属する。
【００１２】
アクティブ状態へのセッティングのための入力またはアクティブ状態へのセッティングを禁止するための入力を有する複数要素トリガーの要素を備えた、複数要素トリガーの有限集合を備える既知のＮＰ−プロセッサにおいて、複数要素トリガーの要素へのアクティブ状態の割当てが、請求された本発明に従って、問題解決法を代表し、トリガー要素の部分集合のアクティブ状態の値の和が、解決されるべき問題の仕様に基づいて、アナログまたは論理加算器によって各複数要素トリガーに対して計算され、問題仕様に従い、計算された和または非アクティブ信号のいずれかが、任意の複数要素トリガーの任意の要素のアクティブ状態へのセッティングを禁止する入力に、またはアクティブ状態へのセッティングのための入力に供給され、および問題の解を代表しない状態を除外するために、問題仕様から独立した被制御負帰還が各複数要素トリガーの各要素に対して導入され、それとともに任意の複数要素トリガーの全ての要素に対する負帰還の強度が、残りの複数要素トリガーに対する類似した和をこえる全ての要素のアクティブ状態のその和の超過の値のアナログまたは論理和によって決定され、超過値が、アナログまたは論理比較器によって計算され、および超過値の和がアナログまたは論理加算器によって決定される。
【００１３】
さらにアクティブ状態へのセッティングのための入力またはアクティブ状態へのセッティングを禁止するための入力を有する複数要素トリガーの要素を備えた、複数要素トリガーの有限集合を備える既知のＮＰ−プロセッサにおいて、複数要素トリガーの要素へのアクティブ状態の割当てが、請求された本発明に従って問題解決法を代表し、トリガー要素の部分集合のアクティブ状態の値の和が、解決されるべき問題の仕様に基づいて、アナログまたは論理加算器によって各複数要素トリガーに対して計算され、問題仕様に従い、計算された和または非アクティブ信号のいずれかが、任意の複数要素トリガーの任意の要素のアクティブ状態へのセッティングを禁止する入力に、またはアクティブ状態へのセッティングのための入力に供給され、および残りの複数要素トリガーに対する類似した和をこえる全ての要素のアクティブ状態の値のその和の超過の値のアナログまたは論理和が、問題の解を代表しない状態を除外するために各複数要素トリガーの全ての要素をアクティブ状態にセッティングするための入力に供給され、超過値が、アナログまたは論理比較器によって計算され、および超過値の和がアナログまたは論理加算器によって決定される。
【００１４】
本発明の実施態様およびその構成的要素が、以下の図面と連動して以下に記述される：
【図面の簡単な説明】
【００１５】
【図１】４−ピークグラフおよびその隣接行列のグラフ図。
【図２】３−ピークグラフおよびその隣接行列のグラフ図。
【図３】グラフを作る構成を例示する補助グラフ。
【図４】グラフを作るグラフィック表現。
【図５】第１の請求項に記載の動的活動レベリングモジュールの代替略図。
【図６】第２の請求項に記載の動的活動レベリングモジュールの代替略図。
【図７】干渉ブロック要素のｎｋ略図。
【図８】コンピューティング環境２、解読出しモジュール４、干渉モジュール３、動的環境要素活動レベリングモジュール１からなるＮＰ−プロセッサのブロック−略図。
【発明を実施するための形態】
【００１６】
ＮＰ−プロセッサが少量の入力データによる単純例を使用してどのように機能するかについて見てみる。２枚のグラフ：３個のピークを有するものおよび４個のピークを有するもう一方を取り上げる。このグラフは、それらの隣接行列によって規定される（図１、２）。３ピークグラフにマッチする４ピークグラフの部分を検索する。
【００１７】
更なる考察を促進するために、隣接行列内のゼロに対応するグラフの点間の連結の欠如が、グラフのグラフィック表現で点間の破線によって示される。
【００１８】
１２個の点、すなわち３回繰り返された垂直列の形で配置される４ピークグラフの４個のピークからなる補助グラフをプロットする。中列の点を連結せずに、それらが上述の４ピークグラフ内に連結されるのと同じように列の全てのペアの点を連結する（図３）。
【００１９】
補助グラフの下に水平にそれぞれの枝を備えた３ピークグラフの３個のピークを配置する。名称の第２の数字に指定される列の下に位置づけられる３ピークグラフの点の数を使用して補助グラフの各列内の点を指定する。更に、（実線または破線で）３ピークグラフの各枝と補助グラフの列の各ペアの対応する点をペアで連結する（図３）。たとえば、３ピークグラフの第１の点および第２の点は、実線で連結される；次に、実線を使用して、それらの名称のマッチしない第１の数字を有する補助グラフの第１および第２の列の点の各ペアを連結する。
【００２０】
以下の表記法を使用して４ピークグラフおよび３ピークグラフの積であるグラフをプロットする。補助グラフおよび３ピークグラフの枝が整列される（実線が実線と整列されるかまたは、破線が破線と整列される）場合、枝とそれらを置換することができ、およびそれらが整列されない場合、何も描画しない。結果として、グラフの積が得られる（図４）。
【００２１】
グラフの積の点１１、３２、４３と２１、３２、４３との間で得られる構造を、灰色およびドットによってこの部分のグラフの点を強調することによって分析する（図４）。２組のペアの数字の各々の第１の数字は、３ピークグラフが４ピークグラフの部分にマッチするように、３ピークグラフの点がマッチされるべき４ピークグラフの点を示す。グラフの積内の強調された構造は、共通の点を有してかつ２つの問題解決法を代表する２つの完全３ピークグラフを形成する。しかしながら、完全部分グラフ（クリーク）を識別する問題もまたＮＰ完全問題であり、およびそれはより大きな数のグラフ点に関してはそれほど容易に解決されることができない。
【００２２】
ＮＰ−プロセッサが電子的または他の物理的ベース上に構築される時、上記の変換を実行することによってそれを満たすことができるか、または初期のＮＰ−問題をグラフの積内に完全部分グラフを見いだすＮＰ−問題に変形することによって通常のコンピュータ上でそれらを実行することができる。
【００２３】
第１のオプションは、より高いハードウェアコストに導くが、しかしながら、完全部分グラフを見いだすＮＰ−問題を解決する装置は、規定されたグラフに同形であるグラフ内に部分を見いだすＮＰ−問題を解決する装置の実現の特定の場合である。
【００２４】
グラフの積の構成（図４）およびそれ上の完全部分グラフの点の配置−解を検討する。２つの解のいずれかを使用する。
【００２５】
解の主特性は、グラフの積の各列が完全部分グラフの１個の点−解を有さなければならず、および１個を超えない点が各行内になければならないことである。
【００２６】
Ｉ．ＮＰ−プロセッサは、３要素の４行、または、一般に、Ｎ行およびＫ列を有する計算行列環境を必要とし、ここでＮはＫ以上である。この環境は、各列が安定したアクティブ状態で１要素だけ、および安定したアクティブ状態で各行内に１を超えない要素を有することを可能にする。
【００２７】
ＮＰ−プロセッサ（図８）は、コンピューティング環境２、解読出しモジュール４、問題仕様を格納してかつ解釈するために使用される干渉モジュール３、およびＩによる環境特性の実現を監視するために使用される、動的環境要素活動レベリングモジュール１を備える。
【００２８】
既知のＮｘＫ−要素行列トリガーが、コンピューティング環境として使用される（特許文献２）。引用された特許明細書は、動作記述を含有する。４ｘ３−要素行列トリガーのオプションの１つが、ＮＯＲゲートのまわりに構築され、かつＮＰ−プロセッサに対するコンピューティング環境２（図８）の一例として下記で使用される。コンピューティング環境は、一組の複数要素トリガー、より詳しくは共通要素を用いて互いに連結される４個の３−要素トリガーおよび３個の４−要素トリガーを備え、共通要素をアクティブ状態にセッティングすることが、共通要素を用いて相互連結される複数要素トリガーの全ての要素を非アクティブ状態にセッティングすることに帰着するようにする。複数要素トリガーの要素は、各々アクティブ状態へのセッティングを禁止する２つの入力を有する。追加的な入力が、他の装置と構成するために、かつインタフェースするために追加されることができる。本発明に従うコンピューティング環境、同じく以下の全ての実施態様が、ＮおよびＫの実際的な値を得るために類似によって拡張されることができる。
【００２９】
４ｘ３−要素行列トリガーの静止アクティブ状態の割当ては、グラフの積内の完全部分グラフの点（図４）の割当てに類似して問題解決法を代表する；それが本願明細書に詳述されない解読出しモジュール４に送られる。
【００３０】
コンピューティング環境でＮＰ−問題を解決するために、問題仕様に依存する、コンピューティング環境の異なる列の要素間に相互に抑制する（干渉する）関係を導入する。グラフの積のそれらのそれぞれの点が、関連がない要素間に、連結が導入される。ＮＰ−プロセッサのこの部分、干渉モジュール３はまた、行列構造、４ｘ３（図８）（汎用の場合ではＮｘＫ）を有し、かつ１２（ＮｘＫ）個の要素から成る。
【００３１】
ｎが、要素が位置づけられる行の数であり、およびｋが列の数である、干渉モジュール３（図８）のｎｋ−要素の可能な回路解の１つが、図７内に示される。各ｎｋ−要素は、ＮＰ−問題を解決するための入力データとして４（Ｎ）−ピークグラフ（Ｎ）の隣接行列のｎ番目の行２５（図７）および３（Ｋ）−ピークグラフの隣接行列のｋ番目の列２７（図７）を使用する。コンピューティング環境のｋ番目の列の４（Ｎ）個の要素からの４（Ｎ）個の出力信号が、干渉モジュールの各ｎｋ−要素の入力に供給される。干渉モジュール内の要素が、コンピューティング環境のｋ番目の列からの要素の出力信号の２つの論理ＯＲ演算子またはアナログ和を生成する。和は、２個の加算器、１３および１４（図７）によって形成される。加算器１４（図７）は、４ピークグラフの隣接行列（Ｎ）のｎ番目の行内のそれぞれのゼロに対応するコンピューティング環境の要素の出力から（０−タイプの）和を形成する。加算器１３（図７）は、４（Ｎ）−ピークグラフの隣接行列のｎ番目の行内のそれぞれの１に対応するコンピューティング環境の要素の出力から（１−タイプの）和を形成する。こうするために、モジュールの要素内に格納される４（Ｎ）−ピークグラフの隣接行列のｎ番目の行２５（図７）の値が、インバータ１、２、３、４（図７）によって反転され、および反転値がスイッチ９、１０、１１、１２（図７）によってゲートで制御され、それがコンピューティング環境から加算器１４（図７）に信号を伝送する。コンピューティング環境から加算器１３（図７）に信号を伝送するスイッチ５、６、７、８（図７）によって、ｎ番目の行の非反転値が、ゲートで制御される。被制御スイッチは、アナログスイッチまたは論理ＡＮＤゲートのまわりに構築されることができる。
【００３２】
干渉モジュールの要素の各行内に、行内の各要素によって形成される２つのタイプの和が、干渉モジュール（図８）内の同じ行の全ての要素の入力に供給される。これらの和が、干渉モジュール（図７）のｎｋ番目の要素の加算器１８内にタイプによって加えられ、かつコンピューティング環境のｎｋ番目の要素の禁止入力に送られる。和タイプ（０−タイプまたは１−タイプ）は、３（Ｋ）−ピークグラフの隣接行列のｋ番目の列２７（図７）内にゼロまたは１として指定される。マスク２６（図７）の値が、加算器１３、１４（図７）によって生成されたそれ自体の和のｎｋ番目の要素内の処理を禁止するために使用される。
【００３３】
マスクは、ＮＰ−問題の次元に対してＮＰ−プロセッサを構成するために使用されることができる。
【００３４】
この回路構造体によって、干渉モジュールがグラフの積の計算のための数学的手順を物理的に実現する。各４−要素トリガーに対して、それの要素の部分集合のアクティブ状態値のアナログまたは論理和が、ＮＰ−問題仕様に基づいて計算される。計算された和または非アクティブ信号のいずれかが−問題仕様に依存して−共通要素経由で上述の４−要素トリガーに連結された任意の３−要素トリガーの任意の要素のアクティブ状態へのセッティングを禁止するための入力に送られることができる。
【００３５】
たとえば正のまたは負のロジック、アナログ回路、などに基づいて、ＮＰ−プロセッサ回路の多数の特定の実施態様が作り出されることができる。
【００３６】
ＩＩ．コンピューティング環境のｎｋ番目の要素の活動は、その他の列内に位置づけられるコンピューティング環境のその他のアクティブ要素がグラフの積（図４）内のそれと連結されない場合、干渉モジュールのｎｋ番目の要素によってその禁止入力経由でブロックされる。
【００３７】
グラフの積で連結されない２個の点、３２および１３（図４）に適用される干渉モジュールの動作を検討する。節ＩＩによれば、３．２および１．３（図８）として指定されるコンピューティング環境２の要素は、同時にアクティブ状態にあることができず、およびコンピューティング環境の要素３．２および１．３がアクティブ状態に遷移するのを禁じる信号が、干渉モジュール３の対応する要素の出力１３（図８）に存在しなければならない。
【００３８】
（第３の行および第２の列内の）コンピューティング環境２の要素３．２（図８）がアクティブ状態にある場合、干渉モジュール３の要素１．３の出力１３（図８）はコンピューティング環境２の要素１．３のアクティブ状態への遷移を禁止する信号を有さなければならない（図８）。ここにそれがどのようになされるかがある。
【００３９】
干渉モジュール要素の動作を検討する（図７）。モジュール３の要素１．３（図８）に対して、４ピークグラフ２５の行列の第１行（図７）の値、マスク２６（図７）の値、および３ピークグラフの隣接行列の第３の列２７（図７）の値が、ビットストリング「１１１０」、「１１０」および「００１」によって代表される。これらのビットストリングが、干渉モジュール３の要素１．３の例証内に従来通りに示される（図８）。
【００４０】
要素の出力信号は、加算器１８（図７）によっておよび加算器と関連付けられる回路の部分によって形成される。アクティブ信号が要素１５、１６、１７、１９、２１、２３のうち少なくとも１出力に存在する時、アクティブ信号が加算器の出力に存在することができる。それらがマスク２６内のゼロによってブロックされるので、要素１７および２３（図７）は詳細解析では無視されることができる。
【００４１】
残りの要素１５、１６、１９、２１（図７）のうち少なくとも１つをアクティブ状態にセットするために、干渉モジュール３の要素１．３の入力６、８（図８）のうち少なくとも１つが、アクティブ状態になければならない。回路図（図８）に示すように、モジュール３の要素１．３の入力６（図８）は干渉モジュール３の要素１．１の出力１１（図８）に連結される。干渉モジュール３の要素１．１（図８）は、その入力１でコンピューティング環境２の要素１．１（図８）の活動信号を受信する。この入力からの信号は、干渉モジュール内部のスイッチ５（図７）へ行き、それが干渉モジュール３の要素１．１（図８）内に書き込まれる４ピークグラフ隣接行列の第１のストリング「１１１０」の第１の１によって開けられる。スイッチ５の出力（図７）からの信号は加算器１３の入力（図７）へ行き、および加算器１３の出力からの信号は干渉モジュール３の要素１．１の出力１１（図８）へ行く。したがって、閉塞信号の通過が完全に実証される。
【００４２】
干渉モジュールの動作はさらに、他の要素の活動を抑制するグラフの積内の残りの要素に連結されない任意の単一アクティブ要素に帰着することができる。同じことが、３（Ｋ）個より少ない点を有する相互関係のあるアクティブ要素の任意の部分集合に生じることができ、およびこれはＮＰ−問題に対する解でない。
【００４３】
ＩＩＩ．問題仕様にかかわりなく、ＮＰ−問題に対する解は、相互にブロックされない要素、コンピューティング環境の各列内の各々１つ、の３つ（Ｋ）の同時アクティブ状態だけによって代表されることができる。これのために、コンピューティング環境の３（Ｋ）列の各々内の活動の値は、コンピューティング環境内の動的変化および過渡現象中の残りの２（Ｋ−１）列内における値より大きくてはならない。
【００４４】
ほとんど定常状態への、すなわち、ＮＰ−問題の解への異なる列内の全ての３（Ｋ）要素の活動の同時および同一の増加が、モジュール１（図８）内のコンピューティング環境の（Ｋ）列間に負帰還を導入すること−動的活動レベリングによって達成される。
【００４５】
図５、６内に示される動的活動レベリングモジュール１の要素１．１、１．２、１．３（図８）の２つの実施態様において、全ての要素の活動の和が、コンピューティング環境の各列に対して個々にアナログまたは論理「ＯＲ」加算器１（図５、６）のどちらかによってまず形成される。したがって、３（Ｋ）和があり、およびそれらのどれか１つの値が、コンピューティング環境の列の動的活動を反映する。残りの列の活動をこえる列活動の超過の値が次いで、アナログ比較器によってまたは論理比較器２および３（図５、６）によってのどちらかで各列に対して計算される。これらの超過値が、アナログ加算器内にまたは論理加算器４（図５、６）内に加えられる。結果として、残りの列の、すなわち残りの４−要素トリガーの、活動をこえる列活動の超過値の和がコンピューティング環境の各列に対して、すなわち各４−要素トリガーに対して計算される。４−要素トリガーは、コンピューティング環境が作成される全ての複数要素トリガーの部分集合を形成する。
【００４６】
ゼロ以外である残りの列の活動をこえる、値の超過の和を有するコンピューティング環境の各列の動的活動は、節ＩＩＩに従って抑制されなければならない。第１の実施態様において、活動はコンピューティング環境の列の全ての禁止入力（図６）に超過値の和の値を送ることによって抑制される。第２の実施態様（図５）において、コンピューティング環境の列の各要素の禁止入力に適用される値は個々であり、かつその活動の値に依存する。このため、被制御強度負帰還がコンピューティング環境の各列の各要素をカバーする。帰還信号が、コンピューティング環境の要素の出力から動的活動レベリングモジュールの要素経由でその禁止入力まで供給される。このフィードバック信号はアナログスイッチを通して、または被制御増幅器を通して、またはＡＮＤゲート５、６、７および８を通して動的活動レベリングモジュールの要素（図５）内に伝送される。超過値の和の値は、負帰還要素５、６、７、８の強度制御入力に供給される（図５）。超過値の和が大きくなればなるほど負帰還の強度も大きくなる。
【００４７】
ＮＰ−プロセッサ（図８）は、以下の方法で機能する。
【００４８】
干渉モジュール３内に位置づけられる入力データの変化は、コンピューティング環境２内のアクティブ状態の現在の割当てに無秩序を引き起こす。干渉関係の構造が変化し、およびコンピューティング環境のアクティブ状態の一部が新規の干渉関係によって非アクティブ状態に抑制される。残りのアクティブ状態は、動的活動レベリングモジュール１によって非アクティブ状態と同一水準にされる。コンピューティング環境２の全ての要素が、非アクティブ状態の近くに移行する。このコンピューティング環境条件は、通常のバイナリトリガーの遷移状態のように不安定である。コンピューティング環境２の全ての要素が正帰還によってカバーされるので、コンピューティング環境要素の活動における無秩序な増加のプロセスが始まる。しかしながら、コンピューティング環境の任意の要素の活動における増加は、節Ｉの条件による相互禁止関係によっておよび節ＩＩによる干渉関係によって限定される。任意の列の要素の活動が活動増加プロセス中に別の列内の要素の活動の値より大きくなる場合、活動は節ＩＩＩによる負帰還によって抑制される。上記のプロセスの全てが、同時に生じる。これらのプロセスの相互作用は、コンピューティング環境の要素の種々の組合せを含む変動に帰着する。「仮想マシン」としてのこの種の組合せ（変動形式）の数は、コンピューティング環境の要素数の増加とともに指数関数的に増加する。節ＩＩおよびＩＩＩによる条件は、それらの相互抑制または干渉に帰着する。
【００４９】
動的活動レベリングモジュール１によって制御されるコヒーレントおよび一様な活動増加を有する変動の形式だけが、最大活動に到達することができる。コンピューティング環境の要素への最大安定活動の割当てが、ＮＰ−問題に対する解を代表する。解は、解読出しモジュール４によって読み出される。
【００５０】
動的活動レベリングモジュール１内のおよび干渉モジュール３内の負帰還の理由で、入力データ内の任意の変化はコンピューティング環境２内の新規の変動プロセスおよび新規の解に導く。
【００５１】
ＮＰ−問題に対する何の解も存在しない場合、変動プロセスが無限に、または解に帰着するデータが入力されるまで続く。
【００５２】
技術的結果
本発明の技術的結果は、予め設定されたグラフに同形である部分をグラフ内に見いだすＮＰ−完全問題を解決するためのＮＰ−プロセッサの開発である。
【符号の説明】
【００５３】
１  動的環境要素活動レベリングモジュール  インバータ  入力  加算器
１．１  要素
１．２  要素
１．３  要素
２  コンピューティング環境  インバータ  論理比較器
３  干渉モジュール  インバータ  論理比較器
３．２  要素
４  解読出しモジュール  インバータ  論理加算器
５  スイッチ  ＡＮＤゲート
６  スイッチ  入力  ＡＮＤゲート
７  スイッチ  ＡＮＤゲート
８  スイッチ  入力  ＡＮＤゲート
９  スイッチ
１０  スイッチ
１１  グラフの積の点  スイッチ  出力
１２  スイッチ
１３  加算器  点  出力
１４  加算器
１５  要素
１６  要素
１７  要素
１８  加算器
１９  要素
２０  要素
２１  グラフの積の点  要素
２２  要素
２３  要素
２４  要素
２５  行
２６  マスク
２７  列
３２  グラフの積の点
４３  グラフの積の点
【図１】
0006425047.tif 000002
【図２】
0006425047.tif 000003
【図３】
0006425047.tif 000004
【図４】
0006425047.tif 000005
【図５】
0006425047.tif 000006
【図６】
0006425047.tif 000007
【図７】
0006425047.tif 000008
【図８】
0006425047.tif 000009