Diskuse:NP-úplnost
Přidat témaVzhled
Pár připomínek k terminologii:
- článek se jmenuje NP-úplnost, ale mluvíme v něm o NP-úplných problémech. Neměl by se jmenovat jinak?
- používáme termíny NP a nedeterministicky polynomiální problémy, a přitom se myslí to samé
- zaměňujeme problém a úloha
- opravdu se říká zavazadlový problém? Zatím jsem to neslyšel. (v angl. je to knapsack tedy batoh)
- není lepší říkat NP-těžké problémy místo nedeterministicky polynomiální?
--Tomash 18:20, 8. 11. 2004 (UTC)
- Odpovídám jen na zavazadlový problém. Tento termín jsem vygooglal na fujtajflu (tedy FJFI) v sylabech přednášek http://www.km.fjfi.cvut.cz/main/sylabyprint.htm Holt, kdo to dřív přeloží, ten určí terminologii. Takto třeba Jiří Grygar do češtiny zavedl Velký třesk, ačkoliv se to mohlo přeložit i jako velký úder, velká rána, velké bum... Osobně by se mi také líbilo spíš ruksakový nebo batohový problém. --Luděk 18:46, 8. 11. 2004 (UTC)
- U nás ve škole jsme používali překlad "problém batohu". 52 stránek z Google tento termín používá taky. Pro spojení "zavazadlový problém" najde Google jen dva záznamy. --Michal Jurosz 19:12, 8. 11. 2004 (UTC)
- U nás se taky používal problém batohu (možná to taky byla stejná škola ;-) ), spousta stránek z Googlu, na kterých to je, taky odkazuje na tentýž předmět...
- Pojmenování toho článku není úplně ideální, ale lepší se těžko hledá. Dalo by se to přesunout rovnou na NPC, ale to taky není ideální. Takže bych to asi nechal.
- Termín NP-problém a nedeterministicky polynomiální problém je to samé, kde je problém?
- NP-těžké problémy nejsou totéž, co nedeterministicky polynomiální, takže to určitě není lepší.
- Celkově, editujte s odvahou! ;-)
- --Mormegil 19:19, 8. 11. 2004 (UTC)
Faktorizace na prvocisla je NP-uplna? Kdyz jsem o tom kdysi cetl, psalo se, ze se to predpoklada, ale neni to dokazane. Forejtv 07:36, 27. 4. 2005 (UTC)
- Ne, faktorizace (tedy její rozhodovací verze, pochopitelně) je v NP a co-NP, ale silně se předpokládá (ale není dokázáno), že není v P ani v NPC. --Mormegil ✉ 09:21, 27. 4. 2005 (UTC)
Ono se taky běžně předpokládá, že P≠NP. ;-) Ale jistě neví nikdo nic.
— Egg ✉ 11:05, 27. 4. 2005 (UTC)