Cyr:
Jakkoliv implementujete algoritmus - vždy musí odpovídat na "pro set A je nejmenší počet bucketů B" a nic jiného. Pro ověření správnosti odpovědi "pro set A je nejmenší počet bucketů B" nemůžete použít algoritmus ve třídě složitosti P. To je celý problém a důvod, proč to je NP-hard a ne NP.
A to zas prrrr. :-) Součástí odpovědi je vždy "certifikát", proč tomu tak je a ověřuje se ten certifikát. Vždyť u decision problému by čistá odpověď ANO (kterou získáš "v čase NP") přeci také nelze ověřit "v čase P". To by to nebyl NP, ale P problém. To, co jde ověřit v čase P je certifikát (např. to jde definovat pomocí DTS s orákulem, kdy orákulum nejdřív "uhádne" certifikát a pak jej v P ověří). V případě decision problému je daným certifikátem rozložení do kyblíků.
A problém je v tom, že pro odpověď NE evidetně neexistuje stroj, který by to v čase NP spočítal, tedy není možno vytvořit "certifikát", který by šel v P čase ověřit. Tedy decision problém je v třídě NP, ale není v třídě co-NP. Proto také asi nefunguje Mirkův postup, kdy to ověřím pro 1 až k. Protože pro ty 1-(k-1) neexistují certifikáty ověřující NE u decision problému.
Mirek:
Tohle je podle me zcestna uvaha. Problem bude imho v tom, ze polynomialni algoritmus porad nema zadny presne dany limit, ktery bys mohl detekovat - cili zrejme dalsi [rypnuti]krasna ukazka informaticky-teoretickeho zaveru s obrovskym teoretickym dopadem a nulovou praktickou vyuzitelnosti 
[/rypnuti]
A zas prrrr. :-) Pokud dokážu, že je ten program v NP, tak musím dokázat existenci polynomu, který zhora omezuje nejdelší možný běh pro odpověď ANO. Takže (pominu-li hustokrutý důkazy typu: "polynom existuje ale neznám ho" :-) který se v algoritmech skoro nevyskytují) znám horní hranici doby běhu. Takže to opravdu omezit můžu. Zpravidla je totiž ten algoritmus nějaké prohledávání stromu a ten certifikát je kterou cestou se mám dát v grafu. A hloubka grafu jde zpravidla odhadnout snadno.
Problém bude v tom, že to počítání nejde asi v polynomiálním čase udělat - jen nevím proč. Představuju si to tak, že každý druhý pole na pásce vyhradím na počítání počtu kroků. Čili každej originální krok se skládá z max 4*O(n) kroků (dojdu na konec počítadla, zapíšu další čárku, 2* kvůli zdvojeným polím, 2*cesta tam a zpět), čili zůstávám v polynomiální složitosti.
U výše uvedeného postupu nevidím, co je certifikátem toho řešení. Ale definice NP nevyžadují explicitně existenci certifikátu. Ta by měla jen vyplývat z toho řešení pomocí NTS v polynomiálním čase. Někde tam asi problém bude, ale kde?
52 Odpovědí
13278 Zhlédnutí