Я думаю, что у с++ очень амбициозные цели. Он хочет быть максимально производительным, максимально универсальным, обратно совместимым и при этом желательно понятным.
Но если с++ не загнётся, а преодолеет эти трудности, возможно у нас будет язык, близкий к идеальному. Так скажем граалем всего программисткого комьюнити.
Не только. В фундаментальную науку в других странах, тоже немного платят (для их страны). Только именитым учёным платят хорошо, и то они особо на яхтах не катаются.
Подчеркну, что я про фундаментальную науку говорю.
Задача: есть ли доказательство данного утверждения, которое по длинне не превосходит 100 * на длину утверждения
сертификат - доказательство
Проверка за полином.
Противоположная задача: есть ли опровержение, которое по длинне не превосходит 100 * на длину утверждения.
сертификат- опровержение
Проверка за полином
В комментарии, действительно я не упомянул, наличие ограничений на длину доказательства. Но суть остаётся такой-же. Так как нам нужны доказательства ограниченной длины. Можно вместо 100, взять число побольше.
И это никак не противоречит теореме Гёделя. Так как в обоих задачах, мы просто не найдем сертификаты.
Так же хочу отметить, что алгоритм может, если он даже будет, слишком громоздким и его использование будет непрактичным.
Но чисто математически, при равенстве p и np классов у нас будет алгоритм нахождения решения для большинства математических задач.
В определении фигурирует функция R, которая по сертификату за полиномиальное время проверяет ответ.
Поставим такую задачу. Существует ли из данных аксиом вывод доказательства данного утверждения за 100 * на длину утверждения. (100 число из головы).
Сертификатом будет доказательство этого утверждения.
И оно будет проверяться за полиномиальное время. (Когда мы читаем доказательство, нам не требуется экспонециальное время на проверку)
И вот у нас np задача. Даже скорее всего np полная.
И как раз таки в том числе и поэтому большинство придерживается того, что p не равно np. Так как если они будут равны, у нас будет алгоритм решающий большинство математических задач.
Ну по сути, мы можем записать её как формальное утверждение и спросить, верно ли оно. Если да, то можно предоставить сертификат, в виде доказательства. Как раз определение NP задачи. Кнш тут есть много ньюансов, но суть такая.
Так что любая математическая задача, чисто формально, np полная задача)
Если окажется, что P=NP, то мы сможем доказывать любые теоремы за полиномиальное время, тк это тоже np полная задача (решение как сертификат). Ну а если мы можем доказать или опровергнуть любой факт из математики, то это в корни изменит математику и весь мир.
Конечно, это всё если нам крупно повезёт: константа будет не очень большой и степень у полинома)
Как нам говорил препод, если доказать np = p, можно получить миллион долларов, а потом доказать оставшиеся задачи 1000летия с помощью того алгоритма и залутать оставшиеся 5 миллионов)
Неевклидовая геометрия, булева алгебра, теория Галуа не были востребованы в своё время. Но сейчас на них держаться все спутники, все компьютеры и квантовая физика.
Неизвестно какая область математики выстрелит в будущем.
А доказывать нерешённые задачи не просто. Так как если бы это было бы просто их бы давно доказали.
Почему статья помечена как сложная? Тут не требуется какие-то специальные знания и тут нет мозговыносящих математических приёмов. Но тут проблема не в авторе, а в сайте.
Думаю на хабре нужно сделать так, что бы пользователи смогли оценивать сложность статьи, а не авторы. Либо вовсе этот параметр удалить, тк часто авторы его не совсем объективно ставят (и тут тоже вопрос, может ли один человек объективно оценить сложность материала).
В начале написана асимптотика алгоритма, и она состовляет .
Так как время работы сильно зависит от машины, на которой работает алгоритм, в теоретической информатике работают с асимптотиками алгоритмов. Про это можно подробнее прочитать тут и на википедии.
Опять реклама платных курсов. Есть куча бесплатных гайдов, по любому языку, просто открываешь и начинаешь изучать.
Я думаю, что у с++ очень амбициозные цели. Он хочет быть максимально производительным, максимально универсальным, обратно совместимым и при этом желательно понятным.
Но если с++ не загнётся, а преодолеет эти трудности, возможно у нас будет язык, близкий к идеальному. Так скажем граалем всего программисткого комьюнити.
Согласен!
Особенно дифференциальные и вариционные исчесления
Не только. В фундаментальную науку в других странах, тоже немного платят (для их страны). Только именитым учёным платят хорошо, и то они особо на яхтах не катаются.
Подчеркну, что я про фундаментальную науку говорю.
Задача: есть ли доказательство данного утверждения, которое по длинне не превосходит 100 * на длину утверждения
сертификат - доказательство
Проверка за полином.
Противоположная задача: есть ли опровержение, которое по длинне не превосходит 100 * на длину утверждения.
сертификат- опровержение
Проверка за полином
В комментарии, действительно я не упомянул, наличие ограничений на длину доказательства. Но суть остаётся такой-же. Так как нам нужны доказательства ограниченной длины. Можно вместо 100, взять число побольше.
И это никак не противоречит теореме Гёделя. Так как в обоих задачах, мы просто не найдем сертификаты.
Так же хочу отметить, что алгоритм может, если он даже будет, слишком громоздким и его использование будет непрактичным.
Но чисто математически, при равенстве p и np классов у нас будет алгоритм нахождения решения для большинства математических задач.
Возможно я не ясно выразился.
Я не утверждаю, что есть алгоритм который решает любую математическую задачу.
Но вопрос о том, является ли утверждение верным, это NP задача.
Давайте возьмём определение отсюда:
https://ru.wikipedia.org/wiki/Класс_NP
В определении фигурирует функция R, которая по сертификату за полиномиальное время проверяет ответ.
Поставим такую задачу. Существует ли из данных аксиом вывод доказательства данного утверждения за 100 * на длину утверждения. (100 число из головы).
Сертификатом будет доказательство этого утверждения.
И оно будет проверяться за полиномиальное время. (Когда мы читаем доказательство, нам не требуется экспонециальное время на проверку)
И вот у нас np задача. Даже скорее всего np полная.
И как раз таки в том числе и поэтому большинство придерживается того, что p не равно np. Так как если они будут равны, у нас будет алгоритм решающий большинство математических задач.
В гугле точно дураки не сидят, поэтому они не будут покупать стартап лапшы на уши.
Но это можно продать инвесторам :D
В данном случае, стартап вполне логичен и с потенциалом.
Ну по сути, мы можем записать её как формальное утверждение и спросить, верно ли оно. Если да, то можно предоставить сертификат, в виде доказательства. Как раз определение NP задачи. Кнш тут есть много ньюансов, но суть такая.
Так что любая математическая задача, чисто формально, np полная задача)
Если окажется, что P=NP, то мы сможем доказывать любые теоремы за полиномиальное время, тк это тоже np полная задача (решение как сертификат). Ну а если мы можем доказать или опровергнуть любой факт из математики, то это в корни изменит математику и весь мир.
Конечно, это всё если нам крупно повезёт: константа будет не очень большой и степень у полинома)
Как нам говорил препод, если доказать np = p, можно получить миллион долларов, а потом доказать оставшиеся задачи 1000летия с помощью того алгоритма и залутать оставшиеся 5 миллионов)
Я думаю, автор имеет в виду, что не стоит только на О нотацию смотреть при выборе алгоритма.
Ещё нужно учитывать константу, железо и ограничения на n.
Для многих математических теорий в начале не находили практического применения. Но сейчас это очень востребованные вещи.
Например, булева алгебра сейчас используется во всех компьютерах. А раньше на практике ей почти никто не пользовался.
Неевклидовая геометрия, булева алгебра, теория Галуа не были востребованы в своё время. Но сейчас на них держаться все спутники, все компьютеры и квантовая физика.
Неизвестно какая область математики выстрелит в будущем.
А доказывать нерешённые задачи не просто. Так как если бы это было бы просто их бы давно доказали.
Для плоских фигур должно выполняться правило, что у них постоянная ширина. Иначе можно меньшую ширину просунуть в большую.
Такие фигуры могут быть только гладкими.
Вот статья с википедии про фигуры постоянной ширины https://ru.wikipedia.org/wiki/Кривая_постоянной_ширины
Для map вы неправильно посчитали асимптотику.
Там будет О(n * log (m)) где m количество букв, в данном случае 26. То есть асимптотика будет O(n)
Действительно, большие матрицы можно оптимизировать под конвейер процессора.
Но для нахождения чисел Фибоначчи используются матрицы 2 на 2. Поэтому такие оптимизации не дадут выйгрыш в скорости.
Подробнее про алгоритм с матрицами 2 на 2 для поиска чисел Фибоначчи можно посмотреть тут: https://habr.com/ru/articles/148336/
Почему статья помечена как сложная? Тут не требуется какие-то специальные знания и тут нет мозговыносящих математических приёмов. Но тут проблема не в авторе, а в сайте.
Думаю на хабре нужно сделать так, что бы пользователи смогли оценивать сложность статьи, а не авторы. Либо вовсе этот параметр удалить, тк часто авторы его не совсем объективно ставят (и тут тоже вопрос, может ли один человек объективно оценить сложность материала).
Почему ваш алгоритм работает за n log n? Когда вы проверяете треугольники на условие Делоне, ваш алгоритм может очень долго сходиться.
Мы не можем перебрать все пары друзей, так как их
. Поэтому нужно использовать приведённый алгоритм, но с некоторой вариацией.
Постараюсь кратко указать направление идеи.
В качестве
и 
возьмем 
равное количеству друзей которые едят именно этот набор пицц.
Так же
будет равен не размеру множества, а количеству пицц нечетного размера.
Делаем свертку
, с самим собой перемножаем в 
и разворачиваем.
Тут нужно учесть, что ответ будет в 2 раза больше, и для
, нужно удалить неподходящие случаи.
Так же у задачи есть разбор и пример кода.
Но эта задача сложная (*3000), и разбор будет большим, поэтому я постарался рассказать только направление идеи.
Да, тут мы работаем с обычными числами. Но этот же алгоритм можно применить, к примеру, если R это матрицы.
Тут я заметил ошибку, в статье мы используем не поле, а кольцо.
В начале написана асимптотика алгоритма, и она состовляет
.
Так как время работы сильно зависит от машины, на которой работает алгоритм, в теоретической информатике работают с асимптотиками алгоритмов. Про это можно подробнее прочитать тут и на википедии.