Teori kompleksitas ketika oracle merupakan bagian dari input

Cara paling umum di mana nubuat muncul dalam teori kompleksitas adalah sebagai berikut: Sebuah nubuat tetap tersedia untuk, katakanlah, mesin Turing dengan sumber daya terbatas tertentu, dan seseorang mempelajari bagaimana oracle meningkatkan daya komputasi mesin.

Namun, ada cara lain di mana nubuat kadang-kadang terjadi: sebagai bagian dari input . Sebagai contoh, misalkan saya ingin mempelajari algoritma untuk menghitung volume polytope dimensi tinggi yang diberikan. Secara klasik, polytope perlu ditentukan dengan memberikan daftar sisi-sisinya atau representasi eksplisit lainnya. Namun, kami juga dapat menimbulkan masalah menghitung volume polytope yang ditentukan oleh a oracle volume, yang mengambil koordinat titik dalam ruang sebagai input dan output "ya" jika dan hanya jika titik yang diberikan terletak di dalam polytope. Kemudian kita dapat bertanya sumber daya komputasi apa yang diperlukan untuk menghitung volume polytope yang ditentukan dengan cara ini. Dalam kasus khusus ini kami memiliki skema perkiraan waktu polinomial yang sangat bagus dari Dyer, Frieze, dan Kannan dan, yang menarik dari sudut pandang teori kompleksitas, bukti bahwa keacakan membantu dengan cara yang esensial untuk masalah ini, dalam hal itu tidak ada algoritma deterministik yang dapat melakukan serta algoritma Dyer-Frieze-Kannan.

Apakah ada cara sistematis untuk mempelajari teori kompleksitas masalah di mana nubuat disediakan sebagai bagian dari input? Apakah itu entah bagaimana direduksi menjadi teori kompleksitas kelas yang biasa dengan nubuat? Dugaan saya tidak, dan itu karena ada terlalu banyak cara yang berbeda yang dapat diberikan oleh oracle sebagai bagian dari input, setiap masalah seperti ini harus ditangani secara ad hoc. Namun, saya akan senang terbukti salah pada titik ini.

Ini disebut Teori Kompleksitas Tipe-2. Ada sebuah makalah karya Cook, Impagliazzo dan Yamakami yang mengaitkannya dengan teori oracle generik.

Ini pasti jauh dari jawaban yang lengkap, tetapi mudah-mudahan ini menunjuk ke beberapa tempat untuk dilihat.

Masalah di mana bagian dari input diberikan sebagai oracle kadang-kadang disebut masalah dengan input implisit . Ini adalah model yang mudah digunakan misalnya ketika mempelajari bukti yang dapat diperiksa secara probabilistik .

Bidang studi penting tentang masalah dengan input implisit adalah teori kompleksitas kueri , di mana kompleksitas diukur semata-mata oleh jumlah query ke oracle input, mengabaikan jumlah perhitungan antara permintaan. Banyak kelas kompleksitas memiliki rekan-rekan mereka dalam kompleksitas kueri, dan pemisahan antara kelas kompleksitas dalam kompleksitas kueri sering menyiratkan pemisahan oracle antara kelas yang sesuai dalam kompleksitas komputasi.

Saya tidak tahu studi tentang kelas kompleksitas masalah dengan input implisit (bukan masalah individu) memperhitungkan biaya perhitungan, tetapi mungkin beberapa orang tahu.

Model di mana input disediakan sebagai oracle dipelajari dalam teori komputabilitas dan analisis yang dapat dihitung. Salah satu model yang sepertinya dekat dengan yang Anda inginkan adalah model TTE (Tipe Dua Efektivitas). Referensi yang bagus untuk itu adalah buku Klaus Weihrauch " Analisis Komputasi ". Dia juga secara singkat berbicara tentang kompleksitas dalam bab 7.

Buku Ker-I Ko " Kompleksitas Komputasi Fungsi Nyata " membahas model lain akses ke oracle yang tampaknya lebih cocok untuk kompleksitas. Masalah-masalah tentang representasi objek tipe yang lebih tinggi dan metode untuk mengakses oracle adalah masalah yang rumit. Lihat misalnya karya Stephen A. Cook dan Akitoshi Kawamura baru-baru ini " Teori Kompleksitas untuk Operator dalam Analisis " dari STOC 2010 dan tesis PhD-nya . Salah satu masalah utama adalah bahwa untuk membuat model masuk akal kita perlu memberi mesin cukup waktu untuk memproses jawaban dari oracle (jika tidak kita bahkan tidak dapat menghitung operator aplikasi). Untuk waktu polinomial dan ruang polinomial dapat dilakukan menggunakan polinomial orde tinggi berdasarkan Stephen A. Cook dan Bruce M. Kapron 'Karakterisasi baru kelayakan tipe-2 "FOCS 1991 dan" Karakterisasi fungsional layak dasar tipe terbatas "STOC 1989.