zurück
zum Seminarplan
Olaf
Beyersdorff: Disjunkte Tupel von NP-Mengen
Disjoint NP-pairs are a well studied complexity theoretic concept with
important applications in cryptography and propositional proof
complexity. In this talk we introduce a natural generalization of the
notion of disjoint NP-pairs to disjoint k-tuples of NP-sets for k>1.
We define subclasses of the class of all disjoint k-tuples of NP-sets.
These subclasses are associated with a propositional proof system and
posses complete tuples which are defined from the proof system.
In our main result we show that complete disjoint NP-pairs exist if and
only if complete disjoint k-tuples of NP-sets exist for all k>1.
Further, this is equivalent to the existence of a propositional proof
system in which the disjointness of all k-tuples is shortly provable.
We also show that a strengthening of this conditions characterizes the
existence of optimal proof systems.
zur
Abstractübersicht
zurück
zum Seminarplan
Carsten
Schwarz: Hyperelliptic
Curve Cryptosystems
Kryptographie ist in Zeiten globaler Datennetze und internationaler
Kommunikation von zentraler Bedeutung. Kryptographische Verfahren auf
Basis hyperelliptischer Kurven bieten den Vorteil, dass kein Angriff
mit subexponentieller Laufzeit gegen sie bekannt ist. Dadurch genügt
ihnen eine kürzere Operandenlänge bei einer im Vergleich zu den
alternativen Verfahren gleichen Sicherheit. Dies spart Rechenzeit,
Speicherplatz und Bandbreite und ist besonders bei Anwendungen auf den
ressourcenknappen Smartcards von großem Vorteil.
zur
Abstractübersicht
zurück
zum Seminarplan
Falk Niehörster: Einführung in die
Quanteninformatik und der Existenzbeweis einer universellen
Quanten-Turingmaschine
Nach einer kurzen Einführung in die Axiome der Quantenmechanik und
die Grundlagen der Quanteninformatik, soll die von David Deutsch
definierte Quanten-Turingmaschine dargestellt werden. Darüber hinaus
wird der Existenzbeweis einer universellen Quanten-Turingmaschine von
Bernstein und Vazirani ausführlich besprochen. Zum Abschluss soll ein
Überblick über die grundlegenden Quantenkomplexitätsklassen gegeben
werden.
zur
Abstractübersicht
zurück
zum Seminarplan
Andre
Hernich: Charakterisierungen von P mittels Selbstreduktion und
Teilinformation
Selbstreduzierbarkeit ist eine Eigenschaft, die sich viele
NP-vollständige sowie PSPACE-vollständige Sprachen teilen.
Teilinformationsklassen
enthalten Sprachen, für die in Polynomialzeit Teilinformation bezüglich
der Mitgliedschaft von Wörtern in solchen Sprachen berechenbar ist.
Beispiele sind die Klassen der p-selektiven, strongly membership
comparable
und der leicht zählbaren Sprachen. Es ist bekannt, dass die Sprachen in
P genau die selbstreduzierbaren
p-selektiven Sprachen sind. In diesem Vortrag soll gezeigt werden, dass
ähnliche Ergebnisse auch für andere Teilinformationklassen gelten. Zum
Beispiel lassen sich die Sprachen in P ebenso charakterisieren als
selbstreduzierbare Sprachen L, die leicht 2-zählbar oder für die L und
das Komplement strongly 2-membership comparable sind.
zur
Abstractübersicht
zurück
zum Seminarplan
Matthias
Schwan: Sicherheitsanforderungen und -massnahmen in Funknetzen (WLAN)
Die Einrichtung eines WLAN's erhöht in der Regel den Kompfort der
Nutzer erheblich, weshalb die Anzahl der Installationen stark steigt.
Die durch den Standard IEEE 802.11 definierten Sicherheitsfunktionen
erfüllen allerdings nur geringe Sicherheitsanforderungen. Im Vortrag
werden die verschiedenen Sicherheitsfunktionen vorgestellt und
analysiert, um abschliessend einen Sicherheitslevel festlegen zu
können.
zur
Abstractübersicht
zurück
zum Seminarplan
Lyuda
Kotomina: Construction of the pseudorandom number generators that use
fast
machine instructions (addition and XOR) and analysis of there
cryptographic characteristics
For the Information security systems we set the problem of finding
pseudorandom number generators (also called generators of initial
cryptographic sequences) that use fast machine instructions. Besides,
such generators must have some characteristics that we can use for
making a conclusion about “reliability” of the generators. In the
overview we analyse generators that use two fastest machine
instructions: arithmetic - addition and logical – XOR (addition modulo
2). We get the criteria that allow both - constructing and analysing of
such generators.
zur
Abstractübersicht
zurück
zum Seminarplan
André Hernich: Transforming Turing into
Truth-table reductions for languages in P[NONSEL_n]
We call a set {b_0,...,b_n} \subseteq {0,1}^n an ascending chain, if
b_0 = 0^n and b_{i+1}, i \in {0,...,n-1}, is obtained from b_i by
changing one 0 to 1. Let NONSEL_n be the set of all subsets D of
{0,1}^n such that there is no ascending chain D' with D' \subseteq D. A
language A is in P[NONSEL_n] if there exists a function f \in FP which
computes on input of n words (w_1,...,w_n) a set D \subseteq NONSEL_n
which contains the value of \chi_A^n(w_1,...,w_n), where \chi_A^n is
the n-fold characteristic function of A.
Beigel, Kummer and Stephan have shown how to transform Turing into
Truth-table reductions for easily countable languages. We show a
generalization of this theorem: every Turing reduction to a language in
P[NONSEL_n] can be transformed into a Truth-table reduction.
zur
Abstractübersicht
zurück
zum Seminarplan
Birgit Schelm: On the role of the class HP
in separating average-case approximation classes
A polynomial-time algorithm scheme A for a distributional problem
(L,\mu), where L is a language and \mu a probability distributions on
words, is a deterministic algorithm with the following properties:
1. It receives a word x and a positive integer m as input.
2. It may err on some inputs; its error probability depends on the
input distribution \mu as follows:
Prob[A(x,1^m) \neq \chi_L(x)] < 1/m.
3. Its running time is polynomial in |x|
and m.
The class HP is defined as the class of all distributional problems
(L,\mu) that have a polynomial time algorithm scheme.
In my talk I will discuss the role of the class HP in separating
average-case approximation classes, or in other words: the role of the
class HP in average-case non-approximability proofs.
zur
Abstractübersicht
zurück
zum Seminarplan
Piyush P Kurur: On the complexity of
computing the units of a number field
Let $K$ be a number field with ring of integers $O_K$. We are
interested
in computing the units of the ring $O_K$. We will prove that the above
mentioned problem is in the complexity class SPP. As a result we show
that the above problem is in and "low" for various complexity classes
like PP, Parity-P, Mod_kP etc. Also the problem is unlikely to be
NP-hard.
I will give a brief introduction to the relavant algebraic number
theory and complexity theory. If time permits, I will also mention the
complexity upperbounds for relate problems viz. Principal ideal testing
and computing the Class group.
zur
Abstractübersicht
zurück
zum Seminarplan
Um einen hohen Qualitätsstandard bei der Konstruktion von
IT-Sicherheitssystemen zu erreichen, ist die Formulierung präziser
Sicherhietseigenschaften notwendig. Durch Modellbildung können für
bestimmte Systeme auf hohem Abstraktionsgrad die Eigenschaften bewiesen
werden.
Der Vortrag beginnt mit einer Einführung der Sciherheitsmodelle und
deren Bedeutung in der IT-Sicherheit. Daraufhin wird das formale Modell
der Zugriffsmatrix vorgestellt und Sicherheitseigenschaften formuliert.
Es wird gezeigt, dass es im allgemeinen Fall unentscheidbar ist, die
"Sicherheit" eines Modells festzustellen. Es wird sich im wesentlichen
auf die Arbeit von Harrison, Ruzzo und Ullman (HRU-Modell) gestützt.
zur Abstractübersicht
zurück
zum Seminarplan
In Teil 1 wurde gezeigt, dass es Sprachen in P[BOTTOM] gibt, die
NICHT polynomiell 1-tt-reduzierbar auf Sprachen in P[SEL] sind.
Entspechendes gilt auch dann noch, wenn man sowohl der
Reduktionsmaschine als auch dem Selektor Zugriff auf ein Orakel aus PH
gibt.
Dieses Mal werden positive Ergebnisse gezeigt:
- Jede Sprache in P[2-SIZE_2] lässt sich 1-tt-reduzieren auf
eine Sprache in P^NP[MIN_2], wenn die Reduktion Zugriff auf ein
NP-Orakel hat.
- Jede Sprache in P[SEL_2 + Xor] lässt sich 1-tt-reduzieren auf
eine Sprache P^NP[SEL], wenn die Reduktion Zugriff auf ein NP-Orakel
hat.
- Jede Sprache in P[TOP u BOTTOM] lässt sich 1-tt-reduzieren auf
eine Sprache P^(Sigma_2)[SEL u BOTTOM], wenn die Reduktion Zugriff auf
ein Sigma_2-Orakel hat.
zur Abstractübersicht
zurück
zum Seminarplan
Optimierungsprobleme haben oft eine reichhaltigere Struktur als
Entscheidungsprobleme. So ist beispielsweise das zum Clique-Problem
gehörige Optimierungspronlem (vermutlich) ungleich schwieriger als das
zum Rucksack-Problem gehörige -- obwohl beide Probleme NP-vollständig
sind.
Im Vortrag sollen nun als neues Konzept Logspace-Optimierungsprobleme
eingeführt werden. Die eingeführten Klassen NLO und LO verhalten sich
zu NL und L wie NPO und PO zu NP und P. Wie im Polynomialzeitfall
können Entscheidungsprobleme die gleiche Komplexität besitzen
(beispielsweise NP-vollständig sein), ihre zugehörigen
Optimierungsprobleme jedoch unterschiedlich schwierig sein. So ist das
Problem zu entscheiden, ob ein Graph einen Weg einer bestimmten
Maximallänge zwischen zwei Knoten enthält, sowohl für DAGs als auch für
Tournaments NL-vollständig. Die zugehörigen Optimierungsprobleme,
nämlich in DAGs bzw. Tournaments möglichst kurze Pfade zu finden,
verhalten sich unterschiedlich: für DAGs ist das Problem nicht
logspace-approximierbar, für Tournaments existiert ein
Logspace-Approximationsschema
zur Abstractübersicht
zurück
zum Seminarplan
Von Krajicek und Alechnovich et al. wurde eine Methode
vorgeschlagen, aus Pseudozufallsgeneratoren Tautologiefolgen zu
gewinnen, die für aussagenlogische Beweissysteme hart sind, d.h. keine
polynomiell grossen Beweise besitzen. Dies sind sogenannte Tauformeln,
die ausdrücken, dass ein String ausserhalb des Bildes einer gegebenen
Polynomialzeitfunktion (des PRG) ist.
Anhand von Resolution und der Nisan-Wigderson-Konstruktion wird die
Methode, der Arbeit von Alechnovich et al. folgend, dargestellt.
zur Abstractübersicht
zurück
zum Seminarplan
Die Schwierigkeit bei der Suche nach einer optimalen Lösung für
ein NP-Optimierungsproblem besteht darin, in einer möglicherweise
exponentiell grossen Lösungsmenge die Lösung mit der optimalen
Bewertung zu finden. Falls P ungleich NP, so lassen sich nicht für alle
NP-Optimierungsprobleme Algorithmen angeben, die solche Lösungen in
polynomieller Zeit finden. Auch die Suche nach möglichst guten
Lösungen, d.h. Lösungen, deren Bewertung nur um einen konstanten Faktor
von der Bewertung der optimalen Lösung abweicht, ist für viele
NP-Optimierungsprobleme nicht in polynomieller Zeit möglich, es ein
denn P=NP.
Ähnlich wie bei NP-Entscheidungsproblemen stellt sich auch im Bereich
der Approximierbarkeit von NP-Optimierungsproblemen die Frage, ob sich
diese negativen Ergebnisse nur auf einige wenige in der Praxis unter
Umständen nur selten auftretende Instanzen beziehen, oder ob bereits
durchschnittliche Instanzen schwer approximierbar sind. Um den Begriff
der Durchschnittlichkeit einer Instanz zu formalisieren, wird bei der
Untersuchung der Durchschnittskomplexität eines NP-Optimierungsproblems
zusätzlich eine Wahrscheinlichkeitsverteilung auf den Instanzen
angegeben, die den Grad der Durchschnittlichkeit jeder Instanz
widerspiegelt. Diese Paare aus NP-Optimierungsproblem und
Wahrscheinlichkeitsverteilung werden als randomisierte
NP-Optimierungsprobleme bezeichnet.
Anders als bei der Betrachtung der Durchschnittskomplexität von
NP-Entscheidungsproblemen, lässt sich bei den NP-Optimierungsproblemen
das aurchschnittliche Verhalten in Bezug auf zwei Parameter
untersuchen. Zum einen kann die durchschnittliche Komplexität der
Laufzeit betrachtet werden, zum anderen die im Durchschnitt erreichbare
Approximationsgüte.
Der Vortrag konzentriert sich nur auf die Approximierbarkeit mit
durchschnittlich polynomieller Laufzeit und stellt eine Reduktion vor,
die diese Approximierbarkeit erhält. Mit Hilfe dieser reduktion lässt
sich dann ein Vollständigkeitsbegriff für Klassen von randomisierten
NP-Optimierungsproblemen definieren und vollständige Probleme für
einige dieser Klassen angeben.
zur Abstractübersicht
zurück
zum Seminarplan
Ein Constraint-Satisfaction-Problem (CSP) besteht aus einer Folge
von Einschränkungen an einen Vektor von Variablen. Eine Lösungen eines
CSPs ist eine Belegung der Variablen, die alle Einschränkungen erfüllt.
Wir untersuchen Boolsche Constraint-Satisfaction-Probleme, bei denen
als Einschränkungen beliebige Boolsche Relationen verwendet werden
dürfen.
Thomas Schaefer erzielte im Jahre 1978 ein bemerkenswertes
Resultat: Er konnte zeigen, dass für jede mögliche Menge von erlaubten
Constraints das Problem, von einem CSP festzustellen, ob es eine Lösung
besitzt, entweder NP-vollständig ist oder in Polynomialzeit lösbar ist
(und nicht etwa in einem der -- unter der Annahme "P ungleich NP"
existierenden -- unendlich vielen Zwischengrade liegt). Neben diesem
sog. Erfüllbarkeitsproblem wurden seitdem viele weitere Fagestellungen
über CSPs komplexitätstheoretisch klassifiziert.
Im Vortrag wird nach einer Einführung in das Themengebiet der
Boolschen Constraint-Satisfaction-Probleme die Fargestellung
untersucht, wie schwierig es ist, festzustellen, ob zwei gegebende CSPs
die gleiche Menge von Lösungen besitzen.
zur Abstractübersicht
zurück
zum Seminarplan
Im Vortrag soll das im Titel genannte Paper von R.Beigel,
L.Fortnow und A.Pavan vorgestellt werden.
Darin wird unter anderem gezeigt:
-
- Es gibt eine Sprache A in P-mc(2), so dass für alle
p-selektiven Sprachen B gilt:
A ist nicht btt-reduzierbar auf B.
- Verstärkung von 1.a.:
Für jede Konstante c gibt es eine Sprache A in P-mc(2), so dass für
alle p-selektiven Sprachen B gilt:
A ist nicht in n^c-tt-reduzierbar auf B.
Ist P=NP, so ist jede 1-cheatable Sprache 1-tt-reduzierbar auf eine
p-selektive Sprache.
zur Abstractübersicht
zurück
zum Seminarplan
Wieviele Anfragen an k-membership-vergleichbare Sprachen sind
nötig, um alle (k+1)-membership-vergleichbaren Sprachen zu netscheiden?
Diese Anzahl ist für k>=2 mindestens linear und höchstens kubisch.
Hieraus kann man folgern, dass es mehr O(log
n)-membership-vergleichbare Sprachen gibt, als Sprachen, die auf
P-selektive Sprachen tt-reduzierbar sind.
zur Abstractübersicht
zurück
zum Seminarplan
We use the notion of general dimension to show that any p-evaluable
concept class with polynomial query complexity can be lerned in
polynomial time with the help of an oracle in the polynomial hierarchy,
where the complexity of the required oracle depends on the query-types
used by the learning algorithm.
In particular, we show that for subset and superset queries an oracle
in Sigma P^3 suffices. Since the concept class of DNF formulas has
polynomial query complexity with respect to subset and superset
querieswith DNF formulas as hypotheses, it follows that DNF formulas
are properly learnable in polynomial time with subset and superset
queries and the help of an oracle in Sigma P^3. We also show that the
required oracle in our main theorem can not be replaced by an oracle in
a lower level of the polynomial-time hierarchy, unless the hierarchy
collapses.
This is joint work with Wolfgang Lindner
zur Abstractübersicht
zurück
zum Seminarplan
Bei der Untersuchung der Aufzählbarkeit von Funktionen stösst man
häufig auf ein überraschendes Phänomen: gleichartig lautende Sätze
gelten sowohl in der Rekursionstheorie als auch in der
Automatentheorie, nicht aber in der (ressourcenbeschränkten)
Komplexitätstheorie.
Im Vortrag soll für den Kreuzproduktsatz aufgezeigt werden, warum dies
der Fall ist. Dazu wird ein wesentlich allgemeinerer Kreuzproduktsatz
formuliert, der rein logischer NAtur ist. Die bereits bekannten
Kreuzproduktsätze aus der Rekursions- und Automatentheorie sind
Spezialfälle dieses Satzes aus der Logik.
zur Abstractübersicht
zurück
zum Seminarplan
Die Identifikation und Authentifikation einer Person anhand
körpereigener Merkmale erscheint intuitiv als eine der sichersten
Methoden.
Doch bedarf entgegen der gewohnten Komplexitätsabschätzung
kryptografischer Algorithmen das Abschätzen der Mechanismenstärke eines
biometrischen Systems anderer Methoden.
Der Vortrag führt in das Thema Biometrie ein und behandelt aktuelle
Fragen.
zur Abstractübersicht
zurück
zum Seminarplan
Im Vortrag wird ein generisches vollständiges Problem für die Klasse
DistNPO, die Klasse aller NP-Optimierungsprobleme mit g-berechenbaren
Eingabeverteilungen, vorgestellt.
zur Abstractübersicht
zurück
zum Seminarplan
Die Kardinalitätsvermutung für endliche Automaten besagt, dass jede
Sprache regulär ist, deren n-fache Anzahlfunktion sich n-aufzählen
lässt mittels eines endlichen Automaten.
Im Vortrag soll diese Vermutung für den Fall n=2 beweisen werden. Der
Beweis stützt sich auf drei unterschiedliche Hilfsmittel:
- den Nonspeedup-Satz für endliche Automaten
- auf Büchis erststufige (!) logische Charakterisierung der
regulären Sprachen
- auf eine Variante der Easy-Hard-Argumentationen von Kadin
zur Abstractübersicht
zurück
zum Seminarplan
Der Kardinaltätssatz für Turing-Maschinen besagt,
dass eine Sprache rekursiv sein muss, wenn ihre n-Kardinaltätsfunktion
n-aufzählbar ist. Die Kardinatätsfunktion bildet jeweils n Worte auf
ihre Anzahl in der Sprache ab. Eine Funktion heißt n-aufzählbar, wenn
eine Turingmaschine bei jeder Eingabe eine Menge von höchstens n
Möglichkeiten für den Funktionswert errechnen kann.
Im Vortrag werden drei Gründe dargestellt, weshalb der Kardinaltätssatz
auch für endliche Automaten gelten könnte.
Beispielsweise gilt er für n=2 auch für endliche Automaten.
zur Abstractübersicht
zurück
zum Seminarplan
Im Vortrag werden obere und untere Schranken für
die Anzahl der statistischen Fragen, die zum Erlernen boolscher Formeln
notwenig werden, gezeigt.
zur Abstractübersicht
zurück
zum Seminarplan
We prove that the graph isomorphism problem restricted to trees and
to colored graphs with color multiplicities 2 and 3 is many-one
complete for several complexity classes within NC2.
In particular we show that tree isomorphism, when trees are encoded as
strings, is NC1-hard under AC0-reductions. NC1-completeness thus
follows from Buss's NC1 upper bound.
By contrast, we prove that testing isomorphism of two trees encoded as
pointer lists is L-complete. Concerning colored graphs we show that
the isomorphism problem for graphs with color multiplicities 2 and 3
is complete for symmetric logarithmic space SL under many-one
reductions. This result improves the existing upper bounds for the
problem.
We also show that the graph automorphism problem for colored
graphs with color classes of size 2 is equivalent to deciding whether
a graph has more than a single connected component and we prove that
for color classes of size 3 the graph automorphism problem is
contained in SL.
zur Abstractübersicht
zurück
zum Seminarplan
Der Vortrag soll überblicksartig die Beziehung zwischen der Länge
aussagenlogischer Beweise und der Beweisbarkeit in Theorien der
beschränkten Arithmetik darstellen. Insbesondere wird eine Übersetzung
arithmetischer Formeln angegeben und daraus eine Methode für untere
Schranken für die Beweislänge in aussagenlogischen Beweiskalkülen
abgeleitet.
zur Abstractübersicht
zurück
zum Seminarplan
Eine Sprache A ist k-approximierbar, falls ein
Polynomialzeitalgorithmus exisitert, der bei Eingabe von k Wörtern
einen Pool von 2^(k-1) Bitstrings der Länge k ausgibt, der den
charakteristischen String enthält.
Es ist bekannt, das für jedes k die k-approximierbaren Sprachen in
P/O(n^2) sind (Amir, Beigel, Gasarch).
Es ist auch bekannt, das die p-selektiven in NP/(n+1) sind
(Hemaspaandra, Torenvliet).
Es wird im Vortrag gezeigt, das die 2-approximierbaren Sprachen in
P^(NP[3])/(n+3) liegen.
Der Beweis benutzt eine Technik, mit der man aus Selektorfunktionen
transitive Selektorfunktionen machen kann.
zur Abstractübersicht
zurück
zum Seminarplan
We study Turing machines that are allowed absolutely no space
overhead. The only work spacethe achines have ist that which they can
create by reusing the input bits' own space. This model more closely
reflects the fixed-sized memory of real computers than does the
standard complexity-theoretic model of linear space. Though some
context-sensitive languages cannot be accepted by such machines, we
show that a large subcalsses of the context-free languages can even be
accepted in polynomial time with absolutely no space overhead.
zur Abstractübersicht
zurück
zum Seminarplan
Im zweiten Teil des Vortrages sollen nun die Techniken auf
Berechnungen mit logarithmischem Platz übertragen werden.
Es soll gezeigt werden, dass:
- Falls GAP in L-mc(const), so ist GAP in L.
- Falls A sich logspace Turing-reduzieren lässt auf L-sel und A
logspace-selbstreduzierbar ist, so ist A in L.
- Falls die Determinatenfunktion logspace Turing-reduzierbar ist
auf eine L-selektive Sprache, so ist sie in FL.
zur Abstractübersicht
zurück
zum Seminarplan
In diesem ersten Teil eines Doppelvortrages will ich drei neue
Resultate über die Reduzierbarkeit der Probleme SAT, GI und GA auf
Sprachen mit geringer Informationsdichte vorstellen.
Konkret soll folgendes gezeigt werden:
- Falls eine Lösung von (1GA,GA) sich tt-reduzieren läßt auf
P-mc(const), so ist GA in P.
- Falls GI in P-mc(log), so gilt GI in RP.
- Falls eine Lösung von (1SAT,SAT) sich tt-reduzieren läßt auf
P-mc(const), so ist SAT in RP.
zur Abstractübersicht
zurück
zum Seminarplan
Der Vortrag soll eine Übersicht über verschiedene Fragmente der
Peano-Arithmetik mit Gewicht auf der beschränkten Arithmetik und ihren
Beziehungen zur Komplexitätstheorie geben.
zur Abstractübersicht
zurück
zum Seminarplan
Abstracts:
A group of knights have gathered to hold a tournament that consists
of a series of jousts between every pair of the knights. After the
tournament Sir Lancelot and Sir Galahad meet and Sir Lancelot says, 'I
liked your style. It is only fair you won our joust.' Sir Galahad
answers, 'I am not sure. I think you won a joust against someone who
won against someone who won against someone, and so forth, who won
against me. Isn`t that true?' The two knights ponder on this, but it
seems difficult to answer as there were so many jousts. So they go to
Merlin, the magician who moves backwards in time, and pose their
problem. Merlin ponders on the problem and finally proclaims: ' If some
of the jousts in the tournament ended in a draw, your question is
difficult to answer. But if none of them did, there is an extremely
efficient algorithmen to solve it.' This talk is about that algorithm.
After a short introduction to descriptive complexity theoriy, I will
show that the tournament reachability problem is first-order definable
and hence has very low computational complexity. In particular, it can
be decided in constant parallel time. This shows that the deciding
reachability for tounaments is probably easier than deciding it for
trees or dags. For the succinct graphs, which frequently arise in
hardware desing, I show that the succinct reachability problem is
complete for the second level of the polynomial hierarchy. In sharp
contrast, succinct reachability problems for most other kinds of graphs
are known to be complete for polynomial space.
zur Abstractübersicht
zurück
zum Seminarplan
Das Prinzip der elektronischen Signatur basierend auf asymmetrischen
Kryptoverfahren ist wohl allen geläufig und schon lange bekannt. Doch,
wer hat denn wirklich schon einmal eine Email signiert oder
verschlüsselt? Bei der praktischen Umsetzung und Anwendung einer
elektronischen Signatur entstehen neue Probleme.
Ich möchte die zu beantwortenden Fragen für den Aufbau einer
Public-Key-Infrastructure (PKI) stellen. Dabei werden verschiedene
Zertifikatsformate und das Signaturgesetz angesprochen.
Weiterhin soll die Einbindung von SmartCards in das Microsoft
Betriebssystem erläutert werden.
Am Ende wollen wir uns ein Zertifikat ausgestellt von der
Zertifizierungsinstanz der HU ansehen, das gemeinsam mit dem privaten
Schlüssel auf einer Smartcard gespeichert ist sowie eine Email
signieren und/oder verschlüsseln.
Damit sollte jeder ein Gefühl dafür bekommen, wo wir mit der
Anwendung digitaler Signaturen heute stehen.
zur Abstractübersicht
zurück
zum Seminarplan
Ben
Bässler - zuletzt geändert am 12.11.2002