В інформатиці існують деякі проблеми, розв’язки яких ще не знайдено, задачі поділяються на класи, відомі як Класи складності . У теорії складності клас складності — це набір проблем із пов’язаною складністю. Ці заняття допомагають вченим групувати проблеми залежно від того, скільки часу та місця їм потрібно для вирішення проблем і перевірки рішень. Це розділ теорії обчислень, який має справу з ресурсами, необхідними для вирішення проблеми.

strsep c

Загальними ресурсами є час і простір, що означає, скільки часу потрібно алгоритму для вирішення проблеми та відповідне використання пам’яті.

• Часова складність алгоритму використовується для опису кількості кроків, необхідних для вирішення проблеми, але вона також може бути використана для опису часу, необхідного для перевірки відповіді.
• Просторова складність алгоритму описує, скільки пам’яті потрібно для роботи алгоритму.

Класи складності корисні для організації подібних типів задач.

Типи класів складності

У цій статті розглядаються такі класи складності:

1. P клас
2. НП Клас
3. Клас CoNP
4. НП-твердий
5. NP-повний

P клас

P у класі P означає Поліноміальний час. Це набір проблем прийняття рішень (завдань із відповіддю «так» або «ні»), які може розв’язати детермінована машина за поліноміальний час.

особливості:

• Рішення для P проблема s легко знайти.
• П часто є класом обчислювальних задач, які можна розв’язати та пров’язати. Поступливість означає, що проблеми можна вирішити як теоретично, так і на практиці. Але проблеми, які можна вирішити в теорії, але не на практиці, відомі як нерозв’язні.

Цей клас містить багато проблем:

1. Обчислення найбільшого спільного дільника.
2. Знаходження максимальної відповідності.
3. Сортування злиттям

НП Клас

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

особливості:

в порядку

• Розв’язки класу NP важко знайти, оскільки вони розв’язуються недетермінованою машиною, але розв’язки легко перевірити.
• Проблеми NP можуть бути перевірені машиною Тьюрінга за поліноміальний час.

приклад:

Розглянемо приклад, щоб краще зрозуміти НП клас . Припустимо, що є компанія, яка має загальну суму 1000 співробітники, які мають унікального співробітника ідентифікатори . Припустимо, що є 200 доступні для них кімнати. Добірка 200 співробітники повинні бути разом, але генеральний директор компанії має дані деяких співробітників, які не можуть працювати в одній кімнаті з особистих причин.
Це приклад ан наприклад проблема. Оскільки легко перевірити, чи даний вибір 200 співробітники, запропоновані колегою, є задовільними чи ні, тобто жодна пара зі списку колег не відображається в списку, наданому генеральним директором. Але створення такого списку з нуля здається настільки складним, що абсолютно непрактичним.

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

Цей клас містить багато проблем, які хотілося б ефективно вирішити:

1. Булева проблема виконуваності (SAT).
2. Проблема гамільтонового шляху.
3. Розфарбовування графіка.

Ко-НП клас

Co-NP означає доповнення класу NP. Це означає, що якщо відповідь на задачу в Co-NP — Ні, то є доказ, який можна перевірити за поліноміальний час.

особливості:

• Якщо задача X знаходиться в NP, то її доповнення X’ також знаходиться в CoNP.
• Для задачі NP і CoNP немає необхідності перевіряти всі відповіді одночасно за поліноміальний час, потрібно перевірити лише одну конкретну відповідь «так» або «ні» за поліноміальний час, щоб проблема була в NP або CoNP.

Деякі приклади проблем для CoNP:

1. Щоб перевірити просте число.
2. Факторізація цілого числа.

NP-твердий клас

NP-складна задача принаймні така ж складна, як і найскладніша задача в NP, і це такий клас задач, що кожна проблема в NP зводиться до NP-складної.

оператори if else java

особливості:

• Усі NP-складні проблеми не в NP.
• Щоб їх перевірити, потрібно багато часу. Це означає, що якщо надано розв’язок NP-складної задачі, потрібно багато часу, щоб перевірити, правильне воно чи ні.
• Проблема A є NP-складною, якщо для кожної проблеми L із NP існує скорочення за поліноміальний час від L до A.

Деякі з прикладів проблем у Np-hard:

1. Проблема зупинки.
2. Кваліфіковані булеві формули.
3. Гамільтонів цикл відсутній.

НП-повний клас

Проблема є NP-повною, якщо вона і NP, і NP-складна. NP-повні задачі — складні задачі в NP.

особливості:

• NP-повні задачі є особливими, оскільки будь-яка задача класу NP може бути перетворена або зведена до NP-повних задач за поліноміальний час.
• Якщо можна розв’язати NP-повну задачу за поліноміальний час, то можна також розв’язати будь-яку NP-проблему за поліноміальний час.

Деякі приклади проблем включають:

1. Гамільтонів цикл.
2. Задовільність.
3. Вершинне покриття .