Apa kelas kompleksitas "terkecil" di mana

Saya percaya jawaban untuk pertanyaan ini memberikan kelas sedemikian rupa sehingga untuk semua polinomial , ada masalah di kelas yang tidak memiliki sirkuit ukuran . Namun, saya bertanya tentang ukuran sirkuit $p$
$p(n)$
. $\omega \hspace{.02 in}(n)$

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ super-linear tetapi tidak . Meskipun perilaku genap seperti itu dapat ditangani dengan padding, orang mungkin malah memiliki garis-garis nilai super-polinomial yang sangat panjang antara nilai-nilai rendah.) $\omega \hspace{.02 in}(n)$

circuit-complexity lower-bounds Komunitas
sumber

Saya pikir batas bawah super-linier berarti ada batas bawah dalam

ω (n)

$\omega(n)$

Kaveh

Saya tidak berpikir kita menyebutnya fungsi superlinear. Sejauh yang saya tahu apa yang orang maksudkan dengan superlinear adalah

dengan cara yang sama dengan sublinear adalah

. Apakah Anda memiliki referensi untuk penggunaan superlinear dalam pengertian Anda? Urutan Anda sangat sering superlinear tetapi tidak superlinear.

ω (n)

$\omega(n)$

o (n)

$o(n)$

Kaveh

Saya percaya penggunaan standar adalah bahwa "ukuran sirkuit superlinear" berarti bahwa ia tidak memiliki sirkuit ukuran

, yaitu sangat sering. "Hampir di mana-mana" batas bawah jauh lebih jarang dan lebih sulit untuk dicapai.

O (n)

$O(n)$

Joshua Grochow

Lihat posting blog Fortnow tentang pertanyaan tentang apa definisi yang tepat dari notasi omega besar.

Robin Kothari

@ Kaveh: Maaf, saya seharusnya lebih spesifik. Maksud saya pernyataan bahwa "masalah X tidak memiliki sirkuit ukuran linear" umumnya setara dengan mengatakan bahwa "masalah X memiliki ukuran sirkuit super-linear terikat lebih rendah ", dan saya percaya kedua mean (dan seharusnya berarti) apa yang saya katakan dalam komentar saya sebelumnya. Ungkapan "masalah X memiliki sirkuit ukuran super-linear" tampaknya aneh bagi saya, karena "memiliki sirkuit ini-dan-itu" adalah batas atas, tetapi "super-linear" adalah batas bawah ...

Joshua Grochow

Jawaban:

dan keduanya dikenal tidak memiliki -circuits untuk setiap k tetap dan tidak ada penahanan dikenal di antara mereka. Detail dalamposting blogsaya. $S^p_2$ $PP$ $n^k$

Pembaruan: Seperti yang ditunjukkan Rickey Demer, hasil ini tidak harus memberikan bahasa dengan batas bawah untuk semua dalam . Saya pikir adalah mungkin yang paling dikenal. Karena memiliki set lengkap, Anda mungkin bisa mendapatkan semua terikat tapi saya tidak punya bukti lengkap. $n$ $S_2^p$ $\Delta^p_3$ $PP$ $n$

Lance Fortnow
sumber

Bagaimana Anda pergi dari "tidak memiliki n

sirkuit-ukuran" ke

ukuran sirkuit batas bawah?

^{k}

$^k$

ω (n)

$\omega(n)$

$\hspace{.84 in}$ Lihat bagian atas halaman ini untuk urutan yang tidak memiliki batas atas polinomial tapi tidak

ω (n)

$\omega(n)$

$\hspace{.58 in}$

@ EmilJeřábek: Bagaimana Anda mendapatkan bahwa untuk semua cukup besar

bukan hanya untuk tak terhingga banyaknya

n

$n$

n

$n$

$\hspace{.08 in}$ (Itu akan diperlukan untuk mendapatkan "ukuran sirkuit adalah

" daripada "ukuran sirkuit bukan

ω (n)

$\omega(n)$

O (n)

$O(n)$

$\hspace{1.12 in}$

@ EmilJeřábek: Lihat tanggapan saya di meta.stackexchange.com/a/293100/232555 .

Anda benar, saya berkonsentrasi pada bagian pertama dari bukti yang hilang di blog, dan tidak menyadari ada masalah besar dengan perbedaan kasus. Jadi, bagaimanapun, ada bahasa dalam

yang membutuhkan rangkaian ukuran

untuk semua yang cukup besar

Δ_{3}^{P}

$\Delta^P_3$

\geq n^{k}

$\ge n^k$

n

$n$

Emil Jeřábek

Bisa mendapatkan batas bawah hampir di mana-mana untuk

. Untuk setiap

, misalkan

adalah himpunan semua sirkuit berukuran

. Untuk

, panggil oracle sekali untuk menentukan apa yang sebagian besar rangkaian dalam jawaban

pada masukan ke-

dari panjang

, dan buang keluar dari

semua sirkuit yang memberikan jawaban ini (ini dapat dikodekan sebagai kendala polytime pada panggilan oracle berikutnya). Fungsi keras kami akan menampilkan nilai yang berlawanan pada

P^{P P [n^{2}]}

$P^{PP[n^2]}$

n

$n$

S

$S$

n \log n

$n\log n$

i = 1, \dots, n^{2}

$i=1,\ldots,n^2$

S

$S$

i

$i$

n

$n$

S

$S$

masukan panjang

.. Akhir untuk. Sekarang, mengingat ae-lb untuk

, dapatkah kita mengangkatnya ke

i

$i$

n

$n$

P^{P P [n^{2}]}

$P^{PP[n^2]}$

P P

$PP$

Ryan Williams

Biarkan dMCSP menjadi versi decisional dari Masalah Ukuran Sirkuit Minimum,
dan biarkan "[1]" menunjukkan " hanya 1 permintaan ".
Jawaban untuk pertanyaan saya tampaknya , Yang sebenarnya adalah seperti bahwa untuk setiap bilangan bulat positif k, ia memiliki $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$
Batas bawah: $\omega \hspace{-0.02 in}\big(\hspace{-0.03 in}n^k\hspace{-0.03 in}\big)$

Ikuti paragraf akhir halaman 7 dari makalah ini , dengan paragraf menjadi satu lebih dari argumen ini , dan tambahan "amati bahwa itu adalah tugas" co_dMCSP "untuk memutuskan apakah tabel kebenaran dengan panjang sulit" , dalam arti yang sama seperti yang digunakan dalam halaman-7 paragraf itu. The DNF sirkuit untuk sewenang-wenang panjang- tabel kebenaran memiliki ukuran paling $k$ $k$
$\ell$

$\ell$ , sehingga dMCSP dalam . Oleh karena itu $\ell^{\hspace{.03 in}2} \cdot \operatorname{polylog}(\ell)$
$\mathbf{NP}$ $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.03 in}\mathbf{NP}}\hspace{-0.03 in}\right)} = \Delta^p_3$

$\subseteq$ $\mathbf{NP}$
$\mathbf{NP}$
, Tetapi khususnya saya tidak mengetahui adanya bukti kekerasan tersebut. $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$

sumber