Intractable problems

U ovom diplomskom radu proučavamo teško rješive probleme odluke. Bavimo se dvjema klasama problema, a to su problemi koji su odlučivi nekim polinomno složenim determinističkim Turingovim strojem (klasa P) i problemi za koje nije poznat deterministički polinomni algoritam (klasa NP). Također bavimo se i NP-potpunim problemima odluke. Uveden je problem ispunjivosti formule logike sudova te je dokazana NP-potpunost tog problema odluke na način da smo jezik bilo kojeg nedeterminističkog Turingovog stroja polinomne vremenske složenosti reducirali na problem ispunjivosti. Budući da se formula logike sudova može zapisati u k-konjunktivnoj normalnoj formi (k ∈N), nameću nam se dva problema odluke CSAT i 3SAT. NP-potpunost navedenih problema odluke potvrdili smo redukcijom instanici SAT problema na instance navedenih problema. Nadalje, razmatrali smo NP-potpunost nekih dodatnih problema odluke (IS, Problem klike, NC, DHC, HC i TSP) i zaključili da se i ti problemi polinomnom redukcijom s nekog drugog NP-potpunog problema potvrđuju kao NP-potpuni problemi odluke.This thesis studies the intractable problems. It deals with two classes of problems solvable in polynomial time by a deterministic Turing machine (class P) and those in which the deterministic polynomial algorithm is not known (class NP). Furthermore, it deals with NP-complete problems. The satisfiability problem has been introduced and its NP-completeness has been proved in a way that the language of any nondeterministic Turing machine solvable in polynomial time has been reduced to a satisfiability problem. Since the Boolean expression can be written in the conjuctive normal form (k ∈ N), two problems emerge CSAT and 3SAT. NP-completeness of the above stated problems has been confirmed by reduction of the SAT problem instances to the instances of the forementioned problems. Furthermore, NP-completeness of some additional intractable problems has been looked into (IS, Clique, NC, DHC, HC i TSP) and the conclusion has been drawn that those problems can be confirmed as NP-complete problems by polynomial reduction from another NP-complete problem