Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26647
Titel: | Why are certain polynomials hard? : A look at non-commutative, parameterized and homomorphism polynomials |
Alternativtitel: | Warum sind bestimmte Polynome schwer? |
VerfasserIn: | Engels, Christian |
Sprache: | Englisch |
Erscheinungsjahr: | 2015 |
Kontrollierte Schlagwörter: | Average-case-Komplexität Komplexität Parametrisierte Komplexität Multivariates Polynom |
Freie Schlagwörter: | arithmetic circuits arithmetic complexity circuit complexity fixed parameter complexity average case complexity computational complexity |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Dissertation |
Abstract: | In this thesis we will try to answer the question why specific polynomials have no small suspected arithmetic circuits. We will look at this general problem in three different ways. First, we study non-commutative computation. Here we show matching upper and lower bounds for the non-commutative permanent for various restricted graph classes. Our main result gives algebraic branching program upper and lower bounds for graphs with connected component size 6 as well as a #P hardness result. We introduce a measure that characterizes this complexity on these instances. Secondly, we introduce a new framework for arithmetic circuits, similar to fixed parameter tractability in the boolean setting. This framework shows that specific polynomials based on graph problems have the expected complexity as in the counting FPT case. We introduce classes BVW[t] which are close to the boolean setting but hardly use the power of arithmetic circuits. We then introduce VW[t] with modified problems to remedy this situation. Thirdly, we study polynomials defined by graph homomorphisms and show various dichotomy theorems. This shows that even restrictions on the graphs can already give us hard instances. Finally, we stray from our main continuous thread and handle simple heuristics for metric graphs. Insteadof studying specific metrics we look at a randomized process giving us shortest path metric instances. In dieser Thesis versuchen wir die Frage zu beantworten, warum allgemein vermutet wird dass bestimmte Polynome keine kleinen arithmetischen Schaltkreise haben. Wir untersuchen dieses Problem in drei verschiedene Richtungen. Erstens, untersuchen wir nicht kommutative Berechnungen. Wir zeigen hier, obere und untere Schranken für die nicht kommutative Permanente auf verschiedenen eingeschränkten Graphen. Unser Hauptresultat zeigt Schranken für Graphen mit Komponenten der Größe höchstens 6 sowie ein #P-härte Resultat. Wir führen ein Maß ein, dass die Komplexität solcher Instanzen charakterisiert. Zweitens, führen wir ein neue theoretischen Rahmen für arithmetische Schaltkreise ein, ähnlich der parametrisierten Komplexität. Dieses zeigt das bestimmte Polynome die auf Graphproblemen basieren, die erwartete Komplexität haben. Die von uns eingeführten Klassen sind ähnlich zu der boolschen Situation und benutzen die Kraft der arithmetischen Schaltkreise kaum. Um dies zu beheben führen wir Klassen VW[t] ein, die modifizierte Probleme beinhalten. Drittens, untersuchen wir Polynome definiert durch Graphhomomorphismen und beweisen Dichotomie Theoreme die zeigen, dass selbst Restriktionen auf den Graphen uns harte Instanzen geben. Zum Schluss weichen wir von unserem roten Faden ab und untersuchen einfache Heuristiken auf metrischen Graphen. Anstatt eine bestimmte Metrik zu untersuchen, schauen wir uns einen randomisierten Prozess an der uns eine kürzeste Pfade Metrik erzeugt. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-64387 hdl:20.500.11880/26703 http://dx.doi.org/10.22028/D291-26647 |
Erstgutachter: | Bläser, Markus |
Tag der mündlichen Prüfung: | 27-Jan-2016 |
Datum des Eintrags: | 1-Apr-2016 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
thesis.pdf | 1,69 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.