7
3

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

задан 26 Мар '14 18:22

изменен 27 Мар '14 0:23

Deleted's gravatar image


126

Вот ещё немного по теме из соседнего подсайта: hashcode.ru/questions/271063/

(27 Мар '14 15:10) VladD
10|600 символов нужно символов осталось
3

Об этом довольно много написано, в том числе есть и популярные изложения. Но, чтобы не искать ссылок, я попробую рассказать, в чём состоит суть этой проблемы. Рассмотрим такую задачу. Дан граф с $%n$% вершинами. Будем считать, что $%n$% достаточно велико (например, порядка 100 или больше). Граф этот задан "машинно", с помощью матрицы, то есть таблицы $%n\times n$%. Вершины занумерованы, а в таблице на пересечении $%i$%-й строки и $%j$%-го столбца стоит 1, если $%i$%-я вершина с $%j$%-й соединена ребром в графе, и 0 в противном случае. Располагая таблицей, такой граф можно нарисовать.

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

Можно предложить очень простой алгоритм, который перебирает все перестановки чисел от 1 до $%n$% и затем по таблице проверяет, будет ли такой порядок вершин задавать гамильтонов цикл. Скажем, если я перенумеровал вершины так: 7, 11, 2, ..., 55, то мне надо проверить, соединена ли 7-я вершина с 11-й, 11-я со 2-й, ..., 55-я с 7-й. Допустим, что где-то происходит "обрыв". Тогда эту перестановку "забраковываем", и смотрим следующую. Проверка одной перестановки занимает небольшое время (порядка $%n$% операций), но общее количество перестановок равно $%n!$%, поэтому оно огромно, и при больших значениях $%n$% такое число вариантов за реальное время перебрать невозможно. А пока все варианты мы не перебрали, не найдя при этом искомого цикла, мы не можем быть уверены в его отсутствии.

Таким образом, встаёт задача о том, можно ли предложить другой алгоритм, основанный на каком-то более "хитром" принципе, который позволяет решить задачу о наличии или отсутствии гамильтонова цикла за "приличное" время. Таковым считается число операций, не превышающее $%n^k$%, где $%k$% -- некоторая константа. Например, речь может идти о величине порядка $%n^3$% или $%n^4$%. Такая величина представляет собой полином от $%n$%, и в этих случаях говорят, что задача решается за полиномиальное время. Класс таких задач обозначается в теории буквой P.

Если какой-то алгоритм есть в наличии, но он решает задачу за время $%2^n$% (экспоненциальное), или за время $%n!$%, как было в рассмотренном примере, то считается, что эти значения слишком велики, и для практической реализации такие алгоритмы непригодны.

Теперь вернёмся к примеру задачи о гамильтоновом цикле и заметим следующее: если эта задача имеет положительное решение, то есть цикл существует, то его чисто теоретически можно предъявить. Проверка того, что он будет решением, занимает совсем небольшое время, "линейное" -- порядка $%n^k$% при $%k=1$%. Если такой цикл как-то угадан, или специально подобран, то после проверки мы имеем строгое доказательство того, что задача имеет положительное решение. Действие по предъявлению такого удачно подобранного цикла ничем не задано, не "детерминировано". Однако оно на чисто теоретическом уровне может быть осуществлено, если граф на самом деле гамильтонов. И в этом смысле получается, что при разрешении таких вот "недетерминированных" действий задача проверки решается за полиномиальное время, то есть "быстро". Этот класс задач принято обозначать в виде NP -- от слов "non-deterministic polynomial".

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

Выше был приведён пример одной конкретной задачи о гамильтоновом цикле. Она принадлежит классу NP (по причине того, что наличие цикла быстро проверяется). Принадлежит ли она классу P, на настоящий момент никто не знает. Если не принадлежит, то $%P\neq NP$%. А что если принадлежит? Это значит, что кто-то вдруг возьмёт и придумает "хитрый" и быстрый алгоритм решения, избегая "грубого" перебора огромного числа вариантов? Оказывается, в этом случае можно будет заключить, что $%P=NP$%. Дело в том, что за время, начиная с 70-х годов XX века, математиками был выделен большой класс задач, которые сводятся друг к другу в следующем смысле: если одна из таких задач (все они берутся из класса NP) может быть решена за полиномиальное время, то и все остальные задачи того же класса решаются алгоритмически за полиномиальное время. Такие задачи принято называть NP-полными. Ещё их называют "задачами максимальной переборной сложности". Они очень разнообразны и непохожи друг на друга, но если кто-то сумеет придумать решение для одной из них, то проблема будет "закрыта".

Многие математики (хотя и не все) склонны полагать, что ответ на вопрос отрицателен, то есть что $%P$% на самом деле не равно $%NP$%. Если это так, то доказать подобное утверждение очень сложно, поскольку надо анализировать все "мыслимые" алгоритмы и как-то доказывать, что ни один из них не годится. Это выглядит принципиально намного труднее, чем предъявление одного, пусть даже "изощрённого" алгоритма, который решает какую-то конкретную задачу.

Что касается вопроса, а какой области эта проблема относится, то можно сказать, что она возникла в Computer Science. В английском языке этот термин стандартен, но на русский его не перевести "буквально". Иногда говорят, что это "теоретическая информатика", но это совсем не программирование, и не клаассическая теория алгоритмов, в которой обычно спрашивается о том, существует ли алгоритм, решающий некую задачу, в принципе (пусть даже и "непрактичный"). Более узко, можно относить эту проблему к теории сложности вычислений (computational complexity). Это относительно новая область, не имеющая по своей проблематике прямой связи с численными методами и прочим.

ссылка

отвечен 26 Мар '14 19:25

@falcao: Огромное спасибо! С термином Computer Science я хорошо знаком, я так и предполагал. Хотя я не все понял, в силу своей неосведомленности (пока), мне очень интересно, сейчас буду читать и разбираться дальше, чтобы полностью понять, что Вы мне написали. А про статьи, Вы имели ввиду, на английском (на русском я даже близкого к Вашему ответу не находил)?

(26 Мар '14 19:49) kirill1771
2

@kirill1771: я старался писать так, чтобы всё было в принципе понятно, то есть какой-то "академической" манеры изложения пытался избегать. Если возникнут вопросы по ходу чтения, то я буду готов на них ответить.

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

(26 Мар '14 20:07) falcao

@falcao: я сейчас одну статейку нашел похожую на нормальную. А можте, пожалуйста, если не сложно дать названия книг (если вы помните), буду очень признателен. Да, Вы написали очень хорошо (не только, потому что все очень информативно и интересно расписано, но и простым языком, так сказать для чайников), просто мои знания пока мне не позволяют понять некоторые моменты (сейчас определю, что мне непонятно и спрошу в следующем комментарии).

(26 Мар '14 20:28) kirill1771

@falcao:я не имею четкого представления - 1) что такое полином? это обычный многочлен? 2)Что значит "детерминированный"? Прочитав еще несколько раз Ваш ответ (предварительно почитав кое-что) и поразмыслив, у меня все осатльные вопросы отпали. Опять хочу поблагодарить Вас за такое замечательное пояснение проблемы.

(26 Мар '14 20:52) kirill1771
2

@kirill1771: литературы по этому вопросу очень много и на русском и на английском, но здесь это скорее "минус", чем "плюс" в том смысле, что надо долго искать и отбирать. Кроме того, какое-то изложение может оказаться хорошим в одном смысле (всё строго, "научно", полно и т.п.), но не подходящим в другом плане (трудно вникать). Честно говоря, я поисковой работой заниматься не очень люблю -- мне проще самому написать. Если я за 5 минут ничего не нахожу, то обычно поиски прекращаю. Посмотрите это -- это популярного типа статья.

(26 Мар '14 20:56) falcao

@falcao: спасибо, не надо искать специально (тратить Ваше время), я имел ввиду, если Вы помните названия или знаете "по какому запросу" надо искать. Дайте, хотя бы что-то (любую книжку) я дальше от нее буду продолжать поиски.

(26 Мар '14 21:00) kirill1771
2

Полином и многочлен -- это синонимы. Здесь важно то, что $%n^3$% считается "быстро", а $%2^n$% -- "медленно". По поводу детерминированности: обычные алгоритмы работают по заданной программе, их поведение предопределено (детерминировано). Но можно рассмотреть более общую ситуацию, когда сделано нечто на уровне "счастливого угадывания". Скажем, надо разложить на множители число n. Я взял и написал два числа, взятых "наобум", перемножил их, и получил n. Это "недетерминированное" действие, одно из многих в принципе разрешённых. В тексте я просто разъяснил смысл аббревиатур.

(26 Мар '14 21:01) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,936

задан
26 Мар '14 18:22

показан
4301 раз

обновлен
27 Мар '14 15:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru