Индивидуальное домашнее задание по математической логике NP класс задач

Липецкий государственный технический университет


Кафедра автоматизированных систем управления








Индивидуальное домашнее задание

по математической логике



NP класс задач
















Студент _____________________ _____________________
подпись, дата фамилия, инициалы

Группа _____________________



Руководитель

___________________________ _______________________ ___________________
Ученая степень, ученое звание подпись, дата фамилия, инициалы







Липецк 2014 г.
Задание кафедры

1.Доказать принадлежность классу NP предложенной задачи
2. Решить одну из двух проблем:
...

-

2) Если предыдущее условие выполняется, проверить:r(a) ≤ d(a').3) Далее проверим I(a) ∩ I(a') с помощью отношения частичного порядка. Если предыдущее условие выполняется, проверить:σ(a) ≥ σ(a').4) Если предыдущее условие выполняется, проверить:σ(a) ≤ σ(a') + s(a') – 1.5) Если предыдущее условие выполняется, то данное распределение – неправильное. Если не выполняется – то правильное. Далее перейдём на нижний правый угол:1) Для каждой пары а, а' ϵ A проверить:d(a) ≥ r(a').2) Если предыдущее условие выполняется, проверить:d(a) ≤ d(a').3) Далее проверим I(a) ∩ I(a') с помощью отношения частичного порядка. Если предыдущее условие выполняется, проверить:σ(a) ≥ σ(a').4) Если предыдущее условие выполняется, проверить:σ(a) ≤ σ(a') + s(a') – 1.5) Если предыдущее условие выполняется, то данное распределение – неправильное. Если не выполняется – то правильное. Далее перейдём на верхний левый угол:1) Для каждой пары а, а' ϵ A проверить:r(a) ≥ r(a').2) Если предыдущее условие выполняется, проверить:r(a) ≤ d(a').3) Далее проверим I(a) ∩ I(a') с помощью отношения частичного порядка. Если предыдущее условие выполняется, проверить:σ(a) + s(a) – 1 ≥ σ(a').4) Если предыдущее условие выполняется, проверить:σ(a) + s(a) – 1 ≤ σ(a') + s(a') – 1.5) Если предыдущее условие выполняется, то данное распределение – неправильное. Если не выполняется – то правильное. Далее перейдём на верхний правый угол:1) Для каждой пары а, а' ϵ A проверить:d(a) ≥ r(a').2) Если предыдущее условие выполняется, проверить:d(a) ≤ d(a').3) Далее проверим I(a) ∩ I(a') с помощью отношения частичного порядка. Если предыдущее условие выполняется, проверить:σ(a) + s(a) – 1 ≥ σ(a').4) Если предыдущее условие выполняется, проверить:σ(a) + s(a) – 1 ≤ σ(a') + s(a') – 1.5) Если предыдущее условие выполняется, то данное распределение – неправильное. Если не выполняется – то правильное. Итого в каждом из четырёх случаев имеем размещение из общему количества элементов в биекции по два. Итого:4∙AA2=4∙A2=4∙A∙A-1…A-2+1=4∙A!A-2!=4∙A2∙2!Согласно определению полинома, это выражение, среди операций которого есть исключительно сложение, вычитание, умножение и возведение в неотрицательную целочисленную степень. А принадлежность к классу NP как раз и определяется возможностью сведения задачи к таким многочленам. Опишем это подробнее согласно одного из определений данного класса.То есть класс сложности NP как раз и определяется для множества языков, то есть множеств слов над конечным алфавитом Σ, для которых выполняется следующее условие. Язык L называется принадлежащим классу NP, если существуют двуместный предикат R(x, y) из класса P (то есть вычислимый за полиномиальное время) и константа c>0 такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдётся y длины меньше |x|c такой, что верно R(x, y)» (где |x| — длина слова x). Слово y называется сертификатом принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L. 2. Мы сводим к этой задаче задачу 3-РАЗБИЕНИЯ.