Access restricted to students and staff of home institution
master's thesis
34   3
Intractable problems
Branka Rajčić (2018)
University of Split
University of Split, Faculty of science
Department of Mathematics
Cite this document...

Rajčić, B. (2018). Teško rješivi problemi odluke (Master's thesis). Retrieved from https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, Branka. "Teško rješivi problemi odluke." Master's thesis, University of Split, University of Split, Faculty of science, 2018. https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, Branka. "Teško rješivi problemi odluke." Master's thesis, University of Split, University of Split, Faculty of science, 2018. https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, B. (2018). 'Teško rješivi problemi odluke', Master's thesis, University of Split, University of Split, Faculty of science, accessed 18 August 2019, https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić B. Teško rješivi problemi odluke [Master's thesis]. Split: University of Split, University of Split, Faculty of science; 2018 [cited 2019 August 18] Available at: https://urn.nsk.hr/urn:nbn:hr:166:530549

B. Rajčić, "Teško rješivi problemi odluke", Master's thesis, University of Split, University of Split, Faculty of science, Split, 2018. Available at: https://urn.nsk.hr/urn:nbn:hr:166:530549

Metadata
TitleTeško rješivi problemi odluke
Title (english)Intractable problems
AuthorBranka Rajčić
MentorMilica Klaričić Bakula (mentor)
Committee memberMilica Klaričić Bakula (predsjednik povjerenstva)
Committee memberJurica Perić (član povjerenstva)
Committee memberAljoša Šubašić (član povjerenstva)
GranterUniversity of Split
University of Split, Faculty of science
(Department of Mathematics)
Split
Defense date and country2018-11-06, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:166:530549
Study programmeTitle: Matematika; smjerovi: teorijski, računarski, nastavnički
Study programme type: sveučilišni
Study level: diplomski
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsRestricted access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
Created on2019-02-01 16:30:07