Michaela Borzechowski

The complexity class Polynomial Local Search (PLS) and PLS-complete problems

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 25.10.2016


The complexity classes P and NP are well known. However we are often interested in the actual globally optimal solutions of some NP decision problems. Local search is an attempt to approximate a hard to find global optimum with a local optimum. The complexity class Polynomial Local Search (PLS) was introduced to analyze the complexity of local search algorithms, where it is verifiable in polynomial time, whether a solution is a local optimum or not. One can PLS-reduce local search problems to one another and establish PLS-completeness. This work presents the basic definitions of the class PLS, its relation to other complexity classes, PLS-reductions, PLS-completeness, as well as a list of PLS-complete problems. The aim is to give a general overview of this topic and make further proofs for PLS-completeness and further investigations of the characteristics of the class PLS easier.