Некоторые аспекты NP-полных задач.
Часть 1.
Уменьшения погрешности в решении СЛАУ (систем линейных алгебраических уравнений) одним из готовых алгоритмов их решения (готовой программой) методом малых изменеий.
Если любую задачу матфизики инженер может свести к СЛАУ то решая СЛАУ готовым алгоритмом делаем погрешность, а предлагаемый нами метод малых изменений который позволяет уменьшить эту ошибку решения (погрешность).
Метод малых изменений заключается в данном случае в перестановке в СЛАУ
порядка уравнений и перестановке (с последующим обратным переименованием) переменных что приводит к эквивалентному данному СЛАУ
что по сути не изменяет СЛАУ (т.к. точное решение одно и то же) [см. литературу:Ф.П.Яремчук, П.А. Рудченко "Алгебра и элементарные функции справочник"].
На практике результат решения СЛАУ
и
одним и тем же алгоритмом
не совпадают из за ошибки округления.
Пусть норма вектора это длинна вектора.
Сравнивая результаты решения мы получаем, что решение СЛАУ
может быть лучше (норма погрешности меньше), хуже (норма погрешности больше), идеальным решением (норма погрешности равна нулю), и таким же (норма погрешностей равны).
В случае если мы получили улучшение, то есть решение с меньшей погрешностью, то к этому условию СЛАУ
применяем тот же алгоритм который описываем, продолжая малые изменения, до тех пор, пока малые изменения дают улучшение.
Таким методом можно найти условие для данного СЛАУ для которого такие изменения не дают улучшений решения. Это и будет результатом метода малых изменений.
Опишем алгоритм формально:
1. Начальное приближение. (В нашем случае начальное условие СЛАУ и его первое решение алгоритмом (программой)
)
2. Малые изменения, которые могут накапливаться, при этом их количество полиномиально (зависит от доступных вычислительных мощностей), т.к. нас интересуют эффективные алгоритмы. (В нашем случае малые изменения это перестановка попарно строк и столбцов в СЛАУ)
3. Сравнивая результаты (погрешность) после каждого малого изменения для повторения малых изменений выбирается наибольшее улучшение до тех пор пока оно есть.
Пример определения погрешности:
Условие
применим алгоритм
для решения
получаем
где
решение.
Погрешность
в идеале
отклонение от идеала и есть погрешность.
где
погрешность.
Получаем
где
уже действительное число а не вектор, т.е. допускает простое сравнение больше и меньше.
-- 26.10.2018, 14:13 --Часть 2.
Мы знаем, что:
1. Арифметика непротиворечива [доказано великим немецким математиком 20-го столетия Герхардом Карлом Эрихом Генценом (нем. Gerhard Karl Erich Gentzen, 24 ноября 1909 — 4 августа 1945) — немецким математиком и логиком, внёсшим большой вклад в исследование оснований математики и развитие теории доказательств, является создателем исчисления секвенций].
2. Арифметика неполна [см. В. А. Успенский, Теорема Гëделя о неполноте в элементарном изложении, УМН, 1974, том 29, выпуск 1(175), 3–47]
3. Из 1. и 2. узнаем, что существуют в арифметике сущности, (обозначим их за
) истинность которых недоказуема, их бесконечное множество
, и это множество
алгоритмически неперечислимо [ см. В. А. Успенский, Теорема Гëделя о неполноте в элементарном изложении, УМН, 1974, том 29, выпуск 1(175), 3–47].
4.1 Система логических уравнений это NP - полная задача [см. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера второе издание (внимание! этого нет в первом издании!)].
4.2 Очевидно, что логическими уравнениями, при переходе к двоичной системе исчисления можно задать арифметику, и математическую логику (пример — L-машина [см. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера второе издание (внимание! этого нет в первом издании!)]) .
5. Теперь сам разбор проблемы NP-полноты.
5.1 Если NP равно P.
То существует хотя бы один алгоритм
, который решает систему логических уравнений или доказывает что решения нет за полиномиальное время. Но для
такое возможно только непосредственной проверкой или алгоритмом
или полным перебором, только это приведет к бесконечному доказательству, т.к. эти сущности, истинность (т.е. например отсутствие решения) которых недоказуема, их бесконечное множество
, и это множество
алгоритмически неперечислимо [ см. В. А. Успенский, Теорема Гëделя о неполноте в элементарном изложении, УМН, 1974, том 29, выпуск 1(175), 3–47].
5.2 Если NP не равно P.
Чтобы обойти
это надо проверить на подмножестве системы логических уравнений, но при этом гарантировать что они не содержат
на бесконечности, т.к. в противном случае прийдется доказательство проводить для каждого такого
, а это весьма проблематично, т.к. они могт встретиться на бесконечности. Доказательство надо проводить для случаев не содержащих
т.е. конструктивно построенными условиями с ответами 0 и 1. А потом перемешать их, и доказать что мы не можем их различить, даже зная алгоритм создания этих условий.
Пусть есть алгоритм
при этом не строящий
а строящий только
такой алгоритм можно искать бесконечно долго, т.к. описать конструктивно
не возможно, и где то на бесконечности
все равно может выскочить в одном из условий.
Отсюда предполагаемая вероятность успеха поиска
стремится к нулю.
Следствия:
Следствие 1. Плазма в ТОКАМАКЕ и магнитной ловушке. Поиск потенциальной ямы для энергии плазмы - NP- полная задача, и плазма решает ее как может. Возникают эвристики которые борются между собой как генетические алгоритмы, и когда их остается 1-3 штуки, а остальные эвристики побеждены, плазма становится неустойчивой. Выход, подходящий для маленьких токамаков, и магнитных ловушек: за время порядка 0.1 от времени удержания плазмы менять напряженность магнитного поля на величину порядка 20% (это можно сделать организовав в катушках индуктивности колебательные контуры, подключив конденсаторы, только сначала надо запустить колебательные контуры, а потом зажигать плазму), таким образом у нас не будет победившей эвристики (из за постоянно меняющихся правил игры), а будет мелкозернистая почти однородная плазма, где каждому зерну отвечает своя эвристика.
Следствие 2. Из за того что на бесконечности для натурального
большего 3-х отсутствие решений в натуральных числах больших 3-х у уравнения
является
причём мы не можем сказать что это за
то всякое доказательство меньшее
страниц содержит ошибку (это если таких
конечное число) или всякое конечное доказательство содержит ошибку (это если таких
безконечное число).
Следствие 3. Если в случае с уравнением Навье-Стокса, в жидкости или газе возможно смоделировать машину эквивалентную машине Тьюринга, то там все аналогично.
-- 26.10.2018, 14:14 --Часть 3.
Результаты получены как следствие рассмотрения свойств приведенной ниже следующей конструкции, которая создавалась как реализуемая на персональном компьютере под управлением Линукс Минт модель естественного человеческого интеллекта, на базе соционической модели.
Далее используется соционическая терминология.
число входов в нейрон для функций:
И 4 элемента на нейрон, плюс несколько входов выходов для следствий, связано намертво с С 6 элементов на нейрон, плюс несколько входов выходов для следствий.
Э 5 элементов на нейрон, плюс несколько входов выходов для следствий, связано намертво с Л 5 элементов на нейрон, плюс несколько входов выходов для следствий.
разничие смысла приставок:
Б -внутреннее, внутренний голос, внутреннее видео, внутренняя кинестетика.
Ч - то же что Б, но внешнее.
пропорция между тренированностью и гормонами для функций:
Э - больше при выборе из 2-х и более вариантов ориентация на гормоны удовольствия- неудовольствия в памяти связей с другими нейронами, а не на тренированность связи примерно как 30% на 70%.
Л - больше при выборе из 2-х и более вариантов ориентация на тренированность связи а не на гормоны удовольствия- неудовольствия в памяти связей с другими нейронами примерно как 30% на 70%.
С и И в сравнении с Э и Л там гормоны и тренированность 50% на 50%.
ИЛЭ(интуитивно логический экстраверт "искатель")
1) ЧИ - сознание, каждый нейрон которого жёстко связан с нейроном БС- подсознание. Подсознание может отменить переход между нейронами сознания и установить свой в 10% случаев.
2) БЛ - сознание, каждый нейрон которого жёстко связан с нейроном ЧЭ- подсознание. Подсознание может отменить переход между нейронами сознания и установить свой в 20% случаев.
3) ЧС - сознание, каждый нейрон которого жёстко связан с нейроном БИ- подсознание. Подсознание может отменить переход между нейронами сознания и установить свой в 30% случаев.
4) БЭ - сознание, каждый нейрон которого жёстко связан с нейроном ЧЛ- подсознание. Подсознание может отменить переход между нейронами сознания и установить свой в 40% случаев.
Нейроны 1)-2)-3)-4) выпадают с какими то вероятностями, зависящими от конкретного интелекта, отсюда подтипы.
Нейроны связаны по количеству от 1 до 9 (звуки в словах) и слова по количеству от 1 до 7 в предложения, и т.д. . Активны около 200 слов одновременно, и они обсчитываются на соответствие внешнему миру. В эти 200 подгружаются и вываливаются в-из долговременной памяти. Связи устанавливаются в количестве от 5 до 9 наиболее активных независимо для сознания и подсознания. Осознанные и неосознанные действия тоже в этом количестве от 5 до 9. Долговременная память на 2-20 лет. В день от 10 до 150 новых слов. Сон медленный - отдых, быстрый - подсознание главное, а снится только отражение в сознании, доступа в подсознание у нас никогда нет даже во сне.
Кроме этого у мужского интеллекта один гормон, у женщин два. И у женщин логический нейронный вывод как по тренированности, так и по этике зависит от того какой гормон преобладает. Таким образом женский интеллект легко и просто находит и усваивает инварианты (методы которые действуют в 95% процентах случаев, т.е. там лучше на уровне аппаратного обеспечения реализована математическая статистика и теория вероятностей). Поэтому лечение шизофрении у женщин должно осуществляться как минимум в 2-е большим набором препаратов т.к. там на каждый гормон всё своё.
Гениальность: при большом избытке связей между нейронами, иногда при следствиях-связях при их большой тренированности: из
следует
, а из
следует
, устанавливается следствие-связь: из
следует
.
-- 26.10.2018, 14:17 --примечания: авторы следующие --- И. Билан, А. Билан, В. Жук
под GNU GPL v.3.0