確率的多項式時間アルゴリズムは、すべて決定的に置き換えられるか？（P = BPP か）

誤り確率が有界な確率的多項式時間で判定できる言語は、すべて決定的多項式時間で判定できるかを決定せよ。

Decide whether every language decidable in randomised polynomial time with bounded error is decidable in deterministic polynomial time.

Hardness-versus-randomness results make P = BPP the expected answer: Impagliazzo and Wigderson show it follows if some problem in E requires exponential-size circuits. The obstacle is therefore not the derandomisation itself but the circuit lower bound it needs.

解決したかどうかは、問いではなくアプローチごとに決まります。Atlas は判定しません。外部の判定者が何をしたかを記録します。

• Hardness versus randomness

  査読付きの証明

  到達状況

  進行中

  判定者

  the complexity theory community, through journal peer review · 査読

  定式化

  Convert a circuit lower bound into a pseudorandom generator and derandomise every bounded-error randomised algorithm.問いと同値

  保たれているもの

  • Gives exactly P = BPP once the required lower bound is available

  弱まっているもの

  • Conditional: the lower bound is not known

  加えられた仮定・条件

  • A circuit lower bound for E, which is itself an open problem of the P vs NP family

  閉じた道

  • Derandomising even polynomial identity testing implies circuit lower bounds, so there is no cheap route: any derandomisation proof must prove a lower bound, and lower bounds carry the natural-proofs and relativization barriers.無条件
    • paperdoi:10.1007/s00037-004-0182-6V. Kabanets, R. Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Comput. Complexity 13 (2004) 1-46

  証拠

  • paperdoi:10.1016/S0022-0000(05)80043-1N. Nisan, A. Wigderson, Hardness vs randomness, J. Comput. System Sci. 49 (1994) 149-167
  • paperdoi:10.1145/258533.258590R. Impagliazzo, A. Wigderson, P = BPP if E requires exponential circuits, STOC 1997, 220-229

• Circuit lower bounds

  査読付きの証明

  到達状況

  進行中

  判定者

  the complexity theory community, through journal peer review · 査読

  定式化

  Prove a superpolynomial lower bound on the circuit size of an explicit function, which would give P = BPP through hardness versus randomness.問いより強い

  保たれているもの

  • A lower bound of this kind settles the question outright

  加えられた仮定・条件

  • Proves a statement about all circuits, which is far stronger than the question needs

  Unconditional progress exists only for restricted circuit classes; Williams' NEXP vs ACC^0 is the high-water mark.

  閉じた道

  • Natural proofs: any lower-bound argument that is constructive and applies to a large fraction of functions would break the pseudorandom generators it assumes; almost every known technique is of this kind.条件つき（the existence of strong pseudorandom generators）— 前提が崩れれば道は開く
    • paperdoi:10.1006/jcss.1997.1494A. Razborov, S. Rudich, Natural proofs, J. Comput. System Sci. 55 (1997) 24-35
  • Relativization: there are oracles making the answer come out both ways, so no argument that survives adding an oracle can settle it.無条件
    • paperdoi:10.1137/0204037T. Baker, J. Gill, R. Solovay, Relativizations of the P =? NP question, SIAM J. Comput. 4 (1975) 431-442: oracles A, B with P^A = NP^A and P^B != NP^B
  • Algebrization: the natural algebraic extension of relativizing techniques is also insufficient, which rules out the arithmetization-based methods that beat relativization.無条件
    • paperdoi:10.1145/1490270.1490272S. Aaronson, A. Wigderson, Algebrization: a new barrier in complexity theory, ACM Trans. Comput. Theory 1 (2009), art. 2

  証拠

  • paperdoi:10.1145/2559903R. Williams, Nonuniform ACC circuit lower bounds, J. ACM 61 (2014), art. 2: NEXP is not contained in ACC^0

• paperdoi:10.1016/S0022-0000(05)80043-1N. Nisan, A. Wigderson, Hardness vs randomness, J. Comput. System Sci. 49 (1994) 149-167
• paperdoi:10.1145/258533.258590R. Impagliazzo, A. Wigderson, P = BPP if E requires exponential circuits, STOC 1997, 220-229

URI

https://atlasalt.com/q/95fb0749-dee7-4a0f-90b6-fc8024ea731c

登録

2026-09-17

最終レビュー

2026-09-19

次回レビュー期限

2026-12-18

版

bc189e7057ac

ライセンス

CC-BY-4.0

立場

record_only（Atlas は判定しない）