Diskuse:NP-úplnost

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)