Contoh menunjukkan kekuatan sirkuit non-deterministik

Sirkuit Boolean yang non-deterministik memiliki, di samping input biasa , satu set input "non-deterministik" y = ( y 1 , ... , y m ) . Sirkuit non-deterministik C menerima input x jika ada y sedemikian sehingga output sirkuit 1 on ( x , y ) . Analog dengan P / p o l $x = (x_1,\dots,x_n)$$y=(y_1,\dots,y_m)$$C$$x$$y$$1$$(x,y)$$P/poly$(kelas bahasa yang dapat ditentukan oleh sirkuit ukuran polinom), dapat didefinisikan sebagai kelas bahasa yang dapat ditentukan oleh sirkuit polinomial ukuran non-deterministik. Hal ini secara luas diyakini bahwa sirkuit non-deterministik lebih kuat daripada sirkuit deterministik, khususnya N P ⊂ P / p o l y menyiratkan bahwa hirarki polinomial runtuh.$NP/poly$$NP \subset P/poly$

Apakah ada contoh eksplisit (dan tanpa syarat) dalam literatur yang menunjukkan bahwa sirkuit non-deterministik lebih kuat daripada sirkuit deterministik?

Secara khusus, apakah Anda tahu keluarga fungsi dihitung oleh sirkuit non-deterministik dengan ukuran c n , tetapi tidak dapat dihitung dengan sirkuit deterministik ukuran ( c + ϵ ) n ?$\{f_n\}_{n > 0}$$cn$$(c+\epsilon)n$

Jika masalah ini tidak ada kemajuan, saya punya jawaban.

-

Saya juga telah mempertimbangkan masalah ini sejak makalah COCOON'15 saya (sebelum pertanyaan Anda).

Sekarang, saya punya strategi bukti, dan segera memberikan berikut teorema: Ada fungsi Boolean sehingga nondeterministic U 2 kompleksitas -circuit dari f adalah paling 2 n + o ( n ) dan deterministik U 2 -circuit kompleksitas f adalah 3 n - o ( n ) .$f$$U_2$$f$$2n + o(n)$$U_2$$f$$3n - o(n)$

Saya minta maaf karena saya belum menulis makalah. Sketsa bukti di bawah ini mungkin cukup untuk menjelaskan strategi pembuktian saya. Saya bertujuan untuk menulis makalah dengan hasil lebih banyak dengan batas waktu STACS (1 Oktober).

[Sketsa Bukti]

Biarkan $f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$

Bukti batas bawah deterministik didasarkan pada metode eliminasi gerbang standar dengan sedikit modifikasi.

Bukti batas atas nondeterministik adalah konstruksi dari rangkaian nondeterministik tersebut.

1. $Parity_{\sqrt{n}}$$o(n)$
2. $\sqrt{n}$$2n + o(n)$
3. Gabungkan kedua sirkuit.