dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 6, пп. 2.4-3. Задачи … из класса NP

к Оглавлению

2.4. Притом «персональную подсказку» для алгоритма-решения «Эдип» алгоритм «Сфинкс» должен выдать за полиномиальное количество шагов относительно не всех аргументов задачи, а относительно какого-то параметра (или параметров), которые позволяют выделить нужную зависимость остальных аргументов так, чтобы получались только «подходящие» аргументы для «персональной подсказки».

Например, пусть среди аргументов будут ещё аргументы S, s. Аргумент S будет обеспечивать все нужные зависимости, а аргумент s будет лишь иметь соответствующий размер, допускающий нужный размер аргумента y (у нас же задача из NP и наибольший размер доказательства y должен опираться через полином на размер каких-то других аргументов). Тогда перепишем формулу «персональной подсказки» для «Эдипа» так:

SphOedSph(…, …, …, …, …)», «-», …, …, …)», t(S), S, s, y) = 0

А теперь можно представить данный алгоритм проверки в сокращённом виде – превратив общую исходную задачу проверки «Сфинкс» в задачу только для разбираемой персональной подсказки:

Sph_S(S, s, y) = 0

При этом известно, что никакое доказательство не подходит и ответ получается без рассмотрения доказательства для данной частной подзадачи. То есть тут – время работы алгоритма Sph_S(S, s, y) не зависит от y (и от размера |y|). И еще – между y и s есть соотношение – полиномиальности. Поэтому, когда «отмирает» y – то «отмирает» и s за ненадобностью.

Вся эта «абстрактная» подготовка в данном пункте – является более развёрнутым изложением пункта 2.3 раздела 1 «Задачи из классов NP и P, NP+ и P+». А соответствующий алгоритм «Сфинкс» будет реализован в следующем разделе.

От «Эдипа» требуется решать полученную «подзадачу» на тех же принципах, что и любую задачу из класса NP (раз мы ищем полный алгоритм-решение, способный сводить произвольную задачу из класса NP к задаче из класса P). И тогда время ответа «Эдипа» для частной задачи из «персональной подсказки» с её ограничивающим полиномом на время работы  p_{Sph_S}(|S|) должно будет уложиться в его («Эдипа») ограничивающий алгоритм от тех же значимых аргументов – p_{Oed_S}(|S|). А такой ограничивающий алгоритм для времени работа «Эдипа» при ответе на «специальный вопрос» может быть неполиномиально меньше, чем у алгоритма-проверки для общей задачи – p_{0}(|S|, |s|, …).

При таком поведении «Эдипа» будет соблюдён и принцип решения задач из класса NP: время работы алгоритма-решения не должно превышать некоторого полинома от тех значений, которые составляют ограничивающий полином для времени работы алгоритма проверки. И будет соблюдён принцип идентичности требований к решению задач – составленных подстановкой нужных зависимостей в некоторые параметры из более общей задачи – с одной стороны, а с другой стороны – те же задачи, но в которых эти же зависимости изначально считаются фиксированными (частью программы).

Обобщим полученный вывод:

Если для «персональной подсказки» алгоритма «Сфинкс» о возможностях алгоритма «Эдип» имеется ограничивающий полином p_0(|x1|, |x2|, … ) на время получения «подсказки», то корректный алгоритм «Эдип», способный сводить задачи из класса NP к задачам из класса P, найдёт правильный ответ (если он есть) или выдаст 0 (если «персональная подсказка» не содержит правильного ответа) за время, ограниченное некоторым полиномом от тех же аргументов p(|x1|, |x2|, … ).

2.5. Для тех, кто помнит пункт 5 из раздела 1 «Задачи из классов NP и P, NP+ и P+» поясню, что полиномиальность времени работы действительно является атрибутом массовой, а не единичной задачи – то есть, не все параметры (аргументы), относящиеся к «персональной подсказке» в ней могут быть зафиксированы. Уже и по этой причине нам потребовались дополнительные аргументы S, s.

3. Возникает вопрос об уместности требования от корректного «Эдипа» выявлять «подзадачи», которые пусть реально существуют внутри общей задачи, но не в «готовом виде». Но в таком нашем требовании к корректному «Эдипу» мы не нарушаем сам принцип требования к «Эдипу» –  «понимать условности». Даже «готовый вид» задачи из класса NP – это некая условность. Мы даже информацию об алгоритме проверки «Сфинкс» передаём на каком-то языке. А это может быть Pascal, C, Prolog или даже на русском – из программы бухучёта 1С.

В сфере IT вопрос взаимодействия между программами является одним из важнейших. Написаны объёмные технологические стандарты типа com+, Corba, программы на .Net содержат в себе «манифесты» для других программ, в Интернете работает множество протоколов взаимодействия между  клиентом и сервером и т.д. и т.п. И это всё – не принципиальные вопросы, а вопросы принятых условностей. Мы просто рассматриваем те алгоритмы-решения, которые «понимают» нужный нам «протокол». Если наша программа ориентирована на русский язык, то «английские» алгоритмы-решения её не поймут, но важен принцип возможности решить (или невозможности решить) со стороны той программы, которая «понимает» не принципиальные условности.

Даже «персональная подсказка» выдаётся по определённому протоколу. Как «Эдипу» выделить нужную «подзадачу»? Такой вопрос стоял бы, если бы у нас было множество «специальных задач», тогда и «Сфинкс» был бы написан иначе – и намного сложнее (в соответствии с каким-нибудь технологическим стандартом, например). Но мы будем рассматривать лишь одну «специальную задачу» – «АнтиЭдип» (для произвольного «Эдипа»). Наш протокол, который должен понимать «Эдип», можно упростить до такого: «Ищи персональную подсказку у «Сфинкса» для соответствующего тебе «АнтиЭдипа».

И ещё – по поводу того, что в общем случае для решения задачи из класса NP алгоритм-решение должен найти и использовать в данной задаче «персональную подсказку» для себя:

Нас ведь не удивляет, что в реальной жизни задачи, которые мы решаем – обычно поставлены персонально перед нами? Или перед нашим коллективом? Иногда их ставят люди, иногда «жизнь» или «воля божья» - кому как нравится считать. И то, что возможность решения задачи и результат решения зависят от «исполнителя» – как правило – факт. А то, что подобные факты до сих пор не были формализованы в математике – огромное упущение, которое будет исправлено в данной работе. И это гораздо более принципиальная и интересная часть работы, чем доказательство NPP – на мой взгляд.

Ещё кое-что о дополнительной «сложности» – понять, что речь «о тебе» – будет сказано в данном разделе ниже в пункте 5.1.


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