Nondeterminisme rata-rata tidak berguna untuk sirkuit?

Savický dan Woods (Jumlah Fungsi Boolean Dihitung dengan Rumus dari Ukuran yang Diberikan) membuktikan hasil berikut.

Teorema [SW98]: Untuk setiap konstan , hampir semua fungsi boolean dengan kompleksitas rumus paling n k memiliki kompleksitas rangkaian setidaknya n k / k .$k>1$$n^k$$n^k/k$

Buktinya terdiri dari menurunkan batas bawah pada , jumlah fungsi boolean pada n input yang dihitung dengan rumus ukuran n k . Dengan membandingkan B ( n , n k ) dengan jumlah sirkuit ukuran C = n k / k , yang paling banyak C C e C + 4 n , dapat disadari bahwa untuk n besar , C C e C + $B(n,n^k)$$n$$n^k$$B(n,n^k)$$C = n^k/k$$C^{C}e^{C+4n}$$n$, dan hasilnya berikut.$C^{C}e^{C+4n} << B(n,n^k)$

Kelihatannya kepada saya bahwa hasilnya bisa diperkuat dengan mencatat bahwa jumlah sirkuit nondeterministic ukuran dengan m nondeterministic masukan adalah tidak lebih besar dari jumlah sirkuit deterministik ukuran n k (untuk m tidak terlalu besar, katakanlah m = n ). Oleh karena itu, saya pikir akibat wajar berikut ini berlaku:$n^k$$m$$n^k$$m$$m=n$

Akibat wajar: Untuk setiap konstan , hampir semua fungsi boolean dengan kompleksitas rumus paling n k memiliki kompleksitas rangkaian nondeterministic setidaknya n k / k (untuk sirkuit non-deterministik dengan n masukan nondeterministic).$k>1$$n^k$$n^k/k$$n$

$x = (x_1,\dots,x_n)$$y=(y_1,\dots,y_m)$$C$$x$$y$$1$$(x,y)$

$B(n,n^k)$$n$$n^k$$n^k$$n^k$

Pertanyaan:

(1) Apakah ada implikasi / konsekuensi menarik dari akibat wajar di atas?

(2) Apakah ada hasil lain dalam arah yang sama? Misalnya, apa yang diketahui tentang proposisi berikut? Untuk masalah dalam P, beralih dari TM ke NTM tidak bisa, rata-rata, mengurangi kompleksitas lebih dari faktor konstan.

(Gil Kalai juga memiliki pertanyaan yang agak terkait dengan yang ini.)

$2^k$$k$

2) Untuk kelas seragam seperti P ini lebih menantang, karena tidak ada definisi yang jelas tentang "fungsi rata-rata dalam P" dan argumen penghitungan tidak lagi berfungsi dengan sangat bersih. Ini konsisten dengan pengetahuan saat ini bahwa segala sesuatu dalam P dapat diselesaikan dalam waktu linear nondeterministic.