16.–17. August 2005, Universität zu Lübeck
Der 52. Workshop über Komplexitätstheorie, Datenstrukturen und Effiziente Algorithmen findet in Lübeck statt.
17.–20. August 2005, Scandic Hotel Lübeck
Die fünfzehnte FCT Konferenz (15th International Symposium on Fundamentals of Computation Theory) findet dieses Jahr in Lübeck statt.
17. November 2005, Musik- und Kongresshalle (MuK) Lübeck, Willy-Brandt-Allee 10
Wir gratulieren Bodo Manthey zur erfolgreichen Promotion zum Dr. rer. nat. mit summa cum laude und zur Verleihung des Fakultätspreises der Universität zu Lübeck für die beste Promotion 2005.
Der Vortrag stellt eine neue und pragmatische Herangehensweise vor, um Consensus in asynchronen Systemen, die mit Ausfalldetektoren (failure detectors) versehen sind, zu lösen. Diese Herangehensweise kann in praktischen Systemen implementiert werden. Das betrachtete Fehlermodell läßt zu, daß Netzwerkverbindungen verloren gehen, daß Prozesse abstürzen und daß unter bestimmten Umständen der Ausfall von Prozessen nicht erkannt wird, bzw. daß aktive Prozesse verdächtigt (d.h. als abgestürzt eingestuft) werden. Byzantinische Fehler treten nicht auf, abgestürzte Prozesse können hochgefahren werden.
Consensus kann mit Hilfe von Ausfalldetektoren, die schwache Vollständigkeit (d.h. jeder abgestürzte Prozeß wird von wenigstens einem Prozeß schließlich permanent verdächtigt) erfüllen, gelöst werden. Fälschlicherweise verdächtigte Prozesse werden gegebenenfalls heruntergefahren.
Erfüllt der Ausfalldetektor starke Vollständigkeit (d.h. abgestürzte Prozesse werden von allen Prozessen schließlich permanent verdächtigt) und ausgewählte Genauigkeitseigenschaften (accuracy properties), dann werden falsch verdächtigte Prozesse nicht heruntergefahren.
Das Transversal-Problem auf Hypergraphen weist als eine Verallgemeinerung des Vertex-Cover-Problems auf Graphen einen engen Bezug zu zahlreichen Problemen aus verschiedenen Gebieten der Informatik wie z.B. den Datenbanken, der Logik, der Künstlichen Intelligenz und der Spieltheorie auf. Die genaue Komplexität des Problems für den allgemeinen Fall ist noch nicht geklärt. Das Entscheidungsproblem liegt in co-NP, aber es wird vermutet, dass es nicht co-NP-vollständig ist. Für eine Reihe von Teilklassen der Hypergraphen ist das Problem in (output-)polynomialer Zeit lösbar.
In diesem Vortag wird zunächst das Transversal-Problem definiert und bekannte Ergebnisse zu seiner Komplexität zusammengetragen. Kurz werden einige seiner verwandten Probleme aus der Logik vorgestellt. Im Hauptteil dieses Vortrags werden die wichtigsten natürlichen Teilklassen der Hypergraphen untersucht, für die das Transversal-Problem effizient gelöst werden kann.
Eine sehr wichtige Teilklasse stellen die simplen a-azyklischen Hypergraphen dar. Die Komplexität des Transversal-Problems für diese Teilklasse war bis zum Jahr 2003 ein offenes Problem. Mit Hilfe des in dieser Arbeit eingeführten Konzeptes der isolierten Eliminationsordnung wird direkt auf Hypergraphen gezeigt, dass für simple a-azyklische Hypergraphen das Transversal-Problem (output-)polynomial ist. Im Gegensatz zum bisherigen Ergebnis wird der Umweg über die Logik vermieden und zudem die Zeitschranke verbessert.
Primzahltests sind Algorithmen, die Primzahlen von zusammengesetzten Zahlen unterscheiden. Wir betrachten hierbei Monte-Carlo-Algorithmen mit einseitigem beschränkten Fehler. Sie klassifizieren Primzahlen immer richtig, während sie zusammengesetzte Zahlen mit unabhängig von der Eingabe beschränkter Wahrscheinlichkeit auch fälschlicherweise als Primzahlen einstufen können. Durch mehrmalige Wiederholung eines solchen Primzahltests erhält man ein für die Praxis ausreichend verlässliches Verfahren zur Erkennung von Primzahlen.
Sehr häufig wird der Miller-Rabin-Primzahltest eingesetzt. Er hat eine Fehlerwahrscheinlichkeit von höchstens 1/4. Ein neuer Primzahltest ist der randomisierte starke quadratische Frobenius-Test (RQFT), der in [Gra98] vorgeschlagen wird und Fehlerwahrscheinlichkeit <1/7710 hat, während die Laufzeit asymptotisch der von drei Iterationen des Miller-Rabin-Tests entspricht.
Der RQFT wird im Vortrag vorgestellt. Dazu wird erläutert, auf welchen mathematischen Zusammenhängen der Test beruht. Außerdem wird die Laufzeit des RQFT diskutiert. Ausgehend von der Darstellung in [Gra98] wird auch auf eine alternative Implementierung eingegangen --- [CP01, Abschnitt 3.5.3], zugeschnitten auf den RQFT ---, die sich als etwas schneller erwiesen hat. Ergebnisse von experimentellen Laufzeitmessungen werden ebenfalls präsentiert.
[Gra98] Grantham, Jon: A Probable Prime Test With High Confidence.Der Einfluss von Datenbanken in heutiger Software nimmt stetig zu. Nichtsdestoweniger ist das zentrale Problem in der Datenbanktheorie (Conjunctive Query; CQ) schwierig in Bezug auf die Berechnung mit dem Computer. Das CQ-Problem, welches nach der Antwort zu einer gegebenen Anfrage (genauer: konjunktiven Anfrage) sucht, ist im allgemeinen NP-schwer.
Während praktische Datenbanksysteme dies ignorieren, gibt es eine Reihe theoretischer Lösungsansätze zu diesem Problem. Für Anfragen mit kreisfreier oder nahezu kreisfreier Struktur (beschränkte Weite) kann das CQ-Problem effizient berechnet werden und ist zudem gut parallelisierbar. Die zur Zeit attraktivste Methode heißt Hyperbaumweite und wurde von Gottlob, Leone und Scarcello in 2002 vorgestellt. Verwandte Begriffe sind Anfrageweite (Chekuri und Rajaraman, 1997) und Baumweite (Freuder, 1990). Der gemeinsame Nachteil dieser Methoden ist die abstrakte, unintuitive und nichtkonstruktive Art, in der sie eingeführt wurden.
Im Vortrag wird ein konstruktiver und praktischer Ansatz zur Formulierung von konjunktiven Anfragen mit beschränkter Weite vorgestellt: Konstruktorweite. Der neue Begriff ist verwandt zur Hyperbaumweite und Anfrageweite. Als Beispiel für eine praktische Anwendung der eingeführten Methode werden Datenbankanfragesprachen vorgestellt, die den Grad der Kreisfreiheit durch ihre Syntax implizit garantieren. Derartige Sprachen bieten eine Reihe von Vorteilen. Erstens garantieren sie die effiziente Berechnung des CQ-Problems, zweitens kann der Grad der Kreisfreiheit durch die Syntax vorgegeben werden und drittens kann die Datenstruktur zur effizienten Berechnung, die Baumdekomposition, leicht aus den Anfragen abgeleitet werden und muss nicht, wie bei anderen Methoden, mit hohen Kosten berechnet werden.
Recently there has been substantial progress in obtaining strong lower bounds on size of monotone circuits computing certain Boolean functions. It is natural to ask if we could put together and make use of the approaches developed so far for monotone case to derive strong lower bounds for more general models. For such a generalized model we consider circuits with a limited number of negation gates and obtain superpolynomial lower bound for circuits computing certain NP complete problem.
