Сложностные классы

16.10.2024

Классы сложности: P, NP, coNP, NP-hard и NP-complete

В информатике существуют задачи, которые сложно решать, их объединяют в классы сложности. Эти классы описывают, сколько времени и памяти нужно, чтобы решить задачу или проверить решение.

Классы сложности показывают, насколько трудно решить или проверить задачу.

Временная и пространственная сложность

• Временная сложность: сколько шагов/времени нужно, чтобы решить задачу.

• Пространственная сложность: сколько памяти нужно для работы алгоритма.

Классы сложности

Класс сложности P

• P — задачи, решаемые за полиномиальное время.

• Решение легко найти.

• Примеры:

  • НОД (наибольший общий делитель)

  • Сортировка слиянием

Класс сложности NP

• NP — задачи, которые можно проверить за полиномиальное время.

• Решение найти трудно, но легко проверить.

• Примеры:

  • SAT (выполнимость логических формул)

  • Раскраска графов

Класс Co-NP

• Co-NP — дополнение к NP, отрицательные ответы можно проверить за полиномиальное время.

• Если задача в NP, её дополнение в Co-NP.

• Примеры:

  • Проверка простоты числа

  • Факторизация чисел

NP-hard

• NP-hard — задачи, не обязательно решаемые за полиномиальное время.

• Проверка решения занимает много времени.

• Примеры:

  • Проблема остановки

  • Нет гамильтонова цикла

NP-complete

• NP-complete — задачи, которые одновременно NP и NP-hard.

• Любую NP-задачу можно свести к NP-complete.

• Примеры:

  • Гамильтонов цикл

  • Вершинное покрытие

Класс сложности	Описание
P	Легко решаются за полиномиальное время.
NP	Легко проверить решение за полиномиальное время.
Co-NP	Легко проверить отрицательный ответ за полиномиальное время.
NP-hard	Задачи сложнее, проверка решения занимает много времени.
NP-complete	NP и NP-hard задачи. Если решена одна, решены все.