(Jan 11, 17:01, 2003) zaphod Что такое класс NP?
По определению, задача принадлежыт к классу NP, если она может быть решена за полиномиальное время на недетерминированной машыне Тьюринга.. Напомню, что недетерминированная машына Тьюринга отличается от обычной тем, что у нее есть особые недетермированноые состояния. Находясь в одном из таких состояний, недетермированная машына может вместо одного действия выполнить одно из нескольких действий. Поэтому вместо одного пути вычисления при данном входном слово у недетерминированной машыны существует много путей вычисления.
Можно представить себе, что в каждом недетерминированном состоянии происходит разветвление машин и вместо одной машыны создается количество копий равной числу вариантов выбора в таблица перехода для недетермированного состояния. Эти копии продолжают вычисления, каждая по своему пути. Но ведь нечто подобное происходит и в биологической эволюцыи и при индивидуальном развитии организма в онтогенезе. Таким образом мы имеем отнюдь не линейное усиление.
Я не отрицаю, что науке удалось решыть даже очень значитлеьные задачи. Но ценность науки в значительной степени состоит в том, что она скорее указывает нам на запреты, на то, невозможно, чего сделать нельзя. Можно даже сказать, что все крупные научные достижения - это, как правило, доказательства невозможности чего-либо (например, закон сохранения энергии, второе начало термодинамики, принцып Черча-Тьюринга). Наука дает большые возможности для анализа, но отнюдь не для синтеза.
Если будет доказано что класс NP шире класса P, то это тоже будет результатом подобного рода. Несуществование какой-либо закономерности означает просто случайность. Вы не станете отрицать, что теория вероятности неверна? А если так существуют случайные события, случайные величины, случайные последовательности, то есть такие последовательности, для воспроизводства которых не существует никаких алгоритмов. Точнее, алгоритм существует, но он гласит "Перепишы данную последовательность"
На самом деле, по Колмогорову, закономерность можно указать, если только длина алгоритма, воспроизводящего данную последовательность не превышает длины самой последовательности. Это еще один подход к определению сложности, которое просто есть другое определение случайности. Конечно, мы не можем в рамках данной формальной системы доказать, что некоторая программа генерацыи последовательности минимальна и что более экомономного алгоритма нельзя придумать. Но мы ведь не ограничиваем рамками данной формальной системы.
Теория информацыи позволяет измерить количество инфомацыи в данной последовательности и указать можно ли ее в принцыпе закодировать более экономно. В этом смысле и следует понимать утверждение о том, в целом аминокислотные последовательности белков носят случайный характер.
(Jan 11, 19:41, 2003) Dmitgu Класс NP - это, грубо говоря, возможность проверить за полиномиальное время решение, которое уже ЕСТЬ.
А класс P - это задачи, которые можно решить (то есть найти решение, которого нет) за полиномиальное время.
Так вот, дарвинизм говорит именно о проверке. Когда уже что-то есть, то он может это отобрать, но утверждать. что он может найти (а не проверить) - это уже утверждение, что NP = P. Но вся современная криптография построена не просто на предположении, что NP > P, но даже на более сильном - о существовании односторонней функции. То есть даже для подавляющего большинства проблем вероятность "расколоть" их неизмеримо сложнее, чем проверить предложенное решение. Это как кодовый замок - легко открыть, если знаешь код (и легко определить, что твой код ошибочен), но вот найти его - куда труднее.
Но природа дает подсказки. Уже само существование закономерностей означает, что ситуация сильнейшим образом "сжимается" (то есть алгоритмы много короче самих последовательностей), но именно поэтому полагаться на случайность невозможно (это NP), а на вылавливание закономерностей - вполне. Это как если вы не знаете шифр, то "честно" вы никогда и не взломаете его, но ведь можно просто подсмотреть его у противника, подкупить его шифровальщика и совершить много других обходных действий. Так же и с природой, мы "подсматриваем", "подкупаем", "изворачиваемся". А расчет на чистую случайность - вещь безнадежная (класса NP).
(Jan 12, 15:21, 2003) zaphod Ну правильно
Это мое определение эквивалентно . Угадывание и проверка - это и есть дарвинизм. Кстати, люди работают над ДНК-компьютерами, которые реализуют идею недетермированной машыны Тьюринга. Существование закономерностей ознает сжымаемость, но опять таки - во первых сущестуют пределеы сжымаемости, а во-вторых, заведомо существуют несжымаемые последовательности. Всякая сжымаемость возножна за счет избыточности информацыи, сжымающий алгоритм просто удаляет эту избыточную информацыю.
Природа конечно дает подсказки и эти подсказки запоминаются эволюцыей. Хотя бы частично. Ведь существует закон Геккеля-Мюллера, в соответствии с которым онтогенез повторяет филогенез, но весь филогенез, не всю историю эволюцыи, а видимо, только успешные шаги. Поэтому у эмбриона человека закладывается хорда, как у ланцетника, потом жаберные дуги, как у рыб, сначала зародыш вместо мочевой кислоты выделяет аммиак, как беспозвочные, потом мочевину как рыбы и земноводные, потом аллатоин как пресмыкающиеся. Это приводит к тому, что эволюцыя канализована.
Например, поскольку все наземные позвочные произошли от кистеперых рыб, то у них, несмотря на все вариацыи только две пары конечностей и никакая эволюцыя уже не может привести к появлению кентавров. По крайней мере, это очень маловероятно. Запоминание же неудачного опыта довольно бессмысленно и накладно. Тогда пришлось хранить всю информацыю о всех предыдущих поколениях. Объем же информацыи, которую может запомнить геном все-таки ограничен.
(Jan 12, 22:43, 2003) Dmitgu Недетерминированная машина Тьюринга практически - тот же вечный двигатель.
И в рассуждения о той же односторонней функции говорится о вероятности с которой эта машина наткнется на решение. И криптография исходит из того, что эта вероятность ничтожна (требуется неполиномиально большое число испытаний). И параллельные вычисления не могут идти быстрее, чем пропорционально количеству параллельных процессов. Потому что они заменяемы (не хуже) одним процессом, который работает во столько раз быстрее, сколько этих самых исходных параллельных процессов.
И никакая теория 1го порядка (в том числе и статистика) не может преодолеть ограничений т. Геделя. Естественно, т. Геделя не утверждает свою собственную непротиворечивость - она допускает, что мир вообще противоречив (хотя этого не наблюдалось), но зато дает способ, как из доказательства невозможности на базе теории о самой теории следует ошибочность теории. Просто если мы упираем на случайность, то это как бы снимает с нас ответственность, но если не думать, то ничего хорошего не получиться и снимать с себя ответственность едва ли правильно.
Видимо, назрел период пересмотра дарвинизма, как назрело в свое время обращение к квантовой механике (после ультрафиолетовой катастрофы) и теории относительности (после прискорбных неудач с "эфиром"). Я уж не говорю о революции в логике. Просто биологи так далеки от строгих методов, что они еще долго будут пытаться "ловить рыбку в мутной воде".