単調回路の図による例（大きさ3 のクリークがグラフに含まれるかの判定）が
Wikipedia の図 [wikipedia.org]にあります。ただし、一番下の頂点はクリークを構成するために選択された辺を示しています。また、非単調回路の例が [IEICE] の2ページ目に図 6.1 論理回路として示されています。
これまでに、(命題1) 「クリーク判定問題を解く単調回路の大きさは、入力の大きさ n の指数倍必要になる」ことがわかっています [Hacker]。また、(命題2) 「非単調回路を使って、ある判定問題を解こうとするとき、入力の長さ n の多項式倍の大きさの非単調回路で解けないならば、その判定問題を解く多項式時間アルゴリズムは存在しない」ことも示されています [Trevisan]。
(命題1) では単調回路が対象ですが、非単調回路の場合はその大きさが同じ（NOT 素子を使わなければ良い）か小さくなるかのどちらかです。非単調回路でも、n の指数倍の大きさになるなら、(命題2) からクリーク判定問題は多項式時間で解くアルゴリズムのない、P に含まれない問題だと導けます。逆に、非単調回路では n の多項式倍の大きさまで小さくなるなら、(命題2) を適用できないため、P と NP の関係を示すために、非単調関数に対する (命題1) の結果は使えず、P vs. NP は未解決のままです。
この論文では、(命題1) における単調回路を非単調回路に拡張した場合でも指数倍の大きさの回路が必要であることを示すことによって、(命題2) の結果から、クリーク判定問題は P に含まれない問題であり、P != NP であることを結論づけている [Trevisan]、という感じです。
先行研究 (スコア:0)
要旨を読むと、先行研究で列挙されている日本人研究者がいますね。
先行研究はmonotone network complexityの場合で、この論文はnon-monotone network complexity
なのか、なるほど分からん。
Re:先行研究 (スコア:2)
この論文に関する次の情報から読み解けた範囲で、monotone network complexity、non-monotone network complexity の意味を含む、先行研究の流れを説明します（以下に書いてあることを鵜呑みにしているので、個別の結果は理解していません）。
間違いを見つけた方はコメントで教えていただけると助かります。
monotone network complexity は単調回路（AND 素子と OR 素子だけで構成される回路）の複雑さ、 non-monotone network complexity は非単調回路（AND 素子と OR 素子に加えて、NOT 素子も含む回路）の複雑さをそれぞれ示しています [Hacker, IEICE]。[IEICE] では、AND 素子、OR 素子、NOT 素子を含む回路のことを非単調回路ではなく、論理回路と呼んでいます。
単調回路の図による例（大きさ3 のクリークがグラフに含まれるかの判定）が Wikipedia の図 [wikipedia.org]にあります。ただし、一番下の頂点はクリークを構成するために選択された辺を示しています。また、非単調回路の例が [IEICE] の2ページ目に図 6.1 論理回路として示されています。
これまでに、(命題1) 「クリーク判定問題を解く単調回路の大きさは、入力の大きさ n の指数倍必要になる」ことがわかっています [Hacker]。また、(命題2) 「非単調回路を使って、ある判定問題を解こうとするとき、入力の長さ n の多項式倍の大きさの非単調回路で解けないならば、その判定問題を解く多項式時間アルゴリズムは存在しない」ことも示されています [Trevisan]。
(命題1) では単調回路が対象ですが、非単調回路の場合はその大きさが同じ（NOT 素子を使わなければ良い）か小さくなるかのどちらかです。非単調回路でも、n の指数倍の大きさになるなら、(命題2) からクリーク判定問題は多項式時間で解くアルゴリズムのない、P に含まれない問題だと導けます。逆に、非単調回路では n の多項式倍の大きさまで小さくなるなら、(命題2) を適用できないため、P と NP の関係を示すために、非単調関数に対する (命題1) の結果は使えず、P vs. NP は未解決のままです。
この論文では、(命題1) における単調回路を非単調回路に拡張した場合でも指数倍の大きさの回路が必要であることを示すことによって、(命題2) の結果から、クリーク判定問題は P に含まれない問題であり、P != NP であることを結論づけている [Trevisan]、という感じです。