Produkcia inovácií

0 hlasov


I je efektívny algoritmus produkujúci inovácie
ak pre každý efektívny obvod S a orákulum K reprezentované efektívnym obvodom
 definujúcim otázky na ktoré vie K odpovedať
 a takým že pomocou K nejde efektívne riešiť celé NP
I efektívne nájde x,y tž text x splňuje (efektívne overiteľné) kritéria y ale
 S používajúc orákulum K žiaden text splňujúci y nenájde

ak teda obvod S efektívne algoritmizuje známe spôsoby produkovania textu
 a NP nejde riešiť efektívnymi obvodmi
I vyprodukuje text x splňujúci kritéria y tž S nebude schopné napísať text kt by splnil y
 ak opakovaním tohto pre rôzne stratégie S dostávame dvojice x,y ktoré sú predvídateľné
 v tom zmysle že sú popísateľné efektívnym obvodom reprezentujúcim orákulum
 pomocou ktorého nejde efektívne riešiť celé NP a potom rozšírime S o toto orákulum
I vyprodukuje nové x,y tž S s týmto orákulom nenájde text splňujúci y atď
v tomto zmysle I produkuje vždy invenčné texty z pohľadu S

dá sa ukázať že ak neexistuje málo efektívnych obvodov reprezentujúcich orákula
 tž pomocou žiadneho z nich nejde efektívne riešiť celé NP ale ktorých zjednotením to už ide
tak existuje efektívny obvod produkujúci inovácie
problém je tento obvod efektívne nájst

 

Poslať nový komentár

Obsah tohto poľa je súkromný a nebude verejne zobrazený.
To prevent automated spam submissions leave this field empty.