Труднорешаемые задачи. NP-полные задачи.

 

В качестве небольшого, но важного отступления отметим в данном разделе, что

алгоритмическая разрешимость еще не означает, что задача может быть реально решена.

Дело в том, что для нас на практике задача, решение которой требует тысячу лет или ресурсы,

превышающие все вычислительные ресурсы планеты, тоже неразрешима.

И здесь вступает в силу «математика практической осуществимости»…Такого рода проблемами занимается

теория сложности вычислений.

Рассмотрим для иллюстрации таблицу, в которой четыре столбца, соответствующие «абстрактному» объему

исходных данных (n)

Три строки соответствуют различным «функциям сложности вычислений». В таблице приведены времена

вычислений в зависимости от объема данных и сложности вычислений (F).

n F
n	10-5 cек	30*10-6 cек.	30*10-6 cек.	30*10-6 cек.
n5	0.1 cек.	24.3 cек.	5.2 мин.	13 мин.
2n	10-3 cек.	17.9 мин.	35.7 лет	366 столетий

 

Бросается в глаза быстрый рост сложности вычислений в последней строке.

Действительно, с точки зрения теории сложности вычислений, между последним и двумя первыми типами

задач пропасть. Первые две задачи относятся к классу задач с полиномиальной сложностью.

А последняя – к задачам с экспоненциальной сложностью. Такие задачи называются трудноразрешимыми.

Класс этих задач формируется эмпирически и носит название класса NP - полных задач.

Есть какая-то аналогия между проблемами алгоритмической разрешимости и трудноразрешимости.

Как из-за невозможности определить понятие алгоритма проблема алгоритмической разрешимости

сводится к возможности построения конкретизации, так и трудноразрешимость устанавливается сведением

исследуемой задачи к одной из «эталонных» NP - полных задач.

 

 

Неклассические логики.

Модальность - дополнительная характеристика, приписываемая высказыванию.

Пусть A - высказывание.

A - необходимо А.

àА - возможно А.

Если. А = 0, то ðА = 0

Если ðА = 1, то àА = 1.

Но если А = 1*, то ðА может быть истинно или ложно.

Скажем, «Вася ловит рыбу» - истинно, но «Необходимо, что Вася ловит рыбу» – ложно, поскольку Вася это

делает только по настроению.

Например, «Летом выпал снег» – может быть ложным высказыванием, а «Возможен случай, что летом

выпадет снег» - истинным.

0, если противоречит (физическим) законам. 1, иначе.

{

Но если

А = 0, то àА =

 

Например, «2 + 2 = 5» - ложно и «возможно, что 2 + 2 = 5» – также ложно, но

«Вася стреляет» – ложно, но «Вася может и пострелять» – истинно (особенно, когда деньги кончились, а

курить охота).

Существует достаточно большое количество разновидностей модальных логик.

Немонотонные логики. Кратко суть таких логик формулируется следующим образом: добавление в

систему новых аксиом может привести к изменению уже существовавших…Они хороши тем, что часто

следуют принципу: Если не нравится полученный в процессе вывода результат - можно изменить

исходные посылки. Существует много весьма разноплановых немонотонных логик. Например, вывод

C(x, y) & Г(y)=z: àГ(x) = z |¾ Г(x) = z

То есть из фактов, что C(x, y) - "x,y - супруги",. Г(y)=z - "город, где проживает y. называется z". Символ «:»

отделяетусловие от предложения.

и à Г(x) = z - "x живет в городе z" не противоречит существующим аксиомам, то.

в этой системе выводимо Г(x) = z, что "x живет в городе z".

Индуктивные логики. Это логики правдоподобных рассуждений "от частного к общему".

Когда Шерлок Холмс по отдельным уликам восстанавливал картину преступления, то его дедуктивный

метод был чистой воды индуктивным методом.

Это элементарно, Ватсон!

Поскольку правдоподобные рассуждения не гарантируют стопроцентно правильность логического

заключения (у Холмса результат был близок к 100%, хотя и у него бывали ошибки), то можно говорить о

большей или меньшей правдоподобности результата.

Эротетические логики. Так названы логики вопросов и ответов.

Правильно поставленный вопрос - это такой вопрос у которого предпосылка истинна и не противоречива.

В рамках этой логики доказана полезная для повседневной практики теорема:

На глупый вопрос нельзя дать умный прямой ответ.

Два основных типа вопросов:

уточняющие (типа. ли),

воспроизводящие (типа что).

Вопросы могут быть простыми и сложными.

А ответы могут быть:

- истинные и ложные,

- прямые и косвенные,

- краткие и развернутые,

- полные и неполные.

Временные логики:

Высказывание А,

Р_А - "было А"

F_A - "будет A"