探索問題の計算複雑さのクラスFD<sub>2</sub><sup>P</sup>と普遍集合を持つその部分クラスについて
3
0
0
全文
(2) Vol.2016-AL-159 No.6 2016/9/23. 情報処理学会研究報告 IPSJ SIG Technical Report. 対化された NP ∩ coNP に関する完全問題の存在性につい. 定 問 題 L1 ∈ ΣPk と L2 ∈ ΠPk が 存 在 す る よ う な 関 数. ての Sipser [6] による定理が知られている．これはクラス. fA の 全 体 で あ る ．与 え ら れ た x ∈ {0, 1} に つ い て ，. NP ∩ coNP. が完全問題を持たないようなオラクル X が. 任 意 の z ∈ {0, 1}pL2 (|x|) に つ い て (x, z) ∈ RL2 な ら. 存在する，という言明である．Sipser の証明 [6] は普遍問. ば，(x, y) ∈ RL1 となるような y ∈ {0, 1}∗ が必ず存在. 題の存在によるものである．Sipser [6] は，ある任意のク. し，fA (x) = y となる．ある z ∈ {0, 1}pL2 (|x|) について. ラスの完全問題の存在性とそのクラスについての普遍問題. (x, z) ̸∈ RL2 ならば fA (x) = “no” となる．「C」 は 「con-. X. X. の存在性が同値であることを示し，クラス NP. X. ∩ coNP. X. が普遍問題を持たないようなオラクル X の存在を証明し ている．. 2. 計算複雑さのクラス FDPk. 入した動機はここに起因する．. 本稿では簡単のため特に断らない限り，問題のアルファ ベットは {0, 1} とする．多項式時間階層を構成する判定問 題のクラス ∆Pk , ΣPk ，ΠPk を次で帰納的に定義する．∆P0 ，ΣP0 ，. ΠP0. はすべて多項式時間計算可能クラス P である．任意の. k≥1. について，ΣPk. ditional」に由来する．TFΣPk から自然に類推されるクラ スとして TFDPk が考えられるが，FDPk の定義のうち判定 問題 L2 は普遍量化子で始まるため，探索問題において， 意味をなさない．CTFDPk のように条件付きのクラスを導. 3. 探索問題の多項式時間還元可能性 本研究では探索問題の多項式時間還元として Levin 還 元を用いる．Levin 還元は判定問題における Karp 還元と. は次を充たす問題 L 全体のクラスであ. 同様な位置付けにあり，最も一般的である Cook 還元に比. る．多項式 pL : {0, 1}∗ → N，判定問題 L′ ∈ ΠPk−1 ，{0, 1}. べ，還元の能力は制限されている．そのため還元に関わる. ∗. 上の 2 項関係 RL が存在して，任意の x ∈ {0, 1} につい ′. て，x ∈ L となるのは，∃y ∈ L ∩ {0, 1}. pL (|x|). (x, y) ∈ RL. 問題の定式化の特徴を十分に捉える必要はあるが，計算複 雑さのクラスをより厳密に解析することには適している．. となるとき，かつそのときに限る．このとき任意の x に. 探 索 問 題 A と B の Levin 還 元 は 次 を 充 た す 二. ついて (x, y) ∈ RL となるような y が決定性多項式時間で. つ の 多 項 式 時 間 計 算 可 能 関 数 s : {0, 1}∗ → {0, 1}∗ と. 見つけられるような ΣPk の部分クラスが ∆Pk である．ΠPk. t : {0, 1}∗ → {0, 1}∗ として定義される．RA を，多項式 pA. は ΣPk の補問題のクラスである．すなわち任意の k ≥ 1. が存在して，任意の x, y ∈ {0, 1}∗ について，(x, y) ∈ RA. について，ΠPk は次を充たす問題 L 全体のクラスである．. ならば |y| ≤ pA (|x|) を充たし，かつ (x, A(x)) ∈ RA を充. ∗. ′. 多項式 pL : {0, 1} → N，判定問題 L ∈. ΣPk−1 ，{0, 1} ∗. 上. たすような関係とする．同様に RB を，多項式 pB が存. の 2 項関係 RL が存在して，任意の x ∈ {0, 1} につい. 在して，任意の x, y ∈ {0, 1}∗ について，(x, y) ∈ RB な. て，x ∈ L となるのは，∀z ∈ L′ ∩ {0, 1}pL (|x|) (x, z) ∈ RL. らば |y| ≤ pB (|x|) を充たし，かつ (x, B(x)) ∈ RB を充. となるとき，かつそのときに限る．判定問題のクラス DPk. たすような関係とする．このとき任意の x ∈ {0, 1}∗ に. を次で定義する．任意の k ≥ 0 について，DPk はクラス ∪ P P L1 ∈ΣP ,L2 ∈ΠP (L1 ∩ L2 ) である．D1 はクラス D と同一. ついて，A(x) ̸= “no” ならば B(s(x)) ̸= “no”，さらに. k. k. B(s(x)) ̸= “no” ならば A(t(s(x))) ̸= “no” となる．. P. である [4]．D は DP とも表される． 探索問題のクラス FΣPk は次のような判定問題 L ∈ ΣPk. 4. 普遍集合と完全問題. が存在するような関数 fA の全体である．x ∈ {0, 1}∗ が与. C を判定問題のクラス，L を判定問題，X をオラク. えられたとき，fA (x) = y となるのは，(x, y) ∈ RL のとき. ルとする．このとき問題 L がクラス C X に属し，任意. であり，そうでないならば，fA (x) = “no” となる．このと. の問題 L′ についてある k ≥ 0 が存在して，L′ = {w ∈. ∗. き任意の x ∈ {0, 1} について fA (x) = y となるような y. {0, 1}∗ : (k, 1|w| , w) ∈ L} ならば，L をクラス C X の普遍集. が必ず存在するような fA のみからなる FΣPk の部分クラス. 合という．任意の判定問題のクラス C ，判定問題 L，オラク. TFΣPk. FDPk. k. は次のよう. ル X について，次の言明が成り立つことを Sipser [6] は示. な判定問題 L1 ∈ ΣPk と L2 ∈ ΠPk が存在するような関数 fA. した．クラス NPX ∩coNPX が完全問題を持たないようなオ. の全体である．x ∈ {0, 1}∗ が与えられたとき，Af (x) = y. ラクル X が存在する．この定理と F(NP ∩ coNP) = TFNP. となるのは，(x, y) ∈ RL1 かつ任意の z ∈ {0, 1}. て直ちに分かるのものとして，FDPk ⊆ F∆Pk+1 ⊆ FΣPk+1 ．と. [3] より，TFΣP2 の完全問題が見つけられそうもない．FDP2 については，完全問題が知られている [8]． 完全問題を持たないクラスが持つ性質として意味的 (semantical) であることが挙げられる [6][5]．つまりそのクラ. いう関係がある．. スを特徴付けを，有限の規則により陽に記述するのではな. を. と定義する．探索問題のクラス. pL2 (|x|). について (x, z) ∈ RL2 のときであり，そうでないならば，. A(x) = “no” となる．以上のクラスに関する包含関係とし. 本研究では探索問題のクラス FDPk の部分クラスとし て新たに. CTFDPk. を導入する．CTFDPk. c 2016 Information Processing Society of Japan ⃝. は次のような判. く，ある意味的な性質により行うということである．John-. son, Papadimitriou, Yannakakis [1] によるクラス PLS や. 2.
(3) Vol.2016-AL-159 No.6 2016/9/23. 情報処理学会研究報告 IPSJ SIG Technical Report. Papadimitriou [5] による PPAD は，統語的 (syntactical). 入した．そしてそのクラスの具体的な問題としてが CTFDP2. なクラスであり，完全問題が知られている．これらのクラ. に属すことを示した．今後は普遍集合を用いた議論によ. スは意味的なクラス TFNP の部分クラスである [3]．TFNP. り，CTFDP2 が完全問題を持つかどうかを観察しその結果. については，完全問題が知られていない点をあわせると，. を証明する予定である．現在は否定的な解決を予想してい. このことは本研究にとっても重要な点である．. る．さらに結果がどちらにしても，CTFDP2 の完全問題の. 5. FDP2 問題と CTFDP2 問題の例. 存在性の証明そのものが難しい可能性もある．したがって. CTFDP2 以外の FDP2 の部分クラスも考えていく予定であ. この節では FDP2 問題の例を考える．より一般に具体的. る．定理 3 の証明で用いた判定問題 L1 と L2 を変形およ. FDPk. び抽象化する方法などが考えられる．. な. 問題として k -交替充足可能性問題の派生を定式化. する． 参考文献. 問題 1 (FΣk SAT-Πk SAT). ′. インスタンス．X1 , · · · , Xk 上の CNF 式の対 (ψ, ψ )． 解．(∀α1 ∈ {0, 1}. |X1,φ. |)(∃α2 ∈ {0, 1}. |X2,φ. [1]. ′. |) · · · (Q αk ∈. {0, 1}|Xk,φ |)[ψ ′ (α1 , · · · , αk ) = 0] が 充 た さ れ な い な ら ば “no” ．そうでないとき，(∀σ2 ∈ {0, 1}|X2,φ |)(∃σ3 ∈. {0, 1}|X3,φ |) · · · (Qσk ∈ {0, 1}|Xk,φ |)[ψ(σ1 , · · · , σk ) = 1] を. [2]. 充たすような σ が見つかれば σ ，そうでないならば “no”． ただし k が奇数のとき Q′ = ∀ かつ Q = ∃, k が偶数のと き Q′ = ∃ かつ Q = ∀ であるとする．. [3]. 問題 2 (区間付表現不能数探索問題). インスタンス．対 (A, [s, e])．ただし A は正整数 a1 , · · · , an の有限集合，[s, e] は正整数の区間，s ≥ e．また n は a1 より大きくないものとする．. [4]. 解．[s, e] に属す任意の正整数が A の非負整数結合として 表すことができるとき，A の非負整数結合として表すこと のできない a1 より大きな整数．そうでないとき “no”． 定理 3. 表現可能区間条件付き表現不能数探索問題は. [5]. CTFDP2 に属す．. (証明) (A, [s, e]) を表現可能区間条件付き表現不能数探索 問題のインスタンスとする．クラス ΣP2 に属す判定問題 L1 とクラス ΠP2 に属す判定問題 L2 を次のように定義す る．L1 と L2 のどちらも対 (A, [s, e]) をインスタンスとす る．L1 は A の非負整数結合で表現できない a1 より大き な整数が存在するような対 (A, [s, e]) からなる判定問題， L2 は [s, e] に属す任意の正整数が A の非負整数結合とし て表現できるような対 (A, [s, e]) からなる判定問題である とする．L1 は非負整数結合で表現できないような整数 b を guess し，その妥当性を判定問題版の整数ナップサック 問題を検証すればよいので，ΣP2 に属す．一方で [2] の結 果より L2 は ΠP2 に属す．よって表現可能区間条件付き表 現不能数探索問題は FDP2 に属す．さらに任意の A につい て，A の非負整数結合で表現できないような a1 より大き な整数は n < a1 という仮定より必ず存在するので CTFDP2. [6]. [7]. [8]. Johnson, D. S., Papadimitriou, C. H. and Yannakakis, M.: How Easy Is Local Search?, Journal of Computer and System Sciences, Vol. 37, No. 1, pp. 79–100 (online), DOI: http://dx.doi.org/10.1016/00220000(88)90046-3 (1988). Matsubara, S.: The Computational Complexity of the Frobenius Problem, CoRR, Vol. abs/1602.05657 (online), available from ⟨http://arxiv.org/abs/1602.05657⟩ (2016). Megiddo, N. and Papadimitriou, C. H.: On total Functions, Existence theorems and Computational Complexity, Theoretical Computer Science, Vol. 81, No. 2, pp. 317–324 (online), DOI: http://dx.doi.org/10.1016/0304-3975(91)90200-L (1991). Papadimitriou, C. and Yannakakis, M.: The Complexity of Facets (and Some Facets of Complexity), Journal of Computer and System Sciences, Vol. 28, No. 2, pp. 244–259 (online), DOI: http://dx.doi.org/10.1016/0022-0000(84)90068-0 (1984). Papadimitriou, C. H.: On the Complexity of the Parity argument and Other inefficient Proofs of Existence, Journal of Computer and System Sciences, Vol. 48, No. 3, pp. 498–532 (online), DOI: http://dx.doi.org/10.1016/S0022-0000(05)800637 (1994). Sipser, M.: On Relativization and the Existence of Complete Sets, Automata, Languages and Programming: Ninth Colloquium Aarhus, Denmark, July 12–16, 1982 (Nielsen, M. and Schmidt, E. M., eds.), Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 523–531 (online), DOI: 10.1007/BFb0012797 (1982). Stockmeyer, L. J.: The Polynomial-Time Hierarchy, Theoretical Computer Science, Vol. 3, No. 1, pp. 1–22 (online), DOI: http://dx.doi.org/10.1016/03043975(76)90061-X (1976). Wooldridge, M. and Dunne, P. E.: On the Computational Complexity of Qualitative Coalitional Games, Artificial Intelligence, Vol. 158, No. 1, pp. 27–73 (online), DOI: http://dx.doi.org/10.1016/j.artint.2004.04.002 (2004).. に属す．. 6. 今後の研究 本稿では探索問題のクラス FDP2 を拡張し，CTFDP2 を導. c 2016 Information Processing Society of Japan ⃝. 3.
(4)
関連したドキュメント
Keywords: continuous time random walk, Brownian motion, collision time, skew Young tableaux, tandem queue.. AMS 2000 Subject Classification: Primary:
Turmetov; On solvability of a boundary value problem for a nonhomogeneous biharmonic equation with a boundary operator of a fractional order, Acta Mathematica Scientia.. Bjorstad;
The study of the eigenvalue problem when the nonlinear term is placed in the equation, that is when one considers a quasilinear problem of the form −∆ p u = λ|u| p−2 u with
It is well known that the inverse problems for the parabolic equations are ill- posed apart from this the inverse problems considered here are not easy to handle due to the
The class of SWKA Banach spaces extends the known class of strongly weakly compactly generated (SWCG) Banach spaces (and their subspaces) and it is related to that in the same way
The proof uses a set up of Seiberg Witten theory that replaces generic metrics by the construction of a localised Euler class of an infinite dimensional bundle with a Fredholm
In conclusion, we reduced the standard L-curve method for parameter selection to a minimization problem of an error estimating surrogate functional from which two new parameter
Beyond proving existence, we can show that the solution given in Theorem 2.2 is of Laplace transform type, modulo an appropriate error, as shown in the next theorem..
