Algoritma polytime dan polyspace untuk menentukan persimpangan terkemuka fungsi monotonik diskrit

Beberapa frontmatter: Saya seorang ilmuwan komputer rekreasi dan insinyur perangkat lunak yang dipekerjakan. Jadi, maafkan jika prompt ini tampaknya agak keluar dari bidang kiri - saya secara rutin bermain dengan simulcra matematika dan membuka masalah ketika saya tidak punya yang lebih baik untuk dilakukan.

Saat bermain dengan hipotesis Riemann , saya menentukan bahwa celah utama dapat direduksi menjadi hubungan perulangan berdasarkan perpotongan semua fungsi komplementer dibentuk oleh kelipatan dari setiap bilangan prima sebelumnya (pengamat yang tajam akan mencatat ini adalah generalisasi dari yang Saringan Eratosthenes ). Jika ini sama sekali tidak masuk akal bagi Anda, jangan khawatir - itu masih lebih baru.$n-1$

Melihat bagaimana fungsi-fungsi ini berhubungan, saya menyadari bahwa instance berikutnya dari setiap prime dapat dikurangi menjadi persimpangan pertama dari fungsi-fungsi ini, berulang terus ke depan tanpa batas. Namun, saya tidak dapat menentukan apakah ini dapat ditelusuri dalam polytime dan polyspace. Jadi: yang saya cari adalah algoritma yang dapat menentukan persimpangan pertama fungsi diskrit (dan, jika berlaku, monotonik) dalam ruang dan waktu polinomial. Jika tidak ada algoritma yang saat ini ada atau dapat ada, bukti singkat atau referensi yang menyatakan itu sudah cukup.$n$

Yang paling dekat yang dapat saya temukan sejauh ini adalah algoritma proyeksi Dykstra (ya, itu RL Dykstra, bukan Edsger Dijkstra ), yang saya yakini mereduksi dirinya menjadi masalah pemrograman integer dan, karenanya, NP-hard. Demikian pula, jika seseorang melakukan persimpangan set transitif dari semua titik yang berlaku (karena mereka saat ini dipahami terikat), kita masih harus membatasi diri kita pada ruang eksponensial untuk pengulangan kita karena batas lemah saat ini bilangan prima untuk setiap nyata (dan karena itu, ruang untuk setiap prime ).$\ln(m)$$m$$e^n$$n$

Secara global, saya bertanya-tanya apakah pemahaman saya tentang pengurangan masalah itu salah. Saya tidak berharap untuk menyelesaikan hipotesis Riemann (atau masalah mendalam dan terbuka di ruang ini) dalam waktu dekat. Sebaliknya, saya ingin belajar lebih banyak tentang hal itu dengan bermain dengan masalah, dan saya mendapat masalah dalam penelitian saya.

Menentukan apakah dua fungsi monoton yang diberikan sebagai program berpotongan tidak dapat dihitung. Demikian pula, menentukan persimpangan pertama di bawah janji bahwa itu ada "sewenang-wenang sulit" (pasti bukan polytime).

Diberikan program , tentukan fungsi yang, untuk input , adalah jika berhenti setelah langkah atau kurang. Perpotongan pertama dari dan fungsi konstan adalah waktu berjalan , jika berhenti. Jadi tidak ada program yang dapat memutuskan apakah dan berpotongan.$P$$f_P$$n$$1$$P$$n$$f_P$$1$$P$$P$$f_P$$1$

Demikian pula, teorema hierarki waktu menunjukkan bahwa untuk tanpa waktu rekursif terikat , titik persimpangan pertama dapat ditemukan dalam waktu , bahkan di bawah janji bahwa itu ada. Menggunakan teorema hierarki ruang, Anda bisa mendapatkan yang sama untuk ruang.$T$$T$