Teorema hierarki untuk ukuran sirkuit

Saya berpikir bahwa teorema hierarki ukuran untuk kompleksitas sirkuit dapat menjadi terobosan besar di bidang ini.

Apakah ini pendekatan yang menarik untuk pemisahan kelas?

Motivasi untuk pertanyaan itu adalah yang harus kita katakan

ada beberapa fungsi yang tidak dapat dihitung dengan ukuran sirkuit dan dapat dihitung dengan ukuran sirkuit di mana . (dan mungkin sesuatu tentang kedalaman)g ( n ) f ( n ) < o ( g ( n ) $f(n)$$g(n)$$f(n)<o(g(n))$

jadi, jika , properti tersebut tampaknya tidak alami (itu melanggar kondisi umum). Jelas kami tidak dapat menggunakan diagonalisasi, karena kami tidak berada dalam pengaturan yang seragam.$f(m)g(n) \leq n^{O(1)}$

Apakah ada hasil ke arah ini?

Faktanya adalah mungkin untuk menunjukkan bahwa, untuk setiap cukup kecil (kurang dari 2 n / n ), ada fungsi yang dapat dihitung oleh sirkuit ukuran f ( n ) tetapi tidak oleh sirkuit ukuran f ( n ) - O ( 1 ) , atau bahkan f ( n ) - 1 , tergantung pada jenis gerbang yang Anda izinkan.$f$$2^n/n$$f(n)$$f(n)-O(1)$$f(n)-1$

Berikut adalah argumen sederhana yang menunjukkan bahwa ada fungsi yang dapat dihitung dalam ukuran tetapi bukan ukuran f ( n ) - O ( n ) .$f(n)$$f(n)-O(n)$

Kita tahu itu:

1. ada fungsi yang membutuhkan kompleksitas sirkuit setidaknya 2 n / O ( n ) , dan, khususnya, kompleksitas sirkuit lebih dari f ( n ) .$g$$2^n/O(n)$$f(n)$
2. fungsi sedemikian rupa sehingga z ( x ) = 0 untuk setiap input x dapat dihitung oleh sirkuit ukuran-konstan.$z$$z(x)=0$$x$
3. jika dua fungsi dan g 2 berbeda hanya dalam satu input, maka kompleksitas sirkuitnya paling banyak berbeda dengan O ( n $g_1$$g_2$$O(n)$

Misalkan bukan nol pada input N. Sebut input seperti x 1 , ... , x N . Kita dapat mempertimbangkan, untuk setiap i , fungsi g i ( x ) yang merupakan fungsi indikator dari set { x 1 , ... , x i } ; dengan demikian g 0 = 0 dan g N = g .$g$$N$$x_1,\ldots,x_N$$i$$g_i(x)$$\{ x_1,\ldots,x_i \}$$g_0=0$$g_N=g$

Jelas ada beberapa sedemikian rupa sehingga g i + 1 memiliki kompleksitas sirkuit lebih dari f ( n ) dan g i memiliki kompleksitas sirkuit kurang dari f ( n ) . Tetapi kemudian g i memiliki kompleksitas rangkaian kurang dari f ( n ) tetapi lebih dari f ( n ) - O ( n ) .$i$$g_{i+1}$$f(n)$$g_i$$f(n)$$g_{i}$$f(n)$$f(n) - O(n)$

Hasil ini dapat dibuktikan menggunakan argumen penghitungan sederhana. Pertimbangkan fungsi acak yang diterapkan pada bit pertama input. Fungsi ini hampir pasti memiliki kompleksitas sirkuit ( 1 + o ( 1 ) ) ( 2 k / k ) oleh argumen penghitungan Riordan dan Shannon, dan pencocokan batas atas. Jadi, memilih k sehingga 2 g ( n ) < 2 k / k < f ( n ) / 2 kita dapat membedakan ukuran $k$$(1+o(1))(2^k/k)$$k$$2g(n) < 2^k/k < f(n)/2$ dari ukuran f ( n ) . Perhatikan bahwa fungsi yang dipermasalahkan bahkan tidak dapat dihitung, tetapi kita dapat menempatkannya dalam hierarki waktu eksponensial dengan teknik standar (selama kita dapat menghitung nilai k yang tepat ). Kami tentu saja tidak dapat membuktikan ikatan apa pun yang lebih besar dari 2 n / n , karena itulah kompleksitas rangkaian kasus terburuk dari fungsi apa pun. $g(n)$$f(n)$$k$$2^n/n$

Bukti alami tidak berlaku untuk jenis argumen ini, karena properti yang dimaksud adalah `` tidak memiliki sirkuit kecil '', yang tidak mudah dihitung dari tabel kebenaran fungsi (mungkin). Tidak jelas seberapa rendah kelas kompleksitas penghitungan seperti ini. Apakah ada alasan mengapa kita tidak bisa menggunakan argumen penghitungan untuk membuktikan batas bawah untuk ? Tidak yang saya tahu. $NE$