В.Б. Алекссев - Сложные алгоритмы (1132790), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

tOT FAKT, ^TO x 2 L,RAWNOSILEN UTWERVDENI@: DLQ WHODA x SU]ESTWUET PRINIMA@]EE (SOTWETOM "DA") WY^ISLENIE MA[INY M . |TO POSLEDNEE UTWERVDENIEMY I WYRAZIM W WIDE FORMULY F (x). tAK VE, KAK PRI DOKAZATELXSTWENP -POLNOTY ZADA^I wyp, WWEDEM DWA MNOVESTWA PEREMENNYH V I V 0,OPISYWA@]IH 2 PROIZWOLXNYE KONFIGURACII NA ZONE p1(n), I ZAPI[EMFORMULU F0(V; V 0) WYRAVA@]U@ TOT FAKT, ^TO V I V 0 PRAWILXNOZADA@T KONFIGURACII I LIBO V = V 0 , LIBO IZ KONFIGURACII V MYZA ODIN [AG MA[INY M PEREHODIM W KONFIGURACI@ V 0.

kAK POKAZANO PRI DOKAZATELXSTWE NP -POLNOTY ZADA^I wyp DLINA FORMULYF0(V; V 0) MOVET BYTX OGRANI^ENA NEKOTORYM POLINOMOM p2(n) I EEMOVNO POSTROITX ZA POLINOMIALXNOE OT n WREMQ. fORMULA F0(V; V 0 )WYRAVAET TOT FAKT, ^TO IZ KONFIGURACII V W KONFIGURACI@ V 0 MOVNOPEREJTI ZA NE BOLEE ^EM 1 [AG. pOSTROIM TEPERX INDUKTIWNO FORMULYF1; F2; : : : ; Fs , GDE s = p(n), SLEDU@]IM OBRAZOM. pUSTX W |E]E ODNOMNOVESTWO PEREMENNYH, OPISYWA@]IH KONFIGURACI@ NA ZONE p1(n).|.76.tOGDA POLOVIMFk (V; V 0) = 9W [Fk;1(V; W )&Fk;1(W; V 0 )]:fORMULA Fk WYRAVAET TOT FAKT, ^TO V; V 0|PRAWILXNYE KONFIGURACIII IZ V W V 0 MOVNO PEREJTI ZA NE BOLEE, ^EM 2k [AGOW.

fORMULA WKWADRATNYH SKOBKAH RAWNOSILXNA SLEDU@]EJ FORMULE:(8Y )(8Z )[(Y = V )&(Z = W ) _ (Y = W )&(Z = V 0 ) ! Fk;1(Y; Z )]GDE Y; Z |DWA MNOVESTWA PEREMENNYH, OPISYWA@]IH 2 PROIZWOLXNYEKONFIGURACII. pO\TOMU FORMULU Fk MOVNO ZAPISATX W WIDE:Fk (V; V 0 ) = (9W )(8Y )(8Z )[(Y = V )&(Z = W )_(Y = W )&(Z = V 0 ) ! Fk;1(Y; Z )]:tAKIM OBRAZOM, DLINA Fk(V; V 0) OTLI^AETSQ OT DLINY Fk;1(V; V 0 ) NEBOLEE ^EM NA NEKOTORYJ POLINOM p3(n) I DLINA Fk (V; V 0) NE PREWOSHODITp2(n) + kp3 (n). pUSTX WREMQ RABOTY MA[INY M NE PREWOSHODIT 2p(n) Is + p(n). tOGDA Fs(V; V 0) IMEET DLINU NE BOLEE p2(n)+ p(n) p3(n) = p4(n),GDE p4| POLINOM, I WYRAVAET TOT FAKT, ^TO V I V 0 PRAWILXNYE KONFIGURACII I IZ V W V 0 MOVNO PEREJTI ZA NE BOLEE 2p(n) [AGOW MA[INYM .

pUSTX FORMULA Gx(V ) WYRAVAET TOT FAKT, ^TO KONFIGURACIQ VQWLQETSQ PRAWILXNOJ NA^ALXNOJ KONFIGURACIEJ DLQ WHODA x (yf pjytp1(n)), A FORMULA H (V ) WYRAVAET TOT FAKT, ^TO W KONFIGURACII VSOSTOQNIE "DA". tOGDA TOT FAKT, ^TO DLQ WHODA x SU]ESTWUET PRINIMA@]EE WY^ISLENIE MA[INY M MOVNO PREDSTAWITX FORMULOJF (x) = (9V )(9V 0)[Gx(V )&H (V 0)&Fs(V; V 0 )]:pOSKOLXKU DLINA FORMUL Gx(V ) I H (V ) MOVET BYTX OGRANI^ENAPOLINOMOM OT n I ONI MOGUT BYTX POSTROENY ZA POLINOMIALXNOE OT nWREMQ (SM.

DOKAZATELXSTWO NP -POLNOTY ZADA^I wyp), TO POLU^AEM,^TO DLINA F (x) NE PREWOSHODIT POLINOMA OT n I F (x) MOVET BYTXPOSTROENA ZA POLINOMIALXNOE OT n WREMQ. tEOREMA DOKAZANA.pRI OPREDELENII KLASSA DLOG OBY^NO ISPOLXZU@T MODELX MNOGOLENTO^NOJ MA[INY tX@RINGA. pUSTX U MA[INY tX@RINGA IMEETSQNESKOLXKO LENT, ODNA IZ KOTORYH WYDELENA KAK WHODNAQ, I NA KAVDOJLENTE IMEETSQ ODNA GOLOWKA. oDIN [AG RABOTY TAKOJ MA[INY SOSTOITW ODNOWREMENNOM WYPOLNENII OBY^NYH DEJSTWIJ KAVDOJ GOLOWKOJ (UKAVDOJ GOLOWKI SWOI DEJSTWIQ), PRI^EM WESX NABOR DEJSTWIJ ODNOZNA^NO OPREDELQETSQ TEMI SIMWOLAMI, KOTORYE OBOZREWA@TSQ WSEMI GOLOWKAMI I SOSTOQNIEM MA[INY.

wHODNOE SLOWO ZAPISYWAETSQ NA WHODNOJLENTE W STANDARTNOJ KONFIGURACII I GOLOWKA NA WHODNOJ LENTE MOVETTOLXKO ^ITATX SIMWOLY, NO NE MOVET ZAPISYWATX NOWYE.77oPREDELENIE. kLASS DLOG OPREDELQETSQ KAK KLASS WSEH ZADA^RASPOZNAWANIQ (QZYKOW), DLQ KOTORYH SU]ESTWUET RASPOZNA@]AQ IHMNOGOLENTO^NAQ MA[INA tX@RINGA, ISPOLXZU@]AQ NA WSEH LENTAH, KROME WHODNOJ, NE BOLEE c log2 n Q^EEK, GDE n |DLINA WHODA I c|NEKOTORAQKONSTANTA (DLQ DANNOJ ZADA^I).iSPOLXZUQ LEMMU, NETRUDNO POKAZATX, ^TO DLOG P .

tAKIMOBRAZOMDLOG P NP PSPACE:mOVNO DOKAZATX, ^TO DLOG =6 PSPACE , PO\TOMU HOTQ BY ODNO IZUKAZANNYH WKL@^ENIJ DOLVNO BYTX STROGIM. oDNAKO KAKOE (ILI KAKIE)IMENNO, POKA (2001 GOD) NE IZWESTNO.78.

Характеристики

Список файлов книги