Pull to refresh

Опубликовано доказательство P ≠ NP?

Algorithms *
Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P ≠ NP.

Само доказательство на ~100 страницах.

Можно почитать более или менее адекватный комментарий на ycombinator.

Добавить нечего, читаем и/или ждем мнений специалистов в этой области.

P.S. На всякий случай, ссылка о том, что такое NP и P. (спасибо, SMiX)
Total votes 311: ↑294 and ↓17 +277
Views 21K
Comments 127

Сведение решения NP-полной задачи «3-выполнимость» к алгоритму с полиномиальной сложностью

Lumber room
По следам публикации P != NP (для которой, кстати, опубликовано опровержение), хочу поделиться ссылкой на статью В.Ф. Романова, в которой он показывает, как можно свести решение NP-полной задачи «3-ВЫП» к полиномиальному алгоритму.

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

Читать дальше →
Total votes 22: ↑19 and ↓3 +16
Views 3.5K
Comments 38

Открытое письмо ученым и эталонная реализация алгоритма Романова для NP-полной задачи 3-ВЫП

Algorithms *
С момента предыдущей публикации о полиномиальном алгоритме Романова для 3-ВЫП прошло 4,5 месяца.

За это время мы с Владимиром Федоровичем подготовили вариант статьи, чтобы отправить его коллегам-ученым и попутно реализовали эталонную реализацию этого алгоритма на Java.
Читать дальше →
Total votes 60: ↑52 and ↓8 +44
Views 8.8K
Comments 132

Обсуждение работы алгоритма Романова на примере

Algorithms *
В продолжение вчерашнего обсуждения.

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

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

Unit-тест и подробный лог работы приложения я выложил здесь:

gist.github.com/791064

Предлагаю по возможности ссылаться туда по номерам строк (там не совсем удобно, что нельзя дать прямую ссылку на номер строки, придется искать ее вручную; если кто-то предложит более удобный сервис, я перенесу лог туда).

Как видно из лога работы, тест заканчивается ситуацией, когда на очередном шаге построения гиперструктуры базисный граф оказался пустым множеством, что согласно алгоритму означает, что формула не выполнима (пункт 2b внизу страницы 11 в тексте статьи).

Чтобы не переписывать здесь еще раз статью, предлагаю в обсуждении задавать вопросы, которые требуют дополнительных разъяснений.
Total votes 26: ↑21 and ↓5 +16
Views 2.6K
Comments 24

Узбекский математик Б.Пономарев разгадал теорему Ферма! Проверим?

Algorithms *
Sandbox
Давным-давно в 1637 году Пьер Ферма имел глупость написать на полях «Арифметики» Диофанта следующее: «… невозможно разложить куб на два куба, биквадрат на два биквадрата и вообще никакую степень, большую квадрата, на две степени с тем же показателем. Я нашел этому поистине чудесное доказательство, но поля книги слишком узки для него».

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

Несмотря на это, она была полностью доказана лишь в 1995 году, используя теории эллиптических кривых.

Недавно сразу несколько достаточно авторитетных по местным меркам новостных порталов взорвала новость: Узбекский математик разгадал теорему Ферма — Математик из Ташкента Борис Пономарев утверждает, что отыскал «простое оригинальное доказательство» Великой теоремы Ферма — загадки, над которой ученые всего мира бьются вот уже 350 лет (например, здесь, здесь и здесь). В одной из них даже было приведено доказательство.
Читать дальше →
Total votes 124: ↑100 and ↓24 +76
Views 11K
Comments 123

Математические доказательства в 140 символов

Mathematics *
Бытует мнение, что в Средние века выпускник университета должен был придумать своё доказательство теоремы Пифагора. Вряд ли ради серьёзной цели (хотя, кто знает), а скорее ради развлечения можно предложить другое занятие — доказать математическую теорему, вместив текст доказательства в обычный твит. Этим заняты создатели твиттера @TinyProof.

Вот так выглядит доказательство от противного того, что полином всегда имеет комплексные решения:



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

Взглянуть на ленту можно здесь.
TinyProof
Total votes 53: ↑48 and ↓5 +43
Views 18K
Comments 5

«Что такое доказательство?»: взгляд из теоретической информатики

Образовательные проекты JetBrains corporate blog Algorithms *Mathematics *
Теоретическая информатика — одно из направлений обучения на кафедре Математических и информационные технологий Академического университета. Нас часто спрашивают, чем занимается теоретическая информатика. Теоретическая информатика — активно развивающееся научное направление, включающее в себя как фундаментальные области: алгоритмы, сложность вычислений, криптография, теория информации, теория кодирования, алгоритмическая теория игр, так и более прикладные: искусственный интеллект, машинное обучение, семантика языков программирования, верификация, автоматическое доказательство теорем и многое другое. Эту статью мы посвятим обзору лишь небольшого сюжета, а именно расскажем о необычных подходах к понятию доказательства, которые рассматривает теоретическая информатика.



Чтобы объяснить, о какого рода доказательствах пойдет речь, рассмотрим пример: есть компьютерная программа, авторы которой утверждают, что программа делает что-то определенное (конкретные примеры будут чуть позже). Программу можно запустить и получить ответ. А как можно удостовериться, что программа делает то, что должна делать? Хорошо бы, если кроме ответа программа выдавала бы доказательство того, что этот ответ правильный.

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



Напомним, что граф называется двудольным, если его вершины можно покрасить в два цвета так, что ребра графа соединяют вершины разных цветов. Паросочетанием в графе называется такое множество ребер, что никакие два из них не имеют общего конца. Множество вершин графа называется покрывающим, если каждое ребро графа имеет как минимум один конец в этом множестве. Теорема Кенига гласит, что в двудольном графе размер максимального паросочетания совпадает с размером минимального покрывающего множества. Таким образом, чтобы доказать, что паросочетание является максимальным, можно предъявить, покрывающее множество, размер которого совпадает с размером данного паросочетания. Действительно, это покрывающее множество будет минимальным, поскольку каждое покрывающее множество обязано покрыть хотя бы один конец каждого ребра этого паросочетания. Например, в графе на рисунке паросочетание (M1, G3), (M2, G2), (M4,G1) будет максимальным, поскольку есть покрывающее множество размера 3, которое состоит из G2, G3 и M4. Отметим, что проверить такое доказательство гораздо проще, чем вычислять максимальное паросочетание: достаточно проверить, что размер паросочетания совпадает с размером покрывающего множества и проверить, что все ребра покрыты.

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



Как можно доказать правильность результата? Если система совместна, то доказательством совместности может стать решение этой системы (нетрудно доказать, что если у такой системы есть решение, то есть и рациональное решение, т.е. его можно записать). А как доказать, что система несовместна? Оказывается, что это сделать можно с помощью леммы Фаркаша, которая утверждает, что если система нестрогих линейных неравенств несовместна, то можно сложить эти неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Например, система на рисунке несовместна, и если сложить первое уравнение с коэффициентом 1, второе с коэффициентом 2, а третье с коэффициентом 1, то получится 0≥1. Доказательством несовместности будет как раз набор неотрицательных коэффициентов.

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

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

Читать дальше →
Total votes 49: ↑46 and ↓3 +43
Views 22K
Comments 11

Задача о ста коробках и спасении заключённых – финальный аккорд

Entertaining tasks Mathematics *
Верный способ войти в историю – ответить, кто побеждает в шахматах при идеальной игре обеих сторон (белые, чёрные или дружба). Нужны ли гроссмейстеры и суперкомпьютеры, чтобы узнать истину? Или достаточно карандаша, бумаги и красивой идеи?

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

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

В самом посте о задаче такого вопроса не поставлено. Однако уже в первом комментарии к нему пользователь mayorovp поднимает тему, а чуть ниже avfonarev сообщает о замечательной статье, раскрывающей тайну.

Этим стоит проникнуться, тем более что рассуждения просты и изящны. В целом же основная идея поста не в решении конкретной задачи (что само по себе тоже интересно), а скорее в том, чтобы в очередной раз дать повод удивиться могуществу или, как выразился Вигнер, непостижимой эффективности математики.
В чём суть?
Total votes 30: ↑29 and ↓1 +28
Views 23K
Comments 7

Доказываем корректность поиска диаметра дерева

Entertaining tasks Algorithms *
Sandbox
Однажды на зачете мне попалась следующая задача. Придумайте алгоритм, находящий две вершины дерева с максимальным расстоянием друг от друга, и докажите его корректность. В тот момент я в принципе не знала, что у деревьев есть диаметр, радиус и много прочих вещей. Уже после зачета друг просветил меня, рассказав, что это за алгоритм, но без доказательства. Именно вопросом о доказательстве долгое время была забита моя голова. После прочтения нескольких статей, стало понятно, что материал не уляжется, пока самостоятельно себе не объясню все практически на пальцах (может, и читателю придется по вкусу). Перейдем от демагогии к сути.

Диаметр дерева — это максимальное расстояние между двумя вершинами в дереве. Алгоритм поиска состоит в двух запусках BFS. Первый идет от произвольной вершины дерева, во время обхода насчитываются расстояния от текущей вершины до всех других. Затем из них выбирается самая удаленная. Из нее делается второй запуск BFS. Насчитываются новые расстояния. Максимальное среди них и будет диаметром.

Почему этот простой с виду алгоритм работает корректно?
Читать дальше →
Total votes 14: ↑11 and ↓3 +8
Views 9.7K
Comments 10

Новое доказательство теоремы о многочлене

Trinity Digital & Баласс Group corporate blog Entertaining tasks Mathematics *
В статье приводится новое доказательство красивой и трудной теоремы математического анализа, изложенное таким образом, что оно доступно учащимся старших классов профильных математических школ.

Пусть $f(x)$ — бесконечно много раз дифференцируемая действительная функция, причем для каждой точки $x\in R$ найдется натуральное $n$ такое, что $f^{(n)}(x)=0$. Тогда $f(x)$ многочлен.

Доказательство


Нам понадобится теорема Бэра о системе замкнутых множеств:

1. Пусть $H$ и $F_{1},F_{2},...,F_{n},...$ замкнутые подмножества прямой, причем $H \neq \varnothing$ и $H\subset \bigcup \limits_{n} F_{n}$. Тогда в $H$ найдется точка, которая содержится в одном из $F_{n}$ вместе со своей окрестностью. Более точно, найдется точка $x\in H$, натуральное $n$ и $\varepsilon >0$ такие, что $(x-\varepsilon;x+\varepsilon)\cap H \subset F_{n}$.

Действительно (от противного), выберем точку $x_{1} \in H$ и окружим ее окрестностью $\Delta_{1}=(x-\varepsilon_{1};x+\varepsilon_{1})$, где $\varepsilon_{1}<1$. Мы предположили, что утверждение теоремы Бэра не верно. Значит $\Delta_{1} \cap H \not \subset F_{1}$. Выберем в $\Delta_{1} \cap H$ точку $x_{2}\notin F_{1}$. Окружим $x_{2}$ интервалом $\Delta_{2}=(x_{2}-\varepsilon_{2};x_{2}+\varepsilon_{2})$ таким, что концы этого интервала — точки $x_{2}-\varepsilon_{2}$ и $x_{2}+\varepsilon_{2}$ лежат в $\Delta_{1}$, а $\varepsilon_{2}<\frac{1}{2}$. По предположению $\Delta_{2}\cap H\notin F_{2}$. Это позволяет выбрать в $\Delta_{2} \cap H$ некоторую точку $x_{3} \notin F_{2},...$ Продолжая процесс, мы построим вложенную стягивающуюся последовательность интервалов $\Delta_{1}\supset \Delta_{2}\supset ...$ Ясно, что

$x_{1}-\varepsilon_{1}< x_{2}-\varepsilon_{2}<...<x_{n}-\varepsilon_{n}...$, (1)
$x_{1}+\varepsilon_{1}>x_{2}+\varepsilon_{2}>...>x_{n}+\varepsilon_{n}...$ (2)

Так как каждый промежуток $\Delta_{i}\cap H\neq \varnothing$, то $\lim _{i\to \infty}(x_{i}-\varepsilon_{i})=\lim_{i\to\infty} (x_{i}+\varepsilon_{i})=y, y\in H$, а из (1) и (2) следует, что $y\in \Delta_{i}$ для каждого $i$. Таким образом мы нашли точку $y \in H$, но не лежащую ни в одном из множеств
$F_{i} \phantom{1} (i=1,2,...)$.
Скажем, что точка на действительной прямой правильная, если в некоторой окрестности этой точки функция $f(x)$ — многочлен. Множество всех правильных точек обозначим символом $E$. Множество $E'$, дополнительное к $E$ обозначим через $F$ и назовем множеством неправильных точек. (Будем говорить, что если $x\in F$, то $x$ — неправильная точка).
Читать дальше →
Total votes 19: ↑17 and ↓2 +15
Views 7.7K
Comments 9

Новый способ введения экспоненты

Trinity Digital & Баласс Group corporate blog Entertaining tasks Mathematics *
Tutorial
В статье предложен новый весьма необычный способ определения экспоненты и на основе этого определения выведены её основные свойства.



Каждому положительному числу $a$ поставим в соответствие множество $E_a=\left\{x:x=\left(1+a_1\right)\left(1+a_2\right)\ldots \left(1+a_k\right)\right.$, где $a_1,a_2,\ldots ,a_k>0$ и $\left.a_1+a_2+\ldots +a_k=a\right\}$.

Лемма 1. Из $0<a<b$ следует, что для каждого элемента $x\in E_a$ найдётся элемент $y\in E_b$ такой, что $y>x$.

Будем писать $A\leq c$, если $c$ верхняя граница множества $A$. Аналогично, будем писать $A\geq c$, если $c$ — нижняя граница множества $A$.

Лемма 2. Если $a_1,a_2,\ldots ,a_k>0$, то $\left(1+a_1\right)\left(1+a_2\right)\ldots \left(1+a_k\right)\geq 1+a_1+a_2+\text{...}+a_k$.

Доказательство


Проведём рассуждение по индукции.

Для $k=1$ утверждение очевидно: $1+a_1\geq 1+a_1$.

Пусть $\left(1+a_1\right)\ldots \left(1+a_i\right)\geq 1+a_1+\ldots +a_i$ для $1<i<k$.

Тогда $\left(1+a_1\right)\ldots \left(1+a_i\right)\left(1+a_{i+1}\right)\geq 1+a_1+\ldots +a_i+\left(1+a_1+\ldots +a_i\right)a_{i+1}\geq$

$\geq 1+a_1+\ldots +a_i+a_{i+1}$.

Лемма 2 доказана.

В дальнейшем мы покажем, что каждое множество $E_a$ ограничено. Из леммы 2 следует, что

$\sup E_a\geq a$ (1)
Читать дальше →
Total votes 29: ↑25 and ↓4 +21
Views 6.9K
Comments 41

Титаны от математики схлестнулись над эпичным доказательством abc-гипотезы

Mathematics *
Translation

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




В отчёте, опубликованном в сентябре 2018 в интернете, Петер Шольце из Боннского университета и Якоб Стикс из Университета имени Гёте во Франкфурте описали то, что Стикс называет «серьёзным и невосполнимым разрывом» в огромной серии объёмных работ Синъити Мотидзуки, знаменитого гениального математика из Киотского университета. Опубликованные в интернете в 2012 году работы Мотидзуки якобы доказывают abc-гипотезу, одну из наиболее далеко идущих задач в теории чисел.
Читать дальше →
Total votes 65: ↑62 and ↓3 +59
Views 47K
Comments 101

Тайны сознания и математика

Mathematics *
В Древнем Египте математики не пользовались доказательствами. Все их утверждения были лишь эмпирически обоснованы. Но тем не менее, пирамиды стояли, а самолеты летали. И, наверное, никто бы и не требовал строгих доказательств, если бы не желание что-то опровергнуть. Вместе с греками математика обрела новую жизнь, в которой появились такие задачи, как квадратура круга, иррациональность корня из двух и задача о трисекции угла. С этого момента потребовались аксиомы, законы логики и теоремы. Современную же математику интересует еще и то, что возможно доказать, а что — нет. Продвижением стали теоремы Геделя о неполноте, формализация логики и Теория доказательств. Я предлагаю теорию и одну аксиому, которая поможет ответить на часть оставшихся вопросов и обозначить границы нашего сознания. В частности, это вопросы полноты, проблема равенства и аксиоматизация нашего воображения.

Читать дальше →
Total votes 36: ↑27 and ↓9 +18
Views 10K
Comments 17

Будущее математики?

Mathematics *Popular science The future is here
Translation
В этом переводе презентации британского математика Кевина Баззарда мы увидим, что следующий комикс xkcd безнадежно устарел.

image

Каково будущее математики?


  • В 1990-х компьютеры стали играть в шахматы лучше людей.
  • В 2018 компьютеры стали играть в го лучше людей.
  • В 2019 исследователь искусственного интеллекта Christian Szegedy сказал мне, что через 10 лет компьютеры будут доказывать теоремы лучше, чем люди.

Конечно, он может быть не прав. А может быть и прав.
Читать дальше →
Total votes 104: ↑104 and ↓0 +104
Views 38K
Comments 202

Что такое свидетельство?

Reading room Popular science Brain

«Безошибочный признак любви к истине, — не принимать никакую гипотезу с большей уверенностью, чем позволяют доказательства, на которых она основана» Джон Локк.

Проявить любопытство
Total votes 18: ↑16 and ↓2 +14
Views 5.9K
Comments 21