Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-57694
URL: http://www.freidok.uni-freiburg.de/volltexte/5769/


Montoya, Juan Andres

On parameterized counting

Über parametrisierte Anzählen Probleme

Dokument1.pdf (428 KB) (md5sum: 164a26d2147289957334c2878a928984)

Kurzfassung in Englisch

In this dissertation we have tried to analyze the intrinsic hardness of parameterized counting problems. We have analyzed the parameterized complexity of #W(P)-complete problems. We proved that, (under some complexity theoretic hypothesis):
1. Any #W(P)-complete is harder than any problem in the A hierarchy.
2. Any parameterized #W(P)-complete problem can be approximated in fpt time, if oracle access to an W(P)-complete problem is provided.
Therefore we can calim that, on the one side parameterized exact counting is very hard, since its intractability degree is lowerbounded by w. On the other side, parameterized approximate counting has a intractability degree upperbounded by 2.


Kurzfassung in Deutsch

In dieser Doktorarbeit haben wir die innere Komplexität von parametrisierten anzählen Probleme analysiert. Wir haben #W(P)-hart Problem betrachtet. Wir konnten bewiesen dass, (unter bestimmten Hypothesen der Komplexität Theorie):
1. Jedes #W(P)-hart Problem ist schwieriger als jeder Problem in der
A Hierarchie.
2. Wenn wir ein Orakel für W(P) verwenden könnten, könnten wir dann jedes #W(P) Problem in fpt-Zeit nähern.


SWD-Schlagwörter: Parametrisierte Komplexität
Freie Schlagwörter (englisch): Counting Complexity , Counting Hierarchies , Parameterized Counting
MSC Klassifikation 68Q10 , 68Q15 , 68Q17
Institut: Institut f. Math. Logik u. Grundlagen d. Mathematik
Fakultät: Fakultät für Mathematik und Physik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Erstgutachter: Flum, Jörg (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 05.09.2008
Erstellungsjahr: 2008
Publikationsdatum: 09.09.2008
Indexliste