Vajon P != NP?

Előálltak egy ~100 oldalas ÁLLÍTÓLAGOS bizonyítással, miszerint P != NP. Hogy helyes-e, még nem tudjuk.

http://gregbaker.ca/blog/2010/08/07/p-n-np/
http://www.scribd.com/doc/35539144/pnp12pt

OFF:
Nem tudom miért, de pár napja pont egy olyan érzés volt bennem, hogy ezt valaki nemsokára meg fogja csinálni. És lám.

( persicsb | 2010. 08. 09., h – 12:07 )

Kíváncsi vagyok, van-e hiba benne, vagy nincs. Mondjuk én ezt a választ vártam a P?=NP kérdésre.

mármint a felhasználók, kriptográfusoknak a törő fele megőröl, a másik felének meg akkor lenne munkája ha folyton új és új nehezen törhető algoritmusokat kellene kitalálnia, mert megint volt idejük találni valami polinomidejűt a másik felének :)

szóval így legfeljebb nyugdíjba mehetnek :)

ez hogy jön ide? az csak egyetlen módszer a "sok" közt

az hogy fellélegezhetnek vagy idegbajt kapnak vagy megszűnik a szakma épp olyan elvi gondolat mint a !=/= bebizonyítása, ha konstruktív lenne bármelyik valamilyen értelemben, akkor jöhetnének az említett lehetőségek igazából :)

A tobbi modszerrol is (diszkret logaritmus stb.) be kene latni, hogy NP-teljesek. Pont ez a lenyeg, hogy ha be lehetne bizonyitani, hogy leteznek valodi csapoajto-fuggvenyek, akkor NP != P igaz lenne. De ezt eddig(?) nem tudtuk, hogy igy van-e. Mondjuk amig ez a P<>NP bizonyitas nem konstruktiv, meg mindig nem tudhatjuk, hogy az altalunk hasznalt fuggvenyek NP teljesek-e, csak azt, hogy vannak olyan fuggvenyek, amik valoban azok.

ahogy en tudom NP beli, csak nem NP teljes, de FIXME ha nem. wikipediat nezgetettem a temaban, amirol ugye tudjuk, hogy nem a legmervadobb sok esetben :)

ui.: megha ki is derulne, hogy P-bel, akkor is P!=NP miatt van olyan (mas) modszer aminel ellenorzes P-beli de maga az eloallitas NP-beli, csak eppen nem az integer factorization lesz az. ellenben P=NP eseten tetszoleges titkositashoz lesz "tores" P-ben

Csak akkor lesz hozza tores, ha a P=NP bizonyitas konstruktiv, azaz meg is adja a modszeert, hogy k-SAT vagy hasonlo eseteben mikepp kell konstrulani a P-beli algoritmust. Addig csak elmeleti lehetoseg, hogy letezik P-beli algoritmus ra. A lehetoseg igaz, valamilyen szinten letezest is jelent, de nem feltetlenul jelent megvalositast is.

szerintem nem feltetlen kell konstruktiv (azert nem art), ugyanis ha mar elmeletileg tudjuk, hogy van megoldas, akkor mar csak ido kerdese, hogy valaki megtalalja, ellenben ha tudjuk nincses nem is lesz akkor nem keressuk. ez azert eros kulonbseg :) de teny ha lenne egy konstruktiv bizonytas az jelentosen megkonnyiteni (vagy megnehezitene, ez POV fuggo :) ) az emberek dolgat.

"ugyanis ha mar elmeletileg tudjuk, hogy van megoldas, akkor mar csak ido kerdese, hogy valaki megtalalja"
Ez nem igaz. Lehet, hogy maga az algoritmus olyan, hogy a gyakorlati leirasa tobb atomot igenyel, mint amennyi az Univerzumban van. Gondolj bele, a 10^(10^100)-on szamot se tudod tizes szamrendszerben kiirni. Nincs ra eleg anyag az Univerzumban. Az, hogy valami elmeletileg lehetseges, meg nem biztos, hogy megvalosithato.