Analisis kompleks dalam ilmu komputer teoretis

24

Ada banyak aplikasi analisis nyata dalam ilmu komputer teoretis, yang mencakup pengujian properti, kompleksitas komunikasi, pembelajaran PAC, dan banyak bidang penelitian lainnya. Namun, saya tidak dapat memikirkan hasil apa pun dalam TCS yang mengandalkan analisis kompleks (di luar komputasi kuantum, di mana bilangan kompleks adalah intrinsik dalam model). Adakah yang memiliki contoh hasil TCS klasik yang menggunakan analisis kompleks?

soft-question big-picture
sumber

1

Pertanyaan bagus! Saya akan menyarankan akan lebih baik untuk mengecualikan hasil yang berkaitan dengan teori bilangan - misalnya setiap penggunaan hipotesis Riemann - daripada komputasi kuantum, yang cenderung tentang sistem dimensi-terbatas (sejauh yang saya tahu).

Colin McQuillan

11

Kami menggunakan analisis kompleks dalam sebuah makalah “Konstanta Grothendieck Strictly Smaller daripada Krivine's Bound,” yang (dari sudut pandang TCS) memberikan algoritma perkiraan untuk masalah memaksimalkan tunduk pada . Lihat ttic.uchicago.edu/~yury/papers/grothendieck-krivine.pdf

\sum_{i, j} a_{i j} x_{i} y_{j}

$\sum_{i,j} a_{ij} x_i y_j$

x_{i}, y_{j} \in {\pm 1}

$x_i, y_j\in \{\pm 1\}$

Yury

3

@Yury, itu bisa menjadi jawaban.

Suresh Venkat

14

Algoritma berbasis kompleks Barvinok untuk memperkirakan algoritma waktu polinomial permanen untuk memperkirakan permanen dan campuran diskriminan dalam faktor eksponensial sederhana .

Juga, jelas, operator kompleks (dan beberapa analisis kompleks) penting dalam komputasi kuantum.

Izinkan saya juga merekomendasikan buku ini: Topik-topik dalam analisis kinerja oleh Eitan Bachmat dengan banyak masalah besar yang relevan dan hal-hal hebat lainnya.

Gil Kalai
sumber

Itu contoh yang bagus, saya tidak menyadari hasil ini - terima kasih!

25

Ini bukan masalah tunggal, tetapi seluruh bidang analitik kombinatorik (lihat buku oleh Flajolet dan Sedgewick ) mengeksplorasi bagaimana menganalisis kompleksitas kombinatorial dari ~~penghitungan~~ struktur (atau bahkan algoritma waktu berjalan) dengan menuliskan fungsi pembangkit yang sesuai dan menganalisis struktur. dari solusi yang kompleks.

Suresh Venkat
sumber

Hai Suresh, apa yang Anda maksud dengan 'analisis kompleksitas'?

Andy Drucker

2

Ah saya salah menulis. Maksud saya "menganalisis kompleksitas struktur kombinatorial" - akan diperbaiki.

Suresh Venkat

15

Jon Kelner memenangkan STOC Best Student Paper Award pada tahun 2004 untuk makalahnya "Partisi spektral, batas nilai eigen, dan kemasan lingkaran untuk grafik genus terikat"

Saya hanya akan mengutip dari abstrak:

Sebagai lemma teknis utama kami, kami membuktikan O (g / n) terikat pada nilai eigen terkecil kedua Laplacian dari grafik tersebut dan menunjukkan bahwa ini ketat, dengan demikian menyelesaikan dugaan Spielman dan Teng. Meskipun lemma ini pada dasarnya bersifat kombinatorial, buktinya berasal dari matematika kontinu, yang mengacu pada teori pengemasan lingkaran dan geometri permukaan Riemann yang ringkas.

Penggunaan analisis kompleks (dan matematika "terus-menerus" lainnya) untuk menyerang masalah pemisah grafik "tradisional" sangat berkesan dan merupakan alasan utama makalah ini terjebak di kepala saya meskipun sama sekali tidak terkait dengan penelitian saya.

