Классификация вычислительных задач по степени сложности. Классы сложности задач P и NP. NP сложные и NP трудные задачи — КиберПедия 

Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...

Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...

Классификация вычислительных задач по степени сложности. Классы сложности задач P и NP. NP сложные и NP трудные задачи

2017-06-19 717
Классификация вычислительных задач по степени сложности. Классы сложности задач P и NP. NP сложные и NP трудные задачи 0.00 из 5.00 0 оценок
Заказать работу

По книге Системы искусственного интеллекта

 

 

По интернетам

Классы задач в зависимости от их трудности

1. Алгоритмически неразрешимые задачи (нерешаемые задачи). Это задачи, для решения которых не существует алгоритма. Например, доказано, что задача определения, остановится или нет на машине Тьюринга заданная программа, является алгоритмически неразрешимой. В этой книге мы не будем обсуждать задачи из этого класса.

2. Труднорешаемые задачи (вероятно, сложные задачи). Это задачи, для решения которых, по-видимому, не существует полиномиального алгоритма. Иными словами, для их решения, скорее всего, существуют только экспоненциальные алгоритмы.

3. NP-задачи (NP — аббревиатура для «недетерминированные полиномиальные»). Это класс задач, которые мы можем решить за полиномиальное время, если угадаем, какой путь вычислений необходимо выполнить. Грубо говоря, этот класс включает в себя все задачи, которые имеют экспоненциальный алгоритм, но не доказано, что они не могут иметь полиномиального алгоритма.

4. Р-задачи (Р — аббревиатура для «полиномиальный»). Этот класс включает в себя задачи, которые имеют полиномиальные алгоритмы. Большинство людей считают, что этот класс является собственным подклассом класса 3.

По википедии

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

Класс сложности — это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:

Класс P

Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть время решения которых полиномиально зависит от размера входа. Сюда относится сортировка, поиск в массиве, выяснение связности графов и многие другие.

Класс NP

Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество шагов от размера входных данных. Их решение может быть проверено детерминированной машиной Тьюринга за полиномиальное количество шагов. Следует заметить, что недетерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют детерминированной машине Тьюринга с ограниченной памятью. Поскольку детерминированная машина Тьюринга может рассматриваться как специальный случай недетерминированной машины Тьюринга, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.


Поделиться с друзьями:

Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...

История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...

Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.006 с.