Mathekram

Mathematik rein und angewandt, erforscht und unterrichtet (ein Matheblog)

Mal wieder ein bisschen Wind um P und NP

Posted by Modulix - August 27, 2010

Damit es nicht langweilig wird, gibt seit kurzem ein bisschen Aufregung um einen möglichen „Beweis“ der P/NP-Vermutung. Sogar der Spiegel berichtet darüber, ein Wiki existiert dazu ebenfalls bereits. Offenbar gibt es Zweifel an der Richtigkeit des Beweises. Allerdings wäre es ganz interessant zu erfahren, ob der Beweisansatz wenn schon nicht den Beweis liefert, so doch einen originellen Beitrag bedeutet, den nachzugehen lohnenswert wäre.

Terence Tao liefert in einem Kommentar zu einen Blog-Beitrag ein paar (mir allerdings unverständliche Anhaltspunkte):

„k-SAT (or more generally, any non-empty solution space of an NP problem) supports ppp distributions (by starting with the uniform distribution on \{0,1\}^n, and then returning some default solution if one falls outside the solution space). ppp supports seem to be close to something like a “polynomially computable image of a cube”, but I do not know the precise characterisation.

In order to support a pp distribution, the behaviour of the solution space in one of the variables (a terminal one in the pp factorisation) must depend on at most a polylog number of the other variables. Thus for instance the set EVEN of n-tuples (x_1,…,x_n) that add up to 0 mod 2 does not support pp, and more generally neither does a typical solution to a XORSAT problem. From the known clustering properties of SAT I can well believe that the same is also true for SAT in the hard phase, and it is likely that Deolalikar’s paper contained a proof of this fact.“

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

 
%d Bloggern gefällt das: