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

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

Languages and Computation (англ.) (вид. 2-ге). Addison-Wesley. ISBN 0-201-44124-1. Портал «Математика» Клас складності NP NP-складна задача NP-повна задача...

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

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

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

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

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

(від англ. Exponential Time — експоненційний час) — в теорії складності обчислень, клас задач, які розв'язні на машині Тюринга за час O(2p(n))), де p(n) —...

{\displaystyle O(f(n))} простір. Класи складності PSPACE і NPSPACE дозволяють f {\displaystyle f} бути будь-яким многочленом, аналогічно P і NP. Тобто, P S P A C E...

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

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

знизити витрати на перевезення. ТЗ по теорії складності обчислень є NP-складною або входить в клас складності NP. Коли сумарний обсяг пропозицій (вантажів...

утворює відношення. Клас складності, отриманий з цього перетворення, позначається через F ( N P ) {\displaystyle \mathbf {F} (\mathbf {NP} )} або FNP[en]...

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

використання паралелізму. Так само, як клас NP-повних задач можна вважати класом «найпевніше непіддатливих» задач, так і клас P-повних задач[en], при зведенні...

називається NP-складною, якщо до неї зводиться будь-яка мова класу NP, і називається NP-повною, якщо вона NP-складна і сама зводиться до класу NP. Якщо буде...

буде знайдено для всіх завдань класу NP. Прикладом NP-повної задачі є задача про кон'юнктивні форми. Дослідження складності алгоритмів дозволили по-новому...

NP-складна задача (англ. NP-hard) — задача не менш складна ніж NP-повна. Задача Π є NP-складною, якщо існує NP-повна задача Π1, що зводиться до Π. Задача...

знаходження критичного шляху в задачах планування. Докладніше: Клас складності NP NP-складність незваженої задачі пошуку найдовшого шляху можна показати, звівши...

scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження...

вершинного покриття, була однією з 21 NP-повної задачі Карпа і, отже, класичною NP-повною задачею в теорії складності обчислень. Задачу найменшого вершинного...

термін «NP-повна задача», і задача SAT була першою задачею, для якої доводилася ця властивість. У доказі теореми Кука кожна задача з класу NP в явному...

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

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

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

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

розв'язувати певні задачі вибору за одну дію. Задача може бути будь-якого класу складності. Можна використовувати навіть нерозв'язні задачі, такі як проблема...

задача з класу NP у явному вигляді зводиться до SAT. С. Кук визначив клас NP задач розпізнавання властивостей наступним чином. Задача належить класу NP, якщо :...

належить до класу NP, невідомо є вона NP-повною чи належить класу P (за умови, що P ≠ NP). При цьому задача пошуку ізоморфного підграфа в графі є NP-повною...

підмножин складності NP, що дозволяє уникнути проміжних задач NP-складності, існування якої було продемонстровано в теоремі ладнері в припущенні, що P ≠ NP. Дихотомічна...