{"id":1523,"date":"2013-05-18T10:25:24","date_gmt":"2013-05-18T08:25:24","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1523"},"modified":"2025-11-25T23:07:33","modified_gmt":"2025-11-25T22:07:33","slug":"tib-np-vollstandige-probleme-lernziele-ke4-13","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1523","title":{"rendered":"TIB: NP-Vollst\u00e4ndige Probleme (Lernziele KE4 1\/2, Update 2)"},"content":{"rendered":"

Update<\/strong>: Antworten zu den Lernzielen hinzugef\u00fcgt.<\/p>\n

Nach dieser Kurseinheit haben wir mehr als die H\u00e4lfte des Weges geschafft und das Licht am Ende des Tunnels ist schon sichtbar. Hoffen wir, dass es kein Zug ist.<\/p>\n

Die Grundlagen des Beweises der Vollst\u00e4ndigkeit einer Menge haben wir bereits in diesem Beitrag<\/a> skizziert. Dass der Beweis nicht unbedingt schwierig ist wenn bereits ein Problem als \\(NP\\)-vollst\u00e4ndig bewiesen ist und wir eine Reduktion durchf\u00fchren k\u00f6nnen, haben wir bereits gelernt. Schwieriger ist es jedoch die \\(NP\\)-Vollst\u00e4ndigkeit ohne diese Reduktion von einer bereits bekannten Menge zu beweisen. Wir wenden uns in diesem Beitrag den zwei Problemen aus dem Skript zu und tun dies.<\/p>\n

Lernziel 1<\/h2>\n

Wie ist der Vollst\u00e4ndigkeitsbeweis zu 2D-DOMINO?<\/em><\/p>\n

Bevor diese Frage beantworten: Was ist \\(2D-Domino\\)? Es wird auch als Kachelproblem<\/a><\/em>\u00a0bezeichnet. Unter diesem Namen findet sich auch in der Literatur eine Erkl\u00e4rung, wer mit der Beschreibung aus dem Skript nicht weiterkommt. Im Grunde geht es um die vollst\u00e4ndige Belegung des Spielbretts nach bestimmten Regeln. Aber fangen wir erstmal klein an und zerlegen die Definition aus dem Skript:<\/p>\n

\\(N\\in\\mathbb{N}\\)<\/blockquote>\n

Das ist die Gr\u00f6\u00dfe des quadratischen Brettes. Ist \\(N := 4\\), so ist unser Spielbrett \\(4×4\\) Felder gro\u00df.<\/p>\n

\\(S\\subseteq{({\\{0,1\\}}^{+})}^4\\)<\/blockquote>\n

Damit bezeichnen wir den Satz unserer Spielsteine. Ein Spielstein ist gegeben durch ein Quintupel: \\((L,R,O,U)\\in{({\\{0,1\\}}^{+})}^4\\). Nehmen wir an, dass wir z.B. \\(S=\\{\\{0,0,0,0\\},\\{0,0,0,1\\}\\}\\) als Steinsatz haben, so befinden sich in unserem Satz zwei Steine: einer hat gar keine Markierung und einer nur unten (siehe n\u00e4chste Abbildung).<\/p>\n

Update<\/strong>: Barbara hat mich hier auf etwas hingewiesen. \\((L,R,O,U)\\in{({\\{0,1\\}}^{+})}^4\\)\u00a0bedeutet, dass wir \\(L,R,O,U\\) als Worte \u00fcber \\({\\{0,1\\}}^{+}\\) codieren k\u00f6nnen. D.h. wir k\u00f6nnen z.B. auch einen einzelnen Stein mit \\(\\{1011,1111,1000,0001\\}\\) abbilden. Die einzelnen Elemente f\u00fcr \\(L,R,O,U\\) bezeichnen dann die Farbe<\/em> links, rechts, oben oder unten im Stein. Bei einem Wort mit der L\u00e4nge \\(4\\) haben wir somit \\(2^4=16\\) verschiedene Farben, die wir nutzen k\u00f6nnen.<\/p>\n

Bei \\(4\\) Feldern auf dem Stein, die jeweils mit \\(16\\) unterschiedlichen Farben codiert werden k\u00f6nnen, haben wir also \\(16^4=65536\\) unterschiedliche M\u00f6glichkeiten einen Stein zu codieren.<\/p>\n

Ich bin aber eine faule Sau und habe nur die Farben Schwarz und Wei\u00df zugelassen um eine kleinere Menge an Steinen zu haben. Das habe ich nicht so konkret aufgef\u00fchrt, wie ich das eig. gedacht habe.\u00a0Dem Beispiel tut das aber keinen Abbruch.\u00a0Daher schr\u00e4nke ich f\u00fcr mein Beispiel die Menge der Steine hier (im Gegensatz zum Skript, bitte daher also nicht vergessen: im Skript sind die Farben codiert mittels einem Wort \u00fcber \\({\\{0,1\\}}^{+}\\)) ein auf: \\((L,R,O,U)\\in({\\{0,1\\}}^{1})^4\\)<\/p>\n

Die folgende Abbildung zeigt alle \\(2^4\\) M\u00f6glichkeiten f\u00fcr die Belegung der Steine, d.h. wir haben insg. 16 Steine in unserer Menge \\(S\\).<\/p>\n

\"steine\"<\/a><\/p>\n

 <\/p>\n

Kommen wir zur Anfangsbelegung:<\/p>\n

\\(\\alpha: \\{1,…,N\\}^2\\rightarrow S\\cup\\{\\varepsilon\\}\\)<\/blockquote>\n

Mit \\(\\alpha\\) bezeichnen wir die Anfangsbelegung eines Feldes auf dem Brett. Hat unser \\(4×4\\) Brett z.B. die ersten Beiden Felder mit einem vollst\u00e4ndig wei\u00dfen und einem vollst\u00e4ndig schwarzen Stein belegt, w\u00e4hrend alle anderen leer sind, so w\u00e4re \\(\\alpha(1,1) = (0,0,0,0)\\),\u00a0\\(\\alpha(1,2) = (1,1,1,1)\\) und der Rest der Felder \\({}=\\varepsilon\\). Das alles kommt in unser \\(D\\), d.h. als \\(D\\) bezeichnen wir das gesamte Spiel mit: \\(D = (N,S,\\alpha)\\).<\/p>\n

\\(\\beta: \\{1,…,N\\}^2\\rightarrow S\\)<\/blockquote>\n

Hier haben wir eine konkrete Belegung eines Feldes. Bitte beachten, dass die Belegung das leere Feld \\(\\varepsilon\\) nicht mehr mit einschlie\u00dft. \\(D\\) ist l\u00f6sbar wenn wir die Anfangsbelegung auf dem Feld belassen und die restlichen leeren Felder nach folgenden Regeln belegen:<\/p>\n

\\((\\beta(i,j) = (l,r,o,u)\\land\\beta(i,j+1) = (l^{‚},r^{‚},o^{‚},u^{‚}))\\Rightarrow r=l^{‚}\\) und<\/p>\n\\((\\beta(i,j) = (l,r,o,u)\\land\\beta(i+1,j) = (l^{‚},r^{‚},o^{‚},u^{‚}))\\Rightarrow u=o^{‚}\\)<\/blockquote>\n

Kleiner Klopper. Sagt aber nichts anderes aus, als dass zwei Steine zueinander passen m\u00fcssen. Der linke und rechte Stein m\u00fcssen bei der jeweils zueinander liegenden Seite eine Markierung aufweisen. Das Gleiche gilt f\u00fcr den oberen und unteren Stein. Beispiel? Klar doch.<\/p>\n

\"felder\"<\/a><\/p>\n

Wir sehen hier zwei Spielfelder mit \\(N=3\\). Das 1. Spielfeld hat die Belegung:<\/p>\n

\\(\\beta(1,2) = (1,0,0,0)\\),\u00a0\\(\\beta(1,3) = (0,1,0,1)\\) und\u00a0\\(\\beta(2,3) = (1,1,1,0)\\). Folgt daraus, dass \\(r=l^{‚}\\) und \\(u=o‘\\) wie oben angegeben? Versuchen wir es:<\/p>\n

\\((\\beta(1,2) = (1,0,0,0)\\land\\beta(1,3) = (0,1,0,1))\\Rightarrow 0=0\\) und<\/p>\n\\((\\beta(1,3) = (0,1,0,1)\\land\\beta(2,3) = (1,1,1,0))\\Rightarrow 1=1\\)<\/blockquote>\n

Sieht gut aus. Nun f\u00fcr Spielbrett Nr. 2 mit Belegung:\u00a0\\(\\beta(1,2) = (1,0,0,0)\\),\u00a0\\(\\beta(1,3) = (1,1,0,0)\\) und\u00a0\\(\\beta(2,3) = (1,1,1,0)\\)<\/p>\n

\\((\\beta(1,2) = (1,0,0,0)\\land\\beta(1,3) = (1,1,0,0))\\Rightarrow 0=1\\) und<\/p>\n\\((\\beta(1,3) = (1,1,0,0)\\land\\beta(2,3) = (1,1,1,0))\\Rightarrow 0=1\\)<\/blockquote>\n

Ne, hier klappt das leider nicht. Damit ist die angegebene Belegung bei Spielbrett 2 nicht zul\u00e4ssig. Das war es auch schon.\u00a0Klingt spannend. Wollt Ihr das mal spielen? Bitte sehr:\u00a0Tetravex<\/a>. Zumindest ist das Browsergame unserem sehr \u00e4hnlich. Nur sind hier die Steine (die Menge \\(S\\)) hier vorgegeben und nicht nur eine Zeile des Bretts belegt.<\/p>\n

Fragestellung<\/strong>: Wir suchen daher nach einer korrekten Belegung f\u00fcr ein Spielbrett. Es ist schnell einzusehen, dass das Spiel in \\(NP\\) liegt: wir k\u00f6nnen eine Codierung angeben und diese dann in polynimieller Zeit auf Korrektheit testen. Dazu m\u00fcssen wir nur eine Kontrollturingmaschine (\\(KTM\\)) angeben, die eine von uns gegebene Hilfseingabe auf Richtigkeit testet. Um die Belegung zu raten, verwenden wir eine \\(NTM\\).<\/p>\n

Der Beweis der \\(NP\\)-Vollst\u00e4ndigkeit des Dominospiels<\/h3>\n

Wir haben hier zwei Dinge zu zeigen: \\(2D-DOMINO\\in NP\\) und anschlie\u00dfend die \\(NP\\)-H\u00e4rte indem wir ein vollst\u00e4ndiges Problem aus \\(NP\\) auf unseres reduzieren. Haben wir keines, so m\u00fcssen wir den m\u00fchsamen Weg selbst gehen und verzichten auf die Reduktion und beweisen die \\(NP\\)-H\u00e4rte direkt. Aber k\u00fcmmern wir uns zun\u00e4chst um Punkt 1:\u00a0\\(2D-DOMINO\\in NP\\). Dazu reicht es eine \\(KTM\\) (oder \\(NTM\\)) anzugeben, die eine Hilfseingabe in Polynomzeit auf Korrektheit pr\u00fcft (eine \\(NTM\\) r\u00e4t diese Hilfseingabe auch noch von alleine).<\/p>\n

Um eine \\(NTM\\) anzugeben, m\u00fcssen wir zun\u00e4chst das Spiel so formalisieren dass wir die Anfangsbelegung und unsere Steinchen auf das Eingabeband codieren. Die Menge \\(S\\) der Spielsteine wird lexikographisch nummeriert und damit das ganze Spiel \\(D\\) durch ein Wort \\(x\\) \u00fcber \\(\\{0,1,\\#\\}^{*}\\) auf das Eingabeband geschrieben.<\/p>\n

Ein Beispiel w\u00e4re hilfreich: Nehmen wir z.B. das\u00a0Spielbrett Nr. 1 von oben als Anfangsbelegung und basteln und daraus das gesamte Spiel \\(D_1\\):<\/p>\n

\\(\\alpha(1,2) = (1,0,0,0)\\),\u00a0\\(\\alpha(1,3) = (0,1,0,1)\\) und\u00a0\\(\\alpha(2,3) = (1,1,1,0)\\), alle anderen Felder sind leer<\/p><\/blockquote>\n

So haben das folgende Wort auf unserer \\(KTM\\) (ich habe aus Faulheit nicht alle 16 Spielsteine auf das Band codiert, sondern nur den ersten \\(000\\) und letzten \\(1111\\), dazwischen mit Punkten \\(…\\) gearbeitet):<\/p>\n\\(\\gamma D(D_1) = 0\\#0\\#0\\#0\\#…\\#1\\#1\\#1\\#1\\#\\#\\varepsilon\\#1\\#0\\#0\\#0\\#0\\#1\\#0\\#1\\#\\varepsilon\\#\\varepsilon\\#1\\#1\\#1\\#0\\#\\varepsilon\\#\\varepsilon\\#\\varepsilon\\)\n

Zun\u00e4chst codieren wir also alle 16 M\u00f6glichkeiten der Steine, d.h. den Steinsatz auf das Band. Anschlie\u00dfend kommt die Anfangsbelegung \\(\\alpha\\) des Bretts, nachdem wir sie mit \\(\\#\\#\\) von dem auf dem Band ebenfalls codierten Steinsatz getrennt haben. Nicht vergessen: mit \\(\\varepsilon\\) werden leere Felder bezeichnet.<\/p>\n

Die Menge aller l\u00f6sbaren Belegungen nennen wir:<\/p>\n

\\(2D-DOMINO = \\{x\\in\\{0,1,\\#\\}^{*}\\mid x\\in Bild(\\gamma D)\\) und \\({\\gamma D}^{-1}(x)\\) ist l\u00f6sbar \\(\\}\\).<\/p><\/blockquote>\n

Aufdr\u00f6seln: \\(2D-DOMINO\\) besteht also aus dem Wort \\(x\\) \u00fcber dem Alphabet\u00a0\\(\\{0,1,\\#\\}^{*}\\), wobei \\(x\\) ein Bild von \\(\\gamma D\\) und die Inverse von \\(\\gamma D(x)\\) l\u00f6sbar sein muss. \\(\\gamma D\\) ist unsere Funktion, die als Parameter unser komplettes Spiel \\(D\\) (Spielbrettgr\u00e4\u00dfe, Steine, Anfangsbelegung) als Wort bekommt und uns dazu das \\(x\\) (das Spiel \\(D\\) als codiertes Wort) ausgibt. Damit ist \\(D\\) unser Definitionsbereich f\u00fcr die Funktion \\(\\gamma D\\) und \\(x\\) liegt im Bildbereich von \\(\\gamma D\\). Wenn nun auch noch das Spiel \\(D\\) l\u00f6sbar ist (nicht jede Initialbelegung auf dem Spielbrett hat eine L\u00f6sung), so geh\u00f6rt das zum Spiel \\(D\\) codierte Wort zur Menge \\(2D-DOMINO\\). Anhand unseres Beispiels von Spielbrett Nr. 1 haben wir zusammengefasst:<\/p>\n

\\(D_1 = (N,S,\\alpha)\\) (unser Spiel)<\/p>\n

\\(S = \\{\\{0,0,0,0\\}, \\{0,0,0,1\\}, …,\\{1,1,1,1\\}\\}\\) (unsere Spielsteine)<\/p>\n

\\(\\alpha(1,2) = (1,0,0,0)\\),\u00a0\\(\\alpha(1,3) = (0,1,0,1)\\) und\u00a0\\(\\alpha(2,3) = (1,1,1,0)\\) (unsere Anfangsbelegung)<\/p>\n

\\(\\gamma D(D_1) = 0\\#0\\#0\\#0\\#…\\#1\\#1\\#1\\#1\\#\\#\\varepsilon\\#1\\#0\\#0\\#0\\#0\\#1\\#0\\#1\\#\\varepsilon\\#\\varepsilon\\#1\\#1\\#1\\#0\\#\\varepsilon\\#\\varepsilon\\#\\varepsilon\\) (unser Spiel als codiertes Wort \\(x\\))<\/p>\n

\\(x\\in Bild(\\gamma D(D_1))\\) (das Wort ist, wie man oben sehen kann im Bildbereich der Funktion \\(\\gamma D\\)) und<\/p>\n

\\(\\gamma D^{-1}(x) = D_1)\\) (die Inverse \\(\\gamma D^{-1}\\) gibt uns zu jedem \\(x\\) ein \\(D\\) zur\u00fcck, d.h. zu jedem Codewort das zugeh\u00f6rige Spiel. Und das Spiel ist l\u00f6sbar. Es gibt also eine vollst\u00e4ndige Belegung \\(\\beta\\) f\u00fcr das Spiel \\(D_1\\), die die oben genannten Regeln nicht verletzt).<\/p><\/blockquote>\n

Bitte beachtet, dass hier das ganze Spiel \\(D\\)\u00a0ohne<\/strong> zu testende Belegung auf das Band codiert wird. Die zu testende Belegung ist unsere Hilfseingabe \\(\\beta\\). Codieren wir also unser Spiel \\(D\\) zusammen mit unserer zu testenden Hilfseingabe \\(\\beta\\) auf das Band, so k\u00f6nnen wir anhand der Regeln in quadratischer Zeit pr\u00fcfen ob \\(\\beta\\) eine L\u00f6sung f\u00fcr \\(D\\) ist.<\/p>\n

Damit ist die Menge \\(2D-DOMINO\\in NP\\).<\/p>\n

Bitte beachten: im Gegensatz zum vorherigen Beitrag zu KE3<\/a> haben wir hier zuerst die Zugeh\u00f6rigkeit von \\(2D-DOMINO\\) zur \\(NP\\) gezeigt indem wir eine \\(KTM\\) angegeben haben, die mit unserem codierten Wort auf dem Eingabeband und unserer zu testenden Hilfseingabe diese L\u00f6sung \u00fcberpr\u00fcft.\u00a0Nun m\u00fcssen wir f\u00fcr die Vollst\u00e4ndigkeit noch \\(2D-DOMINO\\) ist \\(NP\\)-hart zeigen (ich Wiederhole mich h\u00e4ufig, was die Kriterien f\u00fcr die Vollst\u00e4ndigkeit betrifft, aber besser zu viel als zu wenig).<\/p>\n

Dazu zeigen wir, dass alle Mengen aus \\(M\\in NP\\) auf unsere Problemmenge \\(2D-DOMINO\\) in polynomieller Zeit reduzieren lassen, formal ausgedr\u00fcckt:<\/p>\n

\\({M}\\leq_{pol} 2D-DOMINO\\)<\/blockquote>\n

Denn das ist ja der Charme an der Vollst\u00e4ndigkeit: k\u00f6nnen wir eine vollst\u00e4ndige Menge reduzieren, k\u00f6nnen wir alle reduzieren (f\u00fcr eine Auffrischung, schaut in den letzten Beitrag zu KE3<\/a>). Sobald das getan ist, gilt die Menge \\(2D-DOMINO\\) als \\(NP\\)-vollst\u00e4ndig.<\/p>\n

Das Prinzip der in der KE4 beschriebenen Probleme ist es zu zeigen, dass man zun\u00e4chst f\u00fcr alle Mengen \\(M\\in NP\\) diese auf \\(2D-DOMINO\\) reduziert und dann \\(2D-DOMINO\\) nutzt um es dann auf das Problem \\(SAT\\), \\(SAT\\) dann auf \\(3SAT\\) usw. zu reduzieren und so die \\(NP\\)-Vollst\u00e4ndigkeit der Probleme zu beweisen. D.h. haben wir eine Menge initial als \\(NP\\)-Vollst\u00e4ndig nachgewiesen, so k\u00f6nnen wir durch einfache Reduzierung andere Mengen sofort auch als \\(NP\\)-Vollst\u00e4ndig nachweisen (hier sei auf den Abschnitt zu Cook im Beitrag zu KE3<\/a> verwiesen).<\/p>\n

Zeitbedingt muss ich den Beweis der \\(NP\\)-H\u00e4rte f\u00fcr \\(2D-DOMINO\\) \u00fcberspringen, werde versuchen ihn f\u00fcr \\(SAT\\) und \\(3SAT\\) im n\u00e4chsten Beitrag nachzuholen, da \\(SAT\\) doch h\u00e4ufiger anzutreffen ist als \\(2D-DOMINO\\). Wer eine sch\u00f6ne Beschreibung des Beweises aus dem Skript hat, immer her damit.<\/p>\n

Antwort zum Lernziel<\/strong>: zun\u00e4chst wird wie bei allen Beweisen der Vollst\u00e4ndigkeit gezeigt, dass sich \\(2D-DOMINO\\) in \\(NP\\) befindet indem man ein Verfahren angibt, dass das Problem in nichtdeterministischer polynomieller Zeit l\u00f6st, d.h. eine \\(KTM\\), dass unsere Pr\u00fcfbelegung (sog. Hilfseingabe) auf Korrektheit pr\u00fcft. Anschlie\u00dfend zeigt man die \\(NP\\)-H\u00e4rte von\u00a0\\(2D-DOMINO\\) mittels zwei M\u00f6glichkeiten:<\/p>\n

1. die leichte: wir reduzieren \\(2D-DOMINO\\) polynomiell auf ein bekanntes, \\(NP\\)-schweres Problem indem man ein Verfahren angibt, dass diese Reduktion in polynomieller Zeit schafft oder<\/p>\n

2. die schwere: wenn wir kein Problem haben (Henne-Ei-Problem), m\u00fcssen wir eines angeben, bei dem einzusehen ist, dass es definitiv in \\(NP\\) liegt (ob es praxistauglich ist, ist egal).\u00a0Man konstruiert sich sozusagen ein Problem.\u00a0Auf dieses wird dann\u00a0\\(2D-DOMINO\\) reduziert.<\/p>\n

Stephen A. Cook hat uns die Arbeit aber abgenommen und \\(SAT\\) als \\(NP\\)-vollst\u00e4ndig bewiesen, so dass wir die \\(NP\\)-Vollst\u00e4ndigkeit von \\(2D-DOMINO\\) beweisen k\u00f6nnten wenn wir es auf \\(SAT\\) zur\u00fcckf\u00fchren.<\/p>\n

Lernziel 2<\/h2>\n

Wie beweist man die \\(NP\\)-Vollst\u00e4ndigkeit einer Menge?<\/em><\/p>\n

Antwort zum Lernziel<\/strong>: Doppelt h\u00e4lt besser: F\u00fcr die \\(NP\\)-Vollst\u00e4ndigkeit eines Problems m\u00fcssen wir also zuerst nachweisen, dass es in \\(NP\\) liegt (dazu geben wir eine \\(KTM\\) an, die das Problem in Polynomzeit mit einer gegebenen Hilfseingabe entscheiden kann. Oder eine \\(NTM\\) zum vorherigen Ergebnis-orakeln, denn das orakeln ist das \\(N\\) in \\(NTM\\)). Anschlie\u00dfend muss noch die \\(NP\\)-h\u00e4rte nachgewiesen werden, indem wir ein vollst\u00e4ndiges<\/strong> Problem in Polynomzeit auf unseres reduzieren oder auf Reduktion verzichten und die \\(NP\\)-H\u00e4rte direkt nachweisen.<\/p>\n

Wenn wir also noch kein \\(NP\\)-vollst\u00e4ndiges Problem haben, dass wir reduzieren k\u00f6nnen, haben wir ein klassisches Henne-Ei-Problem. Zum Gl\u00fcck gibt es kluge Leute, die das auch ohne die Reduzierung geschafft haben. Und sie leben auch noch: einer davon ist\u00a0Stephen A. Cook<\/a> mit seinem ber\u00fchmten Satz von Cook<\/a>. In diesem zeigte er die Vollst\u00e4ndigkeit des \\(SAT\\)-Problems. Wir wollen den Beweis mal nachvollziehen, so als Kompensation zum fehlenden \\(2D-DOMINO\\)-Beweis von oben.<\/p>\n

Im\u00a0n\u00e4chsten Beitrag<\/a>\u00a0geht es dann entsprechend um \\(SAT\\).<\/p>\n","protected":false},"excerpt":{"rendered":"

Update: Antworten zu den Lernzielen hinzugef\u00fcgt. Nach dieser Kurseinheit haben wir mehr als die H\u00e4lfte des Weges geschafft und das Licht am Ende des Tunnels ist schon sichtbar. Hoffen wir, dass es kein Zug ist. Die Grundlagen des Beweises der Vollst\u00e4ndigkeit einer Menge haben wir bereits in diesem Beitrag skizziert. Dass der Beweis nicht unbedingt … <\/p>\n

\u201eTIB: NP-Vollst\u00e4ndige Probleme (Lernziele KE4 1\/2, Update 2)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-1523","post","type-post","status-publish","format-standard","hentry","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1523","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1523"}],"version-history":[{"count":65,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1523\/revisions"}],"predecessor-version":[{"id":3532,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1523\/revisions\/3532"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1523"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}