Masalah keputusan vs fungsi

Teori kompleksitas tampaknya dibangun di sekitar masalah keputusan daripada fungsi.

Siapa yang memperkenalkan ini terlebih dahulu dan apa alasan pilihan ini?

Misalnya, kertas "Jalur, pohon, dan bunga" Edmond umumnya dikreditkan sebagai sumber gagasan mewakili sekumpulan masalah "yang dapat ditelusuri" dan ini adalah jalan yang telah kita ambil.$\mathsf{PTime}$

Alasan lain adalah bahwa ini sering tanpa kehilangan sifat umum, karena sering (meskipun tidak selalu - lihat di bawah) kompleksitas fungsi dan masalah keputusan adalah setara. Setiap masalah keputusan dapat dilihat sebagai fungsi yang nilainya hanya 0 dan 1. Sebaliknya, mengingat fungsi , ada beberapa masalah keputusan terkait yang biasanya memiliki kompleksitas yang sama dengan f , misalnya:$f$$f$

• yang saya sedikit -th f ( x ) adalah 1 } .$\{(x,i) :$$i$$f(x)$$\}$
• $\{(x,k) : f(x) \leq k\}$$\geq$

$\mathsf{P}^{\mathsf{NP}[\log ]} = \mathsf{P}^{\mathsf{NP}}_{tt}$$\mathsf{FP}^{\mathsf{NP}[\log ]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$$\mathsf{NP} = \mathsf{RP}$$\mathsf{P} = \mathsf{UP}$Selman 1994 ].

$^{\mathsf{NP}[\log]}$$O(\log n)$$\mathsf{NP}$$\mathsf{P}^{\mathsf{NP}}_{tt}$$\mathsf{P}$$\mathsf{NP}$$x$$y_i$$i$$y_i$$x$$y_1, \dotsc, y_m$$y_i$

Teori kompleksitas dibangun dari teori komputabilitas, dan rumusan khas masalah dalam teori komputabilitas adalah sebagai masalah keputusan, yang muncul secara alami dari pengaturannya sebagai pertanyaan tentang menetapkan keanggotaan.

Akar teori komputasi kembali ke belakang, tetapi jika Anda ingin contoh kuat pertama dari Masalah Keputusan, maka Entscheidungsproblem Hilbert adalah contoh Anda - itu adalah bahasa Jerman untuk "Masalah Keputusan".

Sepotong cerita saja:

Makalah seminal tahun 1963 dari Hartmanis dan Stearns, "On Computational Complexity of Algorithms" memperkenalkan definisi kompleksitas waktu dan ruang yang diukur pada model mesin Turing multitape dan menunjukkan bahwa dengan memberikan lebih banyak ruang / waktu TM dapat menghitung lebih banyak hal.

... Kompleksitas komputasi dari suatu urutan harus diukur dengan seberapa cepat mesin Turing multitape dapat mencetak ketentuan dari urutan tersebut. ...

Di mana "urutan" adalah urutan umum. Kemudian, ketika mendefinisikan urutan T-computable , mereka membatasi perhatian pada urutan biner:

$\alpha = a_1 a_2 ...$

$S_T$$T(n)$$S_T$

Dan kemudian di Konsekuensi 2.8:

$n$

Dengan tautan terbelakang ke Hilbert dan karya Church / Turing tentang masalah penghentian:

$T$$\alpha$$S_T$