21 NP-полная задача Карпа | это... Что такое 21 NP-полная задача Карпа? (original) (raw)

21 NP-полная задача Карпа

Список Карпа - список, состоящий из формулировки и доказательства NP-полноты 21 задачи, опубликованный Ричардом Карпом в 1972 году в своем труде «Возможность редукции в комбинаторных задачах» (англ. «Reducibility Among Combinatorial Problems») [1].

Список задач

• Задача выполнимости булевых формул (англ. SAT)
  • Бинарное целочисленное программирование (англ. 1-0 integer programming)
  • Задача о клике (англ. Clique)
    * Задача "упаковки" множества (англ. Set packing)
    * Задача о вершинном покрытии (англ. Vertex Cover)
    * Задача о покрытии множества (англ. Set Covering)
    * (англ. Feedback Vertex Set)
    * (англ. Feedback Arc Set)
    * Задача ориентированного Гамильтонова графа(англ. Hamiltonian path problem, в определении Карпа - англ. Directed Hamilton Circuit)
    * Задача неориентированного Гамильтонова графа(англ. Hamiltonian path problem, в определении Карпа - англ. Undirected Hamilton Circuit)
  • Задача выполнимости булевых формул с тремя литералами (англ. 3-SAT)
    * Задача раскраски графа (англ. Graph coloring)
    * Задача о покрытии клики(англ. Clique cover)
    * Задача о точном покрытии (англ. Exact cover)
    * Задача о вершинном покрытии в гиперграфах (англ. Vertex cover in hypergraphs)
    * Задача дерева Штайнера (англ. Steiner tree problem)
    * (англ. 3-dimensional matching)
    * Задача о ранце (англ. Knapsack problem)
    * (англ. Job sequencing)
    * (англ. Partition problem)
    * Задача о максимальном разрезе (англ. Maximum cut)

См. также

Список NP-полных задач

Примечания

1. ↑ «Reducibility Among Combinatorial Problems», Р. Карп, 1972 год (англ.)

Категория:

• NP-полные задачи

Wikimedia Foundation.2010.

Полезное

Смотреть что такое "21 NP-полная задача Карпа" в других словарях:

• NP-полная задача — В теории алгоритмов NP полная задача задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP полные задачи образуют в некотором смысле подмножество «самых сложных» задач в… … Википедия
• Задача о вершинном покрытии — NP полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP полноты более сложных задач. Содержание 1 Определение 2 NP полнота 3 Ссылки … Википедия
• Задача о покрытии множества — является классическим вопросом информатики и теории сложности. Данная задача обобщает NP полную задачу о вершинном покрытии (и потому является NP сложной). Несмотря на то, что задача о вершинном покрытии сходна с данной, подход, использованный в… … Википедия
• Задача о независимом множестве — относится к классу NP полных задач в области теории графов. Эквивалентна задаче о клике. Содержание 1 Определения 2 Максимальное независимое множество в дереве … Википедия
• Задача о клике — относится к классу NP полных задач в области теории графов. Впервые она была сформулирована в 1972 году Ричардом Карпом.[1] … Википедия
• Задача выполнимости булевых формул — (SAT или ВЫП) важная для теории вычислительной сложности алгоритмическая задача. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача заключается в следующем: можно ли… … Википедия
• Задача коммивояжёра — Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр … Википедия
• Задача о ранце — Пример задачи о ранце: необходимо разместить ящики в рюкзак при условии на вместимость рюкзака 15 кг, так чтобы суммарная полезность предметов в рюкзаке была максимальной. Задача о ранце (рюкзаке) (англ. … Википедия
• Задача об упаковке в контейнеры — В теории сложности вычислений задача об упаковке в контейнеры NP трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число… … Википедия
• Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из… … Википедия