Adakah fungsi yang diketahui ada dengan properti direct-sum berikut?

15

Pertanyaan ini dapat ditanyakan dalam kerangka kompleksitas sirkuit dari sirkuit Boolean, atau dalam kerangka teori kompleksitas aljabar, atau mungkin dalam banyak pengaturan lainnya. Mudah untuk menunjukkan, dengan menghitung argumen, bahwa ada fungsi Boolean pada input N yang membutuhkan banyak gerbang secara eksponensial (meskipun tentu saja kami tidak memiliki contoh eksplisit). Misalkan saya ingin mengevaluasi fungsi yang sama M kali, untuk beberapa bilangan bulat M, pada M set input yang berbeda, sehingga jumlah total input adalah MN. Yaitu, kami hanya ingin mengevaluasi untuk fungsi yang sama pada setiap waktu.f(x1,1,...,x1,N),f(x2,1,...,x2,N),...,f(xM,1,...,xM,N)f

Pertanyaannya adalah: apakah diketahui bahwa ada urutan fungsi (satu fungsi untuk setiap N) sehingga, untuk setiap N, untuk setiap M, jumlah gerbang yang diperlukan setidaknya sama dengan M kali fungsi eksponensial dari N? Argumen penghitungan sederhana tampaknya tidak berfungsi karena kami ingin hasil ini berlaku untuk semua M. Seseorang dapat menghasilkan analog sederhana dari pertanyaan ini dalam teori kompleksitas aljabar dan bidang lainnya.f

Matt terburu-buru
sumber

Jawaban:

13

Ya, itu salah: adalah mungkin untuk mengevaluasi salinan M dari APAPUN f hanya menggunakan gerbang O (N (M + 2 ^ N)) yang bisa jauh lebih kecil dari M * exp (N) (pada kenyataannya, Anda mendapatkan linear diamortisasi kompleksitas untuk eksponensial M). Saya tidak ingat referensi, tapi saya pikir itu bisa seperti ini:

Pertama tambahkan 2 ^ N input fiktif yang hanya konstanta 0 ... 2 ^ N-1 dan sekarang menunjukkan input N-bit ke-i oleh xi (jadi untuk i <= 2 ^ N kita memiliki xi = i, dan untuk 2 ^ N <i <= 2 ^ N + M kami memiliki input asli). Sekarang kita membuat triplet untuk masing-masing input M + 2 ^ N: (i, xi, fi) di mana fi adalah f (i) untuk input 2 ^ N pertama (sebuah konstanta yang tertanam di dalam sirkuit) dan fi = "*" jika tidak. Sekarang kita mengurutkan kembar tiga (i, xi, fi) sesuai dengan kunci xi, dan biarkan triplet j'th menjadi (i_j, x_j, f_j) dari ini kita menghitung triplet (i_j, x_j, g_j) dengan membiarkan g_j menjadi f_j jika f_j bukan "*" dan biarkan g_j menjadi g_ (j-1) sebaliknya. Sekarang urutkan kembali kembar tiga baru sesuai dengan kunci i_j, dan Anda mendapatkan jawaban yang benar di tempat yang benar.

Noam
sumber
Pintar! Satu hal kecil: kita harus mengurutkan kembar tiga secara stabil (atau dalam metode lain yang menjamin bahwa kembar tiga dengan fi ≠ " " datang lebih awal daripada kembar tiga dengan fi = " ").
Tsuyoshi Ito
Sangat pintar, dan terima kasih. Apakah ada yang serupa bekerja, dalam pengaturan kompleksitas aljabar, atau tidak?
Matt Rush
1
Saya kira cara lain untuk mengatakan ini dalam kasus M pergi ke tak terhingga adalah bahwa Anda dapat berinvestasi 2 ^ N * 2 ^ N waktu untuk membangun tabel hash untuk semua nilai f, dan kemudian Anda dapat menghitung setiap salinan dalam O (N ) waktu. Saya pikir ada alasan lain yang setidaknya kita tidak seharusnya tahu jika sesuatu seperti itu benar, bahkan untuk nilai N yang lebih ringan, yaitu bahwa itu akan memberikan yang lebih baik daripada batas bawah yang diketahui. Anda dapat membangun fungsi dengan superlinear terikat lebih rendah dengan brute pertama memaksa untuk menemukan fungsi pada n '= log n (atau mungkin n' = loglog n) input dengan kompleksitas besar dan kemudian mengambil n / n 'salinannya .
Boaz Barak
1
Dalam argumen di atas tentang mengapa hasil seperti itu mengarah ke batas bawah, saya tidak tahu apakah jumlah pengulangan benar-benar lebih ringan, tetapi itu berlaku untuk bidang tak terbatas juga.
Boaz Barak
Hai Boaz, Sebenarnya komentar Anda justru mengapa saya tertarik dengan keberadaan fungsi-fungsi ini. Namun, ada titik halusnya, "brute forcing". Bisa jadi (yang dimaksudkan oleh pertanyaan saya), bahwa fungsi-fungsi seperti itu ada tetapi kami tidak memiliki algoritma yang akan memungkinkan kami untuk menunjukkan bahwa fungsi yang diberikan memiliki properti ini. Lagi pula, sepertinya tidak ada cara untuk secara paksa memaksa properti yang dimiliki batas bawah seperti itu untuk semua M, karena Anda harus memeriksa jumlah rangkaian berbeda yang tak terbatas. Jadi, mungkin fungsi seperti itu ada untuk bidang yang tak terbatas tetapi kami tidak dapat menampilkannya.
matt hastings
10

