dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 1, пп.4-5. Задачи … NP и P, NP+ и P+.

к Оглавлению

4. или 2.1+ Данная задача будет из класса P+, если есть алгоритм M(x), который в пределах полиномиального от |x| и S(x) времени (т.е. количество шагов работы алгоритма M(x) – в пределах p(|x|, S(x)) где S(x) работает полиномиальное время от размера |x|) возвращает:

y, если имеется y, такой что L(x, y) = 1 и в т.ч. |y| ≤ S(x),

0, если такого y нет.

Разумеется, если алгоритм проверки имеет вид L(t, S, y), то соответствующий ему алгоритм из P+ будет иметь вид M(t, S).

И пункт 4 (2.1+) превращается в п.2.1, если S(x) = p_2(|x|). А задача из класса P+ оказывается тогда задачей из класса P.

5. (Не)полиномиальность времени работы алгоритма никак не зависит от того, сколько времени данный алгоритм работает на данной единичной задаче – если время его работы конечно.

Действительно, любая единичная задача, которая решается за конечное время, может считаться решенной за полиномиальное время. Ведь полиномиальность времени решения относится лишь к массовой задаче, и если единственная задача (или конечное их число) из данной массовой задачи решается за огромное, но конечное время, то к полиному просто добавляется какая-то константа. Поэтому корректный алгоритм-решение M(x) может работать сколь угодно долго над решением единичной задачи L(x, y) (при заданном x). Но если он всё же остановится с корректным результатом – то его долгая работа никак не уменьшит возможности найти полиномиальное решение для массовой задачи данного L(x, y) (при произвольном аргументе x).


Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments