Science show. Выпуск № 69. Равенство классов P и NP
Вставка
- Опубліковано 23 жов 2018
- Видео о самой красивой формуле: • #161. САМАЯ КРАСИВАЯ Ф...
Патрион: / makarsvet13
Макар Светлый: id182122590
Наша группа: makarsvet13
Как захватить мир?: habr.com/post/227687/
![Лжецы Ферма [Numberphile]](/img/n.gif)
я человек простой, делюсь только на себя и на единицу
я сложный - делюсь собой с другим человеком и при этом приумножаюсь
Если при делении человека появляются два новых похожих, но не идентичных человека(двойнята), то числа делённые на два только похожи, но не идентичны.
Странный метод размножения¿
Я тебя проинтегрировал, я тебя и продифференцирую!!!
У тебя просто мега качественный контент . Не думаю что кто то ещё спрашивал бы у авторов доказательств про подтверждения или вообще бы с ними связался . Лайк)
Макар показал часть лица!!! Часть задачи тысячелетия решена осталось ещё чуток потерпеть
Спасибо
Макар Светлый
Я человек сложный, но читая комментарии - упростился)))0)
"я стал проще и люди потянулись" =D
Разложился на множители)
Среди всех прочих научно-популярных каналов на ютубе, смотреть твой контент особенно интересно и захватывающе. Продолжай в том же духе, надеюсь канал будет развиваться, а ролики выходить с большей частотой не уступая при этом в качестве, спасибо...
Вау, да это же самый настоящий Макар собственной персоной)) Спасибо тебе за годноту!
Макар (не знаю как вас по отчеству), спасибо, что, несмотря на плохой отклик массовой аудитории, ты делаешь контент. Спасибо ещё раз
Шикарный выпуск!
я человек простой, я вижу новый ролик Макара - я ставлю лайк
А я ставлю Дизлайк!
@@vinivinia3333 Присоединяйся к нам лучше!
он не стадо, он не с нами и не с вами, он нигилист ;)
А я томат.
как круто, что есть люди, которые снимают видео про такие вещи, да и еще понятным языком
❤ как же хочется знать больше,как это интересно!!!! Спасибо сердечное
Живу без ласки,
Боль в душе затая,
Всегда быть в маске -
Судьба моя!
Ставлю лайк, потому что данная тема очень интересная для меня.
Показался, белобрысый))) Годноту делаешь, в радость тебя смотреть
Очень интересно, спасибо!
Лучший из лучших!
Интересная тема. Спасибо!
молодец, классный выпуск!
Очень актуальная тема!)
ООо... Спасибо за этот видос и ссылку на хабру. Именно то, что мне нужно было. Хотя было бы интересно вообще узнать, что нужно прочитать, чтобы лучше понять суть этой проблемы.
Супер! Спасибо за ясное и подробное объяснение столь сложной, но реально мировой темы 😊
Годнота, мне нравится)
. . . агооооонь
я абсолютно не шарю в математике,но обожаю все эти нереально-нереальные задачи и особенно тех кто их решает или уже решили,как Г.Я.Перельман(гипотеза Пуанкарэ)...это же что-то с чем-то:)
Ты лучший математик на Ютуб!!!
то чувство когда в вузе изучаешь теорию алгоритмов, а у Макара выходит видос про P-NP задачи :D
Очень интересный ролик
Когда курсовая работа на эту тему....мммм, спасибо)
Макар ты серьезно? Я прямо сейчас(натуральный в данный момент) дочитываю книжку computer science an overview, и там рассказывали про эту проблему. У меня сразу в голове всплыло что хорошо бы было если бы ты запили ролик об этом. И тут такое. Лови Луи си Кея.
и у меня тоже в универе как раз такой курс. супер видео !
Совпадение?
Andrew Verenev Не думаю...
Брутальный Усач в какой главе там про это?
Simon Morozov Последняя, если не ошибаюсь.
Пауза на девятой минуте. В примере, котором проверяем правильность разложения на простые множители необходимо еще проверить каждый множитель на простоту. Понятно, что это тоже полином, но появляется чувство недосказанности.
Про шахматы - правильность любого хода можно *быстро* проверить по 32-фигурным таблицам Налимова.
это лайк, господа!
Макар, скажи пожалуйста что за музыка на фоне?
Если оперировать бесконечными цифрами, то мгновенный ответ теоретически существует, он конечно будет тоже приблизительным, но если учитывать человеческое ограничение приближённое к равенству то оно будет истинной и появляться оно будет мгновенно полностью решая задачу на данный момент для человеческого постоянного!
Во - первых для решения подобных задач нужно платить больше чем один миллион долларов, а во - вторых я считаю что Да - существует простой алгоритм решения сложных задач.
Хм, а к какому классу относится задача о вычисления коэффициента пропорциональности массы?
Тут, скорее всего, либо P, либо тупо O(1), зависит от конкретной постановки условия.
Макар, если уж затронул компьютеры и математику, как насчет темы для видео: изоморфизм Карри - Ховарда (aka Brouwer-Heyting-Kolmogorov interpretation)?
Доходчиво)
о! я увидел Макара)
16:25 Математики такие необычные люди!Захотел что-то узнать и просто написал человеку, открывшему это)
10:34
Вы не поверите, но сериал След (тот самый, с пятого канала) уже снял серию с таким сюжетом и названием "код Пи".
В серии сначала детально объясняется суть задачи тысячелетия со всеми подробностями, последствиями решения и суммой награды от института Клэя.
А затем начинается кровавый экшн из за того, что P=NP...
Да Макар, изрядно тебя жизнь за 13 лет потрепала
Ага! И жениться успел! Кто эта развратительница несовершеннолетних? :)
что интересно, алгоритм Рыбникова и состоит в упрощении маттеорий...
А что за музыка в ролике?
Здравствуйте.
Вы правда с Оренбурга или учились тут ?
Я человек простой, поэтому напишу очередной комментарий про то, что я человек простой.
Пересматриваю этот роллик из-за того, что он пробивает слезу
Не рассказано про самый важный аспект этой проблемы - сводимость за полиномиальное время. Все задачи из NP, в том числе сами P, при помощи полиномиального алгоритма сводятся к NPC задачам, и именно поэтому полиномиальный алгоритм решения для любой из них автоматически даст равенство P и NP, и про это не было ни слова. Ну и P!=NP автоматически дает гарантию безопасности ассиметричной криптографии от обычных, не квантовых компьютеров, а на ней вся нынешняя банковская система держится
Насчёт сводимости. Были упомянуты труды Кука. Вы считаете для научпопа этого недостаточно?
да. только новый алгоритм с временным сдвигом позволит решить проблему)
*Тук-тук-тук*
Я:Кто там ?
Стучащий: это я O(n!)
Я: Боже упаси.
Бит. маски и O(n!) -> O(n2^n) или типо того)
В том то и деле, что нужно сложное решение.
И где именно можно ознакомиться с решение анатолия плотникова?
Ребят, подскажите музыку на пианино на заднем фоне, пожалуйста, очень нужно. Спасибо!
rob dougan clubbed to death
clubbed to death matrix soundtrack
Всё таки неравенство доказывать проще - достаточно одной задачи-контрпримера. А если равенство докажут, то оч. круто все тут же рванут разваливать ассиметричные алгоритмы шифрования и ломать цифровые подписи)
Вот только я не понял в ряде примеров были задачи у которых в асимптотической сложности есть алгоритм - они относятся к классу P, ведь условная nlog(n) быстрее чем n^2.
а чем тебе nlog(n) не класс P?) Скорость полиномиальна.
@@BlureAbility
Да нет про логарифм... Всё таки полином имеет конкретный вид - линейная комбинация степенных функций и логарифма там нет. Кстати логарифм растёт настолько медленнее полинома, насколько сам полином медленнее показательной функции. Хотя, наверное, придираюсь. Есть алгоритмы log(n), или степень log(n)... Может просто придираюсь что их отнесли в класс полиномиальных.
При этом непонятно. Вот a^n считается плохим, а n^3 - хорошим. При этом какой-нибудь log^3(n) в большей мере ускоряет n^3, чем последний показательную сложность. Извините за косноязычие.)))
Dmitry Polyakov так речь о log(n) или nlog(n)? Второй, про который вы писали изначально, он растет с полиномиальной скоростью, логарифм влияет на скорость роста n слабей, чем любая степень k>1)
Человек в маске заинтриговал, Вудман уже пригласил на кастинг!
расскажите пожалуйста про нейронную сеть.
4:49 - зазор
Посоветуйте книги, для изучения физики/математики сверх школьной программы ( 9 класс ).
Серафим Виногродский, В.А.Зорич Математический анализ, Кострикин Алгебра (1 том), курс общей физики Сивухина. Это не школьная
программа, это для первых курсов вузов, чтобы понять, чем в универах занимаются и познакомиться с математикой и физикой как с более-менее систематической наукой. Из Зорича, если читать, можете прочитать до производных/интегралов, дальше точно не надо, будет круто, если познакомитесь с пределами, это идейно важное понятие, в обычных школах дают производные, но без строгих определений, понятие предела позволит вам как раз узнать такое строгое определение. Эта литература, скорее всего, никак не поможет на экзаменах в школе, но позволит получить некоторое представление о том, что проходят в универах на физмат специальностях и подготовит вас к этому.
P.s. Не уверен, что школьникам надо это читать, возможно лучше поготовиться к тому же ЕГЭ и олимпиадам, порешать задачки, но если тянет к чему-то идейно более сложному и жёсткому - я написал. Математика и физика - они большие, всегда можно найти, что почитать, если есть желание
@@fraikrus я уже и забыл, что здесь это спрашивал. Считай год прошел. Спасибо :)
Уже продолжительное время есть мысли почитать Зорича, но останавливает то, что на практике мне матан применять, собственно, негде, так что это все со временем очень вероятно забудется, да и без этого есть много материала, входящего в сферу моих непосредственных интересов (Программирование и IT), который хотелось бы изучить
А вообще задача теста на простоту относится к P-классу. Просто этот полиномиальный алгоритм настолько медленный что становится быстрее NP алгоритма только на оооооочень больших числах и его почти не используют
На практике используют вероятностные алгоритмы
Допустим я не решил задачу P=NP, но нашел быстрый алгоритм разложения на простые множители, и быстрый алгоритм для получения всех простых чисел меньших 2^n для заданного n(быстрая рекурентная формула, которая перебирает все простые числа в нетривиальном порядке). Также это позволяет находить целый логарифм. Типа log_7(9) = 4 (mod 13). 7^4 = 9 + 184 * 13(понятно, что кроме 4 согласно теореме Эйлера также подходят 16, 28, 40, 52 и т.д.). Если я правильно понимаю, то решение таких задач может привести к краху банковской системы... Ну вот допустим я о них расскажу ради того миллиона, вот только система скорее всего упадет до того, как я смогу воспользоваться деньгами.
P.S. Я просто хотел отсортировать целочисленный массив за линейное время...
- Это ящик Пандоры: если его открыть, всем хана. Открывать?
- Открывай.
- Но ведь хана же всем!
- И Рабиновичу?
- Ну, да...
- Открывай, не томи!
Что ты под нетривиальным порядком понимаешь?
@@BlureAbility В тривиальном порядке - это например в порядке возрастания, или в порядке убывания. В нетривиальном - в любом другом. Например в таком порядке, чтобы расстояние Хэмминга(точнее сумма расстояний Хэмминга между соседними числами в двоичном представлении) было минимальным.
Linux Gaming in FullHD 60FPS как расстояние Хэмминга в переборе простых чисел помогает?
@@BlureAbility Помогает использовании операции xor, которая очень быстрая, и меняет лишь часть числа. Особенно это удобно при работе с большими числами. А также возможно распараллеливание алгоритма, в котором вычисляются числа, с которыми нужно ксорить простые.
Так у меня есть к вам вопрос. Как вы считаете?. если нарисовать окружность радиуса 8 см #, потом, разделите его на 16 к, после по кругу этой окружности нарисовать окружность радиусом 9 см. Зачем измерить длину хорды одной из 16 одинаковых n угольных частей и нарисовать такой же длиной с помощью линейки или циркуля какие же хорды на окружности радиуса 9 см; возможно ли сделать потом, на этой окружности 17n угольник. ? !.
Как складывать числа в системе счисления с основанием бесконечность?
Что такое суммирование цифр?
Это когда мы в алфавите выбранной системы счисления выбираем первое слагаемое суммы и двигаемся дальше по алфавиту на расстояние равное второму слагаемому, если мы вышли за алфавит, то переходим в начало алфавита.
С бесконечным основанием и алфавит символов бесконечный, а значит каждое существующее число будет состоять из одной цифры, то есть перехода по разряду не будет.
Спсб
Щас дам задачу компьютеру лайк поставить
а он тебе смс)))
Топлес одобряет
сужение (ограничение) правил порождает сложности, ибо предполагает ограничение - на ограничение можно опереться - и придумать новые сущности
да просто всё - как ты
@@GavrilaPetrovi4 нормально, а ты как?
Загадка тысячелетия , это супер симметрия !Она дает разгадку на все вопросы!!!Пускай сделают приз в 100 миллионов долларов!!!!За разгадку !!!
Ответ на все вопросы - 42
@@redhook777 поддерживаю) верный ответ 42
сколько времени понадобиться что б докозать что наша вселенная тор? ровно столько сколько придётся литеть. или опровергнуть. придётся литеть столько же. но что если кто то может передвигаться быстрее?
P
Господи, прости им, ибо не ведают, что творят!
10:44 название фильма?
Сериал "Числа".
и че, где реакция на Плотникова
если компьютер научится сам решать любые задачи - мы создадим скайнет.
решать научится, а придумывать нет
@@andrii979 ну это задачка опять из программирования. просто выход зацикливаешь на вход. получается вечно думающий комп.
+- так кстати и наш мозг работает. он сам себя в нейронах зацикливает и возбуждает. от сюда и сны и прочее
11:54
вот даже проще))) нарису за 5 минут лабиринт который я пройду за 6 минут. но самый быстрый и долгий либиринт окажется спираль ) нарисованный за 30 секунд и пройти тебе его придется тоже за 30 секунд . но кто быстрее?
Решил.
А на фоне играет саундтрек к Матрице)
Классы P и NP равны. Это доказано тем, что найден простой алгоритм. Сейчас как раз захватываем мир:) Пользуйтесь знанием того, что доказать неравенство нельзя. Соответственно, Плотников ошибся.
нарисуй лабиринт за 30 секунд который я пройду за более долгое время...
время решения = времени проверки. а время проверки= времени решения.
в доказательстве должно фигурировать время как переменная
Да))) я составлю судоку с 1 циферкой за 1 секунду) а значит и решение будет найдетно за 1 секунду) а вот если ты захочешь поставить 5 чисел то тебе потребуется подумать верон ты их поставил или нет) а значит и решение мной будет такоеже)))) да?
Зачем маску надел?
Это ряд Тейлора! А не формула Эйлера)
P нерано NP. Простое объяснение. Чтобы проверить задачу почему не решается Греко латинский квадрат 6-го порядка. Надо просто проверить Греко латинский квадрат 2-го порядка, почему он нерешаетса. Гениально и просто. Так же с простыми и сложными задачами. Надо находить простой ответ на решение задачи. То есть Центр задачи.
12:40, не ужели, он вынес P!? Славься Баринов, славься Баринов !!! Конечно же я шучу.
Я не понял сути вопроса...(да туповат)). По сути мы ищем более короткие пути решения для упорядочивания больших объёмов информации? Или пытаемся найти универсальный метод на все задачи подобного типа?
Есть задачи, которые можно решить за полиномиальное время. Есть задачи, которые можно только проверить за полиномиальное время. (За полиномиальное время - время напрямую зависит от количества шагов n или от n^m, где ^ возведение в любую степень m. Но не от m^n, если количество шагов в показателе степени, то сложность задачи возрастает очень быстро. Такова, например, задача коммивояжера.) Тождественны ли эти два класса задач между собой? Суть в том, что скорее всего P≠NP, но это ещё надо доказать (ну или проверить то доказательство, о котором говорится в конце видео).
P.S. на мой взгляд, у Макара получилось не то чтоб запутанное объяснение... просто не расставлены акценты важного и неважного.
А что если есть алгоритм(сложный) с правилами, для решения всех задач за одинаковое количество шагов при етом неважно сложная ето задача или легкая (пускай легкие задачи можно решить другим алгоритмом намного быстрее)?
NP=P но не Р=NP
@@Forky320 оператор равенства множеств, насколько я знаю, однозначный и смысл записи А = B тавтологичен записи B = A.
И ещё, путем подобных предположений "а если бы" можно прийти к полному бреду очень быстро, для избежания этого каждое подобное утверждение слудет снабжать доказательством или хотя бы причиной возникновения такого предположения, иначе нигде в серьезном обсуждении на это даже внимания обращать не станут.
@@user-xh9pu2wj6b вы математик?
@@roark_u отчасти, а что?
11:40 как из неравенства классов P и NP следует, что для "сложных" задач бессмысленно искать простой алгоритм? И в каком смысле употреблено слово "сложные"? Если математически, как в начал ролика, то утверждение вообще бессмысленно, ибо для этих задач по определению нет простого решения, независимо от того равны классы P и NP или не равны. Если в бытовом смысле (то есть задачи, для которых на данный момент не найдено простых решений), то ничего подобного не следует, ибо конкретная задача не факт, что принадлежит к классу P или NP. Тут, видимо, следует определить "сложные" задачи, как задачи, для которых доказано, что они принадлежат к классу NP и при этом доказано, что они не принадлежат к классу P. Но поиск такого доказательства само по себе задача как минимум не менее сложная, ибо если найдем, то это автоматически докажет неравенство классов P и NP. Или я что-то не понял?
Тоже заметил, думаю оговорка
Сложные задачи - задачи из NP, не принадлежащие P. Это можно понять из контекста всего видео.
Насчёт бессмысленности поиска. Была упомянута теорема Кука. Как раз при помощи её можно показать, что поиск полиномиального решения не имеет смысла для всех известных сегодня NP-полных задач.
4 краски.
Можно пожайлусто расказать про число"g64"
А почему до сих пор институт Клея не заметил эти статьи Плотникова? Разве нельзя непосредственно туда отправить доказательства? Я просто не в курсе , как работает эта система. Но как-то подозрительно - вроде задача тысячелетия, очень важна для человечества, а до сих пор не проверено, не опровергнуто или не подтверждено...
если все ради денег то будут искать тех кто возможно решил уже))) короче там все запутанно)))
:)
Кто-то моими обозначениями пользуется.
а пока одни ищут простые решения сложных задач , другие создают нейронные сети для упрощения)
Возможно когда-то нейронные сети найдут простые решения для сложных задач. Сейчас все актуальнее
все супер! кроме маски...
Математика царица наук
На экзамене по дискретке это в билете было
Ответ "нет", ибо практика показывает что не бывает простых решений по одной кнопке. =^_^=
И вообще, сам факт существования данной задачи уже делает невозможным P = NP.
...ну как-то так...xD
А теперь математически обоснуй это. Так-то прикол в том, что быстрым решением в информатике считается любое решение за полиномаильное время и таки да, куча задач имеют проверку за полиномаильное время, но при этом их решение будет настолько всратое, что часто может занять пару столетий.
Склоняюсь, эту задачу впринципе невозможно решить (она недоказуема). И вообще - она очень странная какая-то
Не понял.
Дайте музыку пожалуйста. Шазам ее не узнает
Это саундтрек к первому фильму Matrix.
Не стесняйся сними маску
Я думаю так что p=np
21