NEXP は多項式サイズの回路を持つか？

非決定性指数時間で判定できる言語が、すべて多項式サイズのブール回路族で計算できるかを決定せよ。

Decide whether every language in nondeterministic exponential time can be computed by a family of polynomial-size Boolean circuits.

The strongest unconditional circuit lower bound known against a natural class is Williams' NEXP vs ACC^0, proved by the algorithmic method: a faster-than-brute-force satisfiability algorithm for a circuit class yields a lower bound against it. Whether the method reaches general polynomial-size circuits is the open question.

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

• The algorithmic method

  査読付きの証明

  到達状況

  進行中

  判定者

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

  定式化

  Design satisfiability algorithms beating brute force for a circuit class, and convert them into lower bounds against that class.問いと同値

  保たれているもの

  • Produces unconditional lower bounds, and has already reached ACC^0

  弱まっているもの

  • Each new circuit class needs its own algorithm; general circuits are far out of reach

  加えられた仮定・条件

  • Nothing assumed; the cost is algorithmic ingenuity

  閉じた道

  • Any technique that is constructive and large in the Razborov-Rudich sense cannot prove lower bounds against general circuits, on standard pseudorandomness assumptions.条件つき（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
  • Relativizing and algebrizing arguments are insufficient for separations of this kind.無条件
    • 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

• Natural proofs

  閉じた道（障壁）

  到達状況

  この道では到達できないと証明済み

  判定者

  none: the obstruction is a published theorem · 引用

  差分（このアプローチが問いの何を保ち、何を弱めるか）はまだ書かれていません。人類審査で書きます。

  閉じた道

  • A lower-bound argument that is constructive and applies to a large fraction of functions would break the pseudorandom generators it assumes. Almost every technique known before the algorithmic method is of this kind, which is why the field stalled for two decades.条件つき（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
  • Relativizing and algebrizing arguments cannot separate these classes either.無条件
    • 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.1006/jcss.1997.1494A. Razborov, S. Rudich, Natural proofs, J. Comput. System Sci. 55 (1997) 24-35

URI

https://atlasalt.com/q/d6c50311-8529-42a1-838f-85abb0eca7cb

登録

2026-09-17

最終レビュー

2026-09-19

次回レビュー期限

2026-12-18

版

724ff613c8cc

ライセンス

CC-BY-4.0

立場

record_only（Atlas は判定しない）