Mugizi Rwebangira
sumber

8

Saya kira Anda mungkin lebih tertarik pada analisis kompleks yang digunakan langsung dalam buktinya. Namun, berikut adalah dua contoh dari kelas Algoritma tingkat pascasarjana yang saat ini saya ikuti:

a) Fast Fourier Transform, misalnya digunakan dalam perkalian polinomial. Meskipun implementasi dapat dilakukan dengan modulo aritmatika atau floating point (dan beberapa analisis aritmatika), buktinya paling baik dipahami dalam hal bilangan kompleks dan akar persatuannya. Saya belum mempelajari topik ini, tetapi saya sadar bahwa FFT memiliki beragam aplikasi.

b) Secara umum, melengkapi model RAM dengan kemampuan untuk menangani bilangan kompleks dalam waktu konstan (bagian nyata dan imajiner masih memiliki ketepatan terbatas) memungkinkan seseorang untuk secara pintar menyandikan masalah dan mengeksploitasi sifat-sifat bilangan kompleks yang mungkin mengungkapkan solusi (lihat juga komentar mengapa ini tidak memungkinkan Anda menjadi lebih cepat).

chazisop
sumber

Apakah Anda memiliki contoh pengamatan kedua? Ini sepele untuk menambahkan kelas "kompleks O (log n) -bit integer" ke RAM standar dengan operasi waktu-konstan. Atau dengan "lebih cepat", maksud Anda "lebih cepat dengan faktor 2"?

Jeffε

Ini adalah latihan dari kuliah: "Asumsikan Anda sedang berurusan dengan RAM yang diperluas yang dapat menghitung dengan angka kompleks dengan biaya satuan per perkalian, pembagian, penambahan, dan pengurangan. Selain itu juga dapat menghitung nilai absolut | c | dari bilangan kompleks c dalam satuan waktu. Selain itu ia "mengetahui" konstanta kompleks 0, 1, dan i. Tunjukkan bahwa dengan bilangan bulat positif n pada RAM yang diperluas, bilangan n! dapat dihitung dalam

waktu. Solusinya menggunakan multiplikasi polinomial, dari apa yang saya tahu ini lebih cepat daripada model RAM standar.

O (\sqrt{n} \log^{2} n)

$O( \sqrt{n} \log ^{2} n)$

chazisop

6

Algoritma yang diusulkan membutuhkan aritmatika nyata presisi-waktu-tak-terbatas-konstan. (Anda tidak dapat menghitung bilangan bulat

dalam waktu

menggunakan mesin dengan kata

-bit, karena Anda bahkan tidak punya waktu untuk menuliskan output!) Pertanyaannya adalah meminta Anda untuk menambahkan akar kuadrat ke model RAM nyata, bukan angka kompleks per se.

Ω (n \log n)

$\Omega(n\log n)$

o (n)

$o(n)$

O (\log n)

$O(\log n)$

Jeff

Terima kasih atas komentarnya, ini sangat mencerahkan. Saya pikir saya harus memperbarui jawaban saya ke bagian hanya dengan cerdas menyandikan masalah dengan bilangan kompleks, yaitu untuk melihat solusi yang Anda akan kehilangan sebaliknya.

chazisop

6

