Die Stärke probabilistischer Berechnungen im Vergleich mit nichtdeterministischen und deterministischen Berechnungen
Final Report Abstract
Die im Rahmen des Projekts erarbeiteten Publikationen haben zum Verständnis des Ressourcenverbrauchs in eingeschränkten Rechnermodellen beigetragen. Für unäre Automaten wurde überraschenderweise gezeigt, dass die erreichbare Zustandsreduktion für würfelnde Automaten selbst bei beidseitigem, beschränktem Fehler höchstens polynomiell groß sein kann. Der Einfluß von ß-Übergängen auf die Anzahl der Zustandsübergänge in nichtdeterministischen Automaten wurde für die Simulation von regulären Ausdrücken fast vollständig und für die Simulation allgemeiner nichtdeterministischer Automaten zumindest approximativ bestimmt. Zum Beispiel hat sich ergeben, dass nichtdeterministische endliche Automaten ohne ß-Übergänge reguläre Ausdrücke mit fast-linearer Größe erkennen können, eine signifikante Verbesserung gegenüber vorher bekannten Simulationsergebnissen. Die algorithmische Komplexität der Konstruktion kleiner nichtdeterministischer Automaten hat sich selbst dann als außerordentlich hoch erwiesen, wenn die erkannte reguläre Sprache durch einen deterministischen Automaten beschrieben wird: Unter kryptographischen Annahmen wird gezeigt, dass der Approximationsfaktor effizienter Approximationsalgorithmen exponentiell groß sein muss und „brauchbare“ Approximationsalgorithmen sind damit ausgeschlossen. Die Methode der Kommunikationskomplexität wurde angewandt und neue Kommunikationsmodelle wurden entworfen, um den Ressourcenverbrauch von endliche Automaten, Kellerautomaten, Branchingprogrammen und eingeschränkte Schaltkreismodellen untersuchen zu können. Als eine erste Anwendung wurde mit einem neuen Kommunikationsmodell gezeigt, dass würfelnde Kellerautomaten mit beidseitig beschränktem Fehler nicht alle kontextfreien Sprachen erkennen können. Sodann wurde zum ersten Mal die exponentielle Größe nichtdeterministischer Branchingprogramme für ein natürliches graph-theoretisches Problem nachgewiesen. In einer weiteren Anwendung wurde die Graphenkomplexität benutzt, um die Single-Level Vermutung der Schaltkreiskomplexität zu widerlegen.
Publications
- Complexity of semi- algebraic proofs, Moscow Math. Journal, 2(4), pp. 647-679, 2002.
Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.:
- Triangle-Freeness Is Hard To Detect. Combinatorics, Probability & Computing, pp. 549 - 569, 2002.
Jukna, S., Schnitger, G.:
- Nondeterminism versus determinism for two-way ¯nite automata: generalizations of Sipsers separation. Proceedings of 30th International Colloquium on Automata, Lan- guages and Programming (ICALP), Wien, Springer, pp. 439 - 451, 2003.
Hromkovi·c, J., Schnitger, G.:
- Nondeterministic communication with a limited number of advice bits. SIAM Journal on Com- puting 33 (1), pp. 43 - 68, (2003).
Hromkovi·c, J., Schnitger, G.:
- On uncertainty versus size in branching pro- grams. Theoretical Computer Science 290:3, pp. 1851-1867, 2003.
Jukna, S., Zak, S.:
- Probabilistic and Nondeterministic Unary Automa- ta. Proc. of the 28th Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science Bd. 2747, Springer, pp. 460-469, 2003.
Gramlich, G.:
- Pushdown automata and multicoun- ter machines, a comparison of computation modes, Proceedings of 30th International Colloquium on Automata, Languages and Pro- gramming (ICALP), Wien, Springer, pp. 66 - 80, (2003).
Hromkovi·c, J., Schnitger, G.:
- On multipartition communication complexity, Information and Computation 194(1), pp. 49-75, (2004).
Duris, P., Hromkovi·c, J., Jukna, S., Sauerho®, M., Schnitger, G.:
- On the minimum number of negations leading to super- polynomial savings. Information Processing Letters, 89 (2), pp. 71 - 74, 2004.
Jukna, S.:
- Learning unary automata, Procee- dings of the 7th International Workshop on Descriptional Com- plexity of Formal Systems (DCFS), pp. 122-133, 2005.
Gramlich, G., Herrmann, R.:
- Minimizing nfa's and regular expres- sion, Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science 3404, Springer, pp. 399-411, 2005.
Gramlich, G., Schnitger, G.:
- NFAs with and without epsilon- transitions, Proceedings of 32nd International Colloquium on Au- tomata, Languages and Programming (ICALP), Lissabon, Sprin- ger, pp. 385-396, (2005).
Hromkovi·c, J., Schnitger, G.:
- On the Incompressibility of Monotone DNFs, Pro- ceedings of the 15th Symposium on Fundamentals of Computation (FCT), pp. 32-43, 2005.
Krieger, M.:
- On the P versus NP intersected with co-NP question in communication complexity, Information Processing Letters 96(6), pp. 202-206, 2005.
Jukna, S.:
- On the power of randomized multi- counter machines, Theoretical Computer Science vol. 330 (1), pp. 135-144, 2005.
Hromkovi·c, J., Schnitger, G.:
- Polynomial time computing over quadratic maps I: sampling in real algebraic sets, Computational Complexity 14, pp. 20-52, 2005.
Grigoriev, D., Pasechnik, D.V.:
- Disproving the single level conjecture, SIAM J. Com- puting, 36(1), pp. 83{98, 2006.
Jukna, S.:
- On graph complexity, Combinatorics, Probability and Computing, 15(6), pp. 1{22, 2006.
Jukna, S.:
- Regular expressions and NFAs without epsilon- transitions, Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Springer, pp. 432-443, 2006.
Schnitger, G.:
