A complete complexity taxonomy of ‘small’ fragments of theory Multi-Level Syllogistic

The research field of Computable set theory was born in the 1970's with a long-term project to combine computer science and set theory. At an early stage this project was centered on the issue of software prototyping, but the goals of this project shifted towards more theoretic results rooted in the fields of logic and computability. Set-theoretic languages consist in unquantified formulae comprising variables, that will be interpreted as sets, and operations and predicates between sets. Every set-theoretic language is identified by the predicates and operators it comprises, and can be seen as sub-languages, or fragments, of a more generalized set theory comprising all possible operators and predicates. A foundational quest spawned naturally inside the field of Computable Set theory, namely the quest of studying the decidability of all the fragments of Set theory in order to find the boundaries between the decidable and undecidable. This study revolved around one particular sub-language of set theory called Multi-Level Syllogistic, MLS for short, which comprises the operations and predicates that are considered a common core of set theory. Recently a new quest similar to that of finding the boundaries between decidable and undecidable fragments arose in the field of Computable Set theory. The new goal is to study all the small fragments in order to find sub-languages endowed with a deterministic polynomial time decision procedure. In this dissertation we present an in-depth study of the fragments of MLS highlighting a clear boundary between polynomial time satisfiable fragments and NP-complete fragments.

Il campo di ricerca denominato Computable set theory nacque negli anni 70 con un progetto a lungo termine volto a combinare informatica e teoria degli insiemi. In una fase iniziale il progetto era incentrato a trovare nuove forme di prototipazione software, ma gli obbiettivi di tale progetto cambiarono alla ricerca di risultati più teorici con radici nei campi della logica e della computabilità. Un linguaggio nella teoria degli insiemi consiste in formule non quantificate contenenti variabili, che saranno interpretate come insiemi, e operatori e predicati insiemistici. Ogni linguaggio nella teoria degli insiemi è identificato dagli operatori e predicati che lo compongono e può essere visto come sotto-linguaggio, o frammento, di un più generico linguaggio della teoria degli insiemi contenente ogni possibile operatore e predicato. Questo studio generò, in maniera naturale, un bisogno fondazionale, ovvero la necessità di studiare la decidibilità di tutti i frammenti della teoria degli insiemi così da trovare il confine tra decidibile e non decidibile. Questo studio ebbe come fulcro un preciso sotto-linguaggio chiamato Multy-Level Syllogistic, abbreviato in MLS, che contiene gli operatori e predicati insiemistici considerati più comuni.In tempi recenti la Computable set theory ha accolto un nuovo studio, simile al precedente incentrato al trovare il confine tra decidibile e non decidibile. Il nuovo obbiettivo è quello di studiare tutti i piccoli frammenti in cerca di quei sotto-linguaggi la cui procedura di decisione possa essere completate in tempo deterministico polinomiale. In questa tesi presenteremo uno studio approfondito di tutti i frammenti di MLS evidenziando il confine tra frammenti soddisfacibili in tempo polinomiale e frammenti NP-completi.