Pencarian biner

Seandainya kita tidak mengetahui sebuah jangkauan yang tetap tempat dari bilangan "k"berada, kita masih dapat menentukan nilainya dengan mengajukan formula_4 pertanyaan ya/tidak dalam bentuk "Apakah "k" lebih besar dari "x"?" untuk beberapa bilangan "x". Sebagai konsekuensi sederhana dari cara ini, jika kita dapat menjawab pertanyaan "Apakah nilai bilangan bulat "k" lebih besar dari nilai yang diberikan?" pada suatu waktu kemudian kita dapat menemukan nilai dari bilangan tersebut sama lamanya ditambah dengan faktor log "k". Hal ini disebut sebuah "reduksi", dan karena disebabkan reduksi ini maka kebanyakan teoris kompleksitas berkonsentrasi pada permasalahan keputusan, algoritme-algoritme yang mengasihlan jawaban sederhana berupa ya/tidak.