Клас складності P (англ. Complexity class P) — клас задач, що можна розв'язати алгоритмами з поліноміальним часом. Алгоритмом з поліноміальним часом називається...

Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний...

Теорія складності обчислень — підрозділ теоретичної інформатики, що займається дослідженням складності алгоритмів для розв'язання задач на основі формально...

саме сюди P — літера латинської абетки. P — хімічний символ Фосфору. P — клас складності P — символ, яким позначається амінокислота пролін p — глухий губно-губний...

У теорії алгоритмів питання про рівність класів складності P і NP є однією з центральних відкритих проблем вже більше трьох десятиліть. Якщо на нього...

Складність обчислювальних процесів — це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу та пам'яті) необхідних для виконання алгоритму...

Клас складності PH (від англ. polynomial hierarchy) — об'єднання всіх класів складності з поліноміальної ієрархії: PH = ⋃ k ∈ N ( Σ k p ∪ Π k p ) = ⋃...

В теорії алгоритмів класом складності BPP (від англ. bounded-error, probabilistic, polynomial) називається клас предикатів, які швидко (за поліноміальний...

поведінку складності при збільшенні розміру вхідних даних, тобто асимптотичну поведінку складності алгоритму. Це пояснює, чому зазвичай часову складність часто...

NL Твердження: PATH — NL-повна задача. Наслідок: N L ⊆ P {\displaystyle NL\subseteq P} . Клас coNL — мови, доповнення до яких лежать у NL. Теорема Іммермана:...

У теорії складності поліноміальна ієрархія — це ієрархія класів складності, яка узагальнює класи P, NP, co-NP до обчислень з оракулом. Існує багато еквівалентних...

Класи складності PSPACE і NPSPACE дозволяють f {\displaystyle f} бути будь-яким многочленом, аналогічно P і NP. Тобто, P S P A C E = ⋃ c ∈ Z + D S P A...

теорії складності обчислень, клас задач, які розв'язні на машині Тюринга за час O(2p(n))), де p(n) — поліноміальна функція від n. Відомо, що P ⊆ {\displaystyle...

NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний...

теорії складності обчислень, co-NP — клас складності. Задача належить класу co-NP тоді і тільки тоді, коли компланарна до неї задача належить класу NP. Неформально...

В теорії складності обчислень класом NC (від англ. Nick’s Class) називають множину задач розв'язності, що розв'язуються за полілогарифмічний час на паралельному...

складності обчислень — перетворення однієї задачі до іншої. У загальному випадку, для алгоритму, що перетворює примірники задачі P 1 {\displaystyle P_{1}}...

Клас APX (від англ. approximable) у теорії обчислювальної складності — це клас NP-складних задач, для яких існують апроксимаційні алгоритми поліноміальної...

до класу складності P. Перші кроки у визначенні обчислювальної складності зроблено в напрямку доведення, що задача належить до складніших класів складності...

функціональною проблемою у теорії складності обчислень є обчислювальна складність, де для кожного введеного значення очікується окреме вихідне значення...

зв'язки між PSPACE та класами NL, P, NP, PH, EXPTIME, EXPSPACE: NL ⊆ P ⊆ NP ⊆ PH ⊆ PSPACE {\displaystyle {\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq...

Цикломати́чна скла́дність — метрика програмного забезпечення, розроблена Томасом Мак Кабе. Використовується для оцінки складності програм. Обчислює кількість...

здійснюється класифікація завдань за класами складності (P-складні, NP-складні, експоненціально складні і ін.). До класу P відносяться завдання, які можуть...

поліноміальної складності, але для кожного довільного, поліноміальної складності, алгоритму A виконується: P r [ f ( A ( f ( x ) ) ) = f ( x ) ] < 1 p ( n ) {\displaystyle...

завданням: воно потрапляє до класу складності #P-складні[en]. Більше того, його апроксимація в межах мультиплікативної помилки також є #P-складною проблемою. Усі...

включає кілька важливих класів складності, передбачає ймовірність помилки 1/3. Наприклад, клас складності BPP визначається як клас мов, розпізнаних імовірнісною...

часу), він також може швидко знайти цей розв'язок. Проблема рівності класів складності P і NP є однією з найважливіших проблем теорії алгоритмів і має багато...

«P = NP» (див. класи складності P і NP). Клас алгоритмів, виконуваних за поліноміальний час на недетермінованих машинах Тюрінга, називається класом NP...

який показав, що клас складності з поліноміальним часом (клас PostBQP) на такій машині еквівалентний до класичного класу складності PP. Deutsch D. Quantum...

теорії складності обчислень для характеристики обчислювальної складності проблем вибору. Наприклад, задача здійсненості бульових формул є повною у класі складності...

NP-повну задачу за поліноміальний час, тоді всі NP-задачі належать до класу P. Розглянемо дві мови L 1 {\displaystyle L_{1}} і L 2 {\displaystyle L_{2}}...