Задачи тысячелетия. Просто о сложном

image
Привет, хабралюди!

Сегодня я бы хотел затронуть такую тему как «задачи тысячелетия», которые вот уже десятки, а некоторые и сотни лет волнуют лучшие умы нашей планеты.

После доказательства гипотезы (теперь уже теоремы) Пуанкаре Григорием Перельманом, основным вопросом, который заинтересовал многих, был: «А что же он собственно доказал, объясните на пальцах?» Пользуясь возможностью, попробую объяснить на пальцах и остальные задачи тысячелетия, или по крайней мере подойти в ним с другой более близкой к реальности стороны.

Равенство классов P и NP


Все мы помним из школы квадратные уравнения, которые решаются через дискриминант. Решение этой задачи относится к классу P (Polynomial time) — для нее существует быстрый (здесь и далее под словом «быстрый» подразумевается как выполняющийся за полиномиальное время) алгоритм решения, который и заучивается.

Также существуют NP-задачи (Non-deterministic Polynomial time), найденное решение которых можно быстро проверить по определенному алгоритму. Для примера проверка методом перебора компьютером. Если вернуться к решению квадратного уравнения, то мы увидим, что в данном примере существующий алгоритм решения проверяется так же легко и быстро как и решается. Из этого напрашивается логичный вывод, что данная задача относится как к одному классу так и ко второму.

Таких задач много, но основным вопросом является, все или не все задачи которые можно легко и быстро проверить можно также легко и быстро решить? Сейчас для некоторых задач не найдено быстрого алгоритма решения, и неизвестно существует ли такой вообще.

На просторах интернета также встретил такую интересную и прозрачную формулировку:
Допустим, что вы, находясь в большой компании, хотите убедиться, что там же находится ваш знакомый. Если вам скажут, что он сидит в углу, то достаточно будет доли секунды, чтобы, бросив взгляд, убедиться в истинности информации. В отсутствие этой информации вы будете вынуждены обойти всю комнату, рассматривая гостей.

В данном случае вопрос стоит все тот же, есть ли такой алгоритм действий, благодаря которому даже не имея информации о том, где находится человек, найти его так же быстро, как будто зная где он находится.

Данная проблема имеет большое значение для самых различных областей знаний, но решить ее не могут уже более 40 лет.

Гипотеза Ходжа


В реальности существуют множество как простых так и куда более сложных геометрических объектов. Очевидно, что чем сложнее объект тем более трудоемким становится его изучение. Сейчас учеными придуман и вовсю применяется подход, основная идея которого заключается в том, чтобы вместо самого изучаемого объекта использовать простые «кирпичики» с уже известными свойствами, которые склеиваются между собой и образуют его подобие, да-да, знакомый всем с детства конструктор. Зная свойства «кирпичиков», становится возможным подступиться и к свойствам самого объекта.

Гипотеза Ходжа в данном случае связана с некоторыми свойствами как «кирпичиков» так и объектов.

Гипотеза Римана


Всем нам еще со школы известны простые числа которые делятся только на себя и на единицу (2,3,5,7,11...). С давних времен люди пытаются найти закономерность в их размещении, но удача до сих пор так никому и не улыбнулась. В результате ученые применили свои усилия к функции распределения простых чисел, которая показывает количество простых чисел меньше или равных определенного числа. Например для 4 — 2 простых числа, для 10 — уже 4 числа. Гипотеза Римана как раз устанавливает свойства данной функции распределения.

Многие утверждения о вычислительной сложности некоторых целочисленных алгоритмов, доказаны в предположении верности этой гипотезы.

Теория Янга — Миллса


Уравнения квантовой физики описывают мир элементарных частиц. Физики Янг и Миллс, обнаружив связь между геометрией и физикой элементарных частиц, написали свои уравнения, объединяющие теории электромагнитного, слабого и сильного взаимодействий. Одно время теория Янга-Миллса рассматривалась лишь как математический изыск, не имеющий отношения к реальности. Однако, позже теория начала получать экспериментальные подтверждения, но в общем виде она все еще остается не решенной.

На основе теории Янга-Миллса построена стандартная модель физики элементарных частиц в рамках которой был предсказан и не так давно обнаружен нашумевший бозон Хиггса.

Существование и гладкость решений уравнений Навье — Стокса


Течение жидкостей, воздушные потоки, турбулентность. Эти, а также множество других явлений описываются уравнениями, известными как уравнения Навье — Стокса. Для некоторых частных случаев уже найдены решения, в которых как правило части уравнений отбрасываются как не влияющие на конечный результат, но в общем виде решения этих уравнений неизвестны, и при этом даже неизвестно, как их решать.

Гипотеза Бёрча — Свиннертон-Дайера


Для уравнения x2 + y2 = z2 в свое время еще Эвклид дал полное описание решений, но для более сложных уравнений поиск решений становится чрезвычайно трудным, достаточно вспомнить историю доказательства знаменитой теоремы Ферма, чтобы убедиться в этом.

Данная гипотеза связана с описанием алгебраических уравнений 3 степени — так называемых эллиптических кривых и по сути является единственным относительно простым общим способом вычисления ранга, одного из важнейших свойств эллиптических кривых.

В доказательстве теоремы Ферма эллиптические кривые заняли одно из важнейших мест. А в криптографии они образуют целый раздел имени себя, и на них основаны некоторые российские стандарты цифровой подписи.

Гипотеза Пуанкаре


Думаю если не все, то большинство точно о ней слышали. Чаще всего встречается, в том числе и на центральных СМИ, такая расшифровка как «резиновую ленту натянутую на сферу можно плавно стянуть в точку, а натянутую на бублик — нельзя». На самом деле эта формулировка справедлива для гипотезы Тёрстона, которая обобщает гипотезу Пуанкаре, и которую в действительности и доказал Перельман.

Частный случай гипотезы Пуанкаре говорит нам о том, что любое трехмерное многообразие без края (вселенная, например) подобно трехмерной сфере. А общий случай переводит это утверждение на объекты любой мерности. Стоит заметить, что бублик, точно так же как вселенная подобна сфере, подобен обычной кофейной кружке.

Заключение


В настоящее время математика ассоциируется с учеными, имеющими странный вид и говорящие о не менее странных вещах. Многие говорят о ее оторванности от реального мира. Многие люди как младшего, так и вполне сознательного возраста говорят, что математика ненужная наука, что после школы/института, она нигде не пригодилась в жизни.

Но на самом деле это не так — математика создавалась как механизм с помощью которого можно описать наш мир, и в частности многие наблюдаемые вещи. Она повсюду, в каждом доме. Как сказал В.О. Ключевский: «Не цветы виноваты, что слепой их не видит».

Наш мир далеко не так прост, как кажется, и математика в соответствии с этим тоже усложняется, совершенствуется, предоставляя все более твердую почву для более глубокого понимания существующей реальности.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 65
  • +7
    Мне Гипотеза Коллатза очень нравится.

    imgs.xkcd.com/comics/collatz_conjecture.png
    • +1
      Согласен, интересная
      • +5
        xkcd — это комикс ради title-атрибутов объекта img, а вы этот title как раз убили прямой ссылкой на картинку.
    • +26
      Как говорится во фразе, приписываемой Эйнштейну, «объяснение должно быть максимально простым, но не проще».
      • 0
        Полностью согласен, я старался не потерять суть, за максимальным упрощением. Буду очень рад, если Вы укажете мне, где это не совсем получилось.
        • +3
          Спасибо Вам за статью. Как по мне, так всё прекрасно получилось, даже для такого далекого человека как я.
          • 0
            Вам спасибо за приятные слова.
          • +29
            Давайте по порядку:
            1) N =? NP. Не очень понятно, что такое полиномиальное время, но здешняя аудитория более-менее поймет.
            Итог: проблема поставлена, объяснение корректно.
            2) Гипотеза Ходжа. Непонятно, что за объекты, как собираются и т.п. Понятно, что описать циклы Ходжа популярно непросто, но вы же начали зачем-то это писать.
            Итог: проблема не поставлена, написано что-то, не имеющее отношение к проблеме.
            3) Гипотеза Римана. Ну, с натяжкой можно сказать, что что-то описано. Непонятно, какие именно свойства распределений, не сказано, в чем, собственно, состоит гипотеза. Кстати, распределение простых чисел — всего лишь одно из следствий (хотя и самое важное).
            Итог: проблема не поставлена.
            4) Теория Янга-Милса. Уравнений, описывающих поведение частиц куча. Что именно описывает теория Янга-Милса, У вас не сказано. Что значит, справедливы ли уравнения? Если это про отношение к реальной физике, то никто никогда не доказал, что хоть одно уравнение имеет отношение к физике. Текущие онтологические теории говорят, что это невозможно.
            Итог: проблема не поставлена.
            5) Уравнения Навье-Стокса. Из текста можно подумать, что проблема в поиске решений в общем виде, хотя здесь вас спас заголовок. В нем вся формулировка и заключена. Текст к проблеме отношения не имеет. К сожалению, вряд ли все поймут, в чем именно там проблема.
            Итог: проблема поставлена, описание корректно (если говорить только про заголовок).
            6) Гипотеза Берча-Свиннертон-Дайера. Тут можно вообще ничего не говорить, кроме того, что x^2+y^2=z^2 не задает эллиптическую кривую. Более того, это вообще не кривая, а поверхность.
            Итог: проблема не поставлена, есть существенные ошибки в описании.
            7) Гипотеза Пуанкаре. Ни сферу ни бублик нельзя стянуть в точку. Вообщем, та же самая проблема, что и для 6.
            Итог: проблема не поставлена, есть существенные ошибки в описании.

            Интегрально получается следующее: С натяжкой можно утверждать, что вы как-то описали полторы проблемы. P-NP и Навье-Стокса. Остальные не описаны и есть существенные ошибки. То есть, ваша цель объяснить, в чем заключаются эти задачи, не достигнута.
            • +3
              Да, всё так.
              • +1
                Спасибо Вам большое, за подробное описание, постараюсь исправить все замечания
              • +1
                При описании гипотезы Ходжа суть потеряна (но наверное гипотезу Ходжа и невозможно объяснить человеку, незнакомому с алгебраическими многообразиями и когомологиями).
            • +11
              Также существуют NP-задачи, для которых если и придуманы алгоритмы решения, то выполняются они очень-очень долго.
              Суть класса NP не в этом. NP-задача — это та, решение которой можно быстро проверить. Про сложность нахождения этого решения ничего не говорится. И вот равенство P==NP будет означать, что задачу, решение которой можно быстро проверить, можно и быстро решить. Быстро — это за полиномиальное время.
              • 0
                Спасибо большое, поправил
              • +2
                Вот интересный канал про математику для не математиков www.youtube.com/user/numberphile
                • +4
                  Гипотеза римана, ее история и современное положение дел хорошо описана в научпоп книге Простая одержимость. кажется она есть и на флибусте/либрусеке.
                  • +1
                    Да, отличная книга, до такого стиля изложения мне еще расти и расти…
                  • +2
                    В параграфе о гипотезе Римана вы говорите о невозможности функции распределения простых чисел. Можно ли ссылку на доказательство невозможности?
                    • +2
                      Да, спасибо Вам, двоякость закралась. Конечно же такого доказательства нет, я имел в виду, что такую закономерность пока просто не нашли.
                    • +1
                      Как-то вычитал о том, что развитие современной физики, в особенности, касательно «теории всего», очень сильно упирается в низкую скорость развития математики, как науки. Потому что, очень многие вещи не представляется возможным проверить экспериментально. В то время как усиление мат.аппарата, позволило бы решить часть насущных вопросов, как говориться, «не вставая с дивана». Интересно, насколько эта мысль верна?
                      • 0
                        По моему мнению абсолютно верна, математика — это отражение реальности, очевидно, что то, что верно в математике, будет верно и в реальности. К сожалению даже сейчас часто эспериментальные методы обгоняют аналитические. То есть сначала мы видим — а потом проверяем теории и описываем в уравнениях, а ведь многие вещи проверить очень сложно, а то и вовсе невозможно, при современном развитии.
                        • +11
                          Математика — это не отражение реальности.
                          Математика — это способ вывести из системы аксиом утверждение, построив непротиворечивую систему.
                          Например, существует как евклидова геометрия, так и неевклидовы — каждая со своими аксиомами и выводами.
                          А насколько наш реальный мир удовлетворяет той или иной системе аксиом — это уже физика :)
                          • +4
                            «это способ вывести из системы аксиом утверждение, построив непротиворечивую систему» — это только один из этапов развития математики, как и аксиоматика теории множеств, на которой сейчас всё строится. До появления системы аксиом, теорем и логических выводов математика была другой. Возможно, вскоре она перерастёт эту логику, и снова изменится. Например, для того, чтобы оставаться отражением реальности, понимание которой перестанет описываться современной математикой.
                            • 0
                              Математика — это язык. Любой язык — отражение реальности. Вот например уравнения Навье-Стокса — это модель движения жидкости. Модель — это значит она может что-то предсказывать. Можно это же и без математики сделать, словами описать — частица будет двигаться так-то, если то-то и то-то. Тоже будет отражением реальности.

                              Какой язык — такую часть реальности он и отражает (это к вопросу о геометриях). Вас же не смущает 5 объектов + 5 объектов = 10 объектов? Или 5 + 5 = 12 (это ведь тоже верно может быть)? Это одна реальность, или две? А может быть три (две где верно, и одна общая для них), или может их еще больше? Логика (и основания математики) — это одно из возможных обобщений подобного рода вопросов.

                              Для практических математиков, математика как инструмент — это способ предсказания без испытаний (и без отражения реальности в моделях это было бы невозможно). И этим она и отличается от физики. Физика экспериментирует физическими объектами, математика экспериментирует свойствами объектов. Банально, чтобы узнать за сколько велосипедист доедет из точки А в точку B, физик отправит велосипедиста проверить, математик — разделит расстояние на скорость. В этом и разница (я не говорю что математика лучше или хуже), и тот и другой эксперименты нужны, потому как физики делают эксперименты когда нет модели или какие-то параметры неизвестны (неизвестно расстояние), математические эксперименты нужны когда нет нужды в физических (нет велосипедиста).
                              • 0
                                Под «реальностью» стоит понимать «то что существует, видимо и осязаемо». Бутылку Клейна вы не сможете создать «в реальности», а комплексное число яблок не сможете съесть, но описать с точки зрения математики то и другое возможно. Когда вы говорите «отражение реальности» — надо понимать, что вот отражение в зеркале есть, а самого предмета по эту сторону зеркала может не быть. Можно поискать — авось что-то найдется похожее по своим свойствам. А может и не найтись.

                                «5 + 5 = 12» — это вообще лишь запись. Например, в восьмеричной системе так оно и будет правильно.
                                • 0
                                  Записи 5 + 5 = 12 и 5 + 5 = 10 отличаются, правильно, системами, только вот разным системам могут соответствовать разные вычислительные устройства. И много чего разного. Математика изучает системы не всегда для того, чтобы применять их только в физике. А например для того, чтобы применять их в других областях жизни. Хотя алгебраические группы, системы по типу приведенной, используются и в физике (и далеко не всегда для вычислительных устройств).

                                  Под «реальностью» стоит понимать «то что существует, видимо и осязаемо»

                                  Вопрос — откуда в языках берутся новые слова, зачем и как они обретают смысл?
                                  Могу порекомендовать ознакомиться с этим и например вот этим (второе спорно и старо, ряд подходов тем не менее там многое объясняет).

                                  Комплексные числа и бутылка Клейна — это объекты, которые отражают взаимосвязи между объектами или свойствами (иногда умозрительных, иногда — нет) объектов. Если «реальность» для вас состоит только из физических объектов и их физических свойств, то дальше дискуссию продолжать смысла не вижу. Мы тут по разные стороны (онтологически) и консенсус можно искать в библиотеке, если у кого-то есть желание (у меня нет, вряд ли вы мне что-то новое в математике откроете).

                                  Просто скажу, что математика не вещь в себе, не способ вывести из утверждения А эквивалентное утверждение B (это всего лишь математический метод, один из), а способ решения жизненных задач. Описанный вами подход критиковал академик Арнольд, называя его левополушарным, и сокрушался по поводу того, что он очень распространен. Я стою на позиции, высказанной по ссылке:
                                  Основной целью математического образования должно быть воспитание умения математически исследовать явления реального мира… Искусство составлять и исследовать мягкие математические модели является важнейшей составной частью этого умения.
                                  • 0
                                    Мы, говоря о математике, упираемся рогами, как философы-гуманитарии и спорим о значениях слов :)
                                    Вы сказали «математика — способ решения жизненных задач», а я «математика — способ решения задач, не только жизненных приведением их к уже решенным либо придумывая новую аксиоматику». Давайте каждый из нас будет любить свою математику. Peace?
                                    • 0
                                      Вероятно, мысль свою я не совсем донес. Я не могу запретить любить, чем бы что-то ни было для кого угодно :) Peace.
                          • +7
                            А по моему совершенно неверна. Уже более ста лет физики открывают что-то новое и неизменно обнаруживают что математика к этому случаю уже давным давно готова, просто никто ее раньше не использовал. Это похоже на сарай доверху заваленный инструментами на все случаи жизни, надо только знать какой именно нужен в данный момент. СТО один из примеров, наверное есть и более ранние.

                            • +2
                              Подписываюсь под вашими словами. В математике очень много областей, в которой царит такой уровень абстракции, за что многие и начали называть математику оторванной от жизни. Взять хотя бы abc-гипотезу, о которой весьма интересно уже писалось на хабре.
                              • +3
                                Да, в 20 веке в большинстве случаев для новых физических теорий уже существовал готовый математический аппарат.
                                Но и Ньютону, и Лапласу, и Хевисайду (конец 19 века) приходилось самим изобретать новые математические методы.
                                А в 21 веке физика опять упёрлась в отсутствие математики: M-теория (дальнейшее развитие теории струн) существует, а адекватной математики для неё нет.
                                • +1
                                  Да, только многообразия Калау-Якоби придумали сто лет назад, не говоря уже о бета-функциях. Насколько я знаю, физики не могут составить точные уравнения М-таории, так что рановато предьявлять претензии к математикам.
                            • –26
                              Мое мнение: математику сильно переоценивают в физике. У природы нет никакой математики, это исключительно продукт человеческого разума. Нет никаких оснований утверждать, что математические построения и экстраполяции соответствуют реальному положению дел. Природу нужно наблюдать, ставить эксперименты, анализировать результаты, проверять гипотезы. Все это можно делать при минимуме математики, достаточно арифметики и геометрии.
                              • +5
                                Можно конечно волновую функцию и уравнение Шредингера без комплексных чисел записать… но зачем?
                                • +1
                                  Например, для формулировки уравнений квантовой гравитации: вдруг именно комплексные числа и волновые функции — фундаментальное заблуждение, которое мешает идти дальше.
                                • +12
                                  Алхимик детектид:)
                                  • +3
                                    Вполне возможно, что математикой природа не объясняется. Просто пока математика — наиболее простой аппарат, позволяющий описывать и предсказывать природные явления. Почему сейчас самыми подходящими и точными инструментами оказались тензорные уравнения и комплекснозначные волновые функции, не очень важно: наверное, сейчас такой этап развития. Может быть, когда-нибудь доберёмся и до уровня клеточного автомата.
                                    • +1
                                      Обязательно доберемся
                                      • 0
                                        Вполне возможно, что природа — это математика в чистом виде, а мы просто познаём её постепенно.
                                      • +10
                                        Всё верно. Века для 15ого.
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                          • 0
                                            С петабайтами данных я ничего не буду делать потому что они не нужны. Как не нужны они были Ньютону, Фарадею (который, кстати, в математике был не в зуб ногой) и др.
                                            Вы сами сказали, что математика — это абстракция человеческого разума. Это означает, что математические построения — не есть реальный мир.
                                            Наблюдение -> гипотеза -> эксперимент -> анализ результатов -> принятие/непринятие закономерности — вот путь тру-физиков :)
                                            • +1
                                              Но «закономерность» вам придётся формулировать в математических терминах. В реальном мире дальше, чем «если Луна в знаке Козерога, то завтра вам упадёт на голову кирпич» продвинуться трудно. Нужны абстракции, порой выходящие за пределы наблюдаемых явлений, а это и есть математика.
                                          • +3
                                            Рекомендую почитать Фейнмана «Характер физических законов». Особенно вторую лекцию «Связь математики с физикой». Оттуда, в частности:
                                            Подводя итоги, я хочу воспользоваться словами Джинса, который сказал, что «Великий Архитектор, по-видимому, был математиком». Тем, кто не знает математики, трудно постичь подлинную глубокую, красоту природы. Сноу говорил о двух культурах. Я думаю, что разница между этими культурами сводится к разнице между людьми, которые понимают, и людьми, которые не понимают математики в той мере, в какой это необходимо, чтобы вполне оценить природу.

                                            Жаль, конечно, что тут нужна математика, потому что многим людям она дается трудно. Говорят — не знаю, правда ли это — что один царь, которого Евклид пытался обучить геометрии, стал жаловаться на трудности. Евклид ответил: «Нет царского пути к геометрии». И его действительно нет. Физику нельзя перевести ни на какой другой язык. И если вы хотите узнать Природу, оценить ее красоту, то нужно понимать язык, на котором она разговаривает.

                                            Хочу заметить, что при всём этом Фейнман как раз славился тем, что мог на пальцах объяснить сложнейшие разделы физики неспециалистам.
                                            • +8
                                              http://xkcd.ru/435/

                                              Хотя сам склоняюсь ко мнению, что математика — это язык описания науки.
                                              • +1
                                                GPS.
                                                • 0
                                                  Ну, что ж начните с гугления такого понятия, как «золотое сечение», затем можно обратить внимание на фрактальную геометрию.
                                                  • –1
                                                    Во-первых, золотое сечение — это простая арифметика, во-вторых это всего лишь арифметическое описание того что мы и так можем видеть своими глазами. В третьих — какое практическое и прогностическое значение имеет арфиметическое описание золотого сечения? Оно позволяет воссоздать строение вселенной или микромира? Математика — это язык, который человек придумал для описания реального мира. Но это не означает, что конструкции и экстраполяции созданные в рамках математики соответствуют реальности.
                                                    • +2
                                                      Зачастую в ВУЗ'ах в курсе КСЕ даже есть отдельная лекция на тему золотого сечения в природе. Можно еще привести в пример «принцип цикады».
                                                • 0
                                                  Если вы начали объяснять на пальцах, что из себя представляют P и NP задачи, то объясните сначала самые основы. А самые основы — это почему задачи называются P и NP. Что это за аббревиатуры?

                                                  А то получается как в химии, есть оболочки s, p, d, f… А почему они так обозначены — никто не объясняет.
                                                  • 0
                                                    привел расшифровку аббревиатур
                                                • +1
                                                  Пожалуйста, указывайте примеры применения. Каким бы простым не было объяснение — понятнее не становится.

                                                  Так, например, на вере в P ≠ NP держится вся современная асимметричная криптография, на так называемых функциях с «потайным входом», которые быстро решаются со некоторым знанием (ключ) и не решаются никак, кроме как перебором — без него. Пример: ЭЦП. Зная ключ, можно сделать электронную подпись документа. Электронная подпись может быть проверена любым человеком легко и быстро. Сделать такую же подпись, не зная ключа — практически невозможно (только полный перебор).

                                                  Если внезапно окажется, что P = NP, то криптографии придётся плохо.
                                                  • +3
                                                    Если внезапно окажется, что P = NP, то криптографии придётся плохо.

                                                    Нет. Это всего лишь означает, что алгоритм существует. Из самого факта существования полиномиального алгоритма у Вас магическим образом не появится сам алгоритм. Может он вообще будет работать за O(N^9999999999)? Так что не надо тут пугать людей, всё не так плохо :) Да и более того, что многие алгоритмы не принадлежат классу P — это всего лишь предположение, могут, например, отыскать в будущем алгоритм за полином и тогда всё поломается и без доказательства P = NP.
                                                  • +3
                                                    Надеюсь, что это нечто вроде Оглавления. И по каждой из проблем будет свой топик.
                                                    • 0
                                                      «существует ли для всех NP-задач такой алгоритм, который позволял бы решать такие задачи точно так же как и проверять за достаточно быстрое время? Для каких-то существует, а для каких-то его так и не нашли. „

                                                      Разве может быть, что для каких-то существует? Принадлежность к классу NP же вроде доказывается сведением к другой NP-полной задаче, и решение одной означает решение всех. По крайней мере, так запомнил из лекций, поправьте, если ошибаюсь.
                                                      • 0
                                                        Точнее, доказывается не обязательно так (для одной-то всё равно нужно доказать решаемость за полиномиальное время на недетерминированной машине), но все задачи друг к другу сводятся.
                                                        • +1
                                                          Сводятся все-таки за полиномиальное время, а не мгновенно.
                                                          • 0
                                                            Ну, если мы нашли алгоритм решения задачи Б за полиномиальное время, и есть алгоритм построения на его основе решения задачи А за полиномиальное время, то время решения задачи А осталось полиномиальным.
                                                            • 0
                                                              Именно. Поэтому я не понимаю, где вы усмотрели противоречие. Если классы P и NP совпадают, то любую NP задачу можно решить за полиномиальное время. Преобразовать решение любой NP-complete задачи можно в решение любой NP (и, соответственно, P) задачи за тоже полиномиальное время. Никаких проблем не возникает.
                                                      • 0
                                                        Про гипотезу Пуанкаре вообще ничего не понятно.

                                                        Во-первых, вы сказали, что Перельман доказал гипотезу Тёрстона, но как соотносятся между собой две эти гипотезы, вы не объяснили. Гипотеза Тёрстона частный случай гипотезы Пуанкаре? Или наоборот?

                                                        Во-вторых, непонятен смысл слов «стянуть» и «растянуть». Что это значит? Почему сферу можно стянуть в точку, а бублик нельзя? Ваше «объяснение» только ещё больше всё запутывает.
                                                        • +1
                                                          Ну так это вопрос компромисса. Можно давать строже формулировки, можно даже приводить наводящие леммы + доказывать теоремы (уж так-то точно всё будет понятно), но тогда это уже с трудом назовешь «объяснение на пальцах». Статья-то для нематематиков.
                                                          • 0
                                                            Я не говорю о том, чтобы приводить какие-то леммы или доказываь теоремы. Но вот этот раздел как раз для нематематиков совершенно не будет понятен. Да что уж там говорить, я и сам из объяснения ничего не понял, хотя математику знаю не сказать, что уж совсем плохо :)

                                                            Опять же, про соотношение двух гипотез — Пуанкаре и Тёрстона — как читатели должны догадаться? И почему бублик нельзя стянуть в точку? Взяли и уменьшили радиусы внешней и внутренней окружностей до нуля — вот вам и стянули в точку. Или же под «стягивать» подразумевается нечто иное? Правила этого стяжения простому читателю непонятны.
                                                            • 0
                                                              Согласен с Вами, про соотношение гипотез важное упущение, поправил, про стягивание надо подумать как расписать это на пальцах
                                                              • 0
                                                                Непрерывная деформация с сохранением связности, где связность — это количество дыр.

                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.