PolyL - PolyL

Жылы есептеу күрделілігі теориясы, polyL болып табылады күрделілік сыныбы туралы шешім қабылдау проблемалары шешілуі мүмкін детерминирленген Тьюринг машинасы алгоритмі бойынша ғарыштық күрделілік шектеседі полигарифмикалық кіріс өлшеміндегі функция. Басқа сөздермен айтқанда, polyL = DSPACE((журналn)^{O (1)}), қайда n кіріс өлшемін білдіреді және O (1) тұрақты мәнді білдіреді.

Дәл сол сияқты L ⊆ P, polyL ⊆ QP. Алайда, арасындағы дәлелденген жалғыз байланыс polyL және P бұл сол polyL ≠ P; егер екені белгісіз polyL ⊊ P, егер P ⊊ polyLнемесе егер екіншісінде болмаса. Мұның бір дәлелі polyL ≠ P бұл сол P бар толық проблема астында логарифмдік кеңістік бірнеше рет төмендету бірақ polyL байланысты емес ғарыштық иерархия теоремасы.Кеңістік иерархиясының теоремасы бұған кепілдік береді DSPACE(журнал^г. n) ⊊ DSPACE(журнал^{d + 1} n) барлық бүтін сандар үшін d> 0. Егер polyL толық проблема болды, оны шақырыңыз A, бұл элемент болар еді DSPACE(журнал^к n) кейбір бүтін k> 0 үшін. есеп шығарайық B элементі болып табылады DSPACE(журнал^{k + 1} n) \ DSPACE(журнал^к n). Деген болжам A толық дегеніміз келесі О-ны білдіреді (журнал^к n) үшін кеңістік алгоритмі B: азайту B дейін A логарифмдік кеңістікте, содан кейін шешіңіз A O-да (журнал^к n) ғарыш. Бұл мұны білдіреді B элементі болып табылады DSPACE(журнал^к n), демек, ғарыштық иерархия теоремасын бұзады.

Сыртқы сілтемелер

• Хайуанаттар кешені: polyL

P ≟ NP

Бұл теориялық информатика - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.