Decidoproblemo: Malsamoj inter versioj

Ekzemple, la problemo “donite du numeroj ''x'' kaj ''y,'' ĉu ''x'' divizoras ''y''?” estas decidoproblemo. La respondo povas esti aŭ ‘jes’ aŭ ‘ne,’ kaj dependas sur la valoroj de ''x'' kaj ''y''. Solvadmetodo por decidoproblemo, donita en [[algoritma|algoritmo|algoritma]] formo, nomiĝas '''decidoprocedo''' por tiu problemo. Decidoprocedo por la decidoproblemo “donite du numeroj ''x'' kaj ''y,'' ĉu ''x'' divizoras ''y''?” donas la manipuloj kiuj determinas ĉu ''x'' divizoras ''y'', donite ''x'' kaj ''y''. Unu tia algoritmo estas [[longa dividado]], kiu ĉiuj lernantoj devas lerni. Se la cetero estas nulo, la respondo estas 'jes'; alie, ĝi estas 'ne'. Decidoproblemo kiu solveblas per algoritmo, kiel ĉi tiu ekzemplo, nomiĝas ''decidebla''.

La fako de komputa kompliko kategoriigas decideblajn decidoproblemojn laŭ kiel malfacile ili solvendas. "Malfacila", en tiu senco, priskribiĝas laŭ la komputaj rimedoj, kiuj la plej efika algoritmo bezonas por iu problemo. La fako de [[teorio de komputeblo|rikurteorio]], dume, kategoriigas nedecideblajn decidoproblemojn laŭ [[turinga grado]], kiu estas mezuro de la nekomputeblo de ajna solvo. Decidoproblemoj proksime rilatas al [[funkcioproblemo]]j, kiuj povas havi respondojn pli kompleksajn ol simpla "jes" aŭ "ne". Ekvivalenta funkcioproblemo estas "donite du numeroj ''x'' kaj ''y,'' kio estas ''x'' dividita per ''y''?" Ili ankaŭ rilatas al [[problemo de optimumigo|problemoj de optimumigo]], kiuj temas pri trovado de la ''plej bona'' respondo al specifa problemo.