O(2n/n)mmfm2n/n

"Jaringan menghitung fungsi Boolean untuk beberapa nilai input"

m=2o(n/logn)mfO(2n/n)m=1

Saya tidak dapat menemukan salinan yang tidak dikunci online, atau beranda untuk penulis, tetapi saya menemukan makalah ini dalam proses ini:

Kompleksitas Fungsi Boolean (Seri Catatan Ceramah Masyarakat Matematika London)

Andy Drucker
sumber
Terima kasih! Apakah tidak ada pertanyaan yang diajukan tentang paradoks dalam TCS? Ini juga bisa berfungsi sebagai jawaban di sana :)
arnab
Terima kasih atas jawaban ini juga. Karena tidak dapat membaca proses, saya akan menebak bahwa mirip dengan jawaban sebelumnya mungkin bergantung pada jumlah input yang mungkin terbatas, jadi sekali lagi pertanyaan tindak lanjut yang sama seperti di atas: bagaimana dengan dalam kasus kompleksitas aljabar?
Matt Rush
Sebenarnya, tampaknya Shannon pertama kali membuktikan batas atas O (2 ^ n / n); Lupanov mendapat konstanta memimpin kanan. Saya mengoreksi ini. Rinciannya dijelaskan dalam "Meninjau batas ukuran sirkuit dari fungsi yang paling sulit", oleh Frandsen dan Miltersen.
Andy Drucker
5

Mengenai kompleksitas Aljabar, saya tidak tahu contoh di mana kompleksitas eksponensial turun ke kompleksitas diamortisasi sub-eksponensial, tetapi setidaknya ada contoh sederhana bahwa kompleksitas salinan disjoint M dapat secara signifikan kurang dari M kali kompleksitas salinan tunggal. :

Untuk matriks A "acak" n * n, kompleksitas bentuk bilinear didefinisikan oleh A, (fungsi f_A (x, y) = xAy, di mana x dan y adalah 2 vektor panjang n) adalah Omega (n ^ 2 ) - ini dapat ditunjukkan oleh argumen dimensi "menghitung-seperti" karena Anda memerlukan n ^ 2 "tempat" di sirkuit untuk meletakkan konstanta. Namun, mengingat n pasangan vektor yang berbeda (x ^ 1, y ^ 1) ... (x ^ n, y ^ n), Anda dapat memasukkan x ke dalam baris matriks n * n X, dan demikian pula dengan y ke dalam kolom dari matriks Y, dan kemudian baca semua jawaban x ^ iAy ^ i dari diagonal XAY, di mana ini dihitung dalam operasi n ^ 2.3 (atau lebih) menggunakan perkalian matriks cepat, secara signifikan kurang dari n * n ^ 2.

Noam
sumber
Terima kasih, saya tahu contoh itu. Yang serupa adalah bahwa ada derajat n polinomial dalam satu variabel yang membutuhkan waktu n untuk mengevaluasi pada titik tertentu (meskipun saya tidak berpikir ada contoh eksplisit, apakah saya salah?) Namun, seseorang dapat mengevaluasi polinomial semacam itu di n titik waktu n log ^ 2 (n).
matt hastings
1
Saya menemukan dua makalah dari tahun 80-an tentang masalah jumlah langsung aljabar: "Pada validitas dugaan jumlah langsung" oleh Ja'ja dan Takche, dan "Pada dugaan jumlah langsung diperpanjang" oleh Bshouty. Saya tidak bisa meringkas konten mereka, tetapi mungkin mereka akan membantu.
Andy Drucker
5

Ini dipelajari dan diselesaikan oleh Wolfgang Paul yang pada dasarnya menunjukkan apa yang dibicarakan berlaku.

kontol lipton
sumber
2
Bagus! Apakah ada referensi?
Hsien-Chih Chang 張顯 之