Lecture Notes ni Computer Science Edited yb .G Goos and .J Hartmanis 34 tsnrE rekcepS rekloV nessartS Komplexit~t von diehcstnE nemelborpsgnu niE ranimeS Springer-Verlag Berlin. Heidelberg New York 91 6 7 Editoria; ~oar5 .~! Brinch Nansen • D. Gries - C. Moler • G. Seegm~ller • .J Stoer N. Wirth H"ditors ~rD Volker Strassen Seminar fi]r Angewandte Mathematik Universit~it ZLirich FreiestraBe 36 8032 Z~irich/Schweiz Dr. Ernst Specker Mathematisches Seminar der ETH Z0rich 8092 Z~Jrich/Schweiz Library of Congress Cataloging in Publication Data Main entry relcnlt title: Komplexit~t yon Entseheldungsproblemeno (Lecture notes in science eo~imlter 43) ; Bibliography: p. Includes index. 1. theorem--Congresses. s C~del' 2. Coml3u~ations eomplexity--Con~-esseso o3 Turing ms, hines, I. S~eckez~ Ernst~ 1920- II. Strassen, Vo!ker~ 1936- III. Series QAg.65.K65 621.3819'594' 01511 76-25088 CR Subject Classifications (1974): 0.12, 0.16, 0.32, 0.54, 0.60, 0.74, 0.75, 0.77, 0.80, 0.82, 04.60, 05.04, 05.40, 05.55, ,11.01 94.30 ISBN 3-540-07805-3 Springer-Verlag Berlin • Heidelberg • New York ISBN 0-387-07805-3 Springer-Vertag New York- Heidelberg • Berlin This work is subject to copyright. All rights era reserved, whether the whole or part of the material is concerned, specifically those of translation, -er printing, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, dna storage ni data banks. Under § 54 of the German Copyright waL where copies are mfaodre other than private use, a fee is payable to the publisher, the amount of the fee to be determined by agreement with the publisher. © by Springer-Vertag Berlin • Heidelberg 1976 Printed in Germany Printing dna binding: Beltz Offsetdruck, Hemsbach/Bergstr. Inhaltsverzeichnis Einleitung I. Zeitlich beschr~nkte Turingmaschinen und poly- nomiale Reduktion .W( Baur) 11 II. Polynomial beschr~nkte nichtdeterministische Turingmaschinen und die Vollst~ndigkeit des aus- sagelogischen ErfGllungsproblems .A( H~ussler) 2O III. Probleme, die zum Erf~llungsproblem der Aussagen- logik polynomial ~quivalent sind .P( Schuster) 36 IV. Weitere zum ErfHllungsproblem polynomial ~quivalente kombinatorische Aufgaben .J( yon zur Gathen und M. Sieveking) 49 V. Ein polynomialer Algorithmus zur Bestimmung unaS- h~ngiger Repr~sentantensysteme .E( Specker) 72 VI. Polynomiale Transformationen und Auswahlaxiom .M( FOrer) 86 VII. Spektralproblem und Komplexit~tstheorie (C.-A. Christen) 102 VIII. Untere Schranken fur die Komplexit~t logischer Entscheidungsprobleme .J( Heintz) 127 IX. Ein Entscheidungsverfahren fur die Theorie der reell-abgeschlossenen K~rper (H.R. WHthrich) 138 X. Simulation von Turingmaschinen mit logischen Netzen .M( FGrer) 163 XI° L~ngen und Formeln .E( Specker und G° Wick) 182 Vorwort Der vorliegende Band ist aus unserem Seminar ~ber die Komplexit~t logi- scher und kombinatorischer Entscheidungsprobleme (SS 1973, WS 1973/74) hervorgegangen, Wir danken allen Teilnehmern, insbesondere denjenigen, deren Vortragsausarbsitungen bier zusammengestellt sind, Bei der Redak- tion haben uns die Herren W. Baur, C.-A. Christen, M. FSrer, J. yon zur Gathen, .M Sieveking und H.-U. Wegmann tatkrQ{tig unterst~tzt. Bas Manuskript wurda yon Fraulein Vreni SehkSlziger getippt; wit sind ihr ~Qr die sorg~ltige Arbeit sehr dankbar. E.S. V.S. Einleitung Eine Mange Avon natOrliohen Zahlen heisst "entsoheidbar", wenn es sin Verfahren gibt, welches zu vorgelegtBm ~ in ~ in endlich vielen Sohrit- ten entsoheidets ob aE A oder nicht. Oar Bsgriff sines Verfahrens kann bekanntlich auf versohiedene Arten mathematisoh formuliert warden. Osn folgenden Betrachtungen sei dis yon Turing vorgesohlagene maschinells Oefinition zu Grunds gelegt. Dis- se hat unter anderem den Vorteils dess sis die intuitive Vorstellung der zeitlichen Dauer des Entsoheidungsverfahrens mit Hills der Sohritt- zahl in natOrlioher Weiss zu pr~zisieren gestattet. Eine Mange A ist in polynomialer Zeit sntscheidbar~ gewenn [gsnau dann, wenn] es sine Turingmasohine e und sin Polynom p gibt mit folgenden Eigensohaften: Setzt man die Masohine e aug dis bin~r kodiente Zahl a an und ist ~[a] dis Stellenzahl yon sa so kommt e naoh h~ohstens p[~[a]] Sohrittsn zum Stillstand, und e akzeptiert e gewenn aE A. [Man erh~lt sine ~quivelente und etwas kOrzeres wenn auch weniger einlsuch- tends Definition duroh die Forderung: aE A <~> e akzeptisrt a in p(~[a]] Sohritten. Hier kSnnen also auoh Zahlen akzeptiert warden, die gar nicht zu A gehSren.] Analog zu der Klasse P der in polynomialer Zeit entscheidbaren Mengen wird die Klasse ~ der in polynomialer Zeit berechenbaren Funktionen ds- finiert. Die Klasse P ist abgssohlossen gegenOber den Boole'schen Operatienen Vsreinigung, Ourohsohnitt und Komplement, die Klasse ~ gsgenOber Kom- position. Mit A in P und f in ~ ist auch f-IA in .P Die Begriffe der in polynomieler Zeit entsoheidbaren Mengen und bere- chenbaren Funktionen nehmen in der Komplexit~tstheorie sine wiohtige Stellung sin. Oiee h~ngt einmal damit zueammen~ dass sis weitgehsnd unebh~ngig sind vom spsziellen Maschinenmodell. L~uft sin Algorithmus z.B. aug einer Mehrband-Mehrkopf Turingmaschine in polynomial be- sohrQnkter Zeit eb, so auoh aug einer Einband-Einkopf Masohine. Farrier sind esunter den in der Literatur auftretanden Algorithmen im wesent- lichen gerade die polynomial besohr~nktans for welohe der Einsatz elek- tronisoher Reohenanlagsn sine deutliohe Erweiterung des Anwendungsbe- reiches ermSglioht. Was nun Beispiele enbetrifft~ so ergibt sioh die ZugehSrigkeit zu P for vials Mengen unmittelbar aus ihrer Oefinition: Mange der Kubikzahlens Mange der Z~eierpotenzen, Mange der Fibonaccizahlen. FOr andere Mengen folgt die Zugeherigkeit zu P erst auf Grund sines nioht-trivialen "Kri- teriums". Ein Beispiel hierfOr ist die Mange der Primzahlen der Form 2n-I; die Eigenschaft, sine s~Iche Hersenne'sohe Primzahl zu sein, ist nach dem Kriterium van Lucas in polynomialer Zeit antsoheidbar (Knuth 1geg), FOr viele zahlentheoretisch interessante Mengen ist die Zugeh~rigkeit zu Poffen. So ist zwer bekanntlich entscheidbar, ob sine Zahl a Prim- zahl ist oder nicht; es ist aber nicht bskannt, ob es dafOr sin in ~(a) polynomial beschr~nktss Entscheidungsverfahrsn gibt. Weitere sol- che Merger finder man unter den Wertebereichen yon Polynomen in mehre- ren Variablan (mit Koeffizienten und Argumsnten in ~). Ist z.B. D die 3 3 Menge der Zahlen a den Form x +y , so ist D ersichtlicherweise ent- scheidbar. Des naheliegende Entscheidungsverfahren far eE D, bei dam alia Tripel <a,x,y> mit x<a, y!a aug a = x3+y 3 getestet warden, ist aber yon der Gressenordnung e I/3, also exponantiell in ~[a). {Und es schsint Oberhaupt kein polynomial beschr~nktes Entscheidungsverfahren f~r 0 zu geben.) Anhand der Mange D soll nun sin wichtigsr neuer Begriff eingefShrt werden, Nan danke sich des oben angegebene Entseheidungsverfahren for sine Zahl a einmal durchgefOhrt, Je nach dam Ausgang befindet man sich in ganz verschiedenan Situationen. Ist der Test positiv ausgefallen, 3 3 so liegt sin Tripel <a,x,y> mita = x +y vor. Der Besitz sines sol- chan Tripels armeglicht aber schon den Nachweis f~r aE O in polynomia- let Zeit, indem die Summa x3+y 3 berechnet und mita verglichen wird. Ist andersrseits des Testergebnis negativ, so 18sst sich aus der ge- leisteten Arbeit anscheinend kein kurzer Beweis for a~ O entnehmen. Oieser hQufig auftretende Sachverhalt fOhrt zu den folgenden Definiti- onen: .I Die Turingmaschine e verifiziert a in m Schritten, gewenn es sin x gibt, so dass e den Input <a,x> in h6chstsns m Schritten akzeptiert. Bemerkung. Trotz des Existenzquantors Ober x is't entschaidbar, ob e die Zahl a in m Schritten verifiziert. Oenn in der Zeitspanne m liest die Maschine e h6chstens m Stellen des Inputs <a,x>. Gibt es also Oberhaupt ein x, for welches <a,x> akzeptiert wird, so such sins mit den zus~tzlichen Eiganschaft ~(xj!m. 2. Ein8 Msnge A ist in polynomialer Zeit verifizierbar, gewenn es sine Turingmaschine e und sin Polynom p gibt, so dass gilt: aEA < ' > e verifiziert a in p[~[a]] Schritten. PN ist die Klasse der in polynomialar Zeit verifizierbaren Mengen. RN( steht f~r "nichtdeterministisch polynomial besohr~nkt" - in der Tat kann des x in der srsten Oefinition als sine Art nicht determinisrten Leitfadsns aufgefasst warden.) Die Klasse P ist offenbar sine Teilklasse yon NP. Erstaunlicherweise ist es bisher nicht gelungsn zu entscheiden, ob die beiden Klassen R und PN gleich Bind oder nicht. Wenn in der Mathematik ~berhaupt yon ei- meh "Indizienbeweis" gesprochen warden darf, so gewiss hier f~r die Vermutung PtNP ("Cook'sche Hypothese"); der Laser wird die Indizisn im folgenden ke~nen lernsn, Die Klasse PN ist abgeschlossen gegenOber Vereini~ung und Ourchschnitt; mit A in NP und f in ~ gehSrt auch f-IA zu NP. Unbekannt ist, ob NP komplement-abgeschlossen ist oder nicht. Es ist zu vermuten, dass es Mengen in NP gibt, deren Komplement nicht zu NP ge- hSrt; sin Beweis dafOr wOrde natOrlich die Cook'sche Hypothese bestQti- gen. Und wenn sehon Vermutungen formulie#t werden: Es gibt wohl such Mengen A mit der Eigenschaft, dass zwar A und das Komplement yon A zu NP geh~ren, die Mange A aber nicht zu P gehSrt. Sollte dies zutreffen, so words sich das Bsgriffspaar P-NP in einer wesentliohen Eigensohsft vom Begriffspaar entschsidbare-aufz~hlbars Menge untersoheiden, zu dam ss ja der Definition nach in anger Analogie steht. Dass die Analogie auf alle F~lle nicht vollkommsn ist, zeigt die Tatsa- che, dass es zwar universelle aufz~hlbare, abet keine universellen NP- Mengen gibt - g~be es nQmlich sine solche, so w~ren alle Mengen aus NP polynomial verifizierbar mit Polynomen sines fasten Grades, im Wider- spruch zu (Cook 1970). Trotz dieser Unterschiede ist die Analogie der Begriffspaare yon be- trQohtlichem heuristischen Wert. Uebertr~gt man zum Beispiel die uni- verselle Mange dsr Paste <e,a> ("die Naschine e akzeptiert a") aus der Rekursionstheorie in die PNP-Theorie, so wird man unmittelbar zu einer ~enge V gefOhrt, die zwer nicht universell~ aber immerhin noch NP-voll- st~ndig ist, (O.h. V gehert zu NP und zu jedem A aus NP ~ibt es ein f in ~ mit A = f-Iv.) Dabei ist V folgendermassen definiert: Das Tripel <e,a~2m> geh~rt zu V gewenn gilt: Oie Maschine 8 verifiziert den Input a in m Schritten. Erstens zeigt n~mlioh sine einfache Ueberlegung, dass V in polynomia- ler Zeit verifizierbar ist. {Dabei wird auch klar, warum Tripel m <s,a,2 > und nicht etwa Tripel <e,a,m> verwendet werden.l Ist zweitens A sine Menge aus NP (die etwa durch die Turingmaschine ° e und des Poly- nom p verifiziert wird), so definiere man f durch f(a) = <e ,a,2P(~(a))>. 0 Dann sind aE A und f(a)E V beide gleichbedeutend mit der Aussage "e verifiziert a in p(~(a)) Schritten". o Oie Existenz einer vollst~ndigen Menge V reioht nun zwar nioht aus, um mit Hills sines Oiagonalverfahrens die Cook'sohe Hypothese zu beweisen, abet dooh, um sis auf sine besonders einfaohe Form zu bringen: P NP< >v P (Gleicherweise gilt: Gibt es Obsrhaupt sine Menge A in NP, deren Kom- plement nioht zu NP gehBrt, so let V sine solohe.) Unter der Annahme der Cook'sohen Hypothese ist also V nicht polynomial entsoheidbar. Es liegt nun nabs, Qhnlioh wie in der Rekursionstheorie, die Menge V in interessante mathematische Entsoheidungsprobleme zu transformieren. Wie [Cook 1970) und {Karp 1972) gezeigt haben, gelingt dies auf er- staunlich vielf~ltige Weiss. Ganz allgemein ist ein Entsoheidungsproblem gegeben dutch sin Pear von Mengen (A,B) mit Ac 8 (in der Meinung, dass zu entscheiden is@, welohe b aus B zu A geh~rsn]. Oa die Mengen A, B im allgemeinen keine Zahl- mengen sind~ mOssen sis zuerst als solche kodiert werden. FOr die vor- liegenden Zweoke ist sine Kodierung sine injektive Abbildung von B in ~, deren Bild zu P gehBrt. (O.h. man kann in polynomialer Zeit ent- soheiden, ob sine Zahl die Kodenummer sines Elements von B ist.) Zwei Kodierungen ~ und ~ werdsn als ~quivalsnt betraohtet, gewenn die parti- ellen Funktionen @~ I und ~@-I Einsohr~nkungen von in polynomialer Zeit bereohenbaren Funk@ionen sind. VermBge solcher Kodierungen lessen sich die Begriffe "in polynomialer Zeit bereohenbar", "in polynomieler Zeit entsoheidbar", "in polynomia- ler Zeit verifizierbar" und "vollst~ndig" ohne weiteres auf allgemeine Entsoheidungsprobleme Obertragen. Oas Ergebnis disser Uebertragung h~ngt dabei nur vonder Aequivalenzklasse der gew~hlten Kodierung ab. FOr viele ~engen ist (bis auf Aequivalenz] klar, wie man sis kodieren wird~ da ihre Elements ale WBrter Ober einem endlichen Alphabet gegeben sind. Beispiele hierfOr sind Mengen von Polynomen oder Matrizen Ober den ganzen Zahlen oder Ober einem endlichen KBrper, Mengen yon aussa- genlogischen Formeln, yon Formeln airier Sprache ers@er Stufe. Andera Mengen warden in natOrlicher Weise auf solche zur8ckgefOhrt. Z.B. beschreibt man endliche Relationalstrukturen eines fasten nicht- leeren Typs (Graphen, Gruppen usw.) dadurch, dass man ihre Tr~ger als Anfangsabschnitte der Mange der natOrlichen Zahlen annimmt und die Oia- gramme ihrer Relationen etwa lexikographisch aufz~hlt. Man bemerke, dass dann die L~nge der Kodenummer einer Struktur polynomial besohr~nkt ist in der M~ohtigkeit der Struktur und umgekehrt. Polynomiale Ent- scheidbarkeit und Verifizierbarkeit warden also gemessen an der GrBsse der betraohteten Strukturen. Aus der Liste der yon (Cook 1870] und (Karp 1972J angegebenen NP-voll- st~ndi~en Entscheidungsprobleme greifen wir die folgenden heraus: .I Zu entsoheiden, ob eine aussagenlogisohe Formal erfOllbar ist (bier besteht also die obige Menge B aus allen aussagenlogisohen Formeln, die Mange A aus den erfOllbaren). .2 Zu entscheiden, ob ein Graph G einen k-punktigen vollstQndigen Un- tergraphen besitzt [bier besteht B aus allen Paaren (G,k), A aus jenen mit der verlangten Eigenschaft). .3 Zu entscheiden, ob ein Graph I G isomorph einem Untergraphen eines Graphen 2 G ist. (Die VollstQndigkeit des Problems zu entscheiden, ob zwei Graphen isomorph sind, ist dagegen noch fra~lich.) 4. Zu entsoheiden, ob ein Graph G einen Hamilton-Kreis besitzt. {Dage- gen ist in polynomialer Zeit entsoheidbar, ob G einen Euler-Kreis hat.) .5 Zu entsoheiden, ob ein Graph dreifQrbbar ist. (Oagegen ist in poly- nomialer Zeit entsoheidbar, ob G zweif~rbbar ist.) .6 Zu entscheiden, ob zu einem Paar (U,T) von endliohen Mengen mit Uc 3 T eine Menge W existiert, so dass Wc U und die drei Projektionen 3 T -~- T bijektiv aug W sind. (Oas analoge Problem mit UC 2 T ist in po- lynomialer Zeit entsoheidbar.) .7 Zu entscheiden, ob eine lineare diophantische Gleichung alx1+...+a x = b einen LBsungsvektor aus Komponenten 0 oder I besitzt RR ° (Verlangt man vom LBsungsvektor nur, dass seine Komponenten ganzzahlig sinds so erh~lt man ein Problem, welches in polynomialer Zeit entsoheid- bar ist. Dies gilt sogar for Systeme yon Gleichungen.) Unter der Annahme der Cook'schen Hypothese ist keines d/eser Problems polynomial entscheidber. WQre andererseits die Cook'sche Hypothese falsch, so kSnnte man nicht nut die Probleme I his 7 in polynomialer Ze±t entscheiden, sondern Oberhaupt alle Probleme in NP, seien sie nun vollst~ndig oder nicht, und das mit einer einzigen allgemeinen Methade. Bedenkt man, dass z.B. die meisten algorithmischen Probleme der klassischen Zahlentheorie als Entscheidungsprobleme aus NP interpretier£ werden k~nnen und dass es bisher nur in speziellen F~llen u nd mit speziellen Methoden gelungen ist, polynomiale LBsungsverfahren anzugeben, so erscheint die obige Annahme sehr unwahrscheinlich, Ein weiteres Indiz for die Cook'sche Hypothese kann dar±n gesehen wer- den, dass in einem ganz anderen Zusammenhang (nQmlich in der Modell- theorie) sine Vermutung aufgestellt warden ist, welche die Cook'sche Hypothese impliziert: Ist ~ eine Formel erster Stufe, so ist des Spek- trum van ~ die Menge derjenigen natOrlichen Zahlen ,n for die sin n- zahliges Modell van ~ existiert [Scholz 1952). Die "£pektrum-Hypothese" behauptet, dess as ein Spektrum g±bt, dessen Komplement selbst kein Spektrum ist. Wie (Jones-Selman 1974) gezeigt haben, folgt aus der Spektrumhypothese, dass es Mengen in NP gibt, deren Komplement nicht in NP liegt (und die also sicher nich£ zu P gehSren), Oer im vorangehenden beschriebene Themenkreis wird in den Vortr~gen I-IV und VII dargestellt, Dsr erste Vortrag gibt eine EinfOhrung in die verschiedenen Typen van Turingmaschinen, ihre gegenseitigen Bezie- hungen und die Hierarchic der dureh Zeitschranken definierten Klassen van Entscheidungsproblemen. Im zweiten Vortrag wird die NP-Vollst~ndig- keit des Problems nachgewiesen, zu entscheiden, ob eine aussagenlogi- sche Formel erfOllbam ist. Ausgehend van dieser Tatsache werden in den folgenden beiden Vortr~gen eine grosse Anzahl van weiteren vollst~ndi- gen Entscheidungsproblemen abgehandelt. Oer siebente Vortrag ist dem Spektrumproblem gewidmet. Im fOnften Vortrag wird im Anschluss an .M( Hall 1956) ein polynomialer Algorithmus angegeben, welcher (unter anderem) gestattet, zu einer Fol- ge S 1, 2 S .... , mS van endlichen Mengen eine maximale Teilmenge T yon U S. zu bestimmen, for welche die Ourchschnitte T n S. (1 < i < m) hSch- l 1 - stens ein Element enthalten. Die Existenz dieses Algorithmus mag ein Hinweis darauf sein, dass aueh in F~llen, wo sich zun~chst ein exponen- tieller Suchalgorithmus aufd#~ngt, eine genauere Analyse bisweilen zu