На головну

 Примітивно рекурсивні функції |  Приклади примітивно рекурсивних функцій |  Частково рекурсивна функція |

клас P

  1.  Fast Ethernet як розвиток класичного Ethernet'а
  2.  I. Класифікація суспільства за основним фактором виробництва.
  3.  I. Класифікація реклами за типом її спонсора, ініціатора комунікації.
  4.  I. Загальна характеристика та класифікація вуглеводів
  5.  II) Класифікація програм CALL.
  6.  II. Жири (ацілгліцероли). Їх структура, класифікація і властивості
  7.  II. Класна дама 1 сторінка

Основна стаття: клас P

Клас P вміщує всі ті проблеми, вирішення яких вважається «швидким», тобто полиномиально залежать від розміру входу. Так само як сортування, пошук у безлічі, з'ясування зв'язності графів і багато інших.

[Ред] Клас NP

Основна стаття: клас NP

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

[Ред] Проблема рівності класів P і NP

Основна стаття: Рівність класів P і NP

Питання про рівність цих двох класів вважається однією з найскладніших відкритих проблем в галузі теоретичної інформатики. Математичний інститут Клея включив цю проблему в список проблем тисячоліття, запропонувавши нагороду розміром в один мільйон доларів США за її рішення.

 



 Пристрій машини Тьюринга |  Оберіть твердження, вірні при люб. фін. ум.?
© um.co.ua - учбові матеріали та реферати