Apakah ada masalah yang membagi-dan-menaklukkan / rekursi terbukti tidak berguna?

Ketika kami mencoba membuat algoritma untuk masalah baru, bagi-dan-taklukkan (menggunakan rekursi) adalah salah satu pendekatan pertama yang kami coba. Tetapi dalam beberapa kasus, pendekatan ini tampaknya tidak membuahkan hasil karena masalahnya menjadi jauh lebih rumit ketika inputnya bertambah.

Pertanyaan saya adalah: adakah masalah yang bisa kita buktikan bahwa pendekatan membagi dan menaklukkan tidak dapat membantu untuk menyelesaikannya? Pada baris-baris berikut saya mencoba membuat ini lebih formal.

Mari menjadi masalah tertentu yang input memiliki ukuran (misalnya masalah yang menerima input array nomor). Misalkan kita memiliki algoritma rekursif untuk menyelesaikan . The runtime rekursif dari algoritma yang dihitung dengan asumsi oracle yang dapat memecahkan untuk setiap dalam waktu yang konstan. Sebagai contoh: $P(n)$ $n$ $n$ $P(n)$ $P(k)$ $k<n$

Runtime rekursif pencarian biner adalah , karena hanya menggunakan perbandingan dan dua panggilan rekursif. $O(1)$
Elemen maksimum dalam array dapat ditemukan dalam waktu rekursif . $O(1)$
Runtime rekursif dari jenis gabungan adalah , karena langkah penggabungan. $O(n)$

Waktu rekursif biasanya lebih kecil dari runtime yang sebenarnya, yang mencerminkan fakta bahwa algoritma rekursif lebih sederhana daripada solusi non-rekursif langsung untuk masalah yang sama.

Sekarang pertanyaan saya adalah:

Apakah ada masalah yang dapat diselesaikan dalam waktu , tetapi terbukti tidak memiliki algoritma rekursif dengan runtime rekursif asimtotik kurang dari ? $f(n)$ $f(n)$

Beberapa varian spesifik dari pertanyaan ini adalah:

Apakah ada masalah dalam yang tidak memiliki algoritma dengan runtime rekursif ? (Mungkin menyortir?) $P$ $O(1)$
Apakah ada masalah dengan algoritma eksponensial yang tidak memiliki algoritma dengan runtime rekursif polinomial?

EDIT: bertentangan dengan dugaan saya, pengurutan memiliki algoritma dengan runtime rekursif $O(1)$ . Jadi masih terbuka, apakah ada masalah di yang tidak memiliki algoritma dengan runtime rekursif . $P$ $O(1)$

cc.complexity-theory recursion Erel Segal-Halevi
sumber

Mungkin membuktikan batas bawah kernelisasi akan melakukan trik en.wikipedia.org/wiki/Kernelization

Tyson Williams

Ukuran output adalah batas bawah pada waktu berjalan. Jadi setiap masalah dengan ukuran keluaran yang cocok dengan kompleksitasnya memiliki properti ini.

Chao Xu

@ Chen Xu: Mengapa argumen Anda tidak berlaku untuk ukuran input? Saya pikir argumennya tergantung pada model biaya mana (dan model komputasi) yang kami pertimbangkan.

Tsuyoshi Ito

Ini adalah kebalikan dari apa yang Anda cari, tetapi mengingat oracle itu model Anda dapat memecahkan jumlah subset - masalah NP-Complete yang dikenal - dalam waktu linier, sehingga dengan asumsi P! = NP itu jauh lebih kuat daripada fungsi iteratif dalam kasus ini . Fungsi ini hanya akan memeriksa apakah set saat ini menambah 0, maka jika tidak memanggil dirinya pada n himpunan bagian ukuran n-1. Runtime itu sendiri adalah n! Namun, yang lebih buruk daripada brute force, jadi saya tidak begitu yakin berapa banyak nilai yang diberikan model ini, tetapi ini masih merupakan pertanyaan yang menarik.

Phylliida

Hasil edit terbaru Anda ("rekursif" -> "divide-and-conquer") adalah perubahan yang cukup besar untuk pertanyaan tersebut. Saya hanya akan mengirim pertanyaan terpisah sebagai gantinya. Kita mungkin dapat mengatakan hal-hal tentang membagi dan menaklukkan dengan mencari contoh di kedalaman sirkuit.

usul

Jawaban:

Apakah ada masalah dengan algoritma eksponensial yang tidak memiliki algoritma dengan runtime rekursif polinomial?

Iya. Perhatikan bahwa jika bahasa penghitungan memiliki "algoritma rekursif" dengan "runtime rekursif" polinomial, maka itu dalam P. Ada bahasa penghitungan dalam E ∖ P oleh argumen diagonalisasi standar.

Apakah ada masalah yang dapat diselesaikan dalam waktu , tetapi terbukti tidak memiliki algoritma rekursif dengan runtime rekursif ? $f(n)$ $o(f(n))$

Ini mungkin tergantung pada model komputasi, tetapi saya ragu ini diketahui, mengingat bahwa teorema hierarki waktu untuk mesin dua-pita Turing tidak cukup kuat untuk membedakan, katakanlah, O ( n ² ) waktu dan o ( n ² ) waktu bahkan tanpa memberikan yang terakhir waktu akses konstan ke jawaban pada contoh yang lebih kecil.

Komentar acak pada pertanyaan Anda di pos ini:

