Редактирование: Методы оптимизации, обозначения
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 45: | Строка 45: | ||
* '''co-P''' -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12) | * '''co-P''' -- класс задач, дополнительных к полиномиально разрешимым задачам (стр. 12) | ||
* '''co-NP''' -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12) | * '''co-NP''' -- класс задач, дополнительных к недетерменированно полиномиально разрешимым задачам (стр. 12) | ||
- | * '''NC''' (Nick Сlass) -- класс задач, решаемых за время, ограниченное полиномом от | + | * '''NC''' (Nick Сlass) -- класс задач, решаемых за время, ограниченное полиномом от длины входа и требующих полиномиальной памяти.(стр. 19) |
* '''NPC''' -- класс '''NP'''-полных задач (стр. 14) | * '''NPC''' -- класс '''NP'''-полных задач (стр. 14) | ||
* '''PSPACE''' -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19) | * '''PSPACE''' -- класс задач, требующих для решения не более чем полиномиальной памяти (стр. 19) | ||
{{Курс Методы оптимизации}} | {{Курс Методы оптимизации}} |