дно, що здійснимість 3-КНФ рівносильна спільності такої системи.
Зауваження 2.4. Якщо не вимагати цілочисельності рішень, то перевірити спільність системи лінійних нерівностей можна за поліноміальний час. p> Великий список NP-повних задач міститься в книзі Гері і Джонсона [<# "16" src = "doc_zip668.jpg"/>. Питається, чи є-елементне безліч вершин графа, будь-які дві вершини якого з'єднані ребром. p> Завдання
Доведіть, що завдання перевірки здійсненності 2-КНФ (кон'юнкції диз'юнкцій, кожна з яких містить два литерала) належить P.
Доведіть, що завдання про ейлерова шляху в неорієнтованому графі (чи існує шлях, що проходить по всіх ребрах рівно по одному разу) належить P.
Припустимо, що клас NP співпадає з P. Доведіть, що в цьому випадку за поліноміальний час можна не тільки перевірити здійснимість формули, але і знайти значення змінних, при яких вона істинна (аналогічно для Гамільтона циклу тощо)
Доведіть, що завдання про паросполучення (є хлопців і дівчат, відомо, які пари згідні один з одним танцювати, треба визначити, чи можна влаштувати танець, в якому всі хлопців і дівчат з'єднані в пари) належить NP і, більше того, належить P.
Побудуйте
полиномиальное зведення задачі 3-КНФ до задачі Кліка;
те ж питання, але додатково потрібно, щоб кількість рішень зберігалося (якщо 3-КНФ при зведенні відповідає пара (граф, розмір), то кількість виконують наборів змінних для дорівнює кількості клік розміру в графі).
Побудуйте
полиномиальное зведення задачі 3-КНФ до задачі 3-розмальовка;
те ж питання, але додатково потрібно, щоб кількість виконують наборів змінних для будь 3-КНФ дорівнювало б шестикратному кількості 3-розмальовок відповідного їй графа.
Покажіть, що наступна задача є NP-повною: дан набір з не більше ніж типів квадратиків, на сторонах яких написані якісь букви; дано список допустимих пар букв і список граничних букв; питається, чи можна коректно скласти з квадратиків набору великий квадрат розміру (так, щоб на прилеглих сторонах квадратиків були тільки допустимі пари букв, а на кордоні квадрата - тільки граничні літери).
Доведіть, що предикат "- двійкова запис складеного числа" належить NP.
Доведіть, що предикат "- двійкова запис простого числа" належить NP.
Розділ № 3. Імовірнісні алгоритми і клас BPP. Перевірка простоти числа
Тема 3.1 Імовірнісні алгоритми
У імовірнісних МТ (ВМТ), як і в недетермінірованних, маються стану, з яких можливий перехід у кілька (більше одного) станів. Відмінність полягає в тому, що стан, куди ВМТ робить перехід, визначається результатом деякого випадкового процесу ("підкидання монети"). Треба обумовити, які монети допускаються. Наприклад, якщо взяти монету, ймовірність випадання герба для якої дорівнює невичіслімому числа, то можливості ВМТ, що використо...