Некоторые приложения для решения NP

Некоторые приложения для решения NP

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

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

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

Представляя

Чтобы показать, что я хочу сказать, я хочу представить это новое обозначение; как показано на рисунке 1.

Логическая функция (A1 |A2 | A3) возвращает 1 тогда и только тогда, когда одно и только одно из трех значений равно 1, то есть, учитывая логические значения A1, A2, A3, A1+A2+A3 = 1. Я буду называть это функция выбора, как было представлено в (Dato 2015).

Если мы считаем, что одна из вершин (логическая переменная) равна нулю, мы можем представить ее так, как показано на рисунке 2.

На рис. 2 показано, как мы можем построить комплементарность в этой графической модели. Обратите внимание, что у каждой вершины есть имя вершины или нет, а также логическое значение или нет. Если вершина активирована 1, все соседние точки в фигуре треугольника будут активированы 0.

Мы можем легко продемонстрировать, что произведение функций выбора может представлять любую булеву алгебру (алгебру единиц, нулей, И и ИЛИ). Чтобы подтвердить это, вам нужно только изучить рисунок 3, проверив только четыре возможных случая.

В этот момент мы замечаем, что нотация имеет не меньшую силу, чем логика. Представьте, что теперь мы хотим вычислить множественный выбор, например: A=(A1|…|An). Сначала изучим рисунок 4.

Если бы A было равно 1, мы могли бы догадаться, по какому шаблону получить множественный выбор. Если бы мы хотели сделать A эквивалентным множественному выбору, изменение было бы показано на рисунке 5.

Но если мы внимательно изучим рисунок 5, то, во-первых, его можно было бы представить комбинациями рисунка 3, и необходимых ресурсов было бы больше, но…, что мы можем сказать о надежности? Как мы видим, A4 и A5 не могут быть активированы 1 одновременно. То есть Фигура 5 перетянута конкретной Фреймом для той же формулы. В зависимости от обстоятельств, от потоков ветра, вы можете использовать что-то вроде рисунка 4, то, что я назвал квадратным парусом. Это будет работать, если A1…An активированы 0 или не активированы.

Но что делать, если они были активированы 1 или не активированы. Для прямо противоположного ветра я разработал треугольные паруса, как на рис. 6.

На рисунке 6 обратите внимание, что он представлен в виде круга (B повторяется из эстетических соображений). Легко найти шаблон, чтобы получить формулу выбора для большего количества разделов (A1|…|An). В этом случае, если Ai был активирован 0, он будет проигнорирован для оценки A или остальных. Несмотря ни на что, этот дизайн полезен в каком-то особом контексте, где нас не интересуют такие случаи.

Рассмотрим, как можно было бы представить некоторые известные задачи, например поиск подграфа в графе. Если граф представлен буквами, а подграф представлен числами, то каждая вершина нашей модели будет построена комбинацией буквы и числа, так что если вершина A1 активируется 1, то мы должны активировать каждый раз смежный с A с каждым смежным с 1:

Пример: B и C расположены рядом с A. 2 и 3 расположены рядом с 1.

Итак: A1 подразумевает (B2|B3|C2|C3)

И для этой задачи можно рекомендовать рисунок 6.

Управление

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

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

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

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

Если вы можете принять другой цикл for, вы можете избежать замечаний, которые работают примерно в 80% случаев.

Некоторые демонстрации и другие результаты вы можете найти в этом документе.

использованная литература

Дато Руис, JM (2015). Приближаемся к индексу Хосоя. EPH — Международный журнал биологических и фармацевтических наук (ISSN: 2208–2166), 1(1), 25–31. Получено с https://ephjournal.com/index.php/bps/article/view/16