Decidoproblemo

Ĉi tiu artikolo temas pri la decidoproblemojn en komplikteorio. Por informoj pri la decidoproblemo en formala logiko ("Entscheidungsproblem"), vidu la artikolon Decidoproblemo (logiko).

En teorio de komputeblo kaj de komputa kompliko, decidoproblemo estas demando en iu formala sistemo kun jes-aŭ-ne respondo, depende de la valoroj de kelkaj enigaj parametroj. Decidoproblemoj tipe prezentiĝas en matematikaj demandoj de decideblo, t.e., la demando pri la ekzisto de efika metodo determini la ekziston de iu objekto aŭ ĝian membrecon en aro; kelkaj el la plej gravaj problemoj en matematiko estas nedecideblaj.

Prezentaĵo de decidoproblemo, kiu havas nur du eblajn eligojn, jes aŭ ne (aŭ alterne 1 aŭ 0) sur iu enigo.

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 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 rikurteorio, dume, kategoriigas nedecideblajn decidoproblemojn laŭ turinga grado, kiu estas mezuro de la nekomputeblo de ajna solvo. Decidoproblemoj proksime rilatas al funkcioproblemoj, 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 problemoj de optimumigo, kiuj temas pri trovado de la plej bona respondo al specifa problemo. Ekzistas normaj teknikoj transformi funkcioproblemojn kaj problemojn de optimumigo en decidoproblemojn, kaj inverse, kiuj ne signife ŝanĝi la komputan malfacilaĵon de ĉi tiuj problemoj. Por tiu kialo, esploro en teorio de komputeblo kaj komplikteorio tipe centras sur decidoproblemojn.

Difino

Decidoproblemo estas ajna arbitra jes-aŭ-ne demando sur malfinia aro de enigoj. Pro ĉi tio, tradicie oni egalvalore difinas la decidoproblemon kiel la aro de enigoj por kiu la problemo revenigas jes.

Tiuj enigoj eblas esti naturaj nombroj aŭ valoroj de iu alia speco, kiel ĉenoj super la duuma alfabeto {0,1} aŭ super iu alia finia simbolaro. La subaro de ĉenoj aŭ signovicoj por kiu la problemo revenigas "jes" estas formala lingvo, kaj ofte decidoproblemoj difiniĝas tiamaniere kiel formalaj lingvoj.

Alikaze, per kodigo kiel godela numerado, iu ajn ĉeno povas kodiĝi kiel natura nombro, per kiu decidoproblemo difineblas kiel subaro de la naturaj nombroj.