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ý).
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.
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 :).
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 :-)
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)
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.
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.
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).
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.
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 :-)
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:-)))
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é.
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".
Upozorníme vás na články, které by vám neměly uniknout (maximálně 2x týdně).
