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

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.

Grantor dc:publisher

Università degli studi di Catania

Year dc:date

2022

Author dc:creator

• MAUGERI, PIETRO

Contributors dc:contributor

• CANTONE, Domenico

• Computable set theory, Satisifability problem, NP-completeness, Expressibility, Convex theory
• Computable set theory, Problema di soddisfacibilità, NP-completezza, Esprimibilità, Teorie convesse

Statement dc:rights

• info:eu-repo/semantics/openAccess
• license:PUBBLICO - Pubblico con Copyright
• license uri:iris.PUB02

Language dc:language

ita

Handle dc:identifier

https://hdl.handle.net/20.500.11769/581447

OAI identifier oai:identifier

oai:www.iris.unict.it:20.500.11769/581447