Алексеев - Сложность алгоритмов (1123759), страница 15

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

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

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.

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

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