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