Polinomial eksplisit dalam 1 variabel dengan kompleksitas sirkuit superlogaritmik batas bawah?

Dengan menghitung argumen, orang dapat menunjukkan bahwa ada polinomial derajat n dalam 1 variabel (yaitu, sesuatu dari bentuk yang memiliki kompleksitas rangkaian n. Juga, seseorang dapat menunjukkan bahwa polinomial seperti memerlukan setidaknya perkalian (Anda perlu itu hanya untuk mendapatkan gelar cukup tinggi). Apakah ada contoh eksplisit polinomial dalam 1 variabel dengan batas bawah kompleksitas superlogaritmik? (hasil di bidang apa pun akan menarik) $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ $x^n$ $\log_2 n$

cc.complexity-theory circuit-complexity polynomials algebraic-complexity Matt terburu-buru
sumber

Apakah contoh yang ada dalam pikiran Anda dengan kompleksitas sirkuit

atas bidang yang terbatas? Saya tidak melihat bagaimana argumen penghitungan akan bekerja di bidang yang tak terbatas, dan atas rasional saya cukup yakin Paterson-Stockmeyer's

n

$n$

terikat ketat (lihat juga jawaban saya di bawah).

\sqrt{n}

$\sqrt{n}$

Joshua Grochow

Batas sqrt (n) yang Anda sebutkan hanyalah batas atas jumlah perkalian (atas bidang apa pun), tetapi jika kami menghitung penambahan dan perkalian sebagai operasi, maka kami membutuhkan operasi n atas bidang tak terbatas untuk hampir setiap polinomial, hanya karena ada n koefisien yang berbeda dalam polinomial dan tidak ada cara untuk mengevaluasi semua polinomial yang mungkin dengan operasi kurang dari n (saya tidak yakin apakah ini harus disebut argumen penghitungan atau tidak).

Matt Rush

\sum a_{i} x^{i}

$\sum a_i x^i$

x

$x$

a_{i}

$a_i$

a_{i}

$a_i$

Maksud saya adalah: sirkuit terdiri dari gerbang penambahan dan multiplikasi. Input untuk gerbang yang diberikan dapat berupa output dari gerbang sebelumnya, atau x, atau beberapa konstanta. Pertanyaannya adalah: untuk polinomial tertentu, dapatkah kita menemukan rangkaian dan pilihan konstanta di sirkuit itu untuk menghitungnya? Tapi, kita memiliki ruang dimensi (n + 1) polinomial, tetapi jika kita memperbaiki struktur sirkuit dengan kurang dari n gerbang (dengan "struktur", maksudku gerbang mana yang menggunakan keluaran dari gerbang lain) dan mempertimbangkan semua kemungkinan pilihan konstanta ini memberikan kurang dari ruang n dimensi polinomial yang dapat dihitung.

Matt Rush

Btw --- kesan yang saya dapatkan adalah bahwa membangun contoh eksplisit melalui R atau C tanpa pembatasan lebih lanjut pada koefisien sebagian besar diselesaikan. Di sisi lain, membangun contoh eksplisit di mana semua koefisien a_i adalah bilangan bulat dan tidak tumbuh terlalu cepat, masih terbuka? Ada contoh dengan semua konstanta integer dalam survei yang Anda sebutkan, tetapi mereka tumbuh dua kali lipat secara eksponensial.

matt hastings

$n$ $(a_1, \dotsc, a_n)$ $\prod_{i=1}^{n} (x - a_i)$ $\Omega(\sqrt{n})$

$\sqrt{n}$ $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$ $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$ $\sum_{i=1}^{n} i^{r} x^{i}$ $r$

Joshua Grochow
sumber

Terima kasih. Jadi, akan terlihat bahwa masalah terbuka adalah bahwa jika Anda menghitung penambahan juga sebagai operasi, dapatkah seseorang membangun polinomial yang membutuhkan lebih dari operasi sqrt (n), dengan tujuan membangun yang membutuhkan operasi n. Adakah hasil ke arah ini? (Saya ragu, karena dalam metode yang hanya membutuhkan multiplikasi sqrt (n), penambahan memberikan beberapa perkalian matriks dan ini mungkin mengurangi batas yang lebih rendah pada kompleksitas perkalian matriks-skalar)

matt hastings

Polinomial eksplisit dalam 1 variabel dengan kompleksitas sirkuit superlogaritmik batas bawah?

Jawaban: