Решение задачи равенства классов p и Np и последовательность простых чисел

Аннотация

Монография представляет собой исследовательскую работу, посвященную решению одной из важных математических задач, поставленных институтом Клэя, а именно задачи равенства классов p и Np. В ней представлены новые теоремы и концепции, разработанные автором в областях теории чисел и теории алгоритмов. Монография претендует на фундаментальную новизну своего математического введения, учитывая предшествующие работы других математиков, а также актуальные математические публикации.

Особенностью монографии является ее самодостаточность как учебника, который требует от читателя минимального уровня специфических математических знаний. При этом она предоставляет возможность читателю самостоятельно исследовать материал, обращаясь к первоисточникам и дополнительным источникам информации.

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

Цель монографии заключается в том, чтобы предложить читателю новые математические подходы и идеи, расширить его понимание предметной области и стимулировать самостоятельные исследования в данной области.

Введения

Вы являетесь сложной нейробиологической структурой, в которой каждая деятельность неразрывно связана с вычислительными процессами. Как человек, вы сталкиваетесь с широким спектром задач, начиная от простых и повседневных до сложных и специфических, требующих глубокого интеллектуального осмысления. Важно отметить, что каждая задача требует определенного уровня анализа и решения, а для этого необходимо обладать интеллектуальной способностью к осмыслению и обработке информации.

При решении математических задач вычислительная задача должна включать в себя внутренние базовые структуры, которые являются элементарными единицами этой задачи. Эти базовые структуры могут быть использованы для конструирования алгоритмов оптимальных решений, которые в свою очередь могут быть классифицированы по своим конечным значениям. Это позволяет нам систематизировать и организовать процесс решения задач и добиться желаемых результатов.

Учитывая физические ограничения пространства и времени, которым подчиняется наше существование, важно иметь возможность работать с решениями и находить наиболее оптимальные варианты в максимально короткое время. Мы стремимся использовать наши интеллектуальные способности для эффективного поиска решений, основываясь на доступных нам возможностях и знаниях.

Понимание этих фундаментальных принципов позволяет нам разрабатывать и применять различные методы, техники и алгоритмы для решения математических задач. Мы постоянно развиваем и улучшаем наши вычислительные способности, чтобы более эффективно решать задачи и достигать поставленных целей. Это процесс непрерывного развития, и каждая новая задача становится возможностью для применения своих интеллектуальных способностей и стремление к оптимальным решениям.

История становления p и Np

Формализация задачи равенства классов p и Np произошла в середине XX века в контексте развития математической логики и теории алгоритмов. В 1936 году Алан Тьюринг представил понятие вычислимости и разработал модель вычислительной машины, что послужило основой для теории алгоритмов и вычислительной теории. Эти исследования заложили основы для понимания задачи равенства классов p и Np и ее формулировки.

Первое формальное упоминание задачи в современном смысле можно отнести к письму Курта Геделя Джону фон Нейману в 1956 году, где он впервые высказал понятие NP-полных задач. Это открыло новые перспективы для исследования и понимания фундаментальности задачи равенства классов P и NP. В 1971 году Стивен Кук и Леонид Левин дали независимые строгие определения и формулировки NP-полных задач, что привело к более точному определению этой проблемы и ее классификации.

Warning!

Текст требует осмысления, и полного ознакомления с глубоким анализом — ради ее понимания! Многие выкладки идут аксиоматическим образом — для подтверждения требуются ваш собственный разбор. Текст лишь на первый взгляд кажется не последовательным. При детальном анализе вы убедитесь, что это одна из наиболее оптимальных форм изложения.

Определения задач

Зададим некоторое количество натурально пронумерованных действительных чисел

Распределение которых:

• Может иметь произвольный характер

• Нету ограничений в повторе одних и тех же чисел

• Могут вводится, как конечное так и бесконечное количество чисел

  #Различные числовые последовательности оказываются нам постоянно встречающимися явными или более скрытыми способами. Более того, мы подчинены «стреле времени», и практически все наши действия являются поэтапными с обязательной возможностью причинно-следственных связей. Если мы попытаемся перевести это на язык чисел, то можно сказать, что в определенный момент времени t мы совершаем действие r(t), и вслед за ним в момент времени t + (x>0) возникает действие r(t + (x>0)). Такое действие r(t + (x>0)) может быть результатом действия r(t) или же независимым от него.

  Очевидно, что для нахождения общих закономерностей, связывающих r(t) и r(t + (x>0)), логичнее рассматривать их в случае, когда r(t + (x>0)) является следствием r(t). Кроме того, r(t) и r(t + (x>0)) могут быть структурно похожими или иметь определенные отличия друг от друга.

  Математика позволяет нам преодолевать трудности, возникающие из-за огромного разнообразия действий, путем нахождения общих черт явлений и классификации их по группам сходства на основе различных характеристик. Таким образом, математика позволяет рассматривать явления как сходные, даже если на первый взгляд они кажутся разными.

Правило нумерации

Представьте, произвольное множество действительных чисел и начните записывать их на бумаге или в ином информационном носителе… Так нумерация числа с учетом запрета одновременной записи двух или более чисел осуществляется следующим образом: Первое записанное действительное число из вашего множество приобретает значение R(1), второе записанное число приобретает значения R(2), третье R(3) и т.д. вплоть до R(T), где T — потенциально может приобретать значение до + ∞. Пример, скажем вы представили ряд натуральных чисел:

1. Основные операторы

Оператор сдвига W — увеличивает либо уменьшает начальное численное значение T или R(T), с помощью некоторых комбинаций, через базовые арифметические операторы; +, -, *, /.

Оператор объединения U — пример, как определитель; пусть вы задали два ряда чисел — [R(1), R(2), R(3)] и [J(1), J(2), J(3)], тогда, если

а если

Оператор перестановок χ — перемещает число R(T) в иное положение R(T±(x>0)), с соответствующим перераспределением значений всего заданного ряда:

Пример, для ряда натуральных чисел [R(1) = 1, R(2) = 2, R(3) =3,…, R(T)=T]

h в данном случае равен 1, так как для всего ряда требуется лишь одна универсальная операция(функция) от T для соответственного описания численного значение R(T)

Пример, для ряда чисел кратным к двум  [R(1) = 2, R(2) = 4, R(3) =6,…, R(T)=2T]

Пример, для ряда чередующихся, натуральных чисел и кратных к двум [R(1) = 1, R(2) = 4, R(3) =3, R(4) = 8, R(5) = 5, R(6) =12,…, R(T)]

2. Основные отличительные типы последовательностей

R(T)= R(T±1) — однородный тип Ο:

• Каждый элемент данного типа, имеет одно и тоже значение.

• Каждое значение описывается одним оператором прогноза:

Примеры:

[R(T) ≠ R(T±1)  — мульти детерминированный тип Θ:

• Последовательность содержит в себе два и более отличительных элементов

• Каждое значение описывается с выборкой от двух и более операторов прогноза:

Мульти случайный тип χ’Θ:

• Последовательность может содержать в себе, два и более отличительных элементов.

• Каждое значение описывается с выборкой от двух и более операторов прогноза:

R(T)<R(T+1) —  детерминированный псевдо однородный тип ζ:

• Последовательность содержит в себе бесконечное количество отличительных  элементов, при этом, не равных друг другу

• Каждое значение задавалась одним оператором прогноза:

• Существует строго определённый собственный оператор прогноза для каждого из значений.

Пример:

Cлучайный псевдо однородный тип χ’ζ:

• Последовательность содержит в себе бесконечное количество отличительных элементов, не равных друг другу…

• Последовательность является результатом случайной перестановки всех значений ζ

Пример:

Некоторые из возможных случаев…

Детерминированный псевдо мульти тип σ :

• Последовательность обязательно содержать в себе бесконечное количество отличительных элементов, так же может содержать в себе схожие значения

• Каждое значение описывается с выборкой от двух и более операторов прогноза:

Случайный псевдо мульти тип χ’σ :

• Последовательность является результатом случайной перестановки всех значений σ

Какова вероятность того, что при перестановки детерминированных типов последовательности, мы также получим детерминированный тип, при T→∞?

Можно ли рассуждать о переходах некоторых типов к другим типам, при T →∞?

3. Определение проблемы p и Np

Чтобы лучше разобраться в природе проблемы p и Np классов, стоит выяснить то, как она логически интегрируется с теми или иными, прикладными, алгебра-оперативными действиями над типами последовательностей. Т.е. например, допустим дана задача по определению суммы всех чисел до R(T) в той или иной последовательности… В случае с распределением натуральных чисел, задача решаема по формуле:

Но при этом, мы также могли «вручную» просуммировать все числа от натуральной последовательности;

И найти тот же ответ, что дала бы формула.

С этого простейшего примера, можно было, уже приступить к определению проблемы: — «Проблемы методов решений вычислительных задач». Ясно, что по формуле, в отличии от ручного перебора, время решения задачи ниже. Следовательно, и выгоднее в данном случае, пользоваться именно формулой. При этом, задача по «нахождению подобных формул» для задачи суммирования, для других типов последовательностей, очевидно является не совсем тривиальной, и хорошо бы некоторым образом охарактеризовать данный случай.

Но прежде чем приступить к более детальному анализу, рассмотрим задачу по нахождению количество перестановочных значений до R(T) — данная задача решается по формуле, допустим, что T = 3;

Или же, методом перебора

[R(1) = 1, R(2) = 2, R(3) =3]

[R(1) = 1, R(2) = 3, R(3) =2]

[R(1) = 2, R(2) = 1, R(3) =3]

[R(1) = 2, R(2) = 3, R(3) =1]

[R(1) = 3, R(2) = 1, R(3) =2]

[R(1) = 3, R(2) = 2, R(3) =1]

Как видно, представленная задача отличается от предыдущей задачи по суммированию, но при этом оба типа задач имеют схожие методы решения — «формулу и перебор». Однако в данном случае, в отличие от задачи суммирования, для решения требуются лишь знания о количестве чисел в последовательности до R(T), где T является универсальным параметром, применимым к любому типу последовательности. В то время как в задаче о суммировании не всегда так очевидно определить универсальный параметр.

Учитывая, что мы являемся существами с ограниченными ресурсами, а время является крайне ценным ресурсом в жизни, мы должны стремиться к нахождению наиболее быстрых путей решения задач, не теряя при этом в качестве результата. Для этого нам необходимо понимать, с какой вычислительной задачей мы столкнулись, и возможно ли для нее определить существование наиболее быстрых путей решения.

Как было показано выше, в некоторых прикладных примерах задач мы обнаружили два различных метода решения, которые существенно отличаются на фундаментальном уровне:

1. Класс NP (Недетерминированно полиномиальное время): Этот класс содержит задачи, для которых, если у нас есть кандидатское решение (потенциальный ответ), мы можем быстро (в полиномиальное время) проверить, является ли оно правильным или нет. Однако сами эти задачи могут быть трудными для решения, и нет прямого способа найти правильное решение в полиномиальное время. Поэтому переборные методы могут быть одним из способов попытаться найти решение, но они не являются единственным способом, т.е проблема факторизации…

2. Класс P (Полиномиальное время): Этот класс содержит задачи, для которых существует детерминированный алгоритм, способный найти правильное решение в полиномиальное время относительно размера входных данных. Перебор в данном случае не обязателен, так как существует эффективный алгоритм, который может решить задачу быстро и точно.

Вопрос состоит в том, совпадают ли классы P и NP, то есть, существуют ли задачи в NP, для которых существуют полиномиальные алгоритмы решения. Если P = NP, это означает, что эффективные алгоритмы существуют для всех задач в NP, и, следовательно, NP-полные задачи (самые сложные задачи в NP) также могут быть решены эффективно. Это имеет огромные практические и теоретические последствия, так как множество задач, с которыми мы сталкиваемся в нашей повседневной жизни (например, оптимизация, расписание, маршрутизация), принадлежат NP-классу.

_{Возможно подобные определения для столь сложной задачи, кому-то покажутся слишком наивными и простыми, но при этом как полагает автор, если вы действительно так думаете, то вы сильно ошибаетесь с точки зрения практики вещей.}

λ задача:

Пусть дана последовательность действительных чисел [R(1),R(2), R(3),…,R(T)). Задача; найти конечное количество определителей через T для каждого! R(T) так, что;

Тут ĥ ≠ ∞, и является количественным определителем  функций описывающих последовательность, как на примере мульти детерминированного типа;

В данном случае H = 2. — Для каждого нечётного значения T приведенной последовательности, применяется T/T, для каждого чётного значения T/T+1, тем самым, алгоритма-функциональным образом, можно с точностью описать любой диапазон последовательности, за строго фиксированное время;

Отличия в W_ĥT от τ_hT, заключается в том, что h = ĥ, только тогда, когда известно, что для последовательности существует определённый детерминированный алгоритм, по которому за строго фиксированное время, можно описать любой диапазон множество, а иначе ĥ является неопределённым без точного значения.

Если, найдётся такая последовательность, что для неё строго не обнаружиться h ≠ ∞, тогда по определению для неё не существует решения по классу p, и следовательно p ≠ Np. — Допустим, вам дали задачу по определению T = 60, для последовательности квадратичных чисел, и у вас нет функции от T, по которому она описывается. Тогда, единственным вариантом решения остаётся, расписать все натуральные числа и определить в них квадратичные числа до T = 60, а это в свою очередь, как вы понимаете, является решением по классу Np… А иначе, вы бы просто могли подставить к T; W_ĥT = R(T), где ĥ≠∞, и сразу получить нужный вам ответ, зачастую, за существенно быстрое время.

Далее, определим к какому из типов последовательностей принадлежит последовательность простых чисел: Очевидно, что все типы последовательностей помимо типов последовательностей ζ и χ’ζ отпадают по определению последовательности простых чисел… Тогда; что если, последовательность простых чисел принадлежала бы к типу последовательностей ζ? — По определению данного типа, выходит, что последовательность простых чисел должна будет иметь такую единую функцию от T, что для каждого П(T)= W₁T…

Для дальнейших рассуждений стоит ввести понятие об оперативно-количественном весе m(W_hT) — условно определяется через время за которое с точностью в 100%, без методов аппроксимирования, вычисляется R(T)  через W. Например, последовательность натуральных чисел, вычислить легче, нежели последовательность квадратичных чисел, до некоторого R(T), при том, что обе они с точностью вычисляются через функции T = R(T) для натуральных чисел, и T*T= R(T) для квадратичных, т.е. последовательность натуральных чисел занимает меньшее количество операций, в сравнении с квадратичными:

Допустим, что m(П(T)= W₁T) = c ≠ ∞. — тогда, мы должны вывести точечную единую фиксированную формулу для всех значений T: — Хоть и подобную формулу не могут найти на протяжении уже нескольких тысяч лет, это все же не значит, что нету её и вовсе… Всё может оказаться так, что значение с слишком велико и за разумное время её вывести нельзя. Следовательно, если всё действительно так, нельзя и с этого утверждать, что либо о равенстве классов p и Np. Но а если нам получиться доказать, что подобной формулы нету, то и очевидно, что p ≠ Np — так как, это докажет, что последовательность простых чисел задаётся подобно! случайным образом, не имеющих полиномиальных решений по λ задаче…

Внесём дополнительное формальное определение, для детерминированных типов последовательностей:

Ο→ для всякого R(T) — R(T-1) =  R(T-1) — R(T-2)

Θ →существует такое, что если  R(T) — R(T-1) = x, то R(T-1) — R(T-2) = -y.

ζ → для всякого R(T) — R(T-1) >  R(T-1) — R(T-2)

σ → может существовать такое, что если R(T) — R(T-1) = x, то R(T-1) — R(T-2) = -y

Так, из данной определённой аксиоматики становится явным, что последовательность простых чисел не может принадлежать к типу ζ, так как не всегда П(T) — П(T-1) >  П(T-1) — П(T-2) — а это как раз, и описывается типом χ’ζ. — Т.е. последовательность простых чисел принадлежит к случайному псевдо однородному типу, нежели к детерминированному псевдо однородному типу. — Следовательно p ≠ Np!

Что и требовалось доказать!

Ссылки и литература

_{Н. П. Варновский. Проблема P = NP, классы сложностей и криптография. 2005.}

_{Притыкин Ю. Л. Что такое проблема P vs. NP? // VIII летняя школа «Современная математика». — Дубна, 2008.}

_{С. Кук Официальное описание проблемы на сайте института Клэя}