Apakah ada masalah yang dapat diputuskan yang tanpa algoritma kami dapat memberikan batasan waktu?

12

Apakah ada masalah yang dapat diputuskan sedemikian rupa sehingga tanpa algoritma yang memecahkan masalah kita dapat memberikan batasan waktu sebagai fungsi dari panjang n dari instance input?

Saya sampai pada pertanyaan ini karena saya memikirkan hal-hal berikut:

Anggaplah kita memiliki masalah yang berulang secara berulang, tetapi tidak dapat diputuskan. Asumsikan lebih lanjut bahwa saya adalah "ya" - masalah utama. Maka tanpa algoritma yang mengidentifikasi "ya" - keadaan dari masalah kita dapat memberikan batasan waktu dalam hal ukuran n dari I. Karena jika kita dapat memberikan batasan waktu seperti itu, kita dapat memutuskan masalahnya, karena kita dapat dengan mudah menyimpulkan bahwa saya adalah keadaan "tidak" ketika batas waktu terlampaui.

Karena kita tidak dapat memberikan batasan waktu untuk masalah yang berulang secara berulang, tidak dapat diputuskan (untuk waktu perhitungan untuk keadaan "ya"), saya bertanya-tanya apakah ada masalah yang dapat diputuskan juga sehingga kita tidak dapat memberikan batasan waktu.

computability time-complexity Hermann
sumber

9

Ada batasan waktu sepele pada algoritma tersebut: jalankan algoritme, dan kembalikan jumlah langkah yang dilakukan oleh algoritma tersebut. Di sisi lain, mudah untuk membuat contoh yang sulit untuk memberi batasan yang mudah dipahami atau diekspresikan, misalnya fungsi ackermann.

cody

2

Anda harus lebih tepat. Jika Anda berbicara tentang fungsi (matematika), maka ya, ada fungsi yang cocok dengan waktu berjalan dari setiap mesin Turing (pada kenyataannya, ada lebih banyak fungsi daripada mesin Turing). Jika Anda berbicara tentang fungsi yang dapat dihitung atau, setara, algoritma, maka @cody memberi Anda jawabannya: jalankan mesin Turing yang memutuskan masalah dan hitung waktu berjalannya.

Alex ten Brink

8

n

$n$

n

$n$

8

Bolehkah saya menyarankan revisi? Untuk menghindari jawaban yang sepele, anggaplah kita mendefinisikan frasa "kita dapat memberikan batas waktu" yang berarti "kita dapat menghitung batas atas pada waktu menjalankan kasus terburuk lebih cepat daripada dengan menjalankan algoritma pada semua contoh ukuran n." Atau mungkin "semua contoh" harus "satu contoh".

Jeffε

1

Argumen Anda tergantung pada fungsi terikat waktu Anda yang dapat dihitung total . Sudah diketahui umum bahwa ini tidak dapat dilakukan, tetapi jika itu adalah pertanyaan Anda (yaitu ada fungsi parsial yang dapat dihitung tanpa ekstensi fungsi yang dapat dihitung total), maka pertanyaannya bukan pada tingkat penelitian. Silakan lihat FAQ untuk saran tentang di mana Anda mungkin dapat mengajukan pertanyaan semacam ini.

Kaveh

13

$A$ $\mathsf{In}$

f (n) = max_{i \in I n (n)} t i m e (A (i)),

$f(n)=\max_{i\in \mathsf{In(n)}}~~ \mathsf{time}(A(i)),$

I n (n)

$\mathsf{In}(n)$

n

$n$

t i m e (A (i))

$\mathsf{time}(A(i))$

A

$A$

i

$i$

Jika kita menggunakan istilah aljabar sederhana (tanpa rekursi apa pun) sebagai definisi singkat, maka saya pikir jawabannya tidak: Ada masalah yang dapat diputuskan tetapi kompleksitasnya nonelementary. Artinya, tidak ada setumpuk formulir yang membatasi waktu eksekusi suatu algoritma untuk masalah ukuran n. $2^{2^{2^{2^{\dots^n}}}}$

Saya harap saya mengerti pertanyaan Anda dengan cara yang benar.

