2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Что за задача Пи против нПи?
Сообщение06.12.2013, 18:27 


06/12/13
5
В сериале "Элементарно" говорится об этом, что это такое? Google не помог(
Я школьник и поэтому прощу объяснить проще.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 18:33 
Заслуженный участник


27/06/08
4058
Волгоград
grim2d в сообщении #797000 писал(а):
В сериале "Элементарно" говорится об этом, что это такое? Google не помог(
Я школьник и поэтому прощу объяснить проще.
Переведите на английский.
Примерно так: P vs NP
Или даже так: P=NP
И снова обратитесь за помощью к Google

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 18:42 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Это в сериале "числа" в первых эпизодах. Собственно, к числу $\pi$ не имеет отношения. Происходит от слова полиномиальный. В общем, о сложных алгоритмах.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 18:58 
Заслуженный участник
Аватара пользователя


06/10/08
6422
grim2d в сообщении #797000 писал(а):
Я школьник и поэтому прощу объяснить проще.
Попробую объясить.

Вот представьте себе, что у нас есть уравнение с большим количеством переменных, но по условию они могут принимать значение $0$ или $1$. Тогда для того, чтобы узнать, является ли какой-то набор значений переменных решением, можно просто подставить их и проверить. Это делается быстро. А вот найти какое-нибудь решение значительно сложнее: самый простой способ - это просто перебирать значения переменных и проверять. Но если переменных много, то возможных подстановок очень много (1 переменная - 2 значения, 2 переменных - 4 значения, 3 - 8, 4 - 16 и т.д.), поэтому нахождение решений получается очень медленное.

Так вот, очень грубо говоря, проблема $\mathbf{P}\neq \mathbf{NP}$ состоит в том, чтобы либо доказать, что найти решения нельзя быстро, либо найти быстрый способ. Большинство специалистов считает, что, скорее всего, быстрого способа нет.

$\mathbf{P}\neq \mathbf{NP}$ связана не только с этой задачей. Очень многие задачи можно решать перебором, и некоторые из них эквивалентны решению $0-1$-уравнений, то есть если мы найдем способ быстро решать уравнения, мы сможем быстро решать другие переборные задачи, и наоборот.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:26 
Заслуженный участник


04/05/09
4582
Чуть подробнее.

Сначала о полиномиальности - если время на некоторую обработку данных переменного размера зависит от этого размера, как полином какой-то степени - квадрат, или куб, например, то сложность этой обработки называют полиномиальной. Может быть и гораздо медленнее, например, экспоненциальное время, когда оно равно, к примеру - $2^N$, где $N$ - размер данных. (Есть и ещё хуже варианты, но это уже детали.)

Так вот, все задачи, для решения которых есть полиномиальный алгоритм решения относятся к классу $\mathbf{P}$ - polynomial. Примеры таких задач - сортировка, решение системы линейных уравнений, умножение больших чисел.

Есть ещё класс задач, для которых такого алгоритма не известно, но есть хотя бы возможность за полиномиальное время проверить, что решение является именно решением, т.е. если мы каким либо образом быстро угадаем решение, то значит решим задачу за полиномиальное время, т.к. проверка полиномиальна. Такой класс задач назвали $\mathbf{NP}$ - non-determenistic polynomial - негарантированно полиномиальные. Пример такой задачи привёл Xaositect, ещё один пример - разложение на множители большого числа.

Итак, если для таких задач удастся придумать быстрый угадыватель, то эти задачи также окажутся полиномиальными, т.е. окажется $\mathbf{NP}= \mathbf{P}$. А если не удастся, то $\mathbf{NP}\neq \mathbf{P}$.
Вот это и есть главный вопрос теории алгоритмов.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:36 
Заслуженный участник


23/07/08
10626
Crna Gora
Правильно ли я понял, что есть какая-то такая $\mathbf{NP}$-задача, что если для нее мы найдем полиномиальный алгоритм решения, то и все другие $\mathbf{NP}$-задачи сразу станет возможным тоже решать за полиномиальное время?

Или, может быть, для остальных $\mathbf{NP}$-задач лишь станет известно, что такие алгоритмы существуют, только их ещё найти надо?

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:39 
Аватара пользователя


03/10/13
449
svv в сообщении #797043 писал(а):
Правильно ли я понял, что есть какая-то такая $\mathbf{NP}$-задача, что если для нее мы найдем полиномиальный алгоритм решения, то и все другие $\mathbf{NP}$-задачи сразу станет возможным тоже решать за полиномиальное время?

Это верно лишь для $\mathbf{NP}$- полных.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:45 
Заслуженный участник
Аватара пользователя


06/10/08
6422
svv в сообщении #797043 писал(а):
Правильно ли я понял, что есть какая-то такая $\mathbf{NP}$-задача, что если для нее мы найдем полиномиальный алгоритм решения, то и все другие $\mathbf{NP}$-задачи сразу станет возможным тоже решать за полиномиальное время?
Если найдется полиномиальный алгоритм для одной $\mathbf{NP}$-полной задачи, то для всех задач из $\mathbf{NP}$ алгоритм сразу строится по сводимости или по проверяющей машине (правда, степень при $n$ может сильно увеличиться, но все равно все будет полиномиально)

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:48 
Заслуженный участник


04/05/09
4582
Есть группа $\mathbf{NP}$-задач, к которым можно свести все $\mathbf{NP}$-задачи - $\mathbf{NP-complete}$. Если для какой-то из них будет найдено полиномиальное решение, то это докажет, что $\mathbf{P}=\mathbf{NP}$. И наоборот, если докажут, что $\mathbf{P}\neq\mathbf{NP}$, то значит для $\mathbf{NP-complete}$ задач полиномиального решения нет.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:51 
Заслуженный участник


23/07/08
10626
Crna Gora
А, интересно, встречались уже задачи, про которые сначала думали, что они из класса $\mathbf{NP}$ (не полные), а потом для них неожиданно находился полиномиальный алгоритм?

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:54 
Аватара пользователя


03/10/13
449
svv в сообщении #797053 писал(а):
А, интересно, встречались уже задачи, про которые сначала думали, что они из класса $\mathbf{NP}$ (не полные), а потом для них неожиданно находился полиномиальный алгоритм?

Если для задачи существует полиномиальный алгоритм, то она лежит в классе $\mathbf{NP}$.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 19:58 
Заслуженный участник


23/07/08
10626
Crna Gora
Я имел в виду, были ли задачи, для которых позже оказалось, что их не только проверять, но и решать можно за полиномиальное время, и они на самом деле принадлежат классу $\mathbf{P}$?

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 20:01 
Заслуженный участник


04/05/09
4582
Проверка простоты числа. Сначала думали что оно вообще не в $\mathbf{NP}$, потом нашли сертификат простоты, который можно проверить полиномиально, т.е. оказалось в $\mathbf{NP}$, а не очень давно нашли и полностью полиномиальный алгоритм.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 20:04 
Заслуженный участник


23/07/08
10626
Crna Gora
Спасибо. Тогда и надежда на $\mathbf{P}=\mathbf{NP}$ есть.

 Профиль  
                  
 
 Re: Что за задача Пи против нПи?
Сообщение06.12.2013, 20:25 
Заслуженный участник


27/06/08
4058
Волгоград
svv в сообщении #797058 писал(а):
Спасибо. Тогда и надежда на $\mathbf{P}=\mathbf{NP}$ есть.
Надежда, может, и есть. А вот алгоритма решения NP-полных задач за полиномиальное время - нет :wink:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group