Понятие полиномиальной сводимости. Класс NPC. Примеры NP-полных задач

Пусть есть задача А с входными данными из множества х1 и выходными данными из множества у1 и есть задача В, которая переводит х2 в у2

Если существует задачи Т1: х1->x2; T2: y2->y1, такие что:

1. Для любых х x1 T2(B(T1(x)))=A(x)

2. T1,T2 , то говорят, что задача А полиноминально сводима к задаче В:

 

Свойства полиномиальной сводимости:

1. Если В и , то А . Доказательство из определения п.1

2. Если А Pи , то В Р. Доказательство от противного.

3. Если B и , то А . Верно обратное, доказательство аналогично.

4. Если , , то

Пример: НОК (a,b)

Задача:

· А – нахождение НОК

· В – нахождение НОД

· Т1- тождественное преобразование

· Т2 – вычисление по формуле

 

Класс NPC

Задача Т , если:

· T

· Для любых T’

P<>NP

Если Р=NP=NPC

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

 

Принадлежность к классу NPC:

Утверждение: Пусть есть задача T0 , если задача T и задача , то задача T

T0 => =>T

Доказательство принадлежности к NP:

1. Из определения

2. Строго говоря, понятие класса NPвводится только для задач принятия решений

 

Примеры NP-полных задач:

· Задача о минимальном вершинном покрытии

· Задача о рюкзаке