00:00 тетрис в режиме Бога 00:40 сложности задач P и NP 01:50 полиномиальные задачи, полиномиальное время 02:43 задача путешественника, как посетить все города, потратив меньше всего средств 04:06 NP недетерминированные полиномиальные 04:52 Что случится, если найдем алгоритм для решения задач NP 05:33 NP полные задачи 06:00 Задача как собрать рюкзак 06:50 опрос 100 ученых про задачи P и NP
спс, было сложно но интересно). очуметь..) _ кстати как раз, вовремя.. Недавно вспоминал, про степени и т.д. Если возможно, то хотелось бы увидеть на будущее.. видео о комбинаторике. (и какие бывают формулы решения задач о комбинаторике)
А почему в умножении не 2 в степени n, умноженное на n? (2^n*n) Типа одну цифру на другую определенное количество раз и умножить на такое же количество цифр - показывает количество вариантов
А что тут формировать-то? По-моему всё просто: да нет, нет нет, нет да и да да. Блондинка, которую уламывают на постель -- и та даёт эти же самые ответы, причём в том же порядке, стоит только подогнать под них заранее подготовленные вопросы.)
@@kotgav815 вспоминаем анекдот: сыну задают в школе расказать о родителях, сын приходит к отцу -папа а сколько тебе лет? Тот математик: -Десять лет назад мне было столько же сколько тебе умноженное на 2, а сейчас твой возраст и возраст твоей сестры умноженный на 2. Сынок пишет: мой папа мудак.
@@god_slayer-restart нет, это качество образования такое. Я тоже когда-то давно это в институте проходил, и слушал достаточно внимательно чтобы запомнить, что P - решается за полиноминальное время, а NP - нет. А вот что такое "полиноминальное время", объяснили только здесь.
@@bombazook поддерживаю. Если бы в институте остался и пытался бы понять алгоритмическую сложность то навряд ли бы понял хоть что-то. А сам разобрался весьма спокойно. Ещё можно перефразировать так, что это отношение времени к количеству данных. Всякое константное время, линейное приращение времени в зависимости от количества данных, полиномиальное и т.д.
М-да, "сумничал" называется. Я-то книгу про алгоритмы не читал и не видел, а там, оказывается, прямо на обложке цитата из Хайнлайна. Но я-то не из цитаты это знаю, а потому что прочитал "Чужак в стране чужой" от корки до корки. Дважды.
Про задачу с рюкзаком. Вы сказали, что задача переборная, но если я правильно понял смысл задачи, то мы же можем просто рассчитать стоимость каждого кубического см вещи и класть в рюкзак вещи с наибольшей плотностью дороговизны. Правда если мы положем например дорогущие сережки, дорогой телескоп, то для следующего прдемета по списку плотности дороговизны уже может места не хватит и придется искать менее плотные предметы. Пока писал комментарий- сам себя разубедил=)
по обьему считать нельзя, потому что ты можешь не суметь расположить все предметы геометрически, тоесть у тебя мяч большой влезет, но для остальных предметов не хватит места
@@artemmetra8 по весу тоже самое, только вместо тетриса в 3-ёх измерениях, у тебя будет тетрис в одномерном пространстве. Например: рюкзак расчитан на 10 кг; Список предметов: 2 слитка чистого золота по 5.1 кг: и 2 слитка золота низкой пробы по 5 кг. если цена отличается не более чем в 2 раза, то выгоднее взять 2 слитка низкой пробы, не смотря на то, что цена за кг у них меньше.
На самом деле задачу о рюкзаке можно решить методом разбора её на подзадачи, то есть: рассчитать максимальную стоимость для 1 кг, потом для 2кг и тд. Если интересно: книга «Грокаем алгоритмы»
@@UnderKoBep так это не возможно быстро решить, в любом случае придётся проверить все варианты, это как угадать в какой коробке больше вещей, не открывая все, получается решение и будет в степени. как сложить десятизнатные числа в два действия? только если повезёт и будет 8 нулей, или я чего-то не понял, смысл этого видео? для простых задач можно подобрать быстрое решение, а для максимально сложных и решение будет такое
@@UnderKoBep есть эвристические алгоритмы, позволяющие получить результат за приемлемое время, но с некоторыми оговорками, на которые на практике всем насрать. А в математике всё не так, там нужен точный алгоритм, срабатывающий всегда, иначе это не считается.
С начальной школы недолюбливаю математику. Но Георгий так доходчиво объясняет, что это интересно. Печально, что у нас в школах методика преподавания была другой...
Почему так мало - всего лишь миллион долларов за столь сложную и ценную для человечества задачу? Вот, некоторые у себя в квартире миллиарды держат, при этом ничего ценного для человечества не дали.
@@bearmagistr6879 снимают смешные видосики на ютубе? Фоткают жопы в инстаграм? Удачно инвестировали деньги в нужное время? Может, просто напиздили из гос бюджетов?... А настоящие гении человечества при этом довольствуются объедками капитализма
А практически никакую, прочитайте книгу «золотой билет» как раз про p и np. Штука в том, что чтобы выгрузить из квантового компьютера результат вам потребуется np алгоритм , приблизительно так.
а школе, как правило, не учат такому, только в специальных математических. Такое тебе расскажут в универе на дисциплине: теория алгоритмов или сложность вычислений
Я просто любитель, который пытается решить PvNP и уже убил около 9 лет на это. Я более чем уверен, что они не равны, но чтобы доказать это нужно: новая логика, новая теория множеств, новый тип комплексного анализа на недоступных кардиналах и суперконтиннумах. Это то что я понял, что мне нужно сделать с нуля. Поэтому я не думаю, что кто-то случайный сможет всё это решить так легко. А в вашем видео всё выглядит как-то скомкано и не досказано, даже для новичка. Краткий список претензий: где NP-Complete? где P/Poly, где NP-Intermediate, где рандомизированные и квантовые алгоритмы, где упоминание факторинга чисел, где полиномиальные редукции, где универсальная машина Тьюринга, где языки для этой машины(классы языков) и т.д.? Видео очень слабенькое, если берётесь за открытую математическую проблему, то уж хоть разъясняйте почему она сложная, а то опять будут сотни «доказательств последней теоремы ферма», которыми будут мучить профессиональных математиков). Ах да, а ещё и барьеры с Ораклами, булевыми схемами, алгебраизация. Тема просто фантастически объёмная и сложная. Позовите Александра Разборова из института Стеклова в Москве, я думаю он вам годноты напишет
Хм. Проще простого. Нужно проверить каждую вещь по отдельности, бесконечно складывая её в рюкзак до тех пор, пока не будет учитанны все возможные варианты складывания этой вещи, потом вторую проверить и т.д., потом просто взять и наложить все возможные варианты друг на друга и посмотреть, ибо в таком случае только 1 комбинация будет единственная, когда все вещи будут сложенны в самом оптимизированном состоянии, при таком условии вместимости рюкзака.Остальные комбинации или невозможны, или недостаточно идеально оптимизированны. В общем NP≠P, это совсем другой класс решения задач, и я не математик, и не суперкомпьютер, и поэтому патаюсь найти наиболее точное решение такой задачи в голове. Однако такой алгоритм очень простой, и очень легёк в усвоении. И вы правы, благодаря такому алгоритму я решаю(примерно) все задачи вида NP. Например в играх пытаюсь просчитать лучшую тактику для ведения боя и т.п. Псы. Я сказал глупо и не научно. Но черт возми правильно.
*Ну чисто по моему это вычисляется вероятностью,то есть можно предположить что NP при каком-то условии равно P,ну то есть формулу можно написать так NP≝P,или же так NP≈P* Не знаю зачем я полез в то что не знаю,но это чисто мое предположение P.S мое предположение в том,что есть куча знаков равно,и какой то из них подходит для формулы,тупо но мало ли
На самом деле они либо равны, либо нет, и никак иначе. Они не могут быть примерно равны. Мы можем быть уверенны только в том что NP=P или NPXP, и еще возможно в том что доказать это не возможно.
Не хочу быть дотошным, но 02:12 : "Сложность аглоритма увеличивается полномиально..." Такие оговорки могут ввести в заблуждение человека , который никогда с этим не сталкивался
Всегда интересовало, правильно ли будет следующие утверждение: если инопланетяне, прямо сейчас, посмотрят в сверхмощный телескоп на нашу планету на расстоянии 100 млн световых лет, то увидят живых динозавров, хотя по факту, в настоящем, они уже давно вымерли?
оно правильно в своей сути, вероятно мы и правда видим в небе прошлое, ученые так и изучают историю смотрят куда нибудь далеко, и чем дальше, тем ближе по времени к началу времен
Nope. Unless under the term "pseudo-polynomial" you mean exponential but suppressed one ;o). You indeed may suppress exponent considerably yet, it remains to be exponent. Similarly with correcting algorithms for problem of allocation and coverage problem the time-exponent can be considerably suppressed as well. Although, the real-life cases for this problems may indeed on average take a polynomial time to solve similarly as the simplex-method does not warranty polynomial time for all cases but practically it shows P time for real life input data.
Для задачи с рюкзаком видел жадный алгоритм. Он представляет из себя что то такое: 1) делим массу каждого предмета на его стоимость. Таким образом получая "удельную стоимость" 2) предметы с максимальной удельной стоимостью кладём в рюкзак пока не закончится место
задача с сбором содержимого сумки полиноминальна но если предметы имеют больше измерений чем просто вес - все станет намного сложнее хотя... и это можно обойти. придется знать "важность" каждого параметра
Раньше в ВУЗах всю категорию NP определяли как нелинейное программирование. сюда также относили задачу коммивояжера. А теперь вопрос: зачем менять название на непонятное, чтобы возникала необходимость объяснять сущность полинома и еще больше усложнять? Современные авторы учебников совсем забыли бритву Оккама.
Привет, Георгий ! 🌞😉👌 Вау ! - Это Круто ! 🌞🙌🙏😉👌 Решить Тера сложную задачу, Послать к хренам всю безопасность в интернете, и получить за это Милллллион ! 🌞😉✌ Круто, я согласен ! 😂🤣👌 Когда начинать ? А у вас есть печенки, с чаем ? Я очень люблю чёрный чай с кусочком лимона ! 🌞😉👍
Если серьёзно,то вопрос задачи по-человечески звучит так, - "Можно ли выучить китайский, тайский и айский за 5 минут, используя некий алгоритм формул?" И за его нахождение тебе дадут мильон. Сразу попробую предположить, что такой алгоритм существует и его существование описано в Новом Завете, когда неграмотные апостолы в одно мгновенье заговорили на нескольких иностранных языках при многочисленных свидетелях. Поэтому исторически зафиксированно его существование и можно сделать вывод что NP=P. Но как найти такой алгоритм? Видимо нужно подключить режим Бога.
Самое приятное, это конечно не парить мозги с матаном, а браться решать задачу коммивояжера. Если вы не шизоид, то сами сложите все идеи, вопросы и методы работы с данными в своб математику. А вопрос интерпретации дело пустяковое. Так, я решаю коммивояжера порядка двух лет и с радостью могу поделиться тем, что достиг успехов. Сам топик видео говорит о том, что математики креативят и у них есть простые решения определенных примеров задачи,это подразумевает, что пляска от верного ответа к поиску самого алгоритма/метода решения имеет место быть. А диссонанс мозга происходит, когда ты по сути уже решил задачу и ищешь зацепку, т. е. проблему/ошибку. Её же там нет. Но и неправильного ответа нет, потому что неправильные ответы используют неправильный алгоритм/метод. А правильного метода нет. Интересно получается.
Так, лучший способ работы с математической задачей является: 1 сбор информации о том, что вы решаете. Определение сути задачи. 2 упрощение задачи с сохранением ее целостности. 3 составление вариаций данной задачи. 4 поиск закономерностей данных, т. е. определение категорий (групп, зависимостей). *здесь важно отметить, что вы тратите свое время не на слепой перебор решения задачи, а слепой перебор на выявление закономерностей в ней, т. е. данный процесс избыточен и является сбором информации о задаче. 5 определение связи закономерностей друг относительно друга с целью отбора уникальных закономерностей от основных (априорных). 6 проверка наличия основных закономерностей на остальных вариациях задачи. 7 аргументация/обоснование существования уникальных закономерностей. 8 проверка наличия уникальных закономерностей в остальных вариациях задачи. 9 определение противоречия, т. е. когда определение наличия или отсутствия уникальных закономерностей в остальных вариациях задачи и обоснование их уникальности. 10. Определение категорий уникальных закономерностей в вариациях задачи и нахождение их взаимосвязи (если они в одной категории). 11 обоснование отсутствия уникальности данных закономерностей, т. е. мы поясняем, почему это не новое, а измененное старое. Сводим уникальность закономерностей в класс основных/ априорных закономерностей. 12. Находим взаимосвязь или закономерности между закономерностями УЖЕ одной категории (т.е. категории основных, априорных закономерностей). 13. Определяем суть новых основных закономерностей и подводим итог, т. е. Определяем суть решения и проверяем.
С задачей про рюкзак изи, без всякого перебора... просто у каждой вещи считаем цена одного грамма (делим ценность на ее вес), потом сортируем от большей ценности к меньшей... далее отбираем более ценные вещи (считая их вес) пока не дойдем до максимального веса который может выдержать рюкзак...
Тут вопрос не в алгоритме в целом, а в количестве операция на шмотку, т.е. 2^n - брутфорс для NP, да так проблемы решаются, но ты спроси себя, что если у тебя будет хотя бы 100 шмоток или больше? Вот тут-то и нужно всё сводить к n^3 хотя бы)
Вы не совсем корректно, наверное, поняли задачу. Ваше решение отлично подойдет, если бы в рюкзак складывали крупы, т.е. мы без проблем могли бы взять лишь часть предмета. В нашем же случае возможна ситуация, которая ломает ваше решение. Рассмотрим несколько предметов: ноутбук (стоимость 113, масса 9), мяч (стоимость 75, масса 6), книга (стоимость 20, масса 2), бутылка с водой (стоимость 20, масса 2). Ваш алгоритм возьмет только ноутбук (остальные предметы не влезут), в то же время совершенно ясно, что выгоднее взять мяч, книгу и бутылку с водой.
@@gcomsu5819 Я забыл указать, что наш рюкзак может вместить лишь вещи массой 10. Задача же состоит в максимизации стоимости предметов в нем. Причем нам совершенно без разницы, какова масса предметов в рюкзаке, если она не превышает 10, главное - суммарная стоимость. Надеюсь, что теперь понятна сложность задачи.
P != NP at least for Turing/Von-Neumann machine. The proof: Black box of unknown origin has _N_ binary inputs and one binary output. The only known property of this black box is that only one specific input combination may cause "1" output and all other inputs will give "0" output. Apparently that number of all possible "black boxes" with such property == N^2. Randomly selected black box from set of all possible such black boxes will require on average (N^2)/2 operations to determine the input combination which gives "1" output for the specific randomly selected black box. The class of such black boxes belongs to NP class; the class of such black boxes has no other properties as only a single "1" output for all N^2 inputs => essentially it is defined to belong NP class. Thus, at least one example of NP!=P problem can be explicitly constructed; BTW, It has been shown that a non-local hidden variable quantum computer could implement a search for O(cubic_sqrt(N^2)) steps or O(sqrt(N^2)) for more traditional QC (Grover's algorithm).
Если P=NP, то задача доказательства-тоже NP задача. Если это можно доказать, то всё сходится, а если нельзя, то мы нашли не П, а НП задачу. То есть, доказали неравенство. Значит, если П=НП, это можно доказать. Если не равно, а доказать можно, то мы найдём одну НП=П. Но всё в порядке-единичный случай ничего не показывает. Если доказать это нельзя, то одна "нерешаемая" НП задача найдена. Но всё в порядке-единичный случай ничего не показывает. Если NP=P, то это можно доказать, а если NPне =P, то насчёт доказательства- неопределённость.
*Составить список имеющихся вещей, разбить по категориям и выдать каждому предмету баллы от 1 до 100 по их полезности, а затем получим сумму балов за каждый кубический сантиметр каждого предмета. Складываем в рюкзак самые ценные сантиметры из каждой категории*
Ahdruxa неверный подход ввиду того, что запихивая в первую очередь самые ценные вещи у вас может не полностью использоваться пространство Контрпример вашего суждения: 93 кг 10000р 5 кг 5000р 3 кг 2900р 4 кг 3880р
Я может неправильно понял значение слова алгоритм применительно к этим задачам или еще что-то, но разве задачу с рюкзаком (если берем ограничение по весу и требуется максимальная стоимость) не решается так: для каждой вещи делим ее стоимость на вес, по полученному числу сортируем все вещи по убыванию, а затем набираем вещи сверху вниз пока рюкзак не заполнится по весу?
Нет, потому что вещи неделимые и могут быть ситуации, когдв выгоднее в рюкзак положить две вещи менее выгодные, чем одну более выгодную для более плотной упаковки. То есть пустого места в рюкзаке тоже должно остаться минимум.
"Коммивояжер" как-то не правильно переводить как "путешественник" (слишком общее понятие). По-моему он путешествует с целью заработка путём продажи. Скорее будет верным перевод "бродячий торговец", ну да, тоже устарело... Не существует на данный момент полноценного современного перевода слова "коммивояжер" (или как они там сейчас себя называют), как и понятия "венселлинг".
Не понимаю в чём проблема решения, если все данные известны, в примере рюкзака плотность и цена плотности, внешние габариты, просто нужен фильтр, первое выкидываешь то что физически не поместится, 2 отбираешь то чно меньше и дороже, золотые украшения например, наберёшь 10 кг золота, и всё не надо даже до краёв рюкзак грузить... Домушники вообще на глаз это всё делают без всяких расчётов Так же и по банковским операциям, нужны фильтры, и всё можно легко загнать в анализ.
Мало что понятно в таком объяснении, если честно, хоть я с математическим образованием. В задаче коммивояжера же сложность алгоритма пропорциональна факториалу количества городов. Т.е. вся проблема в том, что факториал не расписать полиномом что ли? А если кто то распишет это для конкретной задачи, то чем это поможет в нахождении более быстрого решения?
1) А если окажется, что P =/= NP ? Тогда доступа ко всем банковским картам у тебя не будет, а вот миллион за доказательство получить можно. 2) Чтобы получить миллион за решение этой задачи, достаточно доказать существование алгоритма, решающего NP задачи за время P, а не предъявлять пример такого алгоритма. Может быть, доказать его существование значительно проще, чем найти сам алгоритм. В таком случаи доступа к картам не будет. 3) Может оказаться так, что P=NP и алгоритм решения NP за время P будет найден, но при этом сложность этого алгоритма всё равно окажется непомерно высокой для современных компьютеров. Даже при сложности алгоритма n^100 ( n в степени 100 ) взломать с его помощью банк используя частный компьютер будет практически невозможно (во всяком случаи это будет дольше человеческой жизни), при сложности n^1000 в мире едва ли надётся компьютер способный на это (даже все кластеры google вместе взятые, или даже все компьютеры подключённые к интернету вместе взятые), а при сложности n^10000 такую задачу, не решит даже компьютер размером с Землю (по крайней мере за время меньше человеческой жизни.)
@@Kmiarg , мощность среднестатистического домашнего компьютера примерно 3-15 тераФЛОПС. Но мощность сети биткойн в прошлом году была 67260548 ПетаФЛОПС. Сколько времени нужно, чтобы такой мощностью выполнить рассчеты? Пс. Видюха уровня 1050-1060 взламывает пароль wi-fi состоящий из 8 цифр за 15 минут.
@@DigiMakc на самом деле я лишь предположил цифры что написал выше, чтобы примерно показать что такое степенной рост, реальные расчёты сильно зависили бы от коэффициентов перед n. Но раз вас интересуют более точные расчёты, вот что могу сказать о приведённых вами цифрах: 1) возмём для примера мощность домашнего компьютера раную 2 тераФЛОПС, тогда во сколько раз мощность сети биткойн больше? Ответ: в 2^26 раз, это чуть меньше чем 10^8. Кажется, только теперь я начал понимать, какой невероятно огромный космический запас я заложил между n^100 и n^1000, потому что разница между ними в n^900 раз, это явно перебор. 2) если пароль или система шифрования не содержит известных уязвимостей, то сложность такой задачи составляет ~ 16^8. поскольку каждый символ в wi-fi пароле может принимать лишь 1 из 16 возможных значений, и это число мы возводим в 8 степень из-за длинны пароля. итак если пароль из 8 символов подбирается за 15 минут, то пароль из 9 символов будет подбираться в 16 раз дольше, то есть 240 мин = 4 часа, пароль из 10 символов 64 часа = 5+1/3 суток, пароль из 11 символов - 85 дней, из 12 симв. - 3,7 лет, из 13 симв. - 59,8 лет из 14 симв. - 957 лет из 15 симв. - 15 321 год - и это всё лишь в том случаи, исходный алгоритм не содержал каких-то оптимизаций по времени, за счёт увеличения затрат памяти. (а если препологает то сроки будут ещё больше, когда закончиться память видеокарты и оперативная память, и придётся активно загружать данные с диска) из 16 симв. - 245 146 лет. Кстати именно 16 сивольные пароли используются сейчас. И тут стоить вспомнить, что для шифрования финансовых данных сейчас используются файл-ключи или USB-ключи. Быстрый поиск показал, что сейчас в продаже есть USB-ключи с паролем длинной 32Кб, 64Кб, 128Кб. И там каждый байт(символ) может быть любым от 0 до 255, то есть сложность их взлома будет от 256^(1024*32) до 256^(1024*128)... это число 2^(2^20) Если кто смотрел видео про число Гремма или знаком со стрелочной нотацией, то это число можно записать как 2↑20 , или просто 2 в более чем миллионной степени... у такого числа даже названия вряд ли найдётся. PS это я ещё не учитывал, что более длинные пароли и ключи надо проверять на более длинных блоках данных, что так же занимает всё больше и больше времени с ростом n. Из-за этой особенности программы полного перебора имеют сложность n^n или подобную. Я же рассматривал в примере const^n , что значительно меньше n^n, но для нижней оценки по времени сгодиться и так.
Потому что тогда решение не обязательно будет самым оптимальным. Приведу пример. Пускай вместимость рюкзака равна 7 кг и есть следующий набор предметов: а1 с весом 3 и стоимостью 3, а2 с весом 2 и стоимостью 2, а3 такая же, а4 весом 6 и стоимостью 6,5. Вещи а1, а2 и а3 имеют соотношение 1, а4 - 1.08. Если положим вещь с наибольшим соотношением, то никакая другая не влезет (остаётся всего 1 кг, а наиболее лёгкая вещь весит 2), получим стоимость 6,5. Если положить 3 остальных вещи, то получим как раз 7 кг и стоимостью 7. Наиболее оптимальное решение для данного примера исключает вещь с наилучшим соотношением.
Скорее эта задача про предметы различной формы. Задача вместить как можно больше. Практическое применение - раскрой листовых материалов. Я думаю, в видео перепутали массу и размеры.
00:00 тетрис в режиме Бога
00:40 сложности задач P и NP
01:50 полиномиальные задачи, полиномиальное время
02:43 задача путешественника, как посетить все города, потратив меньше всего средств
04:06 NP недетерминированные полиномиальные
04:52 Что случится, если найдем алгоритм для решения задач NP
05:33 NP полные задачи
06:00 Задача как собрать рюкзак
06:50 опрос 100 ученых про задачи P и NP
спс, было сложно но интересно).
очуметь..) _ кстати как раз, вовремя.. Недавно вспоминал, про степени и т.д.
Если возможно, то хотелось бы увидеть на будущее.. видео о комбинаторике.
(и какие бывают формулы решения задач о комбинаторике)
@@tinkerbel1955 Вполне вероятно, что сделаем! =)
За получение доступа ко всем зашифрованным данным на планете плата 1лям долларов) будем ждать))
А почему в умножении не 2 в степени n, умноженное на n? (2^n*n)
Типа одну цифру на другую определенное количество раз и умножить на такое же количество цифр - показывает количество вариантов
А ты с названием канала не запаривался)
Я пришёл, чтобы собирать сумку и не болело плечо, спасибо, теперь голова болит и плечо.
Только именитые учёные на вопрос типа да/нет могут сформировать 4 группы ответов
точно
А что тут формировать-то? По-моему всё просто: да нет, нет нет, нет да и да да.
Блондинка, которую уламывают на постель -- и та даёт эти же самые ответы, причём в том же порядке, стоит только подогнать под них заранее подготовленные вопросы.)
@@kotgav815 ору
@@kotgav815 xD
@@kotgav815 вспоминаем анекдот: сыну задают в школе расказать о родителях, сын приходит к отцу
-папа а сколько тебе лет?
Тот математик: -Десять лет назад мне было столько же сколько тебе умноженное на 2, а сейчас твой возраст и возраст твоей сестры умноженный на 2.
Сынок пишет: мой папа мудак.
Видос из разряда "Ничерта непонятно, но очень интересно!")
Если такие нравится, зайти в Яндекс.Рефераты и почитай =) ровно тоже самое =)))
Буквально сегодня была лекция по этой теме. Честно сказать, из видоса в 8 минут понял больше, чем за пару.
@@god_slayer-restart нет, это качество образования такое. Я тоже когда-то давно это в институте проходил, и слушал достаточно внимательно чтобы запомнить, что P - решается за полиноминальное время, а NP - нет. А вот что такое "полиноминальное время", объяснили только здесь.
@@bombazook поддерживаю. Если бы в институте остался и пытался бы понять алгоритмическую сложность то навряд ли бы понял хоть что-то. А сам разобрался весьма спокойно. Ещё можно перефразировать так, что это отношение времени к количеству данных. Всякое константное время, линейное приращение времени в зависимости от количества данных, полиномиальное и т.д.
Вот слушаю ребят умных и так хорошо становится от того, что что то понимаю... мало, но что то понимаю.... Причастен)))
0_o черт!), ты мне глаза раскрыл)). Я теперь понял, почему мне это интересно смотреть))
Если кому-то интересна эта тема, есть отличная книга :Бхаргава Адитья Грокаем алгоритмы. В видео все примеры от туда
У меня «Эффект Баадера Майнхофа», 3 дня назад дочитал, а тут видео...
Подтверждаю
А если хотите окончательно сломать мозг: "Алгоритмы: построение и анализ" (с ветками на обложке)
А слово "грокаем" из Хайнлайна
М-да, "сумничал" называется. Я-то книгу про алгоритмы не читал и не видел, а там, оказывается, прямо на обложке цитата из Хайнлайна. Но я-то не из цитаты это знаю, а потому что прочитал "Чужак в стране чужой" от корки до корки. Дважды.
Именно по этой причине Перельман ходит не с рюкзаком, а с сумкой)
Про задачу с рюкзаком. Вы сказали, что задача переборная, но если я правильно понял смысл задачи, то мы же можем просто рассчитать стоимость каждого кубического см вещи и класть в рюкзак вещи с наибольшей плотностью дороговизны. Правда если мы положем например дорогущие сережки, дорогой телескоп, то для следующего прдемета по списку плотности дороговизны уже может места не хватит и придется искать менее плотные предметы. Пока писал комментарий- сам себя разубедил=)
Там еще сложность в каком месте рюкзака положить эти вещи, получается такой тетрис в 3D + задача оптимизации стоимости.
по обьему считать нельзя, потому что ты можешь не суметь расположить все предметы геометрически, тоесть у тебя мяч большой влезет, но для остальных предметов не хватит места
Там по-моему про вес было а не про объём.
@@artemmetra8 по весу тоже самое, только вместо тетриса в 3-ёх измерениях, у тебя будет тетрис в одномерном пространстве.
Например: рюкзак расчитан на 10 кг;
Список предметов: 2 слитка чистого золота по 5.1 кг: и 2 слитка золота низкой пробы по 5 кг.
если цена отличается не более чем в 2 раза, то выгоднее взять 2 слитка низкой пробы, не смотря на то, что цена за кг у них меньше.
На самом деле задачу о рюкзаке можно решить методом разбора её на подзадачи, то есть: рассчитать максимальную стоимость для 1 кг, потом для 2кг и тд. Если интересно: книга «Грокаем алгоритмы»
Задача про рюкзак - это одна из основных задач динамического программирования
И решается за n в квадрате по-моему
@@UnderKoBep
так это не возможно быстро решить, в любом случае придётся проверить все варианты, это как угадать в какой коробке больше вещей, не открывая все, получается решение и будет в степени. как сложить десятизнатные числа в два действия? только если повезёт и будет 8 нулей, или я чего-то не понял, смысл этого видео? для простых задач можно подобрать быстрое решение, а для максимально сложных и решение будет такое
@@UnderKoBep есть эвристические алгоритмы, позволяющие получить результат за приемлемое время, но с некоторыми оговорками, на которые на практике всем насрать. А в математике всё не так, там нужен точный алгоритм, срабатывающий всегда, иначе это не считается.
Рюкзак работает за O(MN) N - количество вещей, M - масса
А задачу про города можно перевести на граф с использованием алгоритма Дийкстры
На математике просмотров наверно мало. Но было интересно. Правда не все с разу понятно пришлось подумать))
Обожаю выпуски Георгия. продолжайте 👍🙂
С начальной школы недолюбливаю математику. Но Георгий так доходчиво объясняет, что это интересно. Печально, что у нас в школах методика преподавания была другой...
Ну, технически это не математика школьного уровня, а программа теоретической информатики, которая ближе к универу.
Почему так мало - всего лишь миллион долларов за столь сложную и ценную для человечества задачу? Вот, некоторые у себя в квартире миллиарды держат, при этом ничего ценного для человечества не дали.
@@bearmagistr6879 снимают смешные видосики на ютубе? Фоткают жопы в инстаграм? Удачно инвестировали деньги в нужное время? Может, просто напиздили из гос бюджетов?...
А настоящие гении человечества при этом довольствуются объедками капитализма
@@ElimDax01 Не стоит так резко разбрасываться громкими словами, хотя в чем то вы правы.
Потому что это частная инициатива отдельного вуза
так мало, чтобы уменьшить стимул уничтожить криптографию
просто в восторге, млн бачей за уничтожение мира
И если уничтожится, то куда их тратить?) Разве что подтереться.
Спасибо за видео, самое понятное объяснение про классы Р и NP
И как Вам мозг изнутри глаза не выдавил? ))
Он иногда играет в современные мейнстрим шутеры, чтобы контролировать рост
Не дождётесь
Первый раз вижу объяснение этой задачи, понятным человеческим языком. Спасибо, вам!
тот неловкий момент, когда живешь в Братиславе :D
Слава славянской славакии.
Братиславе? Зачем жить в брате Славы?
У вас реально там такие дома?
Можно было ещё рассказать о том, какую роль в данном контексте играют квантовые компьютеры. Это тоже занятно)
Вот вот, было бы здорово послушать
А практически никакую, прочитайте книгу «золотой билет» как раз про p и np. Штука в том, что чтобы выгрузить из квантового компьютера результат вам потребуется np алгоритм , приблизительно так.
@@MySaluto , интересно. Тогда получатся, что вообще в квантовых компьютерах смысла нет?
Рюкзак заполнить жёстким диском с биткоинами и калифорнием)
Читал книгу Грокаем алгоритмы на питон и залетел сюда за дополнительной информацией. Стало понятнее
Хотелось бы ещё услышать про остальные задачи тысячилетия!!!!
Вот ради таких роликов я и подписался. Пусть редко, но мне хватит )))
Что тут сказать, спасибо за идею по заработку 1 миллиона $$$
Уверен, есть более короткие пути по заработку миллиона)
Опять мне этот чувак взорвёт мозг.Лайк.
Дико интересно! Давайте больше мозголомательной математики!
10 классов проучился и впервые об этом слышу.
а школе, как правило, не учат такому, только в специальных математических. Такое тебе расскажут в универе на дисциплине: теория алгоритмов или сложность вычислений
Слишком тяжелая информация для меня. Посмотрю когда буду готовым к этому ролику))))
Заходи ко мне, я помогу с этим делом!):)
Это такой синоним слова никогда?
Юрий Якунин сильно много слов в одно превращаешь
Я с такой грыжей сталкивался, когда ехал на регион по программированию. Было прикольно послушать
Спасибо, наконец-то разобралась, в Вики так себе было объяснение
как раз читаю книгу по алгоритмам и дошел до алгоритмов np сложности, и в качестве альтернативы показывают "жадные" алгоритмы, но не точные
Крууть! Расскажи как-нибуть ещё про решения задач симплекс методом.
Я просто любитель, который пытается решить PvNP и уже убил около 9 лет на это. Я более чем уверен, что они не равны, но чтобы доказать это нужно: новая логика, новая теория множеств, новый тип комплексного анализа на недоступных кардиналах и суперконтиннумах. Это то что я понял, что мне нужно сделать с нуля. Поэтому я не думаю, что кто-то случайный сможет всё это решить так легко. А в вашем видео всё выглядит как-то скомкано и не досказано, даже для новичка. Краткий список претензий: где NP-Complete? где P/Poly, где NP-Intermediate, где рандомизированные и квантовые алгоритмы, где упоминание факторинга чисел, где полиномиальные редукции, где универсальная машина Тьюринга, где языки для этой машины(классы языков) и т.д.? Видео очень слабенькое, если берётесь за открытую математическую проблему, то уж хоть разъясняйте почему она сложная, а то опять будут сотни «доказательств последней теоремы ферма», которыми будут мучить профессиональных математиков). Ах да, а ещё и барьеры с Ораклами, булевыми схемами, алгебраизация. Тема просто фантастически объёмная и сложная. Позовите Александра Разборова из института Стеклова в Москве, я думаю он вам годноты напишет
А с чего именно вы подступились к подобной задаче? На первый взгляд она кажется неприступной
нихуя не понял, но очень интересно
Я тут пришёл рюкзак собирать, а не задачи решать)
Спасибо! Это супер важная задача
Как же всё таки близки олимпиадное программирование и олимпиадная математика
Хм. Проще простого. Нужно проверить каждую вещь по отдельности, бесконечно складывая её в рюкзак до тех пор, пока не будет учитанны все возможные варианты складывания этой вещи, потом вторую проверить и т.д., потом просто взять и наложить все возможные варианты друг на друга и посмотреть, ибо в таком случае только 1 комбинация будет единственная, когда все вещи будут сложенны в самом оптимизированном состоянии, при таком условии вместимости рюкзака.Остальные комбинации или невозможны, или недостаточно идеально оптимизированны. В общем NP≠P, это совсем другой класс решения задач, и я не математик, и не суперкомпьютер, и поэтому патаюсь найти наиболее точное решение такой задачи в голове. Однако такой алгоритм очень простой, и очень легёк в усвоении. И вы правы, благодаря такому алгоритму я решаю(примерно) все задачи вида NP. Например в играх пытаюсь просчитать лучшую тактику для ведения боя и т.п.
Псы. Я сказал глупо и не научно. Но черт возми правильно.
Разумная Ящерица слишком сложно, это тупо брутфорс
Задача с рюкзаком самая важная. В Diablo постоянно с ней сталкиваюсь.
Заходи ко мне решать задачки:)
@@JuraSheingart нет
*Ну чисто по моему это вычисляется вероятностью,то есть можно предположить что NP при каком-то условии равно P,ну то есть формулу можно написать так NP≝P,или же так NP≈P*
Не знаю зачем я полез в то что не знаю,но это чисто мое предположение
P.S мое предположение в том,что есть куча знаков равно,и какой то из них подходит для формулы,тупо но мало ли
На самом деле они либо равны, либо нет, и никак иначе. Они не могут быть примерно равны. Мы можем быть уверенны только в том что NP=P или NPXP, и еще возможно в том что доказать это не возможно.
Не хочу быть дотошным, но
02:12 : "Сложность аглоритма увеличивается полномиально..."
Такие оговорки могут ввести в заблуждение человека , который никогда с этим не сталкивался
за решение этой задачи скорее всего открутят голову... очень решительно.
кстати, нынче умножают со сложностью n*log(n)
ZecosMAX примерно с 70-ых умножают быстро, и вот буквально месяц как вы написали)
Ничего не понял но очень интересно 🐒
Всегда интересовало, правильно ли будет следующие утверждение: если инопланетяне, прямо сейчас, посмотрят в сверхмощный телескоп на нашу планету на расстоянии 100 млн световых лет, то увидят живых динозавров, хотя по факту, в настоящем, они уже давно вымерли?
оно правильно в своей сути, вероятно
мы и правда видим в небе прошлое, ученые так и изучают историю
смотрят куда нибудь далеко, и чем дальше, тем ближе по времени к началу времен
Тревожную музыку на фоне надо убрать
Задачу о рюкзаке можно решить за псевдополиномиальное время методами динамического программирования.
Nope. Unless under the term "pseudo-polynomial" you mean exponential but suppressed one ;o). You indeed may suppress exponent considerably yet, it remains to be exponent. Similarly with correcting algorithms for problem of allocation and coverage problem the time-exponent can be considerably suppressed as well. Although, the real-life cases for this problems may indeed on average take a polynomial time to solve similarly as the simplex-method does not warranty polynomial time for all cases but practically it shows P time for real life input data.
Георгий
Богом молю, подскажите что у вас за наручные часы!
А ролик огонь, очень доходчиво все
Так я не поняла, рюкзак то как собирать? Где ответ на этот вопрос? Сижу уже у рюкзака и что дальше? 🤔
* в замешательстве... 🤯
Я доказал, но не расскажу из добрых побуждений.
Забавно. Тот, кто получит этот миллион не положит его в банк.
на коммивояжоре он поржал,а на многочлене сдержался!)))
O(n!).
Решается, но решаться будет по миллиардам лет.
Спасибо за видео.
Может быть np задача сама формируется и решается по алгоритму,который тоже формируется сам в ходе ряда событий?То есть задача есть алгоритм.
"Я бы мог решить , но это слишком скучно " you
Для решения этой задачи не нужен алгоритм по скольку нету бесконечного числа переменных.
Для задачи с рюкзаком видел жадный алгоритм. Он представляет из себя что то такое:
1) делим массу каждого предмета на его стоимость. Таким образом получая "удельную стоимость"
2) предметы с максимальной удельной стоимостью кладём в рюкзак пока не закончится место
Alexander Kostrov это да
задача с сбором содержимого сумки полиноминальна
но если предметы имеют больше измерений чем просто вес - все станет намного сложнее
хотя... и это можно обойти. придется знать "важность" каждого параметра
Если можно ложить только целое количество предметов, то эта задача становится NP
У меня мир вокруг чуть полиномиальным не стал :)
Пожалуйста, больше не говори это слово :)))
Ахаха))) Заходи ко мне такие же комментарии писать:) (у меня видео очень короткие, прокачаешься)
Класс
Чисто подставила единицу в эту формулу и доказала, что np=p, a p=np
Раньше в ВУЗах всю категорию NP определяли как нелинейное программирование. сюда также относили задачу коммивояжера. А теперь вопрос: зачем менять название на непонятное, чтобы возникала необходимость объяснять сущность полинома и еще больше усложнять? Современные авторы учебников совсем забыли бритву Оккама.
Спасибо!
Ух ты!
Для единственной вселенной Np =P для мульти вселенных Np не решаема, так как события дублируются до бесконечности!
Привет, Георгий ! 🌞😉👌
Вау ! - Это Круто ! 🌞🙌🙏😉👌
Решить Тера сложную задачу,
Послать к хренам всю безопасность в интернете,
и получить за это Милллллион ! 🌞😉✌
Круто, я согласен ! 😂🤣👌
Когда начинать ?
А у вас есть печенки, с чаем ?
Я очень люблю чёрный чай с кусочком лимона ! 🌞😉👍
Не до конца вдуплился в тему выпуска. Но мне понравилось.
Если серьёзно,то вопрос задачи по-человечески звучит так, - "Можно ли выучить китайский, тайский и айский за 5 минут, используя некий алгоритм формул?" И за его нахождение тебе дадут мильон. Сразу попробую предположить, что такой алгоритм существует и его существование описано в Новом Завете, когда неграмотные апостолы в одно мгновенье заговорили на нескольких иностранных языках при многочисленных свидетелях. Поэтому исторически зафиксированно его существование и можно сделать вывод что NP=P. Но как найти такой алгоритм? Видимо нужно подключить режим Бога.
А мне интересно, если Перельман решит эту задачу,он снова не возьмет деньги?
Будет зависеть от того, сможет ли он сложить деньги в рюкзак за полиномиальное время.
Самое приятное, это конечно не парить мозги с матаном, а браться решать задачу коммивояжера. Если вы не шизоид, то сами сложите все идеи, вопросы и методы работы с данными в своб математику. А вопрос интерпретации дело пустяковое.
Так, я решаю коммивояжера порядка двух лет и с радостью могу поделиться тем, что достиг успехов.
Сам топик видео говорит о том, что математики креативят и у них есть простые решения определенных примеров задачи,это подразумевает, что пляска от верного ответа к поиску самого алгоритма/метода решения имеет место быть. А диссонанс мозга происходит, когда ты по сути уже решил задачу и ищешь зацепку, т. е. проблему/ошибку. Её же там нет. Но и неправильного ответа нет, потому что неправильные ответы используют неправильный алгоритм/метод. А правильного метода нет. Интересно получается.
Так, лучший способ работы с математической задачей является:
1 сбор информации о том, что вы решаете. Определение сути задачи.
2 упрощение задачи с сохранением ее целостности.
3 составление вариаций данной задачи.
4 поиск закономерностей данных, т. е. определение категорий (групп, зависимостей).
*здесь важно отметить, что вы тратите свое время не на слепой перебор решения задачи, а слепой перебор на выявление закономерностей в ней, т. е. данный процесс избыточен и является сбором информации о задаче.
5 определение связи закономерностей друг относительно друга с целью отбора уникальных закономерностей от основных (априорных).
6 проверка наличия основных закономерностей на остальных вариациях задачи.
7 аргументация/обоснование существования уникальных закономерностей.
8 проверка наличия уникальных закономерностей в остальных вариациях задачи.
9 определение противоречия, т. е. когда определение наличия или отсутствия уникальных закономерностей в остальных вариациях задачи и обоснование их уникальности.
10. Определение категорий уникальных закономерностей в вариациях задачи и нахождение их взаимосвязи (если они в одной категории).
11 обоснование отсутствия уникальности данных закономерностей, т. е. мы поясняем, почему это не новое, а измененное старое. Сводим уникальность закономерностей в класс основных/ априорных закономерностей.
12. Находим взаимосвязь или закономерности между закономерностями УЖЕ одной категории (т.е. категории основных, априорных закономерностей).
13. Определяем суть новых основных закономерностей и подводим итог, т. е. Определяем суть решения и проверяем.
С задачей про рюкзак изи, без всякого перебора... просто у каждой вещи считаем цена одного грамма (делим ценность на ее вес), потом сортируем от большей ценности к меньшей... далее отбираем более ценные вещи (считая их вес) пока не дойдем до максимального веса который может выдержать рюкзак...
Тут вопрос не в алгоритме в целом, а в количестве операция на шмотку, т.е. 2^n - брутфорс для NP, да так проблемы решаются, но ты спроси себя, что если у тебя будет хотя бы 100 шмоток или больше? Вот тут-то и нужно всё сводить к n^3 хотя бы)
Вы не совсем корректно, наверное, поняли задачу. Ваше решение отлично подойдет, если бы в рюкзак складывали крупы, т.е. мы без проблем могли бы взять лишь часть предмета. В нашем же случае возможна ситуация, которая ломает ваше решение. Рассмотрим несколько предметов: ноутбук (стоимость 113, масса 9), мяч (стоимость 75, масса 6), книга (стоимость 20, масса 2), бутылка с водой (стоимость 20, масса 2). Ваш алгоритм возьмет только ноутбук (остальные предметы не влезут), в то же время совершенно ясно, что выгоднее взять мяч, книгу и бутылку с водой.
@@mr.geekman8526 я понял о чем вы... хотя вы допустили ошибку... масса книги, бутылки и воды больше массы ноутбука :)))
@@gcomsu5819 Я забыл указать, что наш рюкзак может вместить лишь вещи массой 10. Задача же состоит в максимизации стоимости предметов в нем. Причем нам совершенно без разницы, какова масса предметов в рюкзаке, если она не превышает 10, главное - суммарная стоимость. Надеюсь, что теперь понятна сложность задачи.
P != NP at least for Turing/Von-Neumann machine. The proof: Black box of unknown origin has _N_ binary inputs and one binary output. The only known property of this black box is that only one specific input combination may cause "1" output and all other inputs will give "0" output. Apparently that number of all possible "black boxes" with such property == N^2. Randomly selected black box from set of all possible such black boxes will require on average (N^2)/2 operations to determine the input combination which gives "1" output for the specific randomly selected black box. The class of such black boxes belongs to NP class; the class of such black boxes has no other properties as only a single "1" output for all N^2 inputs => essentially it is defined to belong NP class. Thus, at least one example of NP!=P problem can be explicitly constructed; BTW, It has been shown that a non-local hidden variable quantum computer could implement a search for O(cubic_sqrt(N^2)) steps or O(sqrt(N^2)) for more traditional QC (Grover's algorithm).
Если P=NP, то задача доказательства-тоже NP задача. Если это можно доказать, то всё сходится, а если нельзя, то мы нашли не П, а НП задачу. То есть, доказали неравенство. Значит, если П=НП, это можно доказать. Если не равно, а доказать можно, то мы найдём одну НП=П. Но всё в порядке-единичный случай ничего не показывает. Если доказать это нельзя, то одна "нерешаемая" НП задача найдена. Но всё в порядке-единичный случай ничего не показывает.
Если NP=P, то это можно доказать, а если NPне =P, то насчёт доказательства- неопределённость.
Ничего не понял, но было интересно!
Подумал что расскажут какой-нибудь математический способ собрать рюкзак комивояжёра а в итоге появилась фобия взлома личных данных
Объяснили. Я понял.
Но зачем?
*Составить список имеющихся вещей, разбить по категориям и выдать каждому предмету баллы от 1 до 100 по их полезности, а затем получим сумму балов за каждый кубический сантиметр каждого предмета. Складываем в рюкзак самые ценные сантиметры из каждой категории*
Про задачу с рюкзаком
Берем и вычисляем для каждой вещи значение = стоимость/масса.
Затем пихаем в рюкзак вещи в порядке убывания этого значения
Ahdruxa неверный подход ввиду того, что запихивая в первую очередь самые ценные вещи у вас может не полностью использоваться пространство
Контрпример вашего суждения:
93 кг 10000р
5 кг 5000р
3 кг 2900р
4 кг 3880р
@@karenyaylyan2243 зато в игрульках самый кайф, потом можно вручную откорректировать.
Было количество операций и вдруг стало количесво времени)
Количество времени пропорционально количеству операций
@@mihail-ln4rf это, как минимум, требует пояснения
42 !
P 42 NP
Вот и все
Освобождаю рюкзак для миллиона долларов!
Я решил эту задачу, но поле для комментариев слишком маленькое чтобы написать решение здесь...
так почем нельзя составить алгоритм в ИИ(Искусственном интелекте), что бы он подобрал нужный алгоритм для PN and P типов задач
Я может неправильно понял значение слова алгоритм применительно к этим задачам или еще что-то, но разве задачу с рюкзаком (если берем ограничение по весу и требуется максимальная стоимость) не решается так: для каждой вещи делим ее стоимость на вес, по полученному числу сортируем все вещи по убыванию, а затем набираем вещи сверху вниз пока рюкзак не заполнится по весу?
Нет, потому что вещи неделимые и могут быть ситуации, когдв выгоднее в рюкзак положить две вещи менее выгодные, чем одну более выгодную для более плотной упаковки. То есть пустого места в рюкзаке тоже должно остаться минимум.
Расскажите подробнее, что там Перельман доказал
Очень интересно, хоть сложновато понять.
P.S. подскажи что за трек на фоне и в конце
Очень интересное видео, но перегруз на петле прям боль 😢
О да. Ещё и хромакей лагает, когда он руками резко двигает.
Ничего не понял, но было интересно.
"Коммивояжер" как-то не правильно переводить как "путешественник" (слишком общее понятие). По-моему он путешествует с целью заработка путём продажи. Скорее будет верным перевод "бродячий торговец", ну да, тоже устарело... Не существует на данный момент полноценного современного перевода слова "коммивояжер" (или как они там сейчас себя называют), как и понятия "венселлинг".
Думаю если кто-то решит данную задачу, то будет взламывать счета и воровать деньги
Как будто без этой задачи не взламывают и не воруют!
Не понимаю в чём проблема решения, если все данные известны, в примере рюкзака плотность и цена плотности, внешние габариты, просто нужен фильтр, первое выкидываешь то что физически не поместится, 2 отбираешь то чно меньше и дороже, золотые украшения например, наберёшь 10 кг золота, и всё не надо даже до краёв рюкзак грузить...
Домушники вообще на глаз это всё делают без всяких расчётов
Так же и по банковским операциям, нужны фильтры, и всё можно легко загнать в анализ.
Мало что понятно в таком объяснении, если честно, хоть я с математическим образованием. В задаче коммивояжера же сложность алгоритма пропорциональна факториалу количества городов. Т.е. вся проблема в том, что факториал не расписать полиномом что ли? А если кто то распишет это для конкретной задачи, то чем это поможет в нахождении более быстрого решения?
Ничего не понял, но очень интересно
Хм, нужен ли будет миллион долларов, если есть доступ ко всем банковским картам?)
1) А если окажется, что P =/= NP ? Тогда доступа ко всем банковским картам у тебя не будет, а вот миллион за доказательство получить можно.
2) Чтобы получить миллион за решение этой задачи, достаточно доказать существование алгоритма, решающего NP задачи за время P, а не предъявлять пример такого алгоритма. Может быть, доказать его существование значительно проще, чем найти сам алгоритм. В таком случаи доступа к картам не будет.
3) Может оказаться так, что P=NP и алгоритм решения NP за время P будет найден, но при этом сложность этого алгоритма всё равно окажется непомерно высокой для современных компьютеров. Даже при сложности алгоритма n^100 ( n в степени 100 ) взломать с его помощью банк используя частный компьютер будет практически невозможно (во всяком случаи это будет дольше человеческой жизни), при сложности n^1000 в мире едва ли надётся компьютер способный на это (даже все кластеры google вместе взятые, или даже все компьютеры подключённые к интернету вместе взятые), а при сложности n^10000 такую задачу, не решит даже компьютер размером с Землю (по крайней мере за время меньше человеческой жизни.)
@@Kmiarg , мощность среднестатистического домашнего компьютера примерно 3-15 тераФЛОПС.
Но мощность сети биткойн в прошлом году была 67260548 ПетаФЛОПС.
Сколько времени нужно, чтобы такой мощностью выполнить рассчеты?
Пс. Видюха уровня 1050-1060 взламывает пароль wi-fi состоящий из 8 цифр за 15 минут.
@@Kmiarg можно ещё доказать, что эта задача в принципе не решаема. И тоже получить свой лям.
@@DigiMakc на самом деле я лишь предположил цифры что написал выше, чтобы примерно показать что такое степенной рост, реальные расчёты сильно зависили бы от коэффициентов перед n. Но раз вас интересуют более точные расчёты, вот что могу сказать о приведённых вами цифрах:
1) возмём для примера мощность домашнего компьютера раную 2 тераФЛОПС, тогда во сколько раз мощность сети биткойн больше? Ответ: в 2^26 раз, это чуть меньше чем 10^8. Кажется, только теперь я начал понимать, какой невероятно огромный космический запас я заложил между n^100 и n^1000, потому что разница между ними в n^900 раз, это явно перебор.
2) если пароль или система шифрования не содержит известных уязвимостей, то сложность такой задачи составляет ~ 16^8. поскольку каждый символ в wi-fi пароле может принимать лишь 1 из 16 возможных значений, и это число мы возводим в 8 степень из-за длинны пароля.
итак если пароль из 8 символов подбирается за 15 минут, то
пароль из 9 символов будет подбираться в 16 раз дольше, то есть 240 мин = 4 часа,
пароль из 10 символов 64 часа = 5+1/3 суток,
пароль из 11 символов - 85 дней,
из 12 симв. - 3,7 лет,
из 13 симв. - 59,8 лет
из 14 симв. - 957 лет
из 15 симв. - 15 321 год - и это всё лишь в том случаи, исходный алгоритм не содержал каких-то оптимизаций по времени, за счёт увеличения затрат памяти. (а если препологает то сроки будут ещё больше, когда закончиться память видеокарты и оперативная память, и придётся активно загружать данные с диска)
из 16 симв. - 245 146 лет. Кстати именно 16 сивольные пароли используются сейчас.
И тут стоить вспомнить, что для шифрования финансовых данных сейчас используются файл-ключи или USB-ключи. Быстрый поиск показал, что сейчас в продаже есть USB-ключи с паролем длинной 32Кб, 64Кб, 128Кб. И там каждый байт(символ) может быть любым от 0 до 255, то есть сложность их взлома будет от 256^(1024*32) до 256^(1024*128)... это число 2^(2^20)
Если кто смотрел видео про число Гремма или знаком со стрелочной нотацией, то это число можно записать как 2↑20 , или просто 2 в более чем миллионной степени... у такого числа даже названия вряд ли найдётся.
PS это я ещё не учитывал, что более длинные пароли и ключи надо проверять на более длинных блоках данных, что так же занимает всё больше и больше времени с ростом n. Из-за этой особенности программы полного перебора имеют сложность n^n или подобную. Я же рассматривал в примере const^n , что значительно меньше n^n, но для нижней оценки по времени сгодиться и так.
@@Kmiarg ахуенна
По поводу сбора вещей в рюкзак. Почему нельзя найти отношение стоимость/вес каждого предмета и брать вещи с наибольшим этим коэффициентом?
Потому что тогда решение не обязательно будет самым оптимальным. Приведу пример.
Пускай вместимость рюкзака равна 7 кг и есть следующий набор предметов: а1 с весом 3 и стоимостью 3, а2 с весом 2 и стоимостью 2, а3 такая же, а4 весом 6 и стоимостью 6,5.
Вещи а1, а2 и а3 имеют соотношение 1, а4 - 1.08.
Если положим вещь с наибольшим соотношением, то никакая другая не влезет (остаётся всего 1 кг, а наиболее лёгкая вещь весит 2), получим стоимость 6,5.
Если положить 3 остальных вещи, то получим как раз 7 кг и стоимостью 7.
Наиболее оптимальное решение для данного примера исключает вещь с наилучшим соотношением.
А я думал будет разбор задачи о рюкзаке по теории игр рассмотренной в качестве кооперативной игры
Насчет рюкзака. Делим стоимость вещи на ее массу и сраниваем показатели
Скорее эта задача про предметы различной формы. Задача вместить как можно больше. Практическое применение - раскрой листовых материалов. Я думаю, в видео перепутали массу и размеры.
лайк не глядя, пошла глядеть
ничего не понял, но продолжайте )
наконец то понял че за дичь эта "нп = п" спасиб)
Я думал типо я такой умный пока не зашёл на видос. (думал N*P=P / 0*0=0)))))