Názory k článku Jak dlouho nám vydrží dnešní šifrovací metody?
-
Článek je starý, nové názory již nelze přidávat.
- Podle hodnocení
- Podle vláken
- Nejnovější
-
Pavel Chromý (neregistrovaný)Malé upřesnění dvou pojmů, které autor článku zamíchal, patrně měl na většině míst článku na mysli probmémy NP-těžké, nikoliv NP-úplné. Rozdíl je následující:
Problém, který neumíme řešit v polynomiálním čase nazýváme NP-těžkým. Problém, který je NP-těžký a navíc lze na něj (v polynimiálním čase) převést všechny ostatní NP-težké problémy nazýváme NP-úplným. To znamená, že třída NP-úplných problémů je podmnožinou třídy NP-těžkých problémů.
Důsledek:
Pokud by bylo nalezeno polynomiální řešení kteréhokoliv NP-úplného problému, mělo by to dalekosáhlé důsledky - vyřešilo by to totiž všechny NP-těžké problémy v polynomiálním čase (díky zmíněné převoditelnosti). Toto o NP-těžkých problémech obecně neplatí.
Co se týče faktorizace, tak zatím (pokud je mi známo) nikdo nedokázal, ža je to problém NP-úplný (je tedy pouze NP-težký). -
EL (neregistrovaný)No, to jste trochu pomotal, i když bych řekl, že se v tom trochu orientujete. Já mám už složitost nějaký pátek za sebou, tak to snad moc nepopletu :-)
V zásadě máme různé třídy problémů - P, NP, P-SPACE..., které obsahují takové problémy, které odpovídají definici té třídy, tj. u NP problémů jsou to takové problémy, které umíme řešit nedeterministickým Turingovým strojem s polynomiální složitostí (proto sem patří i všechny problémy z P například).
Třída problémů, kterým říkáme NP-těžké je taková, kde na každý problém z této třídy umíme polynomiálně převést libovolný jiný problém z třídy NP. Tj. NP-těžký problém vůbec nemusí být ve třídě NP.
NP-úplné problémy jsou takové problémy, které jsou NP-těžké a zároveň patří do třídy NP.
Jinak afaik je v současnosti situace taková, že všechny známé NP problémy jsou NP-úplné nebo patří do P a vztah mezi P a NP není znám. -
Jan Němec (neregistrovaný)Když už se tady pokoušíte machrovat, tak se předtím podívejde do skript nebo zápisků. Mám matfyz už pár let za sebou, ale že "Problém, který neumíme řešit v polynomiálním čase nazýváme NP-těžkým" nebo že "Co se týče faktorizace, tak zatím (pokud je mi známo) nikdo nedokázal, ža je to problém NP-úplný (je tedy pouze NP-težký)" je blbost a "všechny známé NP problémy jsou NP-úplné nebo patří do P" řekněme neodpovídá převažujícím názorům v současné teoretické informatice. Doufám, že jsem taky nenapsal nějakou koninu :-)
-
EL (neregistrovaný)Ad "všechny známé NP problémy jsou NP-úplné nebo patří do P". Mno, to není názor, to je fakt, ne? Jakýkoliv zatím známý NP problém, pro který neznáme polynomiální algoritmus (nebo neexistuje:-) je NP úplný.
Nebo znáte NP problém, který není NP úplný? (to nemyslím jako provokaci, jenom jako dotaz) -
Jan Němec (neregistrovaný)Ad "všechny známé NP problémy jsou NP-úplné nebo patří do P". Osobně se (nemám to ze své hlavy - zkuste se podívat třeba na wikipedii na články o faktorizaci) domnívám, že právě faktorizace patří do NP - P a není NP těžká. Dokázat (ani vyvrátit) to samozřejmě nikdo neumí.
Ad "Nebo znáte NP problém, který není NP úplný". Ano, znám například velmi elementární problém - na libovolný vstup vrať 1. -
EL (neregistrovaný)Ad "Nebo znáte NP problém, který není NP úplný".
Ale notak, vždyť tam někde píšu, že ty NP problémy jsou buď NP-úplné nebo patří do P, což je přesně váš argument.:-)
Ad faktorizace - matně si vzpomínám na nějaký článek nějakého Inda, který se jmenoval "Primes in P", ale detaily se mi úúúplně vykouřily z hlavy:-( -
Jaroslav.Pinkava (neregistrovaný)Primes in P - ten výsledek byl skutečně významný, ale týkal se jiného problému - dokazování prvočíselnosti, tj. v polynomiálním čase lze dokázat, že dané číslo je - či není - prvočíslem. Jestliže o nějakém čísle dokáži, že není prvočíslem, ještě neznamená, že ho umím faktorizovat.
-
Jan Němec (neregistrovaný)http://en.wikipedia.org/wiki/Integer_factorization konkrétně píšou, že
"It is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete. If it could be proved that it is in either NP-Complete or co-NP-Complete, that would imply NP = co-NP. That would be a very surprising result, therefore integer factorization is widely suspected to be outside both of those classes. Many people have tried to find classical polynomial-time algorithms for it and failed, therefore it is widely suspected to be outside P."
Takže faktorizace asi opravdu nebude NP-úplná ani z P. -
Blesk (neregistrovaný)Ale Petre, ze reknu Cerne, ze si ze slozitosti nic nepamatujes??? Priklad problemu, ktery neni znam ze by byl v P, je v NP, ale neni NP uplny (resp. neni znama polynomialni casova redukce) je napriklad jiz zminovana faktorizace, dale treba Graph Isomorphism a nekolik dalsich.
Pokud jde o predchozi, NTM, PSPACE a podobne veci bych sem netahal, jinak skoncime u strukturni slozitosti a tomu uz nebude rozumet nikdo :-) -
EL (neregistrovaný)Vidis, tohle uz si treba nepamatuju:-)
Tak nejak jsem mel zafixovane, ze vsechny zname NP problemy (tj. ty u kterych nevime, jestli jsou v P) jsou NP-uplne (coz mimochodem neni sporne tvrzeni s tvym, ale pouze dira v me pameti:-)))
A strukturni slozitost bych sem vubec netahal. To jsem byl jeste mlady a hloupy a zapisoval si takovehle osklive veci:-))) -
Pavel Chromý (neregistrovaný)Mate pravdu, chtel jsem se vyhnout Turingovym strojum a jeste vice jsem to pomotal spletenim pojmu "NP-tezky", za coz se omlouvam.
Je pravda, ze NP-tezke nemusi byt v NP, treba znamy halting problem.
Vsechno, jak to pisete je to myslim spravne, az na posleni vetu:
Co se tyce toho jestli NP\P=NP-uplne, tak se predpoklada, ze to pravda neni a faktorizace je prave problem, o kterem je domnenka ze neni v P ani NP-uplny. Bylo zmineno, ze faktorizace je v NP i co-NP, takze jeji NP-uplnost by znamenala, ze NP=co-NP, cemuz se "neveri".
-
Milan Prokeš (neregistrovaný)Ten problém nejde vyřešit v rozumném čase na 100 %. Takže je jasné, že každá metoda je pouze přibližná a tedy i metoda elastické neuronové sítě. Sem tam to úplně nejlepší cestu nenajde, ale s velkou pravděpodobností bude nalezený výsledek mezi těmi nejvýhodnějšími.
Uváznutí v lokalním minimu se dá řešit různými způsoby, v tomto případě například provést výpočet vícekrát (s různým počátečním tvarem sítě, případně každou dokončenou "nakopnout", aby se "rozštelovala") a pro každý výsledek změřit délku cesty -
Martin 'Bilbo' Petricek (neregistrovaný)No, rozdil mezi opbchodnim cestujicim a faktorizaci je ten, ze kdyz najdu reseni, ktere je o neco horsi nez optimum, tak u obchodniho cestujiciho a "rozumnych" dat to vetsinou staci (holt nacestuje 104 misto 100 km, ale zase ma naplanovanou cestu behem minuty a ne behem miliardy let)
U faktorizace je mi nejaky castecny vysledek k nicemu ...bud to cislo rozlozim nebo se muzu jit zahrabat ... -
Blesk (neregistrovaný)Ano, toto je klasicky priklad problemu ktery jde resit aproximativne vs. problemu ktery jde resit nahodnostne.
Aproximovane - staci mi dobre reseni, ne nutne optimalni
Randomizovane - s nejakou pravdepodobnosti najdu spravne reseni...
Oboje jen v kostce receno, je to trosku na delsi povidani... -
Skzitesek (neregistrovaný)Uch, napsano jest v clanku samem, ze z pohledu informovaneho ctenare srozumitelnym byt....
Ja vsak ztracen a zmaten citim se, presto jsem kdysi tvrdival ze problem matematicky po vysvetleni neni problem pochopit....
je mozne nasmerovat osobu mou na cestu temito problemy zakladni, ci-li na stranky elementarni? -
Elvis (neregistrovaný)Osobne doporucuji velmi ctiva a prehledna (tedy pro matematika, pochopitelne!) skripta doc. Cerne z brnenske fakulty informatiky, lze je najit tady.
Rozdil mezi C-tezkymi a C-uplnymi problemy pro libovolnou tridu slozitosti C je popsan v definici 5.7 na strane 45, myslim, ze zde to bylo nekolikrat formulovano chybne a nekolikrat ne zcela prehledne.
Doporucuji take clanek Pavla Housera (ano, toho stejneho Pavla Housera, jehoz text prave komentujeme) na jeho domovskem Scienceworldu a predevsim tamni komentare, kde jsem objevil nekolik dalsich odkazu na zakladni literaturu.
-
Dusan (neregistrovaný)Klidne je mozne, ze uz ji pred delsi dobou nekdo vyresil. Neco jako je ta oblibena story (mozna bez realneho zakladu) jak nejaky nateseny vedator na americke VS publikoval svou prevratnou matematickou praci spojenou s kryptografii tesil se na uznani, ceny a svetovou slavu, nacez mu nekdo sdelil, ze jim "vynalezena" metoda byla popsana v tajne praci sponzorovane NSA jiz pred patnacti lety a je bezne pouzivana k lusteni sifer. :-))
ČLÁNKY DO MAILU