Распечатать запись Распечатать запись

Математические болезни: симптомы и примеры

Эх, и меня не миновало… Правда, в довольно легкой форме :-) Моя МБ — изоморфизм графов :-)

Есть математические навязчивые идеи. Они действуют подобно болезням, заставляя людей считать, что они должны решать какую-то математическую задачу. Возможно, проблема P=NP одна из них?

Что такое математические болезни (МБ)?

Во время сезонной эпидемии гриппа болеют многие. Я надеюсь, что вы либо не заболеете, или (если вам все же не повезло и вы заразились) перенесете болезнь достаточно легко.

Существует еще один “вирус’’, который поражает математиков, заставляя их пытаться решить определенные задачи. Эти задачи были названы “болезнями’’ — термином, придуманным великим математиком, специалистом по теории графов, Фрэнком Харари. Они включают в себя многие известные задачи теории графов, некоторые задачи из алгебры, некоторые — из теории чисел, некоторые — из теории сложности вычислений и т.д.

Симптомы гриппа хорошо известны, и я снова выражаю надежду, что вас на мучают лихорадка, озноб и боли. Однако симптомы математических болезней (МБ) гораздо менее изучены. Тем не менее имеются некоторые признаки, что дело в МБ.

1. Задача должна быть легко понимаема, чтобы быть МБ. Это не достаточно, но это требуется. Таким образом, гипотеза Ходжа никогда не будет болезнью. Трудно понять, о чем там идет речь.

2. Задача должна казаться доступной даже для любителя. Это ключевое требование. Когда вы впервые слышите о ней, ваша реакция должна быть такой: это не сделано? Задача должна казаться легкой.

3. Задача должна также неоднократно быть “решена’’, чтобы в самом деле быть МБ. Хорошая МБ обычно была “доказана’’ много раз, часто одним и тем же человеком. Если вы видите статью в arXiv.org со многими “обновлениями’’, это хороший знак, что данная задача МБ.

В отличие от реальных болезней, как лечить МБ, неизвестно. Даже решение задачи не будет пресекать попытки некоторых людей продолжить работу над ней. Если доказательство показывает, что что-то невозможно (как в ситуации с трисекцией угла) люди с МБ часто работают над тем, чтобы обойти это доказательство. Даже тогда, когда есть хорошее доказательство, люди с МБ могут продолжать пытаться найти простое доказательство. Например, доказательство Эндрю Уайлса Последней теоремы Ферма не остановило некоторых от попыток найти “по-настоящему чудесное доказательство’’ Пьера де Ферма.

Некоторые математические болезни

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

Изоморфизм графов. Это классический вопрос о том, существует ли алгоритм, с помощью которого за полиномиальное время можно установить, изоморфны или нет два данные графа. Задача кажется очень простой, но она до сих пор сопротивлялся всем попыткам решения.

Есть несколько красивых частных результатов: например, работа Ласло Бабаи, Ю. Григорьева, и Дэвида Маунта, описывающая случай, когда у графов ограничены кратности собственных чисел. Решение Евгения Лукса для случая ограниченной степени является также важным.

• Изоморфизм групп. Эта задача не так известна, как задача об изоморфизме графов. Вопрос состоит в том, изоморфны ли две конечные группы размером N? Главное то, что эти группы представлены таблицами умножения. Наиболее известным результатом является то, что изоморфизм может быть установлен за время n^{\log n +O (1)}. Это довольно простой результат, основанный на том, что группы всегда имеют множество образующих мощности не больше \log n.

• Перестраивание графа. Эта известная задача принадлежит Станиславу Уламу. Гипотеза состоит в том, что подграфы графа с удаленной вершиной определяют граф с точностью до изоморфизма, при условии, что у графа есть по крайней мере 3 вершины. Это одна из самых известных задач теории графов, она является одной из первых болезней, о которых говорил Харари.

• Проблема якобиана. Это известная задача о том, когда полиномиальное отображение имеет обратное. Предположим, что мы рассматриваем отображение, которое паре комплексных чисел (x,y) сопоставляет пару (p(x,y),q(x,y)), где p(x,y) и q(x,y) — целочисленные полиномы. Гипотеза состоит в том, что отображение обратимо тогда и только тогда, когда отображение локально обратимо. Причина того, что проблему называют гипотезой якобиана, состоит в том, что отображение локально обратимо, если и только если определитель матрицы

\left(\begin{array}{cc}<br />
p_x(x,y)&q_x(x,y)\\<br />
p_y(x,y)&q_y(x,y)<br />
\end{array}\right)
является ненулевой константой. Обратите внимание, здесь p_x(x,y) — частная производная многочлена p(x,y) по x. Матрица, приведенная выше, называется якобианом отображения.

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

• {\bf P = NP}. Вы все знаете эту проблему. Имеется большой список попыток решить эту проблему, свершавшихся на протяжении многих лет.

Вы можете добавлять свои МБ, все это довольно забавно :-)

Источник: https://rjlipton.wordpress.com/2009/11/04/on-mathematical-diseases/

Комментариев: 4

  1. 1 Евгений:

    Да, забавно…
    У меня тоже что-то было, но это относилось к годам учёбы…
    п.с.
    А для рубрики “Развлекалочки”- “альтернативная” теория вероятности, )))
    увидел тут случайно:
    http://www.livejournal.com/magazine/603979.html

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Спасибо, интересно :-)

    [Ответить]

  2. 2 Heart-shaped glasses:

    Гипотеза Коллатца подойдёт? :D

    [Ответить]

    Елизавета Александровна Калинина Reply:

    Ага, это хорошая МБ :-)

    [Ответить]

Оставьте свой отзыв

Добавить изображение