Формула энтропии для NP=P

Формула энтропии для NP=P

Интерпретация скорости передачи информации для полиномиальных задач

# Абстрактный

В этой статье мы исследуем количественный стохастический процесс, основанный на алгоритмической теории информации и критерии Шеннона-Келли, чтобы найти действительные решения, близкие к оптимальным, с использованием новой оптимальной стратегии роста, применяемой к задаче коммивояжёра, которые имеют статистически значимую скорость передачи даже при отсутствии схемы кодирования. доступны, независимо от временной сложности задачи. Новая интерпретация скорости передачи информации, предложенная в данной работе, представляет собой метод, моделирующий границы пространства решений задачи TSP (и задач NP в целом) как канал связи средствами теории информации. Мы описали алгоритм поиска, который обнаруживает шаблоны (т. е. внутреннее информационное содержание) в элементах ограниченного пространства решений, смоделированного как сообщения, передаваемые через системы связи. Границы пространства поиска определяются сложностью Колмогорова-Хайтина последовательностей возможных решений, закодированных в виде строк Шеннона-Бернулли. В заключение мы обсудим качество результатов и последствия для общей проблемы принятия решений в машинах Тьюринга.

Дополнительные ключевые слова и фразы: вычислительная сложность, теория информации, машинное обучение, вычислительная статистика, сложность Колмогорова-Чайтина; критерий Келли

# Гипотеза: NP=P или NP!=P?

Проблема P и NP является серьезной проблемой в информатике. Проще говоря, он спрашивает, может ли каждая проблема, которую можно проверить за полиномиальное время, найти решение за полиномиальное время. Например, проще проверить правильность решения игры в судоку, чем найти правильное решение самому. Любой, кто пытается придумать возможные решения для игры, должен будет протестировать большое количество возможных ответов. Этот «уровень сложности» представляет собой вычислительную сложность, необходимую для последовательной обработки всего пространства решений.

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

В этой статье мы предложили новый подход к моделированию риска/неопределенности на основе критерия Келли-Шеннона-Торпа [1] [4] [5] для измерения оптимального размера ставки (т. е. оптимального распределения каналов), которую продавец должен разместить на каждое взаимодействие алгоритма (реализованного в машине Тьюринга) для решения задачи коммивояжера. Эта новая интерпретация проблемы TSP с помощью теории информации и сложности Колмогорова-Хайтина [2] может быть использована для определения пределов вычислений и ответа на вопрос, в каких случаях P=NP. Он работает, устанавливая границы проблемы в виде функции плотности вероятности, рисуемой в соответствии с выборкой случайных выборок решений, определенных как семантически действительные двоичные строки Бернулли. Стоимость каждого решения-кандидата оценивается по бинарной статистической индексной функции, чтобы разделить его на 2 независимые группы: 0 (меньшее расстояние — лучшее качество); 1 (большее или равное расстояние — хуже или без изменений качество). Это распределение показывает количество внутренней информации, доступной для алгоритма, и можно рассчитать энтропию. Затем машина Тьюринга может использовать эту информацию для снижения энтропии в каждой единице такта выполнения, одновременно максимизируя ожидаемое улучшение качества решения (т. е. нахождение кратчайшего пути евклидова расстояния, который посещает все узлы).

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

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

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

# Результаты и моделирование

Мы создали симуляцию для 10 городов со 100 взаимодействиями/испытаниями. Фиксированная альфа-выборка представляет собой известный эталонный набор модели, а бета-выборка представляет собой альтернативную гипотезу выборки. Оба образца содержат по 300 последовательностей-кандидатов в решениях. Вычисленные исполнения с p-значением хи-квадрат меньше 0,05 и долей Келли больше 0 являются интересными решениями, и они обеспечивают более высокое качество за счет снижения энтропии при каждом взаимодействии.

Для этого моделирования результаты сгруппированы в две группы: пулы решений, близкие к оптимальным (взаимодействие 35, 69 и 4), и еще одна случайная выборка с отброшенными выборками-кандидатами (83, 41, 40). На рисунке ниже мы можем видеть p-значения и доли Келли, например, 4, 35, 69 (хорошие решения, близкие к оптимальным) и 41, 40 и 83 (случайные плохие решения). Мы хотим отфильтровать пулы решений с решениями-кандидатами, которые дают значительные результаты и имеют максимальную скорость уменьшения энтропии. Другими словами, существует меньшая неопределенность в отношении возможного кратчайшего пути с новой альтернативной выборкой по сравнению с предыдущим набором гипотез о наилучшем решении.

Сравнивая p-значение и долю Келли, продавец может делать «обоснованные ставки» на то, какие маршруты/символы могут привести в долгосрочной перспективе к наилучшему возможному повышению качества при многих взаимодействиях. Таким образом, задача сводится к задаче сортировки, использующей p-значение и дробь Келли в качестве первичных и вторичных ключей для несортированного списка вычислений. Чтобы найти лучшие решения, близкие к оптимальным, продавец может отсортировать ключи по убыванию. Кроме того, он может сортировать подсписок по количеству битов, необходимых для кодирования двоичной строки (почти оптимального) решения.

# Мета-алгоритм

Псевдокод для процедуры описан ниже:

• Образец A (референтная группа): Создайте образец модели A, используя случайно сгенерированное (семантически достоверное) решение, метод 2-opt, имитация отжига, генетические алгоритмы или любую эвристику искусственного интеллекта.
• Пусть E(A) — ожидаемая стоимость кандидатов в выборке A.
• Категория (A, 1): подсчитайте количество возможных решений в выборке A, у которых общее расстояние пути (т. е. значение стоимости) больше или равно E (A).
• Категория (A,0): подсчитайте количество решений-кандидатов в выборке A, у которых общее расстояние пути (т.е. значение стоимости) меньше, чем E(A).
• Pr(A,0): вычислить вероятность случайного нахождения решения-кандидата в выборке A, которое повысит качество (т. е. снизит стоимость).
• Pr(A,1): вычислить вероятность случайного нахождения решения-кандидата в выборке A, которое снижает качество (т. е. увеличивает стоимость).
• Пусть A_QualityIncrease: среднее улучшение качества для образца A.
• Пусть A_QualityReduction: среднее снижение качества для образца A.
• Пусть R_Quality_A: A_QualityIncrease/A_QualityReduction будет соотношением качества в образце A.
• Пусть Halt = False будет управляющим логическим флагом.
• Пока Halt равно False, повторите:
• Образец B: создайте альтернативный образец B, используя случайно сгенерированное (семантически достоверное) решение, метод 2-opt, имитация отжига, генетические алгоритмы или любую эвристику искусственного интеллекта.
• Категория (B, 1): подсчитайте количество возможных решений в выборке B, у которых общее расстояние пути (т. е. значение стоимости) больше или равно E (A).
• Категория(B,0): Подсчитайте количество решений-кандидатов в выборке B, у которых общее расстояние пути (т.е. значение стоимости) меньше, чем E(A).
• Pr(B,0): вычислить вероятность случайного нахождения решения-кандидата в выборке B, которое повысит качество (т. е. снизит стоимость).
• Pr(B,1): вычислить вероятность случайного нахождения решения-кандидата в выборке B, которое снижает качество (т. е. увеличивает стоимость).
• Пусть B_QualityIncrease: среднее улучшение качества для образца B.
• Пусть B_QualityReduction: Среднее снижение качества для образца B.
• Пусть R_Quality_B: B_QualityIncrease/B_QualityReduction будет соотношением качества в образце B.
• CT_AB: Создайте таблицу непредвиденных обстоятельств для групп A и B с вхождениями каждой категории 1–0.
• Chi2_AB: рассчитать критерий хи-квадрат для CT_AB.
• k_AB: вычислить долю Келли для Pr(A+B,0) и R_Quality_A + R_Quality_B.
• info_B: Рассчитайте энтропию для оценочной функции распределения вероятностей из альтернативной выборки B, используя CT_AB.
• если Chi2_AB ‹ 0,05 и k_AB > 0, то вернуть [Halt=True, «Решение найдено».] else [Halt=False, «У нас недостаточно доказательств и/или информации, чтобы отвергнуть нулевую гипотезу]

# Вывод

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

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

Дополнительную информацию о моделировании задачи коммивояжёра с помощью алгоритмической теории информации см. в моей статье Лог-нормальная задача о посыльных [6]

[1] Дж. Келли. 1956. Новая интерпретация скорости передачи информации. J, 35: 917–926, июль. Белл Сист. Тех. (1956).
[2] А. Н. Колмогоров. 1968. Логические основы теории информации и теории вероятностей. IEEE транс. Инф. Theory (1968).
[3] М. С. Лима. 2019. Алгоритмически-информационная интерпретация задачи коммивояжера. Препринт (2019 г.).
[4] К. Э. Шеннон. 1948. Математическая теория коммуникации., 27:379–423,623–656. Белл Сист. Тех.Дж. (1948).
[5] Эдвард. Торп. 2008. Критерий Келли в блэкджеке, ставках на спорт и фондовом рынке. 1.10.1016/В978–044453248–0,50015–0. Справочник по управлению активами и пассивами. (2008).

[6] Проблема логнормального мессенджера. Теория информации решает проблему коммивояжера. https://medium.com/@santanalima.matheus/the-log-normal-messenger-problem-c4a0257351ee