Webtagr - Technologienummer

P vs NP Behauptung widerlegt: Springer-Zeitschrift veröffentlicht fehlerhaften Artikel

2025-08-06

Ein Artikel, der behauptet, ein stärkeres Ergebnis als P≠NP zu beweisen, wurde in der Zeitschrift Frontiers of Computer Science von Springer Nature veröffentlicht und löste Kontroversen aus. Einer der Autoren ist stellvertretender Chefredakteur der Zeitschrift. Die Informatiker Ryan Williams und Eric Allender fanden schwerwiegende Mängel im Beweis, die sogar bekannten Algorithmen widersprechen. Sie reichten einen Kommentar ein, in dem sie die Rücknahme des Artikels forderten, doch der Chefredakteur lehnte ab und stimmte nur der Veröffentlichung einer überarbeiteten Version ihres Kommentars zu. Dieser Vorfall zeigt schwerwiegende Probleme im Peer-Review-Prozess der Zeitschrift auf und weckt Bedenken hinsichtlich des Rufs der Zeitschrift. Dies ist eine Technologie-Nachricht.

(blog.computationalcomplexity.org)

Technologie

Gödel-Preis für explizite Zwei-Quellen-Extractors

2025-06-09

Der Gödel-Preis 2025 wurde an Eshan Chattopadhyay und David Zuckerman für ihre bahnbrechende Arbeit "Explizite Zwei-Quellen-Extractors und resiliente Funktionen", veröffentlicht in STOC 2016 und Annals of Math 2019, verliehen. Diese Arbeit verbessert die Konstruktion von Ramsey-Graphen erheblich und erreicht eine exponentielle Schranke, die frühere Methoden übertrifft. Das Ergebnis wird für seine Bedeutung in der Derandomisierung und seine überraschende Anwendung in der Ramsey-Theorie gelobt und löst Debatten über seine doppelte Bedeutung in Pseudorandomness und Kombinatorik aus.

(blog.computationalcomplexity.org)

Entwicklung Ramsey-Theorie Derandomisierung

Erdbebenartiger Wandel in der Algorithmussimulation: Speicher-Durchbruch

2025-06-07

Ein bahnbrechendes Ergebnis hat die Grundlagen der Algorithmussimulation erschüttert. Die neue Forschung von Ryan Williams zeigt, dass alle Algorithmen mit deutlich weniger Speicher simuliert werden können als ihre ursprüngliche Laufzeit, eine enorme Verbesserung gegenüber den bisher besten bekannten Ergebnissen. Diese Entdeckung nutzt einen speichereffizienten Baumbewertungsalgorithmus von Cook und Mertz, der die Berechnungen der Turingmaschine intelligent segmentiert und eine endliche Feldcodierung verwendet, um eine nahezu quadratische Verbesserung der Raumkomplexität zu erzielen. Obwohl die Zeitgrenze nicht erhalten bleibt, hat dieses bahnbrechende Ergebnis tiefgreifende Auswirkungen auf die Komplexitätstheorie und eröffnet Wege für zukünftige Forschung, wie z. B. die weitere Reduzierung der Raumkomplexitätsgrenzen, die möglicherweise zur Trennung der Komplexitätsklassen P und PSPACE führt.

(blog.computationalcomplexity.org)

Entwicklung Algorithmuskomplexität