od adam » 31. 1. 2010 14:16
Osiris píše:No, každý problém ve třídě NP je řešitelný v polynomiálním čase na NTS. Tak si vezmeš ten polynom a čtvercová síť bude mít délku/šířku nastavenou podle toho polynomu. Já myslím ,že stačí EXISTENCE toho polynomu...
(Poznámka: Celý následující argument je naprosto nesmyslný, což si nyní plně uvědomuji, viz níže. Ale nechám to tady pro poučení příštích generací, a taky abych se měl za co stydět:).) To je totéž, co jsem psal v bodu (4), certifikát existuje, polynom existuje, ani jeden ale neznáme. Narážel jsem na to, že z definice převoditelnosti musíš umět udělat převod
f, který v polynomiálním čase DETERMINISTICKY převede zadání převáděného problému na cílový (aniž by dostal ten polynom, resp. konkrétní prostorovou/časovou složitost, nebo certifikát). Ten převod na
KACHL se dělá pro nějaký pevně zvolený problém, pro který máme NTS M (který mimo jiné nějakou přechodovou fci delta), ze kterého mi ten převod
f zkonstruujeme, chceš-li, můžeš při tom využít informaci, že takovýc polynom p EXISTUJE, ale ta je ti IMHO k ničemu. Kdybys chtěl uvnitř
f ten polynom zjistit, tak bys musel spustit NEDETERMINISTICKÝ polynomiální výpočet, pak ale nezaručíš, že ten převod
f je deterministicky polynomiální. Z informace o existenci polynomu
p prostě deterministicky nezkonstruuješ okraj sítě, jehož délka je rovná jeho hodnotě
p(
n) (pro dané
n).
(Poznámka: konec nesmyslného argumentu.)
macbeth píše:a pokial mam spravne poznamky, tak qF je na dolnom okraji hned na zaciatku (stroj po prechode do qy neskonci, ale vsetko na paske prepise prazdnym symbolom, hlavu zaparkuje na zaciatku pasky a prejde do 'noveho' koncoveho stavu)... aspon tak sa to pise v poznamkach z fora, ktore mam...
To je fakt, takhle otázka je asi zbytečná. Dá se to vyřešit obdobně, jako když se tam žádné "místo na pásce" (resp. hvězdičky na horní okraj) nepřidává. Není v tom žádný velký zádrhel. Takže to bychom měli, a zpátky k tomu, jak vyřešit ten hlavní problém:).
[quote="Osiris"]No, každý problém ve třídě NP je řešitelný v polynomiálním čase na NTS. Tak si vezmeš ten polynom a čtvercová síť bude mít délku/šířku nastavenou podle toho polynomu. Já myslím ,že stačí EXISTENCE toho polynomu...[/quote]
[color=#BF0000](Poznámka: Celý následující argument je naprosto nesmyslný, což si nyní plně uvědomuji, viz níže. Ale nechám to tady pro poučení příštích generací, a taky abych se měl za co stydět:).)[/color] To je totéž, co jsem psal v bodu (4), certifikát existuje, polynom existuje, ani jeden ale neznáme. Narážel jsem na to, že z definice převoditelnosti musíš umět udělat převod [i]f[/i], který v polynomiálním čase DETERMINISTICKY převede zadání převáděného problému na cílový (aniž by dostal ten polynom, resp. konkrétní prostorovou/časovou složitost, nebo certifikát). Ten převod na [b]KACHL[/b] se dělá pro nějaký pevně zvolený problém, pro který máme NTS M (který mimo jiné nějakou přechodovou fci delta), ze kterého mi ten převod [i]f[/i] zkonstruujeme, chceš-li, můžeš při tom využít informaci, že takovýc polynom p EXISTUJE, ale ta je ti IMHO k ničemu. Kdybys chtěl uvnitř [i]f[/i] ten polynom zjistit, tak bys musel spustit NEDETERMINISTICKÝ polynomiální výpočet, pak ale nezaručíš, že ten převod [i]f[/i] je deterministicky polynomiální. Z informace o existenci polynomu [i]p[/i] prostě deterministicky nezkonstruuješ okraj sítě, jehož délka je rovná jeho hodnotě [i]p[/i]([i]n[/i]) (pro dané [i]n[/i]). [color=#BF0000](Poznámka: konec nesmyslného argumentu.)[/color]
[quote="macbeth"]a pokial mam spravne poznamky, tak q[sub]F[/sub] je na dolnom okraji hned na zaciatku (stroj po prechode do q[sub]y[/sub] neskonci, ale vsetko na paske prepise prazdnym symbolom, hlavu zaparkuje na zaciatku pasky a prejde do 'noveho' koncoveho stavu)... aspon tak sa to pise v poznamkach z fora, ktore mam...[/quote]
To je fakt, takhle otázka je asi zbytečná. Dá se to vyřešit obdobně, jako když se tam žádné "místo na pásce" (resp. hvězdičky na horní okraj) nepřidává. Není v tom žádný velký zádrhel. Takže to bychom měli, a zpátky k tomu, jak vyřešit ten hlavní problém:).