Ist NP vollständig?
Steffans Aussage (e) können wir streng genommen weder bejahen noch verneinen. Vielleicht ist Ralph ja auch mehr ein Teemensch und mag gar keinen Kakao (oder zumindest keinen, der von Steffan gekocht wurde).
Ich jedenfalls wäre sehr misstrauisch, wenn mein jüngerer Bruder mir freiwillig einen Kakao machen würde 
Steffans Aussage (e) können wir streng genommen weder bejahen noch verneinen. Vielleicht ist Ralph ja auch mehr ein Teemensch und mag gar keinen Kakao (oder zumindest keinen, der von Steffan gekocht wurde).
Ich jedenfalls wäre sehr misstrauisch, wenn mein jüngerer Bruder mir freiwillig einen Kakao machen würde
Ich glaube nach 3 Stunden und 24 Minuten Nordpolkälte wird kaum jemand etwas gegen einen schönen warmen Becher Kakao haben
Sehr hübsche Aufgabe; solche Problemstellungen machen doch immer wieder Spaß! Dank [...] war die optimale Lösung auch nicht sooo schwer zu finden, und der Rest folgt dann eigentlich schon "durch scharfes Hinsehen".
Nachdem mein jüngerer Bruder doch noch in den anderen Postämtern rumschlumpft, mach ich mir nun einfach selbst einen Kakao mit einer Prise Lebkuchengewürz.
Die Knobelei hat Spaß gemacht, probiert es unbedingt aus, trotz dem auf den ersten Blick chaotisch aussehendem Netz!
Wow, ich bin beeindruckt von jpvee und Mathemagierin. Das war schnell! 
Ja, dank [...] Der Rest ergibt sich dann von selbst.
Aber eine schöne Aufgabe, ich mag es, so ein bisschen "herumzuoptimieren" [...] 
Eine wunderschöne Aufgabe, mit einer super formulierten Aufgabenstellung (sehr schön) - und sogar praxisbezug. Danke, gefällt!
Ist NP vollständig?
I hope you are okay with some English.
This question is complicated. It requires a longer preamble to be asked, and also to be answered. Any single challenge itself doesn't really belong to complexity classes (such as P, NP, NP-hard, NP-complete, Co-NP, etc.). Instead types of challenges, which we can call problems, can belong to certain complexity classes.
To start answering this question, we would first need to specify which type of challenge we are talking about. Which problem this is.
Example: the shortest route from Berlin to Venice is a single challenge, and doesn't really have a complexity class. The type of this challenge is the Shortest-Path-Problem on a euclidean graph, which certainly has a complexity class instead. The difference here is that the first one has a single answer, whereas the second one requires a generalized solution strategy.
Later on, when this challenge isn't so fresh, we will be able to tell you more about this whole thing 
Schöne Aufgabe! Ein Text der genau richtigen Länge, fachlich korrekt und unterhaltsam. Und sogar mit einer Maßstabsgerechten Skizze.
Zwar habe ich nur eine Lösung, aber ich bin mir nicht sicher, ob es die einzige ist (Ist Petras Weg eindeutig?)
Handelt es sich hier zufälligerweise um die TransSibirische Postroute? hmm..
Ich habe [... xxx...] und dann [... xxx ... xxx...] . Also -räusper- gerne mehr solche Aufgaben 
Mit Wurmlöchern wäre es sogar in unter 3 Stunden gegangen! Aber ohne Einstein und Rosen mussten Ralph und Steffan mit zwei f auf jegliche Abkürzungen verzichten.
Trotz der Parallelen zur Aufgabe hinter dem 11. Türchen hat mir auch das heutige Rätsel wieder viel Spaß gemacht.
Vielen Dank an die Aufgabensteller!
Auch ich finde diese Aufgabe sehr gelungen!
Im Vergleich zu ähnlichen Aufgaben der vergangenen Jahre wusste man hier auch, wann man mit dem Optimieren aufhören konnte, was die Beurteilung der eigenen Lösung deutlich einfacher macht.
Ich finde Graphoptimierungsaufgaben oft nicht so schön, weil sie oft zu einem Branch-and-Bound-Ansatz verleiten (der dann oft in Branch-everything ausartet) und man dann schnell mit gefühlt 100 Fallunterscheidungen zu kämpfen hat.
Die beiden Graphoptimierungsaufgaben haben die oft sehr aufwendigen und arbeitsintensiven Optimalitätsbeweise schön umgangen weil man mit den 24h in Aufgabe 11 und 3h24 in dieser Aufgabe mit den Zielwerten arbeiten kann und fertig ist, wenn man die Werte gefunden hat.
Die Aufgabe heute hat deshalb unerwartet viel Spaß gemacht.
einem Branch-and-Bound-Ansatz verleiten (der dann oft in Branch-everything ausartet)
When branch-and-bound becomes branch-everything it means that you are not actually doing the bounding part. A key component of b&b is that you are able to prove that all of the branching under a certain node will not be better than the solution at that node. Therefore then you can avoid exploring a certain branching of the search-tree if you have already found a feasible solution that is better than the solution at the root of that branching.
Eigentlich sehr schön (wegen der Zahlen und der Antworten), hab mir nur ziemlich einen abgebrochen.
Dafür können die Aufgabensteller aber nix.
Also: tolle Aufgabe
Für mich waren vielen Aufgaben der letzten Tage sehr schwer (bin zum ersten Mal dabei) und ich fand daher diese echt schön, da man gut auf die Lösung kommen konnte und wie andere schon gesagt haben, sich dann auch sicher war.
Irritierend fand ich nur einige der Aussagen von Steffan und Ralph. Ich wusste nicht immer genau auf was sich welche bezogen haben...
Insgesamt aber wieder eine schöne Aufgabe! Danke an die Aufgabensteller und das Mathekalender-Team! Es ist echt toll jeden Tag neue Aufgaben zu sehen und obwohl manche etwas kniffliger sind, versüßt der Aha-Moment den Abend und man kann stolz ins Bett gehen xD
Bei dieser Aufgabe hatte ich entweder ein Riesenglück oder aber eine gute Intuition: [...] Jetzt bin ich gespannt auf die Herleitung im Lösungsheft.
Bei dieser Aufgabe hatte ich entweder ein Riesenglück oder aber eine gute Intuition: [...] Jetzt bin ich gespannt auf die Herleitung im Lösungsheft.
This is very good! Try thinking what you would tell a computer if you wanted to teach it how to solve this kind of problems in general, for maybe much larger networks, or with many more elves. There are straight-forward solution strategies, but oftentimes it is also better to use what you used: intuition! But then...what is intuition? And how do you teach it? And how do you teach it to a computer???
It's possible, sometimes, a little bit 