Informatik

Millenium-Problem gelöst? N != NP

0

Als jemand der Informatik studieret und dabei die theoretische Aspekte liebt, hat mich heute ein kleiner circa 50 Wörter langer Artikel in der c’t 18/2010 in helle Aufregung versetzt. (Ausführlicher Artikel von heise siehe Link am Ende)

Demnach soll ein amerikanischer Wissenschaftler, der bei HP Labs angestellt ist, das N-NP-Problem gelöst haben. Dieses Problem wurde mir wohl schon im ersten Semester vermittelt. Meine Professoren nannten es als eines der schwierigsten Probleme unserer Zeit, das nicht bewiesen oder widerlegt werden kann (konnte?). Die Frage ist ob sich Probleme, die mit deterministischen (streng algorithmisch ohne Zufallswahl) Turing-Maschinen (Beispiel: Computer) nur in nicht-polynomieller Zeit lösen lassen, vielleicht doch polynomiell lösen lassen. Alle Probleme, die sich in polynomieller Zeit mit einer deterministischen Turing-Maschine (Computer) lösen lassen sind in der Menge P, alle die sich nur mit einer nichtdeterministschen Turing-Maschine (in einem Zwischenschritt wird zufällig das richtige Vorgehen erraten) in polynomieller Zeit lösbaren Probleme in NP. Die Frage ist also ist P gleich zu NP.

Da das Problem so schwierig ist, gehört es zusammen mit sechs (eins wurde bereits 2002 gelöst)) fünf anderen offen Fragen zu den sieben Millennium-Problemen, deren Beantwortung dem Clay Mathematics Institute eine Million Dollar wert ist. Vinay Deolalikar soll das Kunststück der Lösung jetzt gelungen sein. Nach seinem Beweis gilt P != NP. Sollte sich das als wahr herausstellen, sind typische NP-Probleme wie das Travelling-Salesman-Problem (weitere fallen mir auf Anhieb nicht ein) in akzeptabler (polynomieller) Rechenzeit nicht lösbar. Leider hat ein Forscher schon Bedenken angemeldet und zwei fatale Fehler benannt. Für einen normalen Student, wie mich, ist wahrscheinlich weder der Beweis noch die Fehler nachvollziehbar, dennoch ist es enorm spannend. Sollte sich der Beweis erhärten, ist ein Grundproblem, dass für mich als für immer offen galt, nicht mehr offen.

Artikel:

Standardisiertes Internet noch in weiter Ferne

0

Vor ein paar Wochen bin ich über einen interessanten Artikel in der c’t gestoßen, man kan diesen aber auch auf der Internetseite von heise nachlesen. Dort wird von einer Untersuchung von URLs durch Opera berichtet. Diese Untersuchung hat unter anderem circa 3,5 Millionen Seiten daraufhin untersucht ob sie w3c-konform sind. Opera hat nun also eine Statistik veröffentlicht, die Aussagen darüber macht wie stark sich Internetseitenbetreiber an CSS, HTML 4.0 oder XHTML halten.

Nach der Statistik sind nur 4,1 Prozent der von Opera untersuchten Seiten w3c-konform. Daraus ergibt sich eigentlich nur eine Frage: Warum sind das so wenige. Hier kann man eigentlich an 3 Punkten ansetzen:

  1. Internetbetreiber wissen nicht, wie HTML aussieht. Dies trifft aber eigentlich nur noch auf ältere Seiten zu, bei denen die Betreiber gerade mal genug Kenntnis haben um ihre kleinen, persönlichen Inhalte online zu stellen. Wer heute was eigenes haben will nimmt ein Kit (zum Beispiel wordpress) und benutzt eine Web 2.0 Anwendung wie StufiVZ oder myspace. Jedoch habe ich bei letzteren keine Ahnung von der Konformität habe.
  2. Die w3c-Validatoren sind einfach zu schlecht. Diese Idee kam mir gar nicht. Ich habe dazu nur einige Kommentare zum Artikel auf heise gelesen und dort wird gesagt, dass dieser schon kaputt geht, wenn man javascript verwendet. Was aber absolut nicht stimmt. Meine Internetseiten verwenden javascript und kommen beim Validator durch.
  3. Die großen Firmen sind an keiner Standardisierung interessiert. w3c ist eine Non-Profit Organisation und ihre finanziellen Mittel sind deshalb begrenzt. Sie wollen das Internet standardisieren, aber warum haben sie dann keinen Browser mit Referenzimplementierung. Wer heute mit dem neusten css arbeitet, muss immernoch einige Zeit darauf warten, dass das gewünschte auch angezeigt wird. Er ist somit dazu gezwungen, dass zu implementieren, was die Browser können und damit orientiert er sich an die Implementierung der Browserhersteller und diese lassen oft Lücken um slappy Code verarbeiten zu können. Auf der anderen Seite implementieren sie manches gar nicht. Würden alle Browser perfektes XHTML verstehen und alle gleich umsetzen, dann würden auch die Internetseitenbetreiber durchweg auf XHTML setzen und dies gern verfolgen. Daran sind die Browserhersteller aber nicht interessiert, wenn alles überall gleich aussieht, dann hebt sich ja kein Browser mehr ab.

Neben dieser Ãœberlegung fand ich noch einige weiteren Zahlen interessant. WordPress zum Beispiel stellt zu 9% standard-konformen Code. Nur typo3 kann es da schlagen unter den untersuchten Content Management Systemen. Auf der anderen Seite gibt es ja auch Programme, mit denen man Internetseiten erstellen kann. Apples iWeb liegt dort mit unglaublichen 81,9% auf Platz 1. Der unter Webdesignern oft genutzte Adobes Dreamweavers HTML kommt auf schlappe 3,4% und Microsofts Frontpage auf traurige 0,6%.

Wer also standard-konforme Seiten bauen will, sollte sich einen vernünftigen texteditor zur Hand nehmen, der HTML, CSS und JavaScript highlighten kann. Nur so hat man die nötige Kontrolle.

Go to Top