Uwe Schöning

Informático alemán (nacido en 1955)

Uwe Schöning (nacido el 28 de diciembre de 1955) es un informático alemán retirado , conocido por su investigación en teoría de la complejidad computacional .

Educación y carrera

Schöning obtuvo su doctorado. desde el Universidad de Stuttgart en 1981, bajo la supervisión de Wolfram Schwabhäuser. ^[1] Fue profesor en el Instituto de Informática Teórica de la Universidad de Ulm hasta su jubilación en 2021. ^[2]

Contribuciones

Schöning introdujo las jerarquías baja y alta en la teoría de la complejidad estructural en 1983. Como Schöning demostró más tarde en un artículo de 1988, estas jerarquías juegan un papel importante en la complejidad del problema del isomorfismo de grafos , que Schöning desarrolló aún más en una monografía de 1993 con Köbler y Toran. .

En un artículo de FOCS de 1999 , Schöning demostró que WalkSAT , un algoritmo aleatorio previamente analizado para determinar la satisfacibilidad 2 por Papadimitriou , tenía una buena complejidad temporal esperada (aunque todavía exponencial) cuando se aplicaba a los peores casos de satisfacibilidad 3 y otras restricciones NP-completas. problemas de satisfacción . En ese momento, este era el tiempo más rápido garantizado para 3SAT; Investigaciones posteriores se han basado en esta idea para desarrollar algoritmos aún más rápidos.

Schöning también es el inventor de los lenguajes de programación pedagógicos LOOP , GOTO y WHILE, que describió en su libro de texto Theoretische Informatik - kurz gefasst .

Publicaciones Seleccionadas

Schöning es autor o editor de muchos libros sobre informática, incluido

• Complejidad y estructura (Springer, Lecture Notes in Computer Science 211, 1985). ^[3]
• Logik für Informatiker (en alemán, Reihe Informatik, 1987; 5ª ​​ed., Springer, 2000). Traducido al inglés como Lógica para informáticos (Birkhäuser, 1989). ^{[4] [5]}
• Theoretische Informatik - kurz gefasst (en alemán, BI-Wiss.-Verlag, 1992; 5.ª ed., Spektrum, 2008)
• El problema del isomorfismo de grafos: su complejidad estructural (con J. Köbler y J. Toran, Birkhäuser, 1993). ^[6]
• Perlen der Theoretischen Informatik (en alemán, Bibl. Institut Wissenschaftsverlag, 1995). Revisado y traducido al inglés como gemas de la informática teórica (con RJ Pruim, Springer, 1998). ^{[7] [8] [9]}
• Algoritmos - kurz gefasst (en alemán, Spektrum, 1997).
• Algorithmik (en alemán, Spektrum, 2001).
• Ideen der Informatik (en alemán, Oldenbourg, 2002, 2ª ed. 2005).
• Mathe-Toolbox: notaciones matemáticas, Grundbegriffe und Beweismethoden (Lehmanns, 2010).
• Kryptologie-Kompendium (Lehmanns, 2012).
• Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen (con J. Toran, en alemán, Lehmanns, 2012). Traducido al inglés como El problema de la satisfacción: algoritmos y análisis (Lehmanns, 2013).

Sus artículos de investigación incluyen:

• Schöning, Uwe (1983), "Una jerarquía alta y baja dentro de NP", Journal of Computer and System Sciences , 27 (1): 14–28, doi : 10.1016/0022-0000(83)90027-2 , MR  0730913.
• Schöning, Uwe (1988), "El isomorfismo de gráficos está en la jerarquía baja", Journal of Computer and System Sciences , 37 (3): 312–323, doi : 10.1016/0022-0000(88)90010-4 , MR  0975447.
• Schoning, U. (1999), "Un algoritmo probabilístico para k-SAT y problemas de satisfacción de restricciones", Actas del 40º Simposio anual sobre fundamentos de la informática , págs. 410–414, doi :10.1109/SFFCS.1999.814612, S2CID  123177576.

Referencias

1. Uwe Schöning en el Proyecto de Genealogía de Matemáticas
2. Perfil de la facultad, Univ. de Ulm, consultado el 28 de marzo de 2022.
3. Repaso de Complejidad y estructura por Juris Hartmanis (1987), MR 0827009
4. Repaso de Logik für Informatiker de Neculai Curteanu (1989), SEÑOR 0944086; también listado como MR 1244106 (3.a ed.) y MR 2683474 (edición en inglés)
5. Repaso de Lógica para informáticos por Riccardo Pucella (2005), SIGACT News 36 (3): 17–19, doi :10.1145/1086649.1086657
6. Revisión del problema del isomorfismo gráfico por Pavol Hell (1995), MR 1232421
7. Repaso de Gemas de la informática teórica por Rohit Jivanlal Parikh (2000), Journal of Logic, Language and Information 9 (1): 131–132, doi :10.1023/A:1008379701961
8. Repaso de Gemas de la informática teórica por Danny Krizanc (2000), SIGACT News 31 (2): 2–5, doi :10.1145/348210.1042072
9. Repaso de Gemas de la informática teórica por Marius Zimand (2000), MR 1667079

enlaces externos

• Perfil académico de Google