Saya tidak berpikir bahwa pertanyaan-pertanyaan ini terkait dengan kegunaan program rekursif, terlepas dari apa judul posting dan pilihan istilah yang Anda sarankan. Seperti yang ditulis BVMR dalam sebuah jawaban, rekursi dan iterasi setara dalam arti tertentu. Alih-alih, saya pikir pertanyaan-pertanyaan itu ada kaitannya dengan kegunaan pendekatan divide-and-conquer.
Dalam teori kompleksitas, gagasan yang terkait dengan gagasan Anda tentang "algoritma rekursif" dengan "runtime rekursif" mereka disebut "pengurangan diri sendiri yang mengurangi panjang" dengan kompleksitas waktu mereka.
Beberapa bagian dari pertanyaan Anda (pasti bagian yang merujuk pada algoritma waktu sublinear) bergantung pada pilihan model komputasi.

Tsuyoshi Ito
sumber

Mengenai jawaban pertama Anda: izinkan saya mencoba mengembangkannya untuk melihat apakah saya mengerti dengan benar. Asumsikan bahwa bahasa penghitungan tertentu memiliki algoritma dengan "runtime rekursif" polinomial. Algoritma polinomial untuk bahasa ini dapat dibangun menggunakan pemrograman dinamis. Jawaban untuk

dapat ditemukan dalam waktu polinomial karena tidak ada panggilan rekursif yang diperlukan. Jawaban untuk

kemudian dapat ditemukan dalam waktu polinomial menggunakan jawaban untuk

. Maka jawaban untuk

dapat ditemukan dalam waktu polinomial menggunakan jawaban untuk

dan

n = 0

$n=0$

n = 1

$n=1$

n = 0

$n=0$

n = 2

$n=2$

n = 1

$n=1$

n = 0

$n=0$ , dll. Apakah ini benar?

Erel Segal-Halevi

Ya, meskipun lebih baik untuk menghindari gagasan asimptotik seperti "waktu polinomial" ketika Anda berbicara tentang nilai n tertentu; misalnya, tidak masuk akal untuk mengatakan “algoritma berjalan dalam waktu polinomial ketika n = 0.” Jika bahasa penghitungan memiliki “algoritma rekursif” dengan polinomial “rekursif runtime” p (n), maka kita dapat menghitung jawaban untuk n tanpa oracle dengan menghitung jawaban untuk 0, 1, 2,…, n, dan ini membutuhkan waktu

, yang jumlahnya banyak dalam n.

O (\sum_{i = 0}^{n} p (i))

$O(\sum_{i=0}^n p(i))$

Tsuyoshi Ito

Terima kasih. Saya setuju dengan komentar Anda tentang divide-and-menaklukkan dan saya mengedit pertanyaan sesuai.

Erel Segal-Halevi

Setiap pertanyaan yang memiliki jawaban rekursif memiliki jawaban berulang dan sebaliknya.

Algoritma rekursif apa pun dapat ditulis ulang dengan cara iteratif dan sebaliknya.

Karenanya, pertanyaan Anda tidak bagus.

BVMR
sumber

Kompleksitas suatu algoritma, seperti yang saya definisikan dalam pertanyaan, umumnya tidak tetap sama ketika dikonversi dari iteratif ke rekursif. Misalnya, maksimum n elemen dapat ditemukan oleh algoritma iteratif dengan operasi O (n), tetapi juga dapat ditemukan oleh algoritma rekursif dengan operasi O (1) (salah satunya adalah panggilan rekursif). Meskipun akhirnya runtime dari kedua algoritma adalah sama, algoritma rekursif lebih sederhana untuk diprogram karena memiliki lebih sedikit operasi.

Erel Segal-Halevi

-2

Saya tidak yakin apakah saya benar memahami gagasan Anda tentang "kompleksitas rekursif".

Mari (secara wajar) Asumsikan bahasa pemrograman yang berisi skema untuk rekursi primitif yaitu di mana orang dapat mendefinisikan fungsi dari $f$

f (0, \vec{x}) = c (\vec{x}) f (n + 1, \vec{x}) = g (f (n, \vec{x}), n, \vec{x})

$f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x),n,\vec x)$

$c$ $g$ $\mathcal{O}(1)$ $\mathcal{O}(1)$

Jika semua asumsi saya terpenuhi, maka contoh yang Anda cari tidak bisa menjadi rekursif primitif.

DFF
sumber

tolong jelaskan tentang downvotes

DFF

P (k)

$P(k)$

k < n

$k<n$

g (f (n, x), n, x)

$g(f(n,x),n,x)$

f (n, x)

$f(n,x)$ yang memiliki runtime konstan. Saya tidak menurunkan suara Anda, tetapi ini adalah pertanyaan yang dijawab tahun lalu dan Anda juga salah mengartikan definisi yang diberikan.

chazisop

g

$g$

O (1)

$\mathcal{O}(1)$

f (n, x)

$f(n,x)$

O (1 \circ 1) = O (1)

$\mathcal{O}(1\circ 1)=\mathcal{O}(1)$

g

$g$

O (1)

$O(1)$

ahh, ok ... sekarang semuanya masuk akal ... terima kasih atas klarifikasi ... Saya mungkin bingung oleh kenyataan bahwa kompleksitas rekursif tidak dipanggil secara rekursif ^^ (yang tidak terlalu celar dari definisi imo)

DFF