自然な証明
TCは定数深さで多項式サイズを持つ閾値回路で計算可能な問題の複雑性クラスである。これはP/polyよりも小さいと広く信じられているが、下界は未だに証明されていない。現在ではこちらも「自然な証明」が障害になっていると考えられている。何故なら、ある種の楕円関数の族の因数分解に関する困難性を仮定すると(これは広く信じられている)、TCの中に指数的に困難な擬似ランダム関数(en)が存在するからである。しかしながら、一部の研究者はラズボロフ=ルディッチの制限は寧ろ良い指針だと信じており、(訳注:「自然な」証明が駄目ならば、それに代わる)「超自然な」下界証明に用いるべき道具の目安だと考えている。そうした道具の候補としては例えば指数領域困難や同完全な性質などがある。