Математическая логика и теория алгоритмов. Стенюшкина В.А. - 74 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

полиномиальным . Имеет место теорема: задача о выполнимости формулы NР -
полна. Предупреждение: естественный способ построение формулы, которая
вычисляет туже функцию, что и заданная схема, состоящий в последовательной
записи подформул, отвечающих тому или иному элементу (например, для вы-
хода элемента «и» формула имеет вид ϕ1∧ ϕ2, где ϕ1, ϕ2 – формулы, соответс-
твующие входам элемента), не является полиномиальным. Общая идея состав-
ления формулы, которую строит «нужный» сводящий алгоритм – в том, что
вводится дополнительная переменная для каждого провода в схеме (а не только
ее входов). Например, схеме (рисунок 3.1) соответствует формула ϕ = х
8
∧ (х
8
↔(х
7
∨ х
6
)) ∧ (х
7
↔ (х
4
∨ х
5
)) ∧ (х
6
↔ (х
2
∨х
3
) ∧ (х
5
↔ х
3
) ∧ (х
4
↔ (х
1
∧х
2
)). Та-
кое построение приводит к схеме полиномиального размера и выполняется за
полиномиальное время.
Рисунок 3.1
2 Задача о клике Дан граф. Найти максимальный размер клики в этом графе.
Напомним, клика в неориентированном графе есть полный подграф данного
графа. Размером клики называется число ее вершин.
3 Задача о суммах подмножеств Требуется выяснить, существует ли подм-
ножество данного множества с заданной суммой элементов.
х
1
х
4
Λ
х
2
V х
7
х
5
х
8
х
3
V
х
6
V 
полиномиальным . Имеет место теорема: задача о выполнимости формулы NР -
полна. Предупреждение: естественный способ построение формулы, которая
вычисляет туже функцию, что и заданная схема, состоящий в последовательной
записи подформул, отвечающих тому или иному элементу (например, для вы-
хода элемента «и» формула имеет вид ϕ1∧ ϕ2, где ϕ1, ϕ2 – формулы, соответс-
твующие входам элемента), не является полиномиальным. Общая идея состав-
ления формулы, которую строит «нужный» сводящий алгоритм – в том, что
вводится дополнительная переменная для каждого провода в схеме (а не только
ее входов). Например, схеме (рисунок 3.1) соответствует формула ϕ = х8 ∧ (х8
↔(х7 ∨ х6)) ∧ (х7 ↔ (х4 ∨ х5)) ∧ (х6 ↔ (х2 ∨х3) ∧ (х5 ↔  х3) ∧ (х4 ↔ (х1 ∧х2)). Та-
кое построение приводит к схеме полиномиального размера и выполняется за
полиномиальное время.

                 х1                     х4
                                    Λ
                 х2                               V   х7

                                            х5
                                                               х8
                 х3                                        V
                                        х6
                                                      V


                                        Рисунок 3.1

   2 Задача о клике Дан граф. Найти максимальный размер клики в этом графе.
   Напомним, клика в неориентированном графе есть полный подграф данного
   графа. Размером клики называется число ее вершин.
   3 Задача о суммах подмножеств Требуется выяснить, существует ли подм-
   ножество данного множества с заданной суммой элементов.

Страницы