Contoh masalah di mana algoritma eksponensial berjalan lebih cepat daripada algoritma polinomial untuk ukuran praktis?

Apakah Anda mengetahui masalah apa pun (lebih disukai setidaknya agak terkenal), di mana, untuk ukuran masalah praktis , algoritma eksponensial berjalan jauh lebih cepat daripada rekan waktu polinomial yang paling terkenal.

Sebagai contoh, anggaplah suatu masalah memiliki ukuran praktis * dan ada dua algoritma yang dikenal: Satu adalah dan yang lainnya adalah untuk beberapa konstanta . Jelas untuk $n = 100$ $2^n$ $n^c$ $c$ , algoritma eksponensial lebih disukai. $c > 15$

* Saya kira ukuran praktis berarti sesuatu yang umum ditemukan di dunia nyata. Seperti jumlah kereta di jaringan.

time-complexity polynomial-time exp-time-algorithms Ozzah
sumber

Saya pikir Anda mungkin menemukan apa yang Anda cari dalam literatur kompleksitas parameter.

Kaveh

untuk algoritma linier umumnya ada pengganda konstan yang umumnya tidak signifikan dan sering dihilangkan dari kerumitan, tetapi yang saya ingat tampak sangat tinggi adalah penggabungan in-place yang linear, tetapi yang terburuk kira-kira seperti 5000 N ... jadi di skenario itu ada area yang dapat digunakan besar di mana N ^ 2 akan kurang dari 5000 N di mana ukurannya kurang dari sqrt (5000) dan domain yang lebih kecil di mana 2 ^ n masih akan lebih cepat di mana n kurang dari log 5000

Grady Player

Jawaban:

Bagaimana dengan algoritma simpleks untuk pemrograman linier? Dalam banyak kesempatan digunakan dalam praktik.

Diedit untuk menambahkan: Saya pikir ini lebih dari "algoritma eksponensial kasus buruk" yang berjalan secara efisien pada instance / distribusi praktis daripada berjalan lebih cepat pada instance ukuran praktis .

BPR
sumber

@diesalbla - tergantung pada forumaltion yang tepat. Mengutip Wikipedia, "pada tahun 1972, Klee dan Minty [32] memberikan contoh yang menunjukkan bahwa kompleksitas terburuk dari metode simpleks seperti yang dirumuskan oleh Dantzig adalah waktu eksponensial".

$O(n^3)$

Peter Shor
sumber

2^{2^{2^{2^{| H |}}}} \cdot O (n^{3})

$2^{2^{2^{2^{|H|}}}}\cdot O(n^3)$

H

$H$

O (n^{2})

$O(n^2)$

| H |

$|H|$

H

$H$

G

$G$

| H |

$|H|$

-3

Ada beberapa contoh dengan deteksi / pengujian primality (nonprobabilistic / tepat) . The AKS algoritma adalah algoritma pertama untuk primality pengujian terbukti di P. Ini tidak bersaing baik versus beberapa algoritma waktu eksponensial untuk input "kecil". Detailnya agak rumit karena menunjukkan hal ini pada umumnya membutuhkan implementasi algoritma yang merupakan latihan yang menantang dan dapat bergantung pada aspek implementasi spesifik.

Info lebih lanjut / detail / referensi tentang pertanyaan cs.se ini:

Kapan tes primitif AKS sebenarnya lebih cepat dari tes lain?

vzn
sumber

Sejauh yang saya ketahui, algoritma yang bersaing dengan AKS dalam praktiknya adalah polinomial acak (Miller-Rabin, ECPP) atau kuasipolinomial deterministik (Adleman-Pomerance-Rumeley). Tidak ada waktu dekat eksponensial.

Emil Jeřábek mendukung Monica

Versi acak Miller-Rabin, yang digunakan dalam praktik, tidak bergantung pada RH.

Emil Jeřábek mendukung Monica

Itu semua sangat benar, tetapi tidak ada hubungannya dengan pertanyaan aslinya.

Emil Jeřábek mendukung Monica

Ya, saya tahu semua itu. Dan untuk ketiga kalinya, ini tidak relevan. Pertanyaannya menanyakan algoritma waktu-eksponensial yang dalam praktiknya bersaing dengan algoritma waktu-polinomial yang dikenal (di sini, AKS). Satu-satunya algoritma pengujian primitif eksponensial-waktu yang digunakan dalam praktik adalah pembagian percobaan, yang tidak kompetitif untuk jumlah ukuran nontrivial. Algoritme kompetitif yang digunakan dalam praktik jauh lebih efisien daripada eksponensial, meskipun tidak polinomial (atau deterministik, atau tanpa syarat).

Emil Jeřábek mendukung Monica

Apa yang dimaksud dengan apel dan jeruk adalah membandingkan AKS (algoritma pengujian primality) dengan GNFS (algoritma anjak piutang).

Emil Jeřábek mendukung Monica