WikiSysop: Bot: Automatski unos stranica

2021-08-22T05:47:55Z

Bot: Automatski unos stranica

Nova stranica

U [[računska teorija složenosti|računskoj teoriji složenosti]], '''funkcijski problem''' je problem različit od [[problem odluke|problema odluke]], to jest, problem koji zahtijeva složeniji odgovor od pukog da/ne.

Istaknuti primjeri uključuju [[problem trgovačkog putnika]], koji pita za put koji putnik treba obaviti, te problem [[cjelobrojna faktorizacija|cjelobrojne faktorizacije]], koji pita za listu prostih faktora.

Funkcijski problemi su čudniji za proučavanje od problema odluke jer nemaju očitog analogona u terminima jezika, te i stoga jer je notacija svođenja među problemima suptilnija s obzirom da se treba transformirati i ulaz i izlaz.

Funkcijski problemi mogu biti razvrsatni u [[klasa složenosti|klase složenosti]] na isti način kao i problemi odluke. Na primjer, [[FP (složenost)|FP]] je skup svih funkcijskih problema koji mogu biti riješeni [[deterministički Turingov stroj|determinističkim Turingovim strojem]] u [[polinomno vrijeme|polinomnom vremenu]], a [[FNP (složenost)|FNP]] je skup svih funkcijskih problema koji mogu biti riješeni [[nedeterministički Turingov stroj|nedeterminističkim Turingovim strojem]] u [[polinomno vrijeme|polinomnom vremenu]].

Za sve funkcije za koje su rješenja polinomski ograničena, postoji analogan problem odluke takav da funkcijski problem može biti riješen [[vremenski polinomno svođenje|vremenski polinomnim Turingovim svođenjem]] na problem odluke. Na primjer, problem odluke analogan problemu trgovačkog putnika je sljedeći:

:Za dani težinski [[usmjereni graf]] i cijeli broj K, postoji li [[Hamiltonovski put]] (ili [[Hamiltonovski ciklus]] ukoliko je u uvjetima zadatka specificirano da se putnik vraća kući) sa ukupnom težinom manjom ili jednakom K?

Za dano rješenje ovoga problema, problem se trgovačkog putnika može riješiti na sljedeći način. Neka je <math>n</math> broj bridova i <math>w_i</math> težina brida <math>i</math>. Neka se reskaliraju i perturbiraju težine bridova dodjelom bridu <math>i</math> nove težine <math>w'_i = 2^{(n+1)} w_i + 2^i</math>. Ovo ne mijenja najkraći Hamiltonovski put, ali osigurava njegovu jedinstvenost. Sad se zbroje sve težine svih bridova kako bi se dobila ukupna težina <math>M</math>. [[Binarno pretraživanje|Binarnim pretraživanjem]] se traži najkraći Hamiltonovski put: postoji li Hamiltonovski put sa težinom <math>< M/2</math>; postoji li put sa težinom <math>< M/4</math> itd. Potom, određujući težinu <math>W</math> najkraćeg Hamiltonovskog puta, određuje se koji su bridovi na putu pitajući svaki brid <math>i</math> postoji li Hamiltonovski put sa težinom <math>W</math> za graf izmjenjen na način da brid <math>i</math> ima težinu <math>W+1</math> (ako ne postoji takav put u izmjenjenom grafu, tada brid <math>i</math> mora biti na najkraćem putu izvornog grafa).

Ovo smješta problem trgovačkog putnika u klasu složenosti FP <sup>NP</sup> (klasa funkcijskih problema koji mogu biti riješeni u polinomnom vremenu na determinističkom Turingovom stroju sa [[stroj proročište|proročištem]] za problem u NP), i ustvari je potpun za tu klasu.
[[Kategorija:Računska teorija složenosti]]

Funkcijski problem - Povijest promjena

WikiSysop: Bot: Automatski unos stranica