Что нового в проблеме P=?NP. Даниил Мусатов (МФТИ, ЛИСОМО РЭШ)
ฝัง
- เผยแพร่เมื่อ 27 ก.พ. 2018
- 29 декабря 2017г.
Смотрите другие отснятые лекции, узнавайте о предстоящих мероприятиях:
Группа ВК: baikalreadings
сайт проекта: sibscience.org - วิทยาศาสตร์และเทคโนโลยี
Про путь Гамильтона понятно.
А Эйлеров путь = NP-задача? Я уже лет 7 решаю одну большую задачу, связанную с головоломками, похожими на кубик Рубика (и на нем в частности), и недавно совершил некоторый прорыв в ней. Очень интересно, как это относится к более популярной математике)
7:10 А как же алгоритм Куна?
46:50 Могу точно утверждать, что задача определения изоморфизма графа полиномиальная. Я уже почти год как этим пользуюсь. Для этого всего лишь нужен полиномиальный алгоритм для вычисления полного инварианта. И у меня он есть. O(n^4). Правда пока попытки применить этот инвариант для однозначного определения гамильтоновости графа безуспешны. Хотя и доказать, что невозможно определить гамильтоновость при помощи этого инварианта так же не могу.
Очень интересно, можно пруф?
Насколько мне известно, никому ещё не удалось полный инвариант, вычислимый за полиномиальное время.
@@sedfer411 Ну а для док-ва того, что при этом я не пользуюсь методами Монте-Карло предлагаю ответить на большую серию примеров без единой ошибки.
С удовольствием, но мне потребуется время для подготовки. Я тут вижу две проблемы:
1. n^4 не сильно отличается от нового алгоритма Бабаи n^(log n)^2 для малых n, то есть нужны достаточно большие графы. С другой стороны n^4 непрактично уже для n>200. Вы предлагаете n=100, что достаточно убедительно, но сомнения всё же могут быть.
2. Ваш алгоритм может быть применим для широкого круга графов, но при этом ошибаться на остальных. Не зная подробностей алгоритма и не имея достаточной квалификации в составлении задач такого рода, я скорее всего не смогу составить контрпримеры, то есть достаточно сложные псевдоизоморфные графы, которые проходят стандартные эвристические тесты, например перебор полиномиальных инвариантов.
Нам будет неудобно общаться здесь, поэтому предлагаю написать мне в Discord или выбрать любой другой удобный Вам способ связи.
@@sedfer411 ок. готовьте. Для слишком больших n получится недостаточно много примеров, чтобы гарантировать, что это не монтекарло. Ну и потом стоит учитывать что мне при вычислении для больших n так же придется иметь дело с операциями на числах с большой двоичной разрядностью. Тоже над прогой придется поколдовать.
Телеграм?
@@sedfer411 можем обменяться телеграм.
Насчет подбора сложных псевдоизоморфных графов - могу порекомендовать использовать серию однородных графов с кол-вом ребер порядка m = n(n-1)/4.
ужасно тормозит картинка и рассинхрон со звуком
проблема на качестве 240р, с остальными нормально
Скорее всего временно, еще youtube не успел всё обработать. У меня и на 720 проблема. А на 360 ОК
копирует повествование своего учителя, такое не воспринимается