Знаймо

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

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

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

Клас складності



План:


Введення

В теорії алгоритмів класами складності називаються безлічі обчислювальних задач, приблизно однакових за складністю обчислення. Говорячи більш вузько, класи складності - це безлічі предикатів ( функцій, які отримують на вхід слово і повертають відповідь 0 або 1), що використовують для обчислення приблизно однакові кількості ресурсів.

Для кожного класу існує категорія задач, які є "найскладнішими". Це означає, що будь-яке завдання з класу зводиться до такого завдання, і притому саме завдання лежить в класі. Такі завдання називають повними завданнями для даного класу. Найбільш відомими є NP-повні задачі.

Повні завдання - хороший інструмент для доказу рівності класів. Достатньо для однієї такої завдання надати алгоритм, вирішальний її і належить більш маленькому класу, і рівність буде доведено.


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

Кожен клас складності (у вузькому сенсі) визначається як безліч предикатів, що володіють деякими властивостями. Типове визначення класу складності виглядає так:

Класом складності X називається безліч предикатів P (x), вичіслімих на машинах Тьюринга і використовують для обчислення O (f (n)) ресурсу, де n - довжина слова x.

Як ресурси зазвичай беруться час обчислення (кількість робочих тактів машини Тьюринга) або робоча зона (кількість використаних осередків на стрічці під час роботи). Мови, які розпізнаються предикатами з деякого класу (тобто безлічі слів, на яких предикат повертає 1), також називаються належать того ж класу.

Крім того, багато класів можуть також бути описані в термінах математичної логіки або теорії ігор.

Класи прийнято позначати великими літерами. Доповнення до класу C (тобто клас мов, доповнення яких належать C) позначається co-C.

Ієрархія класів складності

2. Відносини між класами

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


3. Ієрархія за часом і ієрархія по пам'яті

Розглянемо функцію f і вхідні ланцюжок довжиною n. Тоді клас DTIME (f (n)) визначають як клас мов, прийнятих детермінованими машинами Тьюрінга, заканчивающими свою роботу за час, не перевершує f (n). Клас NTIME (f (n)), у свою чергу, визначають як клас мов, прийнятих недетермінованої машиною Тьюринга, заканчивающими свою роботу за час, не перевершує f (n). Зазначимо, що обмеження на пам'ять при визначенні даних класів відсутні.

Аналогічно ієрархії за часом вводиться ієрархія по пам'яті. Клас DSPACE (f (n)) позначає клас мов, прийнятих детермінованими машинами Тюрінга, що використовують не більше f (n) елементів пам'яті на робочих стрічках. Клас NSPACE (f (n)) визначають як клас мов, прийнятих недетерміновані машинами Тюрінга, що використовують не більше f (n) елементів пам'яті на робочих стрічках. Тимчасові обмеження щодо даних класів відсутні.

Аналогічно визначаються і інші подібні розглянутим вище класи. Наведемо використовуються скорочення:

  • D - детермінований (детерминистический)
  • N - недетермінірованний
  • R - імовірнісний з обмеженою односторонньої помилкою
  • B - імовірнісний з обмеженою двосторонньої помилкою
  • BQ - квантовий з обмеженою двосторонньої помилкою

Література

  • Джон Хопкрофта, Раджив Мотвані, Джеффрі Ульман Введення в теорію автоматів, мов і обчислень = Introduction to Automata Theory, Languages, and Computation - М .: "Вільямс", 2002. - С. 528. - ISBN 0-201-44124-1.

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

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

Схожі роботи:
Теорія складності
Зведення (теорія складності обчислень)
Клас co-NP
Клас RP
Клас PP
Клас PH
Клас R
Клас NP
Клас P
© Усі права захищені
написати до нас