Markus
sumber

6

Ini sedikit berbeda dengan pertanyaan Anda daripada pertanyaan Marcus, tetapi mengingat penjelasan Anda tentang bagaimana Anda memikirkan pertanyaan ini, mungkin lebih dekat dengan apa yang Anda cari.

Kadang-kadang seseorang dapat membuktikan bahwa suatu masalah dapat diputuskan, tanpa dapat menunjukkan algoritme untuknya. Contoh paling terkenal dari hal semacam ini adalah karya Robertson dan Seymour pada grafik anak di bawah umur, yang menunjukkan bahwa properti grafik herediter dapat diputuskan dalam waktu polinomial, dengan memeriksa keberadaan daftar terbatas yang sesuai dari anak di bawah umur yang dilarang. Bukti mereka hanya menunjukkan bahwa ada daftar terbatas untuk anak di bawah umur terlarang, tetapi tidak memberikan resep untuk menemukan daftar.

Saya bukan ahli dalam bidang ini, jadi saya tidak tahu apa-apa tentang contoh spesifik properti grafik turun-temurun yang kami tidak dapat menunjukkan algoritme karena kami tidak tahu daftar anak di bawah umur yang terlarang dan kami tidak tahu cara lain untuk menyelesaikan masalah, tetapi saya curiga ada contoh seperti itu. (Dan kita dapat mengikat waktu berjalan untuk menemukan contoh jika itu ada, karena kita tahu bahwa ada paling banyak 8 miliar orang di dunia dan dalam kasus terburuk kita dapat menanyakan semuanya!)

Satu komentar lebih lanjut: Karena kita tahu bahwa memeriksa minor dapat dilakukan dalam waktu , Anda dapat berargumen bahwa dalam semua kasus yang disediakan oleh algoritma Robertson-Seymour, kami memang memiliki "ikatan" pada waktu berjalan. Namun, saya berpendapat bahwa ini semacam kecurangan, jika kita tidak terikat pada konstanta. $O(n^3)$ $O(n^3)$

Timothy Chow
sumber

2

Tetapi jika Anda memilih satu set eksplisit anak di bawah umur yang dikecualikan, maka Anda dapat menunjukkan suatu algoritma. Lebih baik memilih properti warisan yang belum dipelajari. Ini agak sulit dilakukan.

Timothy Chow

2

Ini cukup tangensial untuk poin Anda, tetapi: properti grafik minor-tertutup sebenarnya bisa diputuskan dalam waktu research.nii.ac.jp/~k_keniti/quaddp1.pdf .

O (n^{2})

$O(n^2)$

Emil Jeřábek 3.0

1

@ EmilJeřábek: bahkan lebih tangensial, memutuskan apakah grafik dari keluarga kecil-tertutup memenuhi properti urutan pertama dapat dilakukan dalam waktu linier: arxiv.org/abs/1109.5036

András Salamon

1

Omong-omong, Kowarabayashi dan Wollan mengklaim terikat pada konstanta dalam makalah STOC 2011 mereka dsi.uniroma1.it/~wollan/PUBS/shorter_struct_web.pdf yang juga melaporkan kemajuan lebih lanjut yang "belum sepenuhnya ditulis". Namun, saya tidak dapat dengan mudah mengekstraksi batasan eksplisit dari makalah ini.

András Salamon

2

Untuk contoh seperti itu, Anda memiliki grafik dengan sampul planar. Anehnya, kita hampir tahu daftar: ada 31 anak di bawah umur yang terlarang, dan yang ke-32 yang potensial, tetapi untuk yang terakhir ini terbuka apakah memiliki penutup planar atau tidak. Karenanya kami tidak memiliki algoritma untuk kelas grafik ini. Lihat misalnya: fi.muni.cz/~hlineny/papers/plcover20-gc.pdf

Denis

3

Hanya untuk menambahkan perspektif yang berbeda, izinkan saya ingat bahwa tidak setiap masalah memiliki kompleksitas "intrinsik", yang mungkin merupakan konsekuensi paling menarik dan entah bagaimana diabaikan dari teorema speedup Blum.

