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