Mungkin aplikasi ini agak antara TCS dan Disc matematika, tetapi saya sedikit terkejut ketika saya membaca kertas "Pada fungsi Boolean yang simetris yang simetris" oleh Petr Savicky (http://www2.cs.cas.cz/~savicky/ makalah / symmetric.ps). Teorema hanya mengenai fungsi Boolean, namun salah satu buktinya menggunakan bilangan kompleks.

Magnus Find
sumber

5

Kami menggunakan Cuechy's Residue Theorem dari analisis kompleks sebagai alat teknis utama dalam makalah kami " Perkiraan Prediksi Linear Threshold ".

KIA
sumber

5

Teorema pengepakan lingkaran Koebe-Andreev-Thurston berasal dari teorema pemetaan Riemann dan memiliki berbagai aspek algoritmik. Sebagai contoh, ini memberikan bukti teorema seperor Lipton-Tarjan untuk grafik planar.

Gil Kalai
sumber

5

Segar dari oven:

Algoritma Waktu Polinomial untuk Pemulihan Penduduk yang Rugi Oleh: Ankur Moitra, Michael Saks

Mengutip dari makalah: "Di sini kita akan membuktikan prinsip ketidakpastian yang dinyatakan dalam bagian sebelumnya menggunakan alat dari analisis kompleks. Mungkin salah satu teorema yang paling berguna dalam memahami laju pertumbuhan fungsi holomorfik dalam bidang kompleks adalah Teorema Tiga Lingkaran Hadamard. .. "

Gil Kalai
sumber

σ

$\sigma$

p (0) - ϵ ‖ p ‖_{1}

$p(0) - \epsilon \|p\|_1$

n

$n$

p

$p$

‖ q ‖_{1} \leq 1

$\|q\|_1 \leq 1$

q

$q$

p

$p$

‖ \cdot ‖_{1}

$\|\cdot\|_1$ menunjukkan jumlah nilai abs dari koefisien.

arnab

‖ p ‖_{1} \geq ‖ p ‖_{s u p}^{D_{1}}

$\|p\|_1 \geq \|p\|_{sup}^{D_1}$

D_{1}

$D_1$

p (0) - ‖ p ‖_{s u p}^{D_{1}}

$p(0) - \|p\|_{sup}^{D_1}$

p

$p$

1

$1$

D_{1}

$D_1$ . Membuat transformasi koordinat, kita menemukan diri kita dalam pengaturan teorema Tiga Lingkaran: fungsi holomorfik terikat pada titik-titik dalam dua lingkaran konsentris, mengikat fungsi pada setiap lingkaran dengan jari-jari tengah.

arnab

‖ p ‖_{s u p}^{D_{1}} \geq | p (0) |^{Ω (1)}

$\|p\|_{sup}^{D_1} \geq |p(0)|^{\Omega(1)}$

p

$p$

1

$1$

D_{1}

$D_1$

5

$\ell_p$ $0 < p < 2$

Daniel M. Kane, Jelani Nelson, David P. Woodruff. Pada Kompleksitas Ruang Tepat Sketsa dan Streaming Norma Kecil. SODA 2010.

Anda bisa lolos dengan menulis bukti yang tidak menyebutkan analisis kompleks secara eksplisit (lihat butir pertama di bagian "catatan" untuk makalah itu di halaman web saya), tetapi bahkan bukti itu memiliki analisis kompleks yang bersembunyi di bawah selimut.

Jelani Nelson
sumber

4

Ada penggunaan bilangan kompleks dan analisis dalam makalah baru-baru ini oleh Naor, Regev dan Vidick, menghasilkan hasil dalam algoritma pendekatan untuk masalah optimasi NP-hard: http://arxiv.org/abs/1210.7656

Clement C.
sumber

Namun makalah lain yang menggunakan akar acak persatuan adalah Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, dan He Sun. Menghitung Subgraf sewenang-wenang dalam Aliran Data. ICALP 2012.

Jelani Nelson

3

$n + O(n/\sqrt{k})$ $k$ $n \times n$ $n!/n^n$ oleh Laurent dan Schrijver dalam MAA Monthly). Meninggalkan garis nyata untuk pesawat kompleks tampaknya penting untuk bukti Gurvits dan menyederhanakan banyak hal.

Sasho Nikolov
sumber

0

$z \leftarrow z^2 + c$

[1] Tidak dapat diaksesnya dan tidak dapat diputuskannya dalam perhitungan, geometri, dan sistem dinamis Asaki Saito, Kunihiko Kaneko

[2] Teori perhitungan dan kompleksitas bilangan real Lenore Blum, 1990

ay
sumber

0

$\mathbb{C}$

Reb.Cabin
sumber

Analisis kompleks dalam ilmu komputer teoretis

Jawaban: