NP-полные задачи
От: GhostCoders Россия  
Дата: 21.06.10 08:42
Оценка:
Описание что такое NP-полные задачи из Википедии

Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.

Сводимость по Карпу из Википедии


как я понял, f — должна устанавливать взаимно-однозначное соответстие между L1 и L2?

не пойму, а что мешает использовать простую таблицу для такой функци?

например алфавит, {a,b,c}
Множество всех возможных слов — это бесконечное множество,
например,
"a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa" и так далее...

Допустим L1 = {"aa", "ab", "ac"}

функция f такая (задана при помощи таблицы):
вход выход
"aa" -> "ba"
"ab" -> "bb"
"ac" -> "bc"

так как функция задана при помощи таблицы, то ее вычисление занимает 1 шаг.

или еще лучше:
"Задачей распознавания слова для языка L называется определение того, принадлежит ли данное слово языку L."

Ну вот есть у нас L1 = {"aa", "ab", "ac"}
Что тут трудного определить, скажем "a" входит в L1 или нет?

Что-то я вообще не догоняю, объясните плиз....


21.06.10 13:20: Перенесено модератором из 'Философия программирования' — Хитрик Денис
поправил ссылки — Кодт
Третий Рим должен пасть!
Re: NP-полные задачи
От: dilmah США  
Дата: 21.06.10 08:52
Оценка: +1
GC>Ну вот есть у нас L1 = {"aa", "ab", "ac"}
GC>Что тут трудного определить, скажем "a" входит в L1 или нет?
GC>Что-то я вообще не догоняю, объясните плиз....

интересные языки бесконечны
Re: NP-полные задачи
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 21.06.10 08:59
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>Что-то я вообще не догоняю, объясните плиз....

Выбором конечного языка ты ты сделал не NP задачу, так как еще решение перестало зависеть от входных данных (строки).
Для решения достаточно перебрать все варианты строк языка L1, что есть O(1) от размерности входных данных.
Re: NP-полные задачи
От: Кодт Россия  
Дата: 21.06.10 09:31
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


Те, которые заведомо не решаются за полиномиальное время — это NP-трудные.
А NP-полные — это те, про которые это неизвестно. (Проблема P≠NP до сих пор открыта).
Перекуём баги на фичи!
Re: NP-полные задачи
От: CaptainFlint Россия http://flint-inc.ru/
Дата: 21.06.10 09:53
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>Описание что такое NP-полные задачи из Википедии


GC>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


Не совсем так. Как Кодт написал чуть выше, ни решаемость, ни нерешаемость за полиномиальное время для NP пока не доказаны.
Изначально, P — это задачи, которые решаются за полиномиальное время, NP — задачи, которые проверяются за полиномиальное время (т.е. можно проверить, что ответ действительно соответствует условию; это само по себе далеко не всегда простая задача: скажем, проверить оптимальность маршрута по некоему критерию зачастую требует полного перебора всех остальных маршрутов и сравнения с ними, что будет явно не полиномиально). При этом, очевидно, класс P включается в NP.

NP-полные же задачи — это такие NP-задачи, к которым сводятся все остальные NP-задачи.
Почему же, ё-моё, ты нигде не пишешь «ё»?
Re: NP-полные задачи
От: Кодёнок  
Дата: 21.06.10 09:55
Оценка: 2 (1)
Здравствуйте, GhostCoders, Вы писали:

GC>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».
Re[2]: NP-полные задачи
От: GhostCoders Россия  
Дата: 21.06.10 09:56
Оценка:
Здравствуйте, dilmah, Вы писали:

GC>>Ну вот есть у нас L1 = {"aa", "ab", "ac"}

GC>>Что тут трудного определить, скажем "a" входит в L1 или нет?
GC>>Что-то я вообще не догоняю, объясните плиз....

D>интересные языки бесконечны

ок.

то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9}
множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число).
и, скажем, язык L1 — множество четных чисел, или множество всех простых чисел.

напрмер, множество все четных чисел можно обратить в множество нечетных чисел, прибавляя 1.

ВОПРОС:
Функция f, как я понял должна быть взаимно-однозначной в сводимости по Карпу или достаточно однозначности в одну сторону (сторону преобразования)?

то есть получается, что имеея язык L1 (или некую процедуру, которая генерирует этот язык), у нас есть функция преобразования из L1 в L2 за некоторое полиномиальное время.
То есть, если нам нужно сформировать очередное слово языка L2, то нам надо сначала выполнить некую процедуру для формирования слова из L1, а потом эту самую f.
Причем время нахождения слова для L2 будет больше, чем для слова из L1, так как нахождение слова из L1 требует меньше времени по определению.

ВОПРОС:
Это и имеют в виду, говоря, что "Таким образом, неформально язык L1 «не сложнее» языка L2."? То есть, найти какие-то слова из L1 всегда быстрее чем L2.


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

например, генерирующая функция для всех четных чисел

int even_number(int order_number)
{
  return 2*order_number;
}


1 -> 2
2 -> 4
3 -> 6
и т.д.
Для случая всех простых чисел, данная генерирующая функция будет посложнее и работать будет помедленнее.

"Язык L2 называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP."
но тут я все же не понимаю. только ввели понятие алфавит, множество всех возможных слов из алфавита, определение языка,
определение сводимости по Карпу, и используют понятие "класс NP", хотя ранее (на этой странице), не описывали что такое "класс NP"?

ВОПРОС:
Что такое класс NP?

Наверное, это множество каких-то языков, но каких?
Третий Рим должен пасть!
Re[2]: NP-полные задачи
От: _DAle_ Беларусь  
Дата: 21.06.10 09:59
Оценка: 3 (1) +2
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, GhostCoders, Вы писали:


GC>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


К>Те, которые заведомо не решаются за полиномиальное время — это NP-трудные.

К>А NP-полные — это те, про которые это неизвестно. (Проблема P≠NP до сих пор открыта).

Нет. Все не так. Во-первых, класс NP — это класс задач распознавания, решаемых за полиномиальное время на недетерминированной МТ (NP = Nondeterministic Polynomial).
NP-полная задача — это задача, принадлежащая классу NP, с таким свойством, что любая задача из NP сводится к ней за полиномиальное время.
NP-трудная задача — это задача (необязательно распознавания), к которой сводится за полиномиальное время какая-нибудь NP-полная задача. То есть NP-hard в общем-то содержит в себе множество NP-complete.

Связь между множествами в случаях P=NP, P≠NP показана, например, тут.
Re[2]: NP-полные задачи
От: _DAle_ Беларусь  
Дата: 21.06.10 10:01
Оценка: 3 (1)
Здравствуйте, Кодёнок, Вы писали:

Кё>Здравствуйте, GhostCoders, Вы писали:


GC>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


Кё>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».


NP содержит в себе P.
Re[2]: NP-полные задачи
От: GhostCoders Россия  
Дата: 21.06.10 10:02
Оценка:
Здравствуйте, Кодёнок, Вы писали:

Кё>Здравствуйте, GhostCoders, Вы писали:


GC>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


Кё>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».

Ок, спасибо, но хочеться иметь углубленные знания.
Третий Рим должен пасть!
Re[3]: NP-полные задачи
От: Wolverrum Ниоткуда  
Дата: 21.06.10 10:03
Оценка:
Здравствуйте, GhostCoders, Вы писали:
GC>то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9}
GC>множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число).

По-моему, множество возможных слов будет очень похожим на R\{,}
Re[4]: NP-полные задачи
От: GhostCoders Россия  
Дата: 21.06.10 10:06
Оценка:
Здравствуйте, Wolverrum, Вы писали:

W>Здравствуйте, GhostCoders, Вы писали:

GC>>то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9}
GC>>множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число).

W>По-моему, множество возможных слов будет очень похожим на R\{,}

Не понял, поясните. Откуда в моем алфавите символы "R" и ","? (запятая у меня всего-лишь отделяет один символ от другого, а фигурные скобки для красоты)
Третий Рим должен пасть!
Re[3]: NP-полные задачи
От: _DAle_ Беларусь  
Дата: 21.06.10 10:09
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, Кодёнок, Вы писали:


Кё>>Здравствуйте, GhostCoders, Вы писали:


GC>>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


Кё>>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».

GC>Ок, спасибо, но хочеться иметь углубленные знания.

Так не вопрос.
http://en.wikipedia.org/wiki/Decision_problem
http://en.wikipedia.org/wiki/P_(complexity)
http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine
http://en.wikipedia.org/wiki/NP_(complexity)
http://en.wikipedia.org/wiki/P_versus_NP_problem
http://en.wikipedia.org/wiki/Turing_reduction
http://en.wikipedia.org/wiki/NP-complete
http://en.wikipedia.org/wiki/NP-hard
Re[5]: NP-полные задачи
От: Wolverrum Ниоткуда  
Дата: 21.06.10 10:14
Оценка:
Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, Wolverrum, Вы писали:


W>>Здравствуйте, GhostCoders, Вы писали:

GC>>>то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9}
GC>>>множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число).
W>>По-моему, множество возможных слов будет очень похожим на R\{,}
GC>Не понял, поясните. Откуда в моем алфавите символы "R" и ","? (запятая у меня всего-лишь отделяет один символ от другого, а фигурные скобки для красоты)
множество возможных слов, имхо, будет очень похожим на множество действительных чисел из десятичной записи которых выброшена запятая — примерно так. Засомневался, что "немного избыточных слов, вроде 000001" действительно будет немного.
Re[4]: NP-полные задачи
От: Кодёнок  
Дата: 21.06.10 10:16
Оценка:
Здравствуйте, _DAle_, Вы писали:

Кё>>>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».

GC>>Ок, спасибо, но хочеться иметь углубленные знания.

_DA>Так не вопрос.

_DA>http://en.wikipedia.org/wiki/Decision_problem
_DA>http://en.wikipedia.org/wiki/P_(complexity)
_DA>http://en.wikipedia.org/wiki/NP_(complexity)

Это несеръезно. Ты правда думаешь, что он не умеет искать в википедии, и ты такой из благородных побуждений нашел ему нужные статьи, и все его проблемы теперь решены, тему можно удалять, всем спасибо?
Re[5]: NP-полные задачи
От: _DAle_ Беларусь  
Дата: 21.06.10 10:22
Оценка:
Здравствуйте, Кодёнок, Вы писали:

Кё>Здравствуйте, _DAle_, Вы писали:


Кё>>>>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».

GC>>>Ок, спасибо, но хочеться иметь углубленные знания.

_DA>>Так не вопрос.

_DA>>http://en.wikipedia.org/wiki/Decision_problem
_DA>>http://en.wikipedia.org/wiki/P_(complexity)
_DA>>http://en.wikipedia.org/wiki/NP_(complexity)

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


Я думаю, что чтобы иметь "углубленные знания" нужно прочитать соответствующую литературу или хотя бы статьи в википедии. Минимальный набор статей я привел. А пересказывать всю теорию в форуме слишком долго, сложно, и незачем, имхо.
Re[5]: NP-полные задачи
От: GhostCoders Россия  
Дата: 21.06.10 10:24
Оценка:
Здравствуйте, Кодёнок, Вы писали:

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

Да, статьи я и сам могу найти. Но друное дело разобраться в них. Тут надо с кем-то посоветоваться, обсудить, так как всегда возникают вопросы...
Третий Рим должен пасть!
Re[6]: NP-полные задачи
От: GhostCoders Россия  
Дата: 21.06.10 11:42
Оценка:
Здравствуйте, _DAle_, Вы писали:

_DA>Я думаю, что чтобы иметь "углубленные знания" нужно прочитать соответствующую литературу или хотя бы статьи в википедии. Минимальный набор статей я привел. А пересказывать всю теорию в форуме слишком долго, сложно, и незачем, имхо.

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

[urlсведение по Карпу — из книги Вялого]http://nature.web.ru/db/msg.html?mid=1161983&uri=node12.html[/url]
мне кажеться, что тут определение сводимости по Карпу противотечит, тому что в википедии, через языки.

"Функция f1 сводится к функции f (обозначение f1 <= f2), если существует такая функция f < P, что для всех x f1(x) = f2(f(x))."

мне кажетcя, что должно быть, f(f1(x)) = f2(x).

потому как f(x) из википедии применяеться к L1, то естественно f(x) применять к f1(x), то есть вот так f(f1(x)), а не f2(f(x)).
Хотя, конечно, что-то от меня может и ускальзает.

но самое главное, так на каждом шагу... вопросы, вопросы и еще раз вопросы....
Третий Рим должен пасть!
Re[7]: NP-полные задачи
От: _DAle_ Беларусь  
Дата: 21.06.10 12:12
Оценка: 3 (1) +1
Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, _DAle_, Вы писали:


_DA>>Я думаю, что чтобы иметь "углубленные знания" нужно прочитать соответствующую литературу или хотя бы статьи в википедии. Минимальный набор статей я привел. А пересказывать всю теорию в форуме слишком долго, сложно, и незачем, имхо.

GC>Прочитать — не достоточно, ведь это не художественная литература. Начал "читать" — и сразу начали возникать вопросы, начал находить ошибки (ну мне так кажется что кое-где ошибки есть,
GC>конечно, от моего незнания). Ну вот, например,

GC>[urlсведение по Карпу — из книги Вялого]http://nature.web.ru/db/msg.html?mid=1161983&amp;uri=node12.html[/url]

GC>мне кажеться, что тут определение сводимости по Карпу противотечит, тому что в википедии, через языки.

GC>"Функция f1 сводится к функции f2 (обозначение f1 <= f2), если существует такая функция f < P, что для всех x f1(x) = f2(f(x))."


Тут сведение в терминах функций. То есть на пальцах, f1 сводится к f2, если для любых входных данных x функции f1, их можно за полиномиальное время преобразовать с помощью некоторой функции f во входные данные для функции f2 так, что значения функций будут совпадать.

GC>мне кажетcя, что должно быть, f(f1(x)) = f2(x).


GC>потому как f(x) из википедии применяеться к L1, то естественно f(x) применять к f1(x), то есть вот так f(f1(x)), а не f2(f(x)).

GC>Хотя, конечно, что-то от меня может и ускальзает.

Мы любое множество можем представить в виде функции, которая возвращает 1, если параметр принадлежит множеству, и 0 иначе. То есть вместо L1 и L2 можем рассмотреть f1(x), f2(x). В википедии написано, что должна существовать функция f такая, что x < L1 <=> f(x) < L2. Для наших функций это равносильно f1(x) = f2(f(x)).

GC>но самое главное, так на каждом шагу... вопросы, вопросы и еще раз вопросы....
Re: NP-полные задачи
От: Буравчик Россия  
Дата: 21.06.10 12:31
Оценка: 3 (1) +3
Здравствуйте, GhostCoders, Вы писали:

GC>Описание что такое NP-полные задачи из Википедии


GC>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.


Задача в классе NP — это такая задача, которая может быть решена за полиномиальное время на недетерминированной машине Тьюринга. Решение этой задачи можно проверить за полиномиальное время на обычной машине Тьюринга (детерминированной).

NP-полная задача — это задача, к которой можно свести любую задачу NP. Если задача NP-полна, то её можно свести к другой NP-полной задаче.

GC>Сводимость по Карпу из Википедии

GC>как я понял, f — должна устанавливать взаимно-однозначное соответстие между L1 и L2?
GC>...

Алфавит и слова используются для формального описания понятия "сведения" одной задачи к другой, важно понять идею.

Пусть есть NP-полная задача T1 — получить на входе данные d1 и выдать ответ ДА или НЕТ.
Пусть есть задача Т2 — получить на вход данные d2 и выдать ответ ДА или НЕТ.

Пусть у нас есть полиномиальный алгоритм F, который умеет однозначно преобразовывать данные d1 в данные d2. Тогда задача T2 тоже является NP-полной.
Введь если мы умеем решать T2, то мы сможем решить и T1: Т1(d1) = T2(F(d1)), т.е. задача Т1 не сложнее Т2.

Т.е. d1 описывается алфавитом и словами (L1), d2 описывается алфавитом и словами (L2), функция f определяет соответствие d2->d1 (L2->L1).
Best regards, Буравчик
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.