Pada dasarnya teorema menyatakan bahwa, memperbaiki speedup g yang diinginkan, Anda mungkin selalu menemukan masalah komputasi P sehingga untuk setiap penyelesaian program P ada program lain yang masih menyelesaikan P dan menjalankan g-kali lebih cepat daripada yang sebelumnya.

Karenanya, untuk masalah seperti ini Anda tidak dapat memberikan batasan waktu. Luar biasa, dan hasilnya cukup membingungkan. Tentu saja P memiliki kompleksitas yang sangat besar.

Andrea Asperti
sumber

Kenapa P memiliki kompleksitas yang sangat besar?

Karena proses percepatan dapat diulang, maka itu harus kompatibel dengan rantai algoritme tak terbatas dengan kompleksitas yang menurun.

Andrea Asperti

3

Aspek teoretis dari pertanyaan Anda ditangani oleh Markus. Secara lebih praktis, cara yang menarik untuk memahami pertanyaan Anda adalah: adakah masalah yang bisa diputuskan yang tidak kita ketahui ada batasan waktu?

Jawabannya adalah ya: sebagai contoh, dapat terjadi bahwa Anda memiliki semi-algoritma untuk instance YA dari masalah Anda, dan semi-algoritma untuk instance NO. Ini memberi Anda decidability dari masalah Anda, tetapi tidak ada batas waktu.

Berikut adalah contoh umum: anggap Anda memiliki sistem aksiomatik yang memungkinkan Anda untuk membuktikan semua identitas sejati dalam beberapa aljabar. Selain itu, Anda tahu bahwa identitas palsu selalu disaksikan oleh struktur yang terbatas.

Kemudian Anda memiliki algoritma berikut untuk memutuskan apakah identitas benar: sebutkan dengan bukti paralel dan struktur hingga, dan berhenti ketika Anda menemukan bukti atau struktur yang menyaksikan bahwa salah. Ini memberi Anda algoritma yang benar tetapi tidak ada kompleksitas terikat, kecuali Anda dapat mengikat ukuran bukti dan struktur hingga sehubungan dengan . $I$ $I$ $I$ $I$

Contoh dari hal ini adalah affine linear logic (LLW): sekarang dikenal sebagai Tower-complete [1], tetapi untuk beberapa waktu tidak ada batasan yang diketahui, dan hanya decidability yang ditunjukkan, dengan menggunakan di antara teknik lainnya model properti hingga [2] .

Referensi:

[1] Kompleksitas non-dasar untuk percabangan VASS, MELL, dan ekstensi. Ranko Lazic dan Sylvain Schmitz. CSL-LICS 2014

[2] Properti model hingga untuk berbagai fragmen logika linier. Yves Lafont, J. Symb. Logika. 1997

Denis
sumber

-4

seperti orang lain telah menyatakan pertanyaannya tidak dinyatakan dengan cara yang menghindari jawaban sepele namun ada beberapa konsep dalam TCS & teori bilangan yang terkait / mirip.

1) dalam teorema hierarki ruang dan waktu diperlukan konsep fungsi "konstruktif waktu" dan "konstruktif ruang" . fungsi non konstruktif waktu dan non ruang konstruktif ada dan mengarah ke properti yang tidak biasa yang ditemukan dalam teorema Blum seperti teorema "gap, speedup". sebagian besar (semua?) std kelas kompleksitas didefinisikan dalam hal fungsi ruang dan waktu yang dapat dibangun.

2) fungsi ackerman bersifat total rekursif tetapi tidak primitif rekursif dan ini berimplikasi pada batas waktunya. fungsi rekursif primitif dalam beberapa hal mewakili operasi matematika "dasar".

3) ada beberapa hal tentang deretan teori bilangan yang tidak dapat dihitung dalam aritmetika peano yang dapat diartikan sebagai menciptakan batas waktu yang tidak dapat dihitung dalam batas waktu seperti deretan goodstein atau paris-harrington thms

vzn
sumber

5

bukan jawaban untuk pertanyaan itu.

Kaveh

Apakah ada masalah yang dapat diputuskan yang tanpa algoritma kami dapat memberikan batasan waktu?

Jawaban: