Comments 14
Подскажите, возможно ли решить любую математическую нерешаемую на данный момент задачу человечества, используя только суперкомпьютер и брутфорс просчет всех возможных вариантов решения?
Количество чисел бесконечно, так что все возможные варианты не просчитать.
Но ведь рано или поздно решение найдется не так ли? Возможно через неделю просчетов, возможно через год или никогда, и с появлением квантовых компьютеров, просчет млрд'ов ккомбинаций решений в секунду, сможет существенно ускорить процесс. Можно составить базу допустимых вариантов для анализа, запрограммировать алгоритм на перебор и проверку на допустимость решения, проанализировав допустимость свойств и их комбинаций исходя из известных данных о математических законах.
Конечно, математики пользуются перебором, но это не панацея. Например, перебором не доказать великую теорему Ферма, но если она не верна, перебором возможно можно будет найти опровержение.
Почитайте про логическое программирование (напр. Prolog)
из википедии: Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем.
Есть опыт автоматического доказательства простеньких теорем на прологе, могу написать на хабре статью на эту тему, если кому интересно.
Есть опыт автоматического доказательства простеньких теорем на прологе, могу написать на хабре статью на эту тему, если кому интересно.
Lerg: Количество чисел бесконечно, так что все возможные варианты не просчитать.
EvilGenius18: Но ведь рано или поздно решение найдется не так ли?Конечно найдется!
Иногда через бесконечное количество времени. Чак Норрис, как известно, досчитавший до бесконечности дважды — не в счет.
Компьютер может помочь в случае, если задача сводится к большому, но конечному числу вариантов. Как в решении проблемы четырех красок, доказательство которого не проверить вручную. Но такие случаи — редкость.
Если человек не может доказать, что сумма углов треугольника = 180, то компьютер не сможет помочь, так как не в состоянии перебрать все возможные треугольники.
Если человек не может доказать, что сумма углов треугольника = 180, то компьютер не сможет помочь, так как не в состоянии перебрать все возможные треугольники.
Представим себе, что мы решаем задачу коммивояжера. Допустим, что для 20 городов мы можем компьютером перебрать все варианты за 1 минуту. Тогда для перебора всех вариантов для задачи из 30 городов нам потребуется 138 289 384 лет. Для 40 городов уже не хватит и времени существования вселенной.
Задачи с комбинаторным взрывом количества возможных решений нельзя решить проверив все возможные решения.
Задачи с комбинаторным взрывом количества возможных решений нельзя решить проверив все возможные решения.
А мы спешим куда-то?
Какой это по конфигурации компьютер вы брали при расчете количества лет? Что если объединить 10 суперкопьютеров Tianhe-2 или 1 квантовый компьютер с тысячами кубитов? Ведь при добавлении какждого последующего 1 кубита мощность возрастает экпотенциально. при нескольких тысячах кубитов можно будет за считанные месяца или года решать подобные задачи.
Конфигурация компьютера не играет роли. Допустим, 10 суперкопьютеров Tianhe-2 задачу коммивояжера для 100 городов полным перебором решает за 1 минуту (но это нереально, так как число вариантов 99!, а это огромное число). Тогда задачу из 130 городов 10 суперкопьютеров Tianhe-2 не решат за всё время существования вселенной.
А квантовые компьютеры… Ну, предоставьте такой вот комп, который это решает.
Почитайте вот это: ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0
А квантовые компьютеры… Ну, предоставьте такой вот комп, который это решает.
Почитайте вот это: ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0
Sign up to leave a comment.
Математики решили проблему Ферми-Паста-Улама