Uwe Schöning

Uwe Schöning (född 28 december 1955) är en pensionerad tysk datavetare , känd för sin forskning inom beräkningskomplexitetsteori .

Utbildning och karriär

Schöning tog sin doktorsexamen. från universitetet i Stuttgart 1981, under ledning av Wolfram Schwabhäuser. Han var professor vid Institutet för teoretisk informatik vid universitetet i Ulm fram till sin pensionering 2021.

Bidrag

Schöning introducerade låg- och höghierarkierna i teorin om strukturell komplexitet 1983. Som Schöning senare visade i en artikel från 1988 spelar dessa hierarkier en viktig roll i komplexiteten i grafisomorfismproblemet, vilket Schöning vidareutvecklade i en monografi från 1993 med Köbler och Toran .

I ett FOCS -dokument från 1999 visade Schöning att WalkSAT , en randomiserad algoritm som tidigare analyserats för 2-tillfredsställelse av Papadimitriou , hade god förväntad tidskomplexitet (även om den fortfarande är exponentiell) när den tillämpades på värsta fall av 3-tillfredsställelse och andra NP-fullständiga begränsningar tillfredsställelse problem. Vid den tiden var detta den snabbaste garanterade tiden för 3SAT; efterföljande forskning har byggt på denna idé för att utveckla ännu snabbare algoritmer.

Schöning är också uppfinnaren av de pedagogiska programmeringsspråken LOOP , GOTO och WHILE som han beskrev i sin lärobok Theoretische Informatik - kurz gefasst .

Utvalda publikationer

Schöning är författare eller redaktör för många böcker inom datavetenskap, bl.a

• Komplexitet och struktur (Springer, Lecture Notes in Computer Science 211, 1985).
• Logik für Informatiker (på tyska, Reihe Informatik, 1987; 5:e upplagan, Springer, 2000). Översatt till engelska som Logic for Computer Scientists (Birkhäuser, 1989).
• Theoretische Informatik - kurz gefasst (på tyska, BI-Wiss.-Verlag, 1992; 5:e upplagan, Spektrum, 2008)
• Grafisomorfismproblemet: dess strukturella komplexitet (med J. Köbler och J. Toran, Birkhäuser, 1993).
• Perlen der Theoretischen Informatik (på tyska, Bibl. Institut Wissenschaftsverlag, 1995). Reviderad och översatt till engelska som Gems of Theoretical Computer Science (med RJ Pruim, Springer, 1998).
• Algoritmen - kurz gefasst (på tyska, Spektrum, 1997).
• Algorithmik (på tyska, Spektrum, 2001).
• Ideen der Informatik (på tyska, Oldenbourg, 2002, 2:a upplagan 2005).
• Mathe-Toolbox - Mathematische Notationen, Grundbegriffe und Beweismethoden (Lehmanns, 2010).
• Kryptologie-Kompendium (Lehmanns, 2012).
• Das Erfüllbarkeitsproblem SAT - Algorithmen und Analysen (med J. Toran, på tyska, Lehmanns, 2012). Översatt till engelska som The Satisfiability Problem - Algorithms and Analyzes (Lehmanns, 2013).

Hans forskningsartiklar inkluderar:

•   Schöning, Uwe (1983), "A low and a high hierarchy within 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), "Graph isomorphism is in the low hierarchy", Journal of Computer and System Sciences , 37 (3): 312–323, doi : 10.1016/0022-0000(88)90010-4 , MR 0975447 .
• " A probabilistic algorithm for k-SAT and constraint satisfaction problems", Proceedings of 40th Annual Symposium on Foundations of Computer Science , s. 410–414, doi : 10.1109 /SFFCS.1999.814C 5.7.71C   .

externa länkar

• Google scholar-profil