Algoritma yang efisien secara konstruktif tanpa kebenaran yang efisien dan bukti efisiensi

Saya mencari contoh alami dari algoritma yang efisien (yaitu dalam waktu polinomial) st

kebenaran dan efisiensi mereka dapat dibuktikan secara konstruktif (misalnya di $PRA$ atau ), tetapi $HA$
tidak ada bukti menggunakan hanya konsep efisien yang diketahui (yaitu kita tidak tahu bagaimana membuktikan kebenaran dan efisiensinya di atau ). $TV^0$ $S^1_2$

Saya bisa membuat contoh buatan sendiri. Namun saya ingin contoh alami yang menarik, yaitu algoritma yang dipelajari untuk kepentingan mereka sendiri, tidak dibuat hanya untuk menjawab pertanyaan jenis ini.

cc.complexity-theory reference-request lo.logic proof-complexity constructive-mathematics Kaveh
sumber

Mungkin sesuatu dari teori automata, di mana algoritma itu mudah, tetapi untuk menunjukkannya berhasil, kita perlu mempertimbangkan semua himpunan bagian dari sesuatu atau yang lain?

Andrej Bauer

Bagaimana dengan pemeriksaan keutamaan waktu polinomial? Bukti itu sepertinya cukup rumit sehingga sulit menempel di dalam

S_{2}^{1}

$S^1_2$

Andrej Bauer

@Neel, sebenarnya tesis Emil " Prinsip dasar lubang lemah, dan perhitungan acak " adalah tentang memformalkan algoritma probabilistik. Aksioma utama yang diperlukan untuk memformalkan beberapa di antaranya tampaknya merupakan penghitungan perkiraan yang bukan bagian dari

atau

. Saya pikir mungkin lebih mudah untuk tetap menggunakan kasus polytime deterministik dengan

dan

T V^{0}

$TV^0$

S_{2}^{1}

$S^1_2$

T V^{0}

$TV^0$

S_{2}^{1}

$S^1_2$

Kaveh

ps: Akan lebih menarik jika kita dapat membuktikan bahwa kebenaran / efisiensi algoritma tidak dapat dibuktikan dalam teori-teori ini, atau setidaknya setara dengan pernyataan yang diyakini tidak dapat dibuktikan di dalamnya. Namun meminta itu mungkin terlalu banyak dengan apa yang kita ketahui saat ini.

Kaveh

@Neel, sebagian besar probabilitas yang relevan dapat dilakukan dalam sistem urutan pertama karena Anda tidak pernah benar-benar perlu mengetahui probabilitas pasti suatu peristiwa, Anda biasanya hanya perlu membandingkan probabilitas itu dengan angka-angka rasional tertentu.

François G. Dorais

Jawaban:

Ini adalah ide yang sama dengan jawaban Andrej tetapi dengan lebih detail.

Krajicek dan Pudlak [ LNCS 960, 1995, hlm. 210-220 ] telah menunjukkan bahwa jika adalah properti yang mendefinisikan bilangan prima dalam model standar dan $P(x)$ $\Sigma^b_1$

S_{2}^{1} ⊢ \neg P (x) \to (\exists y_{1}, y_{2}) (1 < y_{1}, y_{2} < x \land x = y_{1} y_{2})

$S^1_2 \vdash \lnot P(x) \to (\exists y_1,y_2)(1 < y_1, y_2 < x \land x = y_1y_2)$ kemudian ada algoritma anjak polinomial waktu. Ini memberikan banyak contoh karena setiap algoritma NP untuk pengujian primality pada dasarnya menghasilkan formula

. Secara khusus, tes primitif AKS memberikan formula seperti itu (bila disusun ulang dengan tepat dalam bahasa

). Makalah oleh Krajicek dan Pudlak memberikan lebih banyak contoh terkait kriptografi dari jenis ini tetapi mendahului AKS dan kemajuan terkait beberapa tahun.

Σ_{1}^{b}

$\Sigma^b_1$

S_{2}^{1}

$S^1_2$

François G. Dorais
sumber

$\mathrm{TC}^0$ $\mathit{VTC}^0$

$\mathit{TV}^0$ $\mathit{VTC}^0$ $\mathrm{TC}^0$

$\left(\frac an\right)$

$p$ $\left(\frac ap\right)=1$ $a$ $p$

$S^1_2$

Kelas contoh lain diberikan oleh pengujian irreducibilitas dan algoritma faktorisasi untuk polinomial (terutama di atas bidang terbatas dan atas rasional). Ini selalu bergantung pada teorema kecil Fermat atau generalisasi (antara lain), dan dengan demikian tidak diketahui dapat diformalkan dalam teori aritmatika terbatas yang sesuai. Biasanya, algoritma ini diacak, tetapi untuk contoh waktu polinomial deterministik, seseorang dapat mengambil uji irreducibilitas Rabin atau algoritma akar kuadrat Tonelli-Shanks (diformulasikan sehingga nonresid kuadrat diperlukan sebagai bagian dari input).

Emil Jeřábek mendukung Monica
sumber

The tes AKS primality tampaknya seperti kandidat yang baik jika Wikipedia adalah bisa dipercaya.

Namun, saya berharap contoh seperti itu sulit ditemukan. Bukti yang ada akan diutarakan sehingga mereka jelas tidak dilakukan dalam aritmatika terbatas, tetapi mereka kemungkinan akan "beradaptasi" dengan aritmatika terikat dengan lebih atau kurang usaha (biasanya lebih).

Andrej Bauer
sumber

S_{2}^{1}

$S^1_2$

S_{2}^{1}

$S^1_2$

S_{2}^{1}

$S^1_2$

Ada sebuah makalah yang luar biasa dari Krajicek dan Pudlak yang memberikan lebih banyak contoh: karlin.mff.cuni.cz/~krajicek/j-crypto.ps

François G. Dorais

@ François, mengapa tidak mengirim jawaban? :)

Kaveh

Jadi, saya mendapat hitungan upvote tertinggi untuk membuat perkiraan keberuntungan awal, sementara yang lain benar-benar tahu apa yang sedang terjadi. Matematika seperti MTV.

Andrej Bauer