Решена вторая задача миллениума ?

[NT]

Millennium Prize Problems

Хотя потом сообразил, что Таланова другой список интересует.

[Swetlana]

Source of the post
задачу Пуанкаре и решение её Пелерманом. ... Просто интересуюсь этим по инерции...

а фамилию Перельман пишите на автопилоте

[Sonic86]

Странно, в Википедии вроде описания нет.
А вообще, уже Svetlana Fainshtein описала проблему кратко.
Что такое "машина Тьюринга" знаете? Если нет, то объяснять не буду - длинно очень.

[folk]

Машина Тьюринга это (неформально) конечный автомат с алфавитом состояний A, который при переходе из состояния в состояние может
- написать символ алфавита A на всунутой в него бесконечной ленте
- сдвинуть ленту влево или вправо
- считать написанный символ и в зависимости от него перейти в другое состояние
- остановиться

Бесконечная лента = бесконечная память поэтому может реализовать любой алгоритм.

[s2009_33]

Source of the post
Странно, в Википедии вроде описания нет.
А вообще, уже Svetlana Fainshtein описала проблему кратко.

На математическом языке. А неплохо было бы объяснить на общеупотребимом. Вот например: упругое рассеяние нейтронов можно сравнить с ударами биллиардных шариков.

[Swetlana]

Предлагаю модераторам компутер сайенс сделать тему с названием
"Что вы всегда хотели узнать о сексе о NP-полноте, но боялись спросить", не всё же об антивирусниках писать

У меня есть кое-какие мои лекции, но они имеют очевидные недостатки:
1. формулы набраны в ворде, переводить всё в tex не подъёмно
2. лекции предназначены для программистов, а не для прикладных математиков, поэтому имеют скорее обзорный характер, без углубления в интересные специальные вопросы
3. мои собственные знания крайне ограничены и устарели, вместе с книгой Гэри-Джонсона

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

[s2009_33]

Как бы это сказать..Интересуют не лекции (хотя и они тоже). А грамотное объяснение сути теоремы, размером несколько строк. Но на общедоступном языке.

[peregoudov]

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

Вы с классификацией двумерных многообразий знакомы? Что-то не могу найти в вики... Можете почитать статью "Многообразия", особенно раздел "Классификация" (в английской версии есть картинки ). В двух словах: все двумерные многообразия подобны сфере с произвольным числом "ручек" (либо вовсе без "ручек"). "Ручка" --- это когда вы из сферы вырезали два круга и склеили их края друг с другом. Например, сфера с одной ручкой --- это тор. Односвязна только сфера. Все остальные можно замкнутым путем "взять за ручку", такой путь в точку стянуть не получится.

Это что касается ориентируемых многообразий (у таких многообразий есть "лицевая" и "обратная" стороны). А для неориентированных есть еще возможность вырезать сколько-то кругов и заклеить их листами Мебиуса. Например, сфера с двумя вклеенными листами Мебиуса --- бутылка Клейна.

P. S. Если мне не изменяет память, по машине Тьюринга и NP-задачам я что-то доступное читал у Пенроуза в "Новом уме короля". По крайней мере из всей книги мне этот раздел понравился, в отличие от других, по физике. Может оттого, что я в этом профан...

[Swetlana]

Source of the post
Как бы это сказать..Интересуют не лекции (хотя и они тоже). А грамотное объяснение сути теоремы, размером несколько строк. Но на общедоступном языке.

вас не интересуют, а других могут заинтересовать
сути какой теоремы? которую никто не доказал? пока говорить не о чем

суть проблемы следующая
1. Все задачи классифицируются по вычислительной сложности наилучшего (самого быстрого) алгоритма, известного для ея решения.
Вычислительная сложность алгоритма меряется по "самому плохому случаю" и выражается как функция от размерности исходных данных. Такая сложность называется асимптотической и показывает, как быстро растёт время работы алгоритма при увеличении размерности входных данных.
Например, если сортируем массив алгоритмом "пузырёк", то число шагов этого алгоритма растёт пропорционально квадрату числа элементов массива.

2. Все задачи из класса P, которые решаются "эффективными" алгоритмами (эффективный = полиномиальный) давно решены. Эти алгоритмы нетрудно выучить, и ещё надо уметь делать постановки реальных задач так, чтобы можно было воспользоваться эффективными алгоритмами, это требует определённой квалификации и этому нигде не учат.

3. Есть так называемые NP-полные задачи, которые возникают на каждом шагу на производстве и в науке, конечно... на самом деле, чего не коснись - везде NP-полные задачи...
так вот, все точные алгоритмы, известные для решения NP-полных задач, экспоненциальные, то есть их можно решать точно только для малой размерности. Справедливости ради замечу, что псевдополиномиальными алгоритмами можно решать среднюю размерность.
Но в реальных NP-полных задачах обычно большая и сверхбольшая размерность, поэтому их приходится решать приближёнными (известна скорость сходимости к точному решению или известна оценка погрешности) или эвристическими алгоритмами (ничего не известно).

Поэтому надо
или доказать, что NP-полные задачи нельзя рещить за полиномиальное время и на этом успокоиться,

или для какой-то NP-полной задачи найти полиномиальный алгоритм. Поскольку NP-полные задачи между собой эквивалентны, в смысле полиномиальной сводимости, то все они будут решены за полиномиальное время и P=NP.

[Swetlana]

забыла упомянуть, NP-полные задачи в самой общей постановке - это задачи, которые требуют ответа да/нет (существует/не существует).
Например, заданы целые положительные числа и целое положительное число B, можно ли набрать число B, да или нет?

И часть NP-полных задач могут быть переформулированы как задачи оптимизации.
Например, задача "Сумма размеров" в оптимизационной постановке звучит так:
набрать заданное число B с помощью заданных слагаемых c минимальным отклонением.
Реальные задачи в основном задачи оптимизации, именно их решают приближёнными и эвристическими алгоритмами.
Задачи распознавания приближённо решать нельзя.