NP ?

[Necroman]

Mohl by mi prosím udělat jasno v jednom, jaký je vztah těchto pojmů:
NP (problém řešitelný v polynomiálním čase pomocí nedeterministického Turingova stroje)
NP-těžký (existuje NP-úplný problém, který je na tento v polynomiálním čase redukovatelný)
NP-úplný problém (je NP a NP-těžký)

ty definice se poněkud nerozumně kryjí, tak by mě zajímalo, co všechno platí

1. IF NP, potom je NP-těžký?
2. IF NP, potom, je NP-úplný?
3. IF NP-těžký, potom je NP?
4. IF NP-těžký, potom je NP-úplný?
5. IF NP-úplný, potom je NP
6. IF NP-úplný, potom je NP-těžkými pravidy, těžko říct

odpoved nalezena, diky Hippies

[twoflower]

Podle me:

1. Neplati
2. Neplati
3. Neplati
4. Neplati
5. Plati
6. Plati

[draracle]

Co psal twoflower, souhlasi.

Co nesouhlasi, je definice NP-tezkeho problemu z otazky. Spravne by melo byt:

Kód: Vybrat vše

Problem je NP-tezky, pokud je KAZDY problem tridy NP na nej polynomialne prevoditelny.

To znamena, ze kdybych umel v rozumne dobe vyresit NP-tezky problem, dovedu vyresit kazdy problem tridy NP.

Definice se nekryji, jen NP a NP-tezky maji neprazdny prunik.
Problem muze byt NP-tezky a nebyt NP, tedy nebyt v polynomialnim case resitelny na NTS. Prevodem na nej bychom si nepomohli.
Oproti tomu problem muze byt NP a nebyt NP-tezky. Proste ho dovedeme na NTS rychle vyresit, ale k reseni ostatnich NP nam to nepomuze. A problemy, ktere jsou oboje, jsou NP-uplne.

[Necroman]

Definice se nekryji, jen NP a NP-tezky maji neprazdny prunik.
Problem muze byt NP-tezky a nebyt NP, tedy nebyt v polynomialnim case resitelny na NTS. Prevodem na nej bychom si nepomohli.
Oproti tomu problem muze byt NP a nebyt NP-tezky. Proste ho dovedeme na NTS rychle vyresit, ale k reseni ostatnich NP nam to nepomuze. A problemy, ktere jsou oboje, jsou NP-uplne.

Aha, to jsem netusil, ze NP-tezky a NP maji jen prunik, nejedna se o podmnozinu. Ted uz to dava i smysl, dik

[Dawe]

Jinak dukaz toho že je něco v třídě NP = pokud mi dá někdo správný řešení, jsem pak jednoduše schopnej říct, že je to správný řeeí (např. Hamiltonovská kružnice - naít ji je složitý, ale když mi někdo řekne která to je, je jasný, že je to ona).
Že je NP těžký = vezmu jakejkoliv NP úplnej a ten transformuju (v polynomiálnm čase!!!) na ten muj (triviálně třeba problém obchodního cestujícího na Hamiltonovskou kružnici).
No a jestli jsem pro jeden problém schopnej udělat obe věci, pak můžu prohlásit, že problém je NP-úplný.
Jako příklad problému ze třídy NP, kterej není NP-těžkej se dává regulární výraz.
Snad jsem to nijak neomotal, většina tohodle se dělalana Složitosti, moc nechápu proč je to teda u státnic, z algoritmů jsem taky věděl velký kulový, jen tenkrátu zkoušky, když jsem to dostal mi to David Kronus spíš vysvětloval

[twoflower]

Že je NP těžký = vezmu jakejkoliv NP úplnej a ten transformuju (v polynomiálnm čase!!!) na ten muj (triviálně třeba problém obchodního cestujícího na Hamiltonovskou kružnici).

Nemelo by byt spis "jakykoli NP problem a ten transformuju"? Aspon ja se setkal s touto definici a ekvivalentni to zrejme neni.

[Dawe]

Jo, máš pravdu.

[sulthan]

Že je NP těžký = vezmu jakejkoliv NP úplnej a ten transformuju (v polynomiálnm čase!!!) na ten muj (triviálně třeba problém obchodního cestujícího na Hamiltonovskou kružnici).

Nemelo by byt spis "jakykoli NP problem a ten transformuju"? Aspon ja se setkal s touto definici a ekvivalentni to zrejme neni.

Proc? Staci mi, abych umel transformovat jeden NP-uplny problem na ten muj a z definice NP-uplnosti to znamena, ze i ten muj je NP-tezky, staci jenom dat za sebe ty dve polynomialni transformace a mam prevod libovolneho NP-problemu na ten muj problem.
Ekvivalentem to sice neni, ale je tu implikace

[hippies]

Aha, to jsem netusil, ze NP-tezky a NP maji jen prunik, nejedna se o podmnozinu. Ted uz to dava i smysl, dik

http://ms.gotowin.com.tw/web/a6/01/13/04/91/02.htm

[draracle]

Že je NP těžký = vezmu jakejkoliv NP úplnej a ten transformuju (v polynomiálnm čase!!!) na ten muj (triviálně třeba problém obchodního cestujícího na Hamiltonovskou kružnici).

Nemelo by byt spis "jakykoli NP problem a ten transformuju"? Aspon ja se setkal s touto definici a ekvivalentni to zrejme neni.

Nemelo.

Budto bych musel ukazat, ze kazdy NP problem jsem schopny polynomialne transformovat na ten muj. To je typicky dost pracne a staci, kdyz to udelam pro jeden NP-upnej problem a ostatni prevadim (treba neprimo) na nej. Bezne se primo dokazuje kachlikovani (nebo SAT) pomoci simulace prace nedeterministickeho TS.

No a dalsi moznosti je prevest jeden libovolny NP-uplny problem na ten muj. O tom NP-uplnem problemu uz mame dokazane, ze na nej lze libovolny NP problem prevest, tak by se transformace pouze slozily...

[twoflower]

Jasne, nevim proc jsem v tu chvili chapal "jakejkoli" v Daweove prispevku jako "kazdy".