KELAS KOMPLEKSITAS DAN STRUKTUR ALJABAR PADA MASALAH KOMBINATORIAL

DEA MAULIDYA, Dr. Aluysius Sutjijana, M.Sc.

2018 | Skripsi | S1 MATEMATIKA

Pada tugas akhir ini, akan dibahas mengenai kompleksitas dari suatu algoritma, masalah satisfaction dan struktur aljabar pada masalah kombinatorial. Hal yang dibahas mengenai kompleksitas algoritma meliputi definisi, contoh, sifat, serta pengelompokkan dari kompleksitas. Pada masalah satisfaction akan dibahas mengenai definisi, contoh, operasi, dan sifat-sifat mengenai masalah satisfaction. Sementara itu, dalam pembahasan struktur aljabar pada masalah kombinatorial akan dideskripsikan suatu formula aljabar umum untuk suatu jangkauan yang luas mengenai masalah kombinatorial termasuk satisfiability, pewarnaan graf dan isomorfisma graf. Pada formula ini, setiap kasus dari masalah direpresentasikan oleh pasangan struktur relasi, dan solusi dari kasus yang diberikan merupakan homomorfisma antara struktur relasi tersebut. Masalah keputusan yang sesuai memutuskan ada atau tidaknya homomorfisma semacam itu. Selanjutnya, didemonstrasikan bahwa kompleksitas dalam menyelesaikan masalah keputusan ini ditentukan dalam banyak kasus oleh sifat aljabar sederhana dari struktur relasi yang terlibat. Hasil ini digunakan untuk mengidentifikasi sub masalah yang tractable dari satisfiability, dan untuk menyediakan suatu tes sederhana untuk menetapkan relasi Boolean yang diberikan sesuai dengan salah satu sub masalah tractable tersebut atau tidak.

In this final project, we discuss the complexity of algorithm, the satisfaction problem, and the algebraic structure of combinatorial problems. For the complexity of algorithm and satisfaction problems we discuss the definition, examples, grouping, and their properties. For the satisfaction problems we discuss the definition, examples, operations, and their properties.For the algebraic structure of combinatorial problems we describe a general algebraic formulation for a wide range of combinatorial problem including satisfiability, graph colorability and graph isomorphism. In this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. This result is used to identify tractable subproblems of satisfiability, and to provide a simple test to establish whether a given set of Boolean relations gives rise to one of these tractable subproblems.

Kata Kunci : Kompleksitas, Satisfability, Struktur Relasi, Closure, Homomorfisma