В.Б. Алексеев - Электронный коспект лекций, страница 15
Описание файла
PDF-файл из архива "В.Б. Алексеев - Электронный коспект лекций", который расположен в категории "". Всё это находится в предмете "сложность алгоритмов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 15 страницы из PDF
pOSKOLXKU PO USLOWI@ PRI L@BOM WHODE MA[INA OSTANAWLIWAETSQ, TO ONA NE MOVET "ZACIKLITXSQ", TO ESTX KONFIGURACIQ NE MOVETPOWTORITXSQ. PO\TOMU WREMQ RABOTY PRI L@BOM WHODE NE PREWOSHODIT^ISLA RAZLI^NYH KONFIGURACIJ. pRI \TOMlog2(rp1(n) p1(n) k) = p1 (n) log2 r + log2 p1(n) + log2 k 6 p(n);GDE p(n)| NEKOTORYJ POLINOM. tEOREMA DOKAZANA.sLEDSTWIE. dLQ L@BOJ ZADA^I IZ PSPACE t(n) 6 2p(n) GDEp(n) NEKOT RYJ POLINOMoPREDELENIE. zADA^A RASPOZNAWANIQ (QZYK) L NAZYWAETSQPSPACE -POLNOJ, ESLI:1)L PSPACE ,2)K L POLINOMIALXNO SWODQTSQ WSE ZADA^I IZ PSPACE .uTWERVDENIE.
eSLI DLQ NEKOTOROJ PSPACE POLNOJ ZADVA^I SU]ESTWUET ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ TO,|o.-PSPACE = P-,.zADA^A O KWANTIFICIROWANNYH BULEWSKIH FORMULAH (QBF).wHOD FORMULA WIDA:(Q1x1)(Q2x2) : : : (Qm xm)[F (x1; : : : ; xm )];GDE x1; : : : ; xm |BULEWSKIE PEREMENNYE, F |BULEWSKAQ FORMULA W BAZISEfKON_@NKCIQ,DIZ_@NKCIQ,OTRICANIEg, Q ; i 2 f9; 8g DLQ WSEH i.tREBUETSQ WYQSNITX, ISTINNA LI DANNAQ FORMULA.lEMMA.
QBF 2 PSPACE:.dOKAZATELXSTWO pUSTX NA WHOD POSTUPILA FORMULA(Q1x1)(Q2x2) : : : (Qm xm)[F (x1; : : : ; xm )];DLINY n. tOGDA DLINA FORMULY F (x1; : : : ; xm ) NE BOLEE n, I DLQ L@BOGOZADANNOGO NABORA (1; : : : ; m WY^ISLENIE F (1; : : : ; m ) MOVNO WYPOLNITX ZA WREMQ, A ZNA^IT I S ISPOLXZOWANIEM PAMQTI, NE BOLEE p1(n),GDE p1 |NEKOTORYJ POLINOM.
eSLI ZAFIKSIROWANY TOLXKO ZNA^ENIQ1; : : : ; k PEREMENNYH x1; : : : ; xk , TO MY POLU^AEM PODZADA^U: NAJTIISTINNOSTNOE ZNA^ENIE FORMULY(Qk+1xk+1) : : : (Qmxm )[F (1; : : : ; k )(xk+1; : : : ; xm )]:pRIMENIM DLQ RE[ENIQ ISHODNOJ ZADA^I (I WSEH EE PODZADA^) SLEDU@]IJ REKURSIWNYJ ALGORITM:1.wY^ISLITX (Q2x2) : : : (Qm xm)F (0; x2 ; : : : ; xm ) \TIM VE REKURSIWNYM ALGORITMOM. zAPOMNITX POLU^ENNOE ZNA^ENIE (1 BIT) W DOPOLNITELXNOJ Q^EJKE..752.wY^ISLITX NA TOJ VE ZONE \TIM VE ALGORITMOM(Q2x2) : : : (Qm xm )F (0; x2; : : : ; xm ).3.eSLI Q1 = 8 I OBA ZNA^ENIQ, WY^ISLENNYE W 1 I 2, RAWNY 1,TOWYDATX OTWET 1, INA^E WYDATX 0.eSLI Q1 = 9 I OBA ZNA^ENIQ W 1 I 2RAWNO 0, TO WYDATX 0, INA^E WYDATX 1.iZ OPISANIQ ALGORITMA WIDNO, ^TO DLQ RE[ENIQ ZADA^I KAVDOGO UROWNQ NUVNO NA 1 Q^EJKU BOLX[E, ^EM NA RE[ENIE L@BOJ EEPODZADA^I.
tAK KAK NA WY^ISLENIE F (1; : : : ; m ) TREBUETSQ PAMQTINE BOLEE p1 (n), TO DLQ WY^ISLENIQ ISTINNOSTNOGO ZNA^ENIQ ISHODNOJFORMULY TREBUETSQ PAMQTX NE BOLEE p1(n) + n Q^EEK. dLQ UPRAWLENIQPROCESSOM PEREHODA OT ODINH PODZADA^ K DRUGIM W OPISANNOM ALGORITMEDOSTATO^NO POMNITX, KAKAQ PODZADA^A RE[AETSQ W DANNYJ MOMENT, TOESTX POMNITX ZNA^ENIQ 1 ; : : : ; k , OPREDELQ@]IE \TU PODZADA^U. tAKIMOBRAZOM, W CELOM OPRISANNYJ ALGORITM TREBUET NE BOLEE p(n) Q^EEKPAMQTI, GDE p|NEKOTORYJ POLINOM.tEOREMA. zADA^A QBF QWLQETSQ PSPACE POLNOJdOKAZATELXSTWO nAM NADLO DOKAZATX, ^TO L@BAQ ZADA^A L IZPSPACE POLINOMIALXNO SWODITSQ K QBF . eSLI L 2 PSPACE , TOSU]ESTWUET MA[INA tX@RINGA M , KOTORAQ RE[AET ZADA^U L S PAMQTX@NE BOLEE p1 (n) I WREMENEM NE BOLEE p(n) (SM. LEMMU), GDE n|DLINA WHODA.pUSTX x|WHOD DLINY n DLQ ZADA^I L.
nAM NADO ZA POLINOMIALXNOEWREMQ POSTROITX KWANTIFICIROWANNU@ FORMULU F (x) TAK, ^TO F (x)ISTINNA TOGDA I TOLXKO TOGDA, KOGDA x 2 L. 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.