Masalah nontrivial dipecahkan dalam waktu yang konstan?

Waktu konstan adalah kompleksitas akhir waktu mutlak yang rendah. Orang mungkin bertanya-tanya: adakah sesuatu yang nontrivial yang dapat dihitung dalam waktu yang konstan? Jika kita berpegang pada model mesin Turing, maka tidak banyak yang dapat dilakukan, karena jawabannya hanya dapat bergantung pada panjang segmen awal input, karena bagian input yang lebih jauh bahkan tidak dapat dicapai dalam waktu konstan.

Di sisi lain, jika kita mengadopsi model RAM unit-cost yang agak lebih kuat (dan lebih realistis), di mana operasi dasar pada $O(\log n)$ -bilangan bit dihitung sebagai langkah tunggal, maka kita mungkin dapat menyelesaikan nontrivial tugas, bahkan dalam waktu yang konstan. Berikut ini sebuah contoh:

Instance: Integer , masing-masing diberikan dalam format biner oleh bit. $n, k, l, d$ $O(\log n)$

Pertanyaan: Apakah ada grafik -vertex, sehingga konektivitas verteksnya adalah , konektivitas tepinya adalah , dan derajat minimumnya adalah ? $n$ $k$ $l$ $d$

Perhatikan bahwa dari definisi itu bahkan tidak jelas bahwa masalahnya ada di NP . Alasannya adalah bahwa saksi alami (grafik) mungkin perlu $\Omega(n^2)$ -bit panjang deskripsi, sedangkan input hanya diberikan oleh $O(\log n)$ bit. Di sisi lain, teorema berikut (lihat Teori Grafik Ekstrimal oleh B. Bollobas) datang untuk menyelamatkan.

Teorema: Biarkan menjadi bilangan bulat. Ada grafik -vertex dengan konektivitas vertex , konektivitas edge , dan derajat minimum , jika dan hanya jika salah satu dari kondisi berikut dipenuhi: $n, k, l, d$ $n$ $k$ $l$ $d$

, $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$
$1\leq 2d+2-n\leq k\leq l = d< n-1$
$k=l=d=n-1.$

Karena kondisi ini dapat diperiksa dalam waktu konstan (dalam model RAM unit-cost), Teorema mengarah ke algoritma waktu konstan dalam model ini.

Pertanyaan: Apa sajakah contoh nontrivial lain dari algoritma waktu konstan?

cc.complexity-theory ds.algorithms time-complexity Andras Farago
sumber

Apakah memverifikasi bukti yang dapat diperiksa secara probabilistik dihitung?

David Eppstein

Jangan kira contoh Anda adalah

waktu. Input Anda memiliki panjang

, dalam hal ini RAM kata khas hanya akan memungkinkan operasi

-bit dalam satu langkah. (Alternatifnya adalah memungkinkan ukuran kata proporsional dengan panjang input, tetapi dalam hal ini orang dapat menyebutkan banyak algoritma "waktu konstan" ...) Anda dapat mencoba menambahkan string panjang

setelah angka-angka itu, tetapi kemudian saya tidak melihat bagaimana memeriksa format itu akan berjalan di

O (1)

$O(1)$

m = O (\log n)

$m=O(\log n)$

O (\log m)

$O(\log m)$

\geq n

$\geq n$

O (1)

$O(1)$ time: tampaknya Anda harus memeriksa (melalui pencarian biner, katakanlah) bahwa total panjang string memang

, yang membutuhkan

waktu.

Ω (\log n)

$\Omega(\log n)$

\log n

$\log n$

Ryan Williams

Saya pikir saran David Eppstein menunjuk ke arah yang lebih menarik: mempertimbangkan algoritma waktu O (1) acak . Setidaknya dalam kasus itu, Anda dapat berharap bahwa setiap bit input diakses setidaknya dalam satu kemungkinan proses algoritma.

Ryan Williams

Contoh sederhana dari algoritma waktu O (1) acak adalah median perkiraan (perkiraan dalam arti bahwa ia akan membagi input sekitar 50-50). Cukup pilih 1000000 elemen dari input secara seragam secara acak, hitung mediannya, dan hasilkan.

Jukka Suomela

Saya suka pertanyaan Anda, tetapi kekurangan dari contoh Anda adalah bahwa itu bergantung pada teorema matematika. Mendorong ini ke batas yang bisa Anda katakan: Instance Positive integer

. Pertanyaan Apakah ada bilangan bulat

sehingga

(jawabannya Benar atau Salah). Ya, memang ada algoritma waktu yang konstan karena jawabannya selalu salah, tetapi ini jelas bukan jenis contoh yang Anda inginkan.

x, y, z

$x, y, z$

n > 2

$n > 2$

x^{n} + y^{n} = z^{n}

$x^n + y^n = z^n$

J.-E.

Jawaban:

Makalah Algoritma Perkiraan Konstan-Waktu melalui Perbaikan Lokal oleh Nguyen dan Onak memberikan banyak contoh skema perkiraan waktu konstan acak: Pencocokan Maksimum (waktu berjalan hanya bergantung pada tingkat maksimum grafik), Atur penutup, dll. Penulis menyajikan metode untuk merancang algoritma tersebut.

Lamin
sumber

Ada banyak contoh gim yang dipelajari dalam teori gim kombinatorial di mana keadaan gim dapat digambarkan dengan jumlah nilai integer yang konstan. Untuk beberapa di antaranya, strategi kemenangan untuk permainan dapat dihitung dalam waktu yang konstan. Tetapi mereka juga mengajukan pertanyaan tentang apa sebenarnya model perhitungan Anda.

Salah satu permainan kombinatorial yang paling sederhana dan paling dasar adalah nim: satu memiliki jumlah tumpukan kacang yang konstan, dan dalam satu gerakan Anda dapat menghilangkan sejumlah biji dari satu tumpukan, baik menang atau kalah (tergantung pada pilihan aturan Anda) jika Anda mengambil kacang terakhir. Strategi optimal dapat dihitung dalam waktu konstan jika Anda mengizinkan operasi bitor Boolean xor (yaitu operator ^ dalam bahasa pemrograman seperti C / C ++ / Java / dll.) Apakah ini algoritma waktu konstan dalam model Anda?

Inilah salah satu di mana diketahui bahwa ada algoritma deterministik tepat waktu konstan yang konstan (dalam model perhitungan yang mungkin tidak realistis yang memungkinkan Anda untuk menguji keutamaan angka dalam waktu yang konstan) tetapi tidak diketahui apa algoritma itu: diberi permulaan bergerak dalam permainan koin Sylver , tentukan apakah itu langkah menang atau kalah. Diagram alir untuk masalah ini diberikan dalam Berlecamp, Conway, dan Guy, Winning Ways , tetapi itu tergantung pada seperangkat contoh tandingan hingga karakterisasi umum dari langkah-langkah kemenangan, dan tidak diketahui apa set itu (atau bahkan apakah itu adalah kosong).

Contoh lain yang menarik dari teori permainan kombinatorial adalah permainan Wythoff. Setiap posisi permainan dapat digambarkan oleh sepasang bilangan bulat (yaitu, ruang konstan, dalam model perhitungan Anda), gerakan dalam permainan melibatkan pengurangan salah satu dari dua bilangan bulat ini ke nilai yang lebih kecil, dan strategi yang menang melibatkan pindah ke posisi di mana rasio antara kedua bilangan bulat ini sedekat mungkin dengan rasio emas. Tetapi dalam banyak posisi permainan ada pilihan: Anda dapat mengurangi yang lebih besar dari dua bilangan bulat baik ke titik di mana itu (hampir) bilangan bulat lebih kecil kali rasio emas, atau bilangan bulat yang lebih kecil dibagi dengan rasio emas. Hanya satu dari dua pilihan ini yang akan menjadi langkah kemenangan. Jadi strategi optimal dapat didefinisikan dalam hal jumlah konstan operasi aritmatika, tetapi operasi ini melibatkan bilangan irasional, rasio emas. Apakah itu algoritma waktu yang konstan dalam model Anda? Mungkin itu' $n$ $\log n$

David Eppstein
sumber

Terima kasih, ini semua contoh menarik. Mereka juga dengan baik menjelaskan fakta bahwa konsep "waktu konstan" kurang jelas dari yang saya kira ...

Andras Farago

$|G|$ $G$ $p$ $m$ $m$ $|G|$ $G$ $p$ $m$ $G$ $|G|$ $m$ $m$ $m$

orgesleka
sumber