P≠NP!

Niekto potrebuje dokaz, niekomu staci zdravy rozum a predpoklad.

Je fakt, že podstatně větší bomba by vybuchla, kdyby se dokázalo, že P=NP.
Zdravý rozum nepřeceňuju, například na Banachův-Tarského paradox fakt nestačí

Urcite staci, len to treba pochopit (nemam teraz na to cas studovat ten paradox)
Mne osobne pride divne ze kazdy chce cosi exaktne dokazovat ked svet evidentne neni exaktny ani trochu (vid kvantova mechanika a princip neurcitosti :) To je lahoda :) Ja osobne dokazy neznasam a riadim sa zdravym rozumom, a dokazovacich docentov som mal kedysi chut niecim ovalit :)

Jenže zdravý rozum se často plete. A dost lidí stále špatně věří zdravému rozumu a to i v případě, že se jim předloží srozumitelný důkaz opaku.

to potom neni zdravy rozum :)

P.S. kazdemu zdravemu cloveku je jasne ze P sa nerovna NP aj bez dokazu. Druha vec je ze aj ked nieco dokazes, tak to este neznamena ze to aj plati (dokaz mohol byt zalozeny na chybnych predpokladoch. Napr. newtonova fyzika neplati, a pritom vsetko v nej bolo "dokazane")

Oni jsou ale stále přesvědčeni, že to zdravý rozum je. Důkazy jsou vhodné právě pro ověření zdravého rozumu.

To, že newtonova fyzika tak úplně neplatí, se vědělo v podstatě od začátku. Stejně tak neplatí velké množství teorií. Zatím postačuje, že platí ve většině případů, alespoň mají vědci co dělat při zpřesňování.

Jéje, takovejch znám, až hanba...

a to sme este nedosli k najvyssej lige - pinokio paradox

vole

jo, to mi připomnělo knížku Raymonda Smullyana nazvanou Jak se jmenuje tahle knížka?. Je to moc pěkné počteníčko..

Modifikovaný Banach-Tarský by se hodil. Třeba bankovky nebo na měděné rýny. Navíc, když výsledné dva kusy je možno použít jako základ pro další fázi (a získat 4, atd.)

Tak já jsem to začal číst, ale skončil jsem u tohohle:

Pokud jste se s touto informací nepokojili

Fakt nevím, jak to souvisí s kojením - o tom, že pokojit se opravdu nedokážu, už ani nemluvím.

radujme se a šifrujme :)

Nerozumím tomu.

Četl jsem si v živáckém odkazu o použití/pomoci v kryptografii. Domnívám se, že u Vernamovy šifry je ale naprosto jedno, zda mezi P a NP platí nerovnost či rovnost. Stejně se nedá prolomit

To je sice pravda, ale tahle šifra je naneštěstí nepraktická: jak chceš bezpečně distribuovat příjemci klíč, navíc pokaždý?

Snad pri takmer kazdych dnesnych sifrach sa posiela kluc. Finta je v nesymetrickom kluci (symetricky kluc mozes zakodovat nesymetrickym sposobom a poslat :)

IMHO ale ta sifra o ktorej tam pisal L-Core je slaba a prelomitelna pri vacsom mnozstve dat. Problem je totiz velkost kluca, je nezmysel mat kluc velky ako samotne data (to by som mohol rovno poslat nesymetricky zakodovane data, namiesto kluca), a pri kluci mensom ako data sa to da prelomit analyzou pocetnosti pismen, staci vediet velkost kluca (co spravny KGB spion ma vediet, analyzou prenesenych dat alebo od manzelky nepriatela :)

Stačí se domluvit ústně, že (binárním) klíčem bude konkrétní jakýkoliv soubor na internetu (obrázek, hudba, binárka nebo text... cokoliv). Třeba od pozice 14.548 bajtu. Pak už stačí jen jednoduchá utilita na transformaci bajt po bajtu.

Pochopitelně neočekávám, že takto se bude šifrovat 700MB porno, ale holý text.

Ked sa budes domluvovat tak bude KGB spion odpocuvat telefon.

A ked sa domluvios len raz a bdues tak kodovat viac sprav, tak je to prelomitelne velmi lahko (lebo kazda sprava zacina stejnym klucom).
Kdeze, take sifry su v praxi slabota. To mas jak nemecku Enigmu vo vojne, ked anglicania odkodovavali nemecke spravy rychlejsie jak samotny nemec prijemca :D

Každá další zpráva musí být šifrována novým klíčem. Nebo stejným souborem, ale od pozice znaku, který doposud použit nebyl. Při textových zprávách o velikosti třeba tisíce-desetitisíce znaků (bajtů) by obyčejná empétrojka mohla vydržet docela dlouho.

Problém je ve velké nepohodlnosti. Pokud se tohle překousne, není Vernamova šifra prolomitelná ani teoreticky.

Takym sposobom jak to popisujes ty, by bola neprelomitelna akakolvek sifra, aj obycajne XOR. Cely problem je prave v tom kluci ktory podla teba musi byt stejne dlhy ako plaintext, a nesmie sa opakovat, a musis sa nejak dohodnut s prijemcom, co je v praxi problem takmer neprekonatelny (az prekonas tento problem, tak vymyslis vpodstate novu sifru)

P.S. jedine ak by si vedel detekovat odposluch kluca, jak sa pise na tej wikipedii, tak by sa to dalo pouzit. Detekovat odposluch ale dnes neni mozne, a dokonale vylucit sa to nebude dat nikdy, kvoli moznosti man-in-the-middle.

no to teda neni jedno, ted jsme pomoci ruznech redukci prevadeli mezi sebou NP problemy, coz melo bejt jako neco, co melo dat zaklad tomu, ze kdyby se na jeden NP nasel P algoritmus tzn NP=P, tak bychom dikdy temto prevodum/redukci dokazali v P spocitat libovolne NP. A ted se krasne ukazalo, ze to cele bylo na picu

nechapu proc do toho motate sifrovani, to s tim ma opravdu, ale opravdu malo spolecneho, toto je pouze matematicky doukaz toho ze P!= NP a pro sifrovani to nema zadnej dopad. Zadnej algoritmus P jsme nemeli, nemame a tohle je jen matematicky dukaz, ze ho mit nemuzeme a nebudeme. Krome nobelove ceny, prepisu historie matematiky, vysrani se na prevody NP mezi sebou (protoze je to k nicemu), rozpadu nekolik oboru, prepisu prednasek na VŠ... kazdopadne na sifrovani to naprosto zadnej dopad nema, mozna bude jen par neznalcu a blaznu klidneji, prestoze k tomu nemaj zadny racionalni duvod.

Pokud je důkaz korektní, pak se jedná bez diskuse o významnou událost aspoň pro mě.
Že jsme to tušili ( někdo přímo věděl), je velmi pěkné.
Pokud někdo dokáže nahlédnout Pythagorovu větu ( o jejíž užitečnosti nepochybovali ani ve starověku) zdravým rozumem - klobouk dolů, já hlupáček si důkaz radši rozkreslím.

Ad důkazy :
Důkaz je posloupnost formulí, které odvozujeme zadanými pravidly z daných axiomů.
Axiomy si sice můžeme položit, jaké chceme, ale určitě chceme vycházet z takových, jejichž důsledky by nebyly v příkrém rozporu např. s empirií nebo něčím, čemu dáváme přednost ( vyhýbám se nebezpečnému spojení zdravý rozum). Důkaz, že 1+1=8 může být v nějakém systému správný, ale tvrzení by mou přítelkyni nepřesvědčilo. Ona nečte ani mé důkazy a tvrzení ve "správných systémech".

Situace nemusí být v případě některých axiomů tak jasná : nepřijmeme-li v matematice tzv. axiom výběru, nedokážeme mnohá základní tvrzení analýzy.
Přijmeme-li axiom výběru, dokážeme např. zmíněný Banach-Tarského paradox.
http://en.wikipedia.org/wiki/Banach-Tarski_paradox

Z hrášku složíme celé Slunce, aniž bychom něco deformovali či přidali. Z axiomu výběru ( stačí o drobet slabší axiomek) plyne existence neměřitelné množiny a neštěstí je na světě. Ale ono se přece o žádné neštěstí nejedná : svět je zase o něco zajímavější a je jenom dobře, že jej matematika ( ač ji mám rád) nedokáže popsat dokonale.