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ý).
Názory k článku
Jak dlouho nám vydrží dnešní šifrovací metody?
Jan Tichý (neregistrovaný)
17. 8. 2005 10:44
Nový
Re: NP-úplnost
celé vlákno
AFAIK se předpokládá, že by se NP-úplné problémy možná daly řešit, ale nikoliv v tradičních existujících axiomatických soustavách. Takže to vlastně vyjde nastejno :).
EL (neregistrovaný)
17. 8. 2005 10:54
Nový
Re: NP-úplnost
celé vlákno
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.
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ý)
17. 8. 2005 12:34
Nový
Re: NP-úplnost
celé vlákno
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ý)
17. 8. 2005 12:45
Nový
Re: NP-úplnost
celé vlákno
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)
Nebo znáte NP problém, který není NP úplný? (to nemyslím jako provokaci, jenom jako dotaz)
Jan Němec (neregistrovaný)
17. 8. 2005 12:58
Nový
Re: NP-úplnost
celé vlákno
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.
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ý)
17. 8. 2005 13:12
Nový
Re: NP-úplnost
celé vlákno
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:-(
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ý)
17. 8. 2005 13:17
Nový
Re: NP-úplnost
celé vlákno
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ý)
17. 8. 2005 13:24
Nový
Re: NP-úplnost
celé vlákno
No vždyť. A já jsem odpověděl, že moudré hlavy soudí, že faktorizace je problém z NP (což je zjevné), ale zároveň nepatří ani do NP-úplných ani do P (což je jen domněnka).
Jan Němec (neregistrovaný)
17. 8. 2005 13:33
Nový
Re: NP-úplnost
celé vlákno
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.
"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ý)
17. 8. 2005 14:09
Nový
Re: NP-úplnost
celé vlákno
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 :-)
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ý)
17. 8. 2005 15:20
Nový
Re: NP-úplnost
celé vlákno
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:-)))
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:-)))
Jaroslav.Pinkava (neregistrovaný)
17. 8. 2005 13:09
Nový
Re: NP-úplnost
celé vlákno
Pan Němec mě předběhl - tj. faktorizace je jeden příklad, ale do NP patří i všechny problémy s P (například řešení soustavy rovnic). Klíčovou otázkou je, zda není množina NP\P prázdná.
Jinak k článku, téma zajímavé, ale mohlo být opravdu lépe zpracované.
Jinak k článku, téma zajímavé, ale mohlo být opravdu lépe zpracované.
Pavel Chromý (neregistrovaný)
17. 8. 2005 23:58
Nový
Re: NP-úplnost
celé vlákno
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".
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".
Radek Burda; (neregistrovaný)
17. 8. 2005 11:00
Nový
Obchodni cestujici
celé vlákno
http://home.eunet.cz/berka/o/elanet.htm
Dehtak (neregistrovaný)
17. 8. 2005 12:30
Nový
Re: Obchodni cestujici
celé vlákno
Ten aplet opravdu hledá nejkratší cestu?
Zkoušel jsem to a v tomto případě se jednoznačně spletl.
Žlutě jsem dokreslil, jak je to nejkratší.
viz: www.habesky.info/cesta.png
Zkoušel jsem to a v tomto případě se jednoznačně spletl.
Žlutě jsem dokreslil, jak je to nejkratší.
viz: www.habesky.info/cesta.png
Milan Prokeš (neregistrovaný)
17. 8. 2005 13:00
Nový
Re: Obchodni cestujici
celé vlákno
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
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ý)
17. 8. 2005 13:38
Nový
Re: Obchodni cestujici
celé vlákno
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 ...
U faktorizace je mi nejaky castecny vysledek k nicemu ...bud to cislo rozlozim nebo se muzu jit zahrabat ...
Blesk (neregistrovaný)
17. 8. 2005 14:12
Nový
Re: Obchodni cestujici
celé vlákno
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...
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ý)
17. 8. 2005 11:21
Nový
ZTRACEN
celé vlákno
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?
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?
Obi-Wan Kenobi (neregistrovaný)
17. 8. 2005 12:19
Nový
Re: ZTRACEN
celé vlákno
nasmerovat osobu vasi ke slovosledu ceskeho pravidlum mozne je taktez, uzitecnejsi by bylo to vice nez matematika abstaktni vam.
Yoda (neregistrovaný)
17. 8. 2005 13:39
Nový
Re: ZTRACEN
celé vlákno
To jsem já měl pronésti. Před nepřesnou citací ostatních rytířů Jedi varovat Tě musím.
Elvis (neregistrovaný)
17. 8. 2005 13:30
Nový
Re: ZTRACEN
celé vlákno
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.
MrMak (neregistrovaný)
18. 8. 2005 8:47
Nový
Riemann
celé vlákno
Priznavam, ze matematice rozumim jako koza petrzeli, ale jedno je mi jasne. Pokud nekdo nekdy dokaze nejak prakticky vyresit Riemannovu domnenku, tak my se to nikdy nedozvime. Protoze misto toho aby to zverejnil tak to nekomu proda za opravdu astronomickou sumu ;)
Jaroslav.Pinkava (neregistrovaný)
18. 8. 2005 9:11
Nový
Re: Riemann
celé vlákno
Proč by dotyčný někoho hledal - odměna je již vypsána:
http://www.claymath.org/millennium/
http://www.claymath.org/millennium/
J (neregistrovaný)
18. 8. 2005 15:27
Nový
Re: Riemann
celé vlákno
Myslim, ze prodat to nekomu jako tajnym sluzbam by mohlo byt podstatne vyhodnejsi. Druha vec ovsem je, ze by jste si te odmeny asi moc neuzil, nemyslim ze by se nekomu hodilo ze existuje nekdo kdo vi.
ufik (neregistrovaný)
18. 8. 2005 22:06
Nový
Re: Riemann
celé vlákno
Proto muze bet velmi vyhodne to poskytnout verejnosti. Kdyz to budou vedet vsichni a odborna verejnost me bude znat, pak budu v relativnim bezpeci a nebudu se moct zabit padem z okna (v prizemi, ...
Dusan (neregistrovaný)
22. 8. 2005 8:27
Nový
Re: Riemann
celé vlákno
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. :-))
