ScholarLens Back to search
2018•Unpublished venueRequires access

Teško rješivi problemi odluke

Branka Rajčić

Open publisher page 0 citations

Abstract

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.

About this research paper

What this paper is about

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.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

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.

Key concepts: P versus NP problem, NP, Boolean satisfiability problem, NP-complete, Mathematics, Completeness (order theory), Combinatorics, Turing machine

Back to paper searchBrowse research topicsOriginal source
Teško rješivi problemi odluke — Research Paper | ScholarLens