|
|
Monadic NP sets
Putzer, Martin ; Krajíček, Jan (advisor) ; Honzík, Radek (referee)
Generalised spectra, id est classes finitely axiomatisable in existential second-order logic restricted to finite structures, are known by Fagin's theorem to coincide with members of the complexity class NP. Thereby, the problem of NP being closed under complementation reduces to the problem whether every class of finite struc- tures complementary to a generalised spectrum is, too, a generalised spectrum. Provided P ̸= NP, a proof thereof could then possibly be based on finding a par- ticular generalised spectrum (thereby an NP class) whose complement, while in coNP would not be in NP. Pursuits of such a proof, too, however, have been to no avail. A partial resolution of this problem (itself a special case to so called Asser's problem) is Fagin-Hájek theorem, claiming that a subclass of NP, the class of so called monadic NP sets is not closed under complementation. Reproduc- ing Fagin's original proof of the theorem is the aim of this thesis, along with introducing the reader to all preliminary apparatus needed for the proof. 1
|
guest ::
