Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Клас P



План:


Введення

В теорії алгоритмів класом P (від англ. polynomial) називають безліч завдань, для яких існують "швидкі" алгоритми рішення (час роботи яких поліноміальної залежить від розміру вхідних даних). Клас P включений в більш широкі класи складності алгоритмів.


1. Визначення

1.1. Формальне визначення

Алгоритм ототожнюється з детермінованою машиною Тьюринга, яка обчислює відповідь з даного на вхідну стрічку слову з вхідного алфавіту Σ . Часом роботи алгоритму T M (x) при фіксованому вхідному слові x називається кількість робочих тактів машини Тьюринга від початку до зупинки машини. Складністю функції f: \ Sigma ^ * \ to \ Sigma ^ * , Що обчислюється деякою машиною Тьюринга, називається функція C: \ mathbb N \ to \ mathbb N , Що залежить від довжини вхідного слова і рівна максимуму часу роботи машини по всіх вхідним словами фіксованої довжини:

C_M (n) = \ max \ limits_ {x: | x | = n} T_M (x) .

Якщо для функції f існує машина Тьюринга M така, що C M (n) c для деякого числа c і досить великих n, то кажуть, що вона належить класу P, або поліноміальна за часом.

Згідно тези Черча - Тьюринга, будь мислимий алгоритм можна реалізувати на машині Тьюринга. Для будь-якого мови програмування можна визначити клас P подібним чином (замінивши у визначенні машину Тьюринга на реалізацію мови програмування). Якщо компілятор мови, на якому реалізований алгоритм, уповільнює виконання алгоритму поліноміальної (тобто час виконання алгоритму на машині Тьюринга менше деякого многочлена від часу виконання його на мові програмування), то визначення класів P для цієї мови і для машини Тьюринга збігаються. Код на асемблері допускає перетворення в машину Тьюринга з невеликим поліноміальним уповільненням, а оскільки всі існуючі мови допускають компіляцію в асемблер (знову ж, з поліноміальним уповільненням), то визначення класу P для машин Тьюринга і для будь-якого існуючого мови програмування збігаються.


1.2. Більш вузьке визначення

Іноді під класом P мають на увазі більш вузький клас функцій, а саме клас предикатів (функцій f: \ Sigma ^ * \ to \ {0, \, 1 \} ). У такому разі мовою L, який розпізнає даний предикат, називається безліч слів, на яких предикат дорівнює 1. Мовами класу P називаються мови, для яких існують розпізнають їх предикати класу P. Очевидно, що якщо мови L 1 і L 2 лежать в класі P, то і їх об'єднання, перетин та доповнення також лежать в класі P.


2. Включення класу P в інші класи

Клас P є одним із самих вузьких класів складності. Алгоритми, що належать йому, належать також класу NP, класу BPP (як допускають поліноміальну реалізацію з нульовою помилкою), класу PSPACE (тому зона роботи на машині Тьюринга завжди менше часу), класу P / Poly (для доказу цього факту використовується поняття протоколу роботи машини, який переробляється в булеву схему поліноміальною розміру).

Вже більше 30 років залишається невирішеною завдання про рівність класів P і NP. Якщо вони рівні, то будь-яке завдання з класу NP можна буде вирішити швидко (за полиномиальное час). Проте наукове співтовариство схиляється в бік негативної відповіді на це питання. Крім того, не доведена і строгість включення в більш широкі класи, наприклад, в PSPACE, але рівність P і PSPACE виглядає на даний момент дуже сумнівно.


3. Приклади завдань

3.1. Завдання, що належать класу P

Прикладами завдань з класу P є цілочисельне додавання, множення, ділення, взяття залишку від ділення, множення матриць, з'ясування зв'язності графів і деякі інші.

3.2. Завдання, приналежність яких класу P невідома

Існує багато задач, для яких не знайдено поліноміальною алгоритму, але не доведено, що його не існує. Відповідно, невідомо, чи належать такі завдання класу P. Ось деякі з них:

  1. Завдання комівояжера (а також всі інші NP-повні задачі). Це завдання рівносильна встановленню рівності класів P і NP.
  2. Розкладання числа на прості множники.
  3. Дискретне логарифмування в кінцевому полі.
  4. Завдання про приховану підгрупі з n утворюють.
  5. Дискретне логарифмування в групі точок аддитивной на еліптичної кривої.

4. Практичне значення

Оскільки часто доводиться обчислювати значення функцій на вхідних даних великого обсягу, знаходження поліноміальних алгоритмів для обчислення функцій є дуже важливим завданням. Вважається, що обчислювати функції, не лежать в класі P, значно складніше, ніж лежать. Більшість алгоритмів, що лежать в класі P, мають складність, не перевищує многочлен невеликому ступені від розміру вхідних даних. Наприклад, стандартний алгоритм перемножування матриць вимагає n 3 множень (хоча існують і більш швидкі алгоритми, наприклад, алгоритм штрассе). Ступінь многочлена рідко буває великий. Один з таких випадків - запропонований в 2002 індійськими математиками тест Агравал - Каяла - Сакса, що з'ясовує, чи є число n простим, за O (log 6 n) операцій.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Клас co-NP
Клас RP
Клас
Клас PP
Клас PH
Клас R
Клас NP
Клас EXPTIME
Клас PSPACE
© Усі права захищені
написати до нас