Здравствуйте, 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).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, GhostCoders, Вы писали:
GC>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
К>Те, которые заведомо не решаются за полиномиальное время — это NP-трудные. К>А NP-полные — это те, про которые это неизвестно. (Проблема P≠NP до сих пор открыта).
Нет. Все не так. Во-первых, класс NP — это класс задач распознавания, решаемых за полиномиальное время на недетерминированной МТ (NP = Nondeterministic Polynomial).
NP-полная задача — это задача, принадлежащая классу NP, с таким свойством, что любая задача из NP сводится к ней за полиномиальное время.
NP-трудная задача — это задача (необязательно распознавания), к которой сводится за полиномиальное время какая-нибудь NP-полная задача. То есть NP-hard в общем-то содержит в себе множество NP-complete.
Связь между множествами в случаях P=NP, P≠NP показана, например, тут.
Здравствуйте, GhostCoders, Вы писали:
GC>Здравствуйте, _DAle_, Вы писали:
_DA>>Я думаю, что чтобы иметь "углубленные знания" нужно прочитать соответствующую литературу или хотя бы статьи в википедии. Минимальный набор статей я привел. А пересказывать всю теорию в форуме слишком долго, сложно, и незачем, имхо. GC>Прочитать — не достоточно, ведь это не художественная литература. Начал "читать" — и сразу начали возникать вопросы, начал находить ошибки (ну мне так кажется что кое-где ошибки есть, GC>конечно, от моего незнания). Ну вот, например,
GC>[urlсведение по Карпу — из книги Вялого]http://nature.web.ru/db/msg.html?mid=1161983&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>но самое главное, так на каждом шагу... вопросы, вопросы и еще раз вопросы....
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, GhostCoders, Вы писали:
GC>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
Кё>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».
Здравствуйте, GhostCoders, Вы писали:
GC>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».
GC>Ну вот есть у нас L1 = {"aa", "ab", "ac"} GC>Что тут трудного определить, скажем "a" входит в L1 или нет? GC>Что-то я вообще не догоняю, объясните плиз....
как я понял, 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 или нет?
Здравствуйте, GhostCoders, Вы писали:
GC>Что-то я вообще не догоняю, объясните плиз....
Выбором конечного языка ты ты сделал не NP задачу, так как еще решение перестало зависеть от входных данных (строки).
Для решения достаточно перебрать все варианты строк языка L1, что есть O(1) от размерности входных данных.
Здравствуйте, GhostCoders, Вы писали:
GC>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
Те, которые заведомо не решаются за полиномиальное время — это NP-трудные.
А NP-полные — это те, про которые это неизвестно. (Проблема P≠NP до сих пор открыта).
Здравствуйте, GhostCoders, Вы писали:
GC>Описание что такое NP-полные задачи из Википедии
GC>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
Не совсем так. Как Кодт написал чуть выше, ни решаемость, ни нерешаемость за полиномиальное время для NP пока не доказаны.
Изначально, P — это задачи, которые решаются за полиномиальное время, NP — задачи, которые проверяются за полиномиальное время (т.е. можно проверить, что ответ действительно соответствует условию; это само по себе далеко не всегда простая задача: скажем, проверить оптимальность маршрута по некоему критерию зачастую требует полного перебора всех остальных маршрутов и сравнения с ними, что будет явно не полиномиально). При этом, очевидно, класс P включается в NP.
NP-полные же задачи — это такие NP-задачи, к которым сводятся все остальные NP-задачи.
Здравствуйте, 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?
Наверное, это множество каких-то языков, но каких?
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, GhostCoders, Вы писали:
GC>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
Кё>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение».
Ок, спасибо, но хочеться иметь углубленные знания.
Здравствуйте, GhostCoders, Вы писали: GC>то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9} GC>множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число).
По-моему, множество возможных слов будет очень похожим на R\{,}
Здравствуйте, Wolverrum, Вы писали:
W>Здравствуйте, GhostCoders, Вы писали: GC>>то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9} GC>>множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число).
W>По-моему, множество возможных слов будет очень похожим на R\{,}
Не понял, поясните. Откуда в моем алфавите символы "R" и ","? (запятая у меня всего-лишь отделяет один символ от другого, а фигурные скобки для красоты)
Здравствуйте, GhostCoders, Вы писали:
GC>Здравствуйте, Кодёнок, Вы писали:
Кё>>Здравствуйте, GhostCoders, Вы писали:
GC>>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
Кё>>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений, а P — это те, к которым «есть короткий способ вычислить решение». GC>Ок, спасибо, но хочеться иметь углубленные знания.
Здравствуйте, GhostCoders, Вы писали:
GC>Здравствуйте, Wolverrum, Вы писали:
W>>Здравствуйте, GhostCoders, Вы писали: GC>>>то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9} GC>>>множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число). W>>По-моему, множество возможных слов будет очень похожим на R\{,} GC>Не понял, поясните. Откуда в моем алфавите символы "R" и ","? (запятая у меня всего-лишь отделяет один символ от другого, а фигурные скобки для красоты)
множество возможных слов, имхо, будет очень похожим на множество действительных чисел из десятичной записи которых выброшена запятая — примерно так. Засомневался, что "немного избыточных слов, вроде 000001" действительно будет немного.
Это несеръезно. Ты правда думаешь, что он не умеет искать в википедии, и ты такой из благородных побуждений нашел ему нужные статьи, и все его проблемы теперь решены, тему можно удалять, всем спасибо?
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, _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)
Кё>Это несеръезно. Ты правда думаешь, что он не умеет искать в википедии, и ты такой из благородных побуждений нашел ему нужные статьи, и все его проблемы теперь решены, тему можно удалять, всем спасибо?
Я думаю, что чтобы иметь "углубленные знания" нужно прочитать соответствующую литературу или хотя бы статьи в википедии. Минимальный набор статей я привел. А пересказывать всю теорию в форуме слишком долго, сложно, и незачем, имхо.
Здравствуйте, Кодёнок, Вы писали:
Кё>Это несеръезно. Ты правда думаешь, что он не умеет искать в википедии, и ты такой из благородных побуждений нашел ему нужные статьи, и все его проблемы теперь решены, тему можно удалять, всем спасибо?
Да, статьи я и сам могу найти. Но друное дело разобраться в них. Тут надо с кем-то посоветоваться, обсудить, так как всегда возникают вопросы...
Здравствуйте, _DAle_, Вы писали:
_DA>Я думаю, что чтобы иметь "углубленные знания" нужно прочитать соответствующую литературу или хотя бы статьи в википедии. Минимальный набор статей я привел. А пересказывать всю теорию в форуме слишком долго, сложно, и незачем, имхо.
Прочитать — не достоточно, ведь это не художественная литература. Начал "читать" — и сразу начали возникать вопросы, начал находить ошибки (ну мне так кажется что кое-где ошибки есть,
конечно, от моего незнания). Ну вот, например,
"Функция 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)).
Хотя, конечно, что-то от меня может и ускальзает.
но самое главное, так на каждом шагу... вопросы, вопросы и еще раз вопросы....
Здравствуйте, _DAle_, Вы писали:
_DA>Мы любое множество можем представить в виде функции, которая возвращает 1, если параметр принадлежит множеству, и 0 иначе. То есть вместо L1 и L2 можем рассмотреть f1(x), f2(x). В википедии написано, что должна существовать функция f такая, что x < L1 <=> f(x) < L2. Для наших функций это равносильно f1(x) = f2(f(x)).
Мы любое множество можем представить в виде функции, которая возвращает 1, если параметр принадлежит множеству, и 0 иначе.
Если так, то да, верно, большое спасибо!
Дело в том, что я представлял функцию f(x) немного по другому.
Функция по моим представлениям, принимает не x — кандидата в язык, а порядковый номер слова в нашем языке, и возвращает значение слова в этом языке.
то есть, например f для определения языка всех четных чисел = в ихнем понимании
int GetSpecifiedEvenNumber(int orderNumber) // orderNumber от 1 и далее
{
return orderNumber * 2;
}
тогда, например, язык множества четных чисел сводим по Карпу к языку множества нечетных чисел так:
(в "ихнем" или правильном понимании)
int f(int x) // Функция преобразования
{
return x+1;
}
bool IsEven(int number)
{
return (0 == number % 2);
}
bool IsOdd(int number)
{
return (0 != number % 2);
}
то есть получается, что IsEven(x) = IsOdd(f(x)) — любое четное число можно преобразовать при помощи f() в четное, поэтому результаты
IsEven(x) и IsOdd(f(x)) будут всегда совпадать!
и в моем понимании:
int GetSpecifiedEvenNumber(int orderNumber) // orderNumber от 1 и далее
{
return orderNumber * 2;
}
int GetSpecifiedOddNumber(int oderNumber)// orderNumber от 1 и далее
{
return orderNumber * 2 + 1;
}
int f(int x) // Функция преобразования
{
return x+1;
}
то есть f(GetSpecifiedEvenNumber(x)) = GetSpecifiedOddNumber(x),
здесь мы получили слово языка (читай четное число) по его порядковому номеру в языке (orderNumber или x) при помощи GetSpecifiedEvenNumber(),
затем преобразовали слово (читай четное число) при помощи функции преобразования f, и результат совпал с результатом функции GetSpecifiedOddNumber() от того
же порядкового номера orderNumber (x).
Что меня подтолкнуло к моему выбору? Это неправильное понимание как работают функции f1() и f2(), спасибо!
Здравствуйте, Буравчик, Вы писали:
Б>Пусть у нас есть полиномиальный алгоритм F, который умеет однозначно преобразовывать данные d1 в данные d2. Тогда задача T2 тоже является NP-полной. Б>Введь если мы умеем решать T2, то мы сможем решить и T1: Т1(d1) = T2(F(d1)), т.е. задача Т1 не сложнее Т2.
Б>Т.е. d1 описывается алфавитом и словами (L1), d2 описывается алфавитом и словами (L2), функция f определяет соответствие d2->d1 (L2->L1).
Что-то я совсем запутался... Вначале Вы вроде писали, что f определяется как соответствие из d1 -> d2, потом пишете обратное...
Здравствуйте, GhostCoders, Вы писали:
GC>Что-то я совсем запутался... Вначале Вы вроде писали, что f определяется как соответствие из d1 -> d2, потом пишете обратное...
Ой, действительно, очпятка.
Мы одну задачу решаем через другую. Для этого нужно за полиномиальное время преобразовать входные данные одной задачи в другую так, чтобы из решения второй задачи получили решение первой. Если мы смогли это сделать, то сложность второй задачи не меньше сложности первой. С помощью таких вещей мы можем сравнивать сложность задач.
По определению NP-полные задачи имеют наибольшую сложность среди NP, т.к. через них можно решить все задачи NP.
Поэтому если вторая задачи является NP, и через нее мы выразили какую-нибудь NP-полную задачу, то она (вторая задача) тоже является NP-полной.
Насчет википедии и фразы "Задачей распознавания слова для языка L называется определение того, принадлежит ли данное слово языку L". По-моему это не так.
Там как раз разъясняется, что задача распознавания — это задача которая для своего входа дает ответ либо ИСТИНА либо ЛОЖЬ.
Алгорити распознает язык L, если для любого x принадлежащего к L, алгоритм может выдать ответ (ИСТИНА/ЛОЖЬ).
В этой же статье указан список литературы, из которго две книги на русском:
1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2001. (PDF)
Эта статья, вкратце повторяет содержимое главы "NP-полнота" этой книги.
2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с. англ. — М.: Мир, 1982. (у меня есть в djvu)
Целая книга, в которой расписано про сложность задач, машины Тьюринга и формальные языки.
Здравствуйте, GhostCoders, Вы писали:
GC>1. Если некая задача при использовании множества команд I является NP, то есть ли другое множество команд I*,
Выделенное содержит проблему. Задача «является P», если известен метод решения, либо доказано, что задача сводится к другой P-задаче, или их простой (линейной?) комбинации. И не является, если не известен или не доказано. Это не строгая математическая принадлежность, по крайней мере в общем случае, это субъективный признак — известен ли лично тебе или можешь ли ты доказать. Если окажется P=NP, вопрос не будет иметь смысла.
Я могу ответить на твой вопрос и «да» и «нет», ибо проверить ответ ты не сможешь. Найти способ проверки — это собственно будет решением проблемы P ?= NP.
GC>в котором эта задача P?
На эквивалентной машине — очевидно нет, что следует из их эквивалентности Но можно сделать другую машину с одной инструкцией “спросить у оракла”, который решает нашу задачу мгновенно.
Здравствуйте, Кодёнок, Вы писали:
GC>>в котором эта задача P?
Кё>На эквивалентной машине — очевидно нет, что следует из их эквивалентности Но можно сделать другую машину с одной инструкцией “спросить у оракла”, который решает нашу задачу мгновенно.
Дело в том, что мне кажется все наши компьютеры используют одни и те же наборы команд.... они основаны на арифметике...
нет, различаются конечно, но все они эквивалентны, то есть из одного набора команд можно перейти в другой за полиномиальное время.... наподобие сведения по Карпу...
А если придумать такой набор команд, который не сводиться за полиномиальное время к нашим базовым (INC, DEC, ADD, DEC и т.д.) ?
И можно ли реализовать такой набор команд в аппаратном виде? Тут еще должно быть условие "расшияемости"...
Как бы это объяснить... например существующие 16-разрядные процессоры могут складывать 32-разрядные числа, используя флаг переноса.. и т.д.
Так вот, если бы удалось сделать аппаратную команду, которая скажем решала SAT для какого-то фиксированного числа аргументов,
и при помощи полиномиальной комбинации таких команд можно было решать SAT для произвольного числа аргументов, то это было бы гууд.
Но я никак придумать не могу такую команду, да и невозможно это, наверное.
Кстати, машина Тьюринга, как я понял, обладает свойством "расширяемости"....
Здравствуйте, Wolverrum, Вы писали:
W>Здравствуйте, GhostCoders, Вы писали: GC>>то есть например, если алфавит = {0,1,2,3,4,5,6,7,8,9} GC>>множство возможных слов — это множество натуральных чисел, плюс немного избыточных слов, вроде 000001 (незначащих нулей можеть быть много в начале, бесконечное число).
W>По-моему, множество возможных слов будет очень похожим на R\{,}
Слово языка в данном контексте — это конечная последовательность символов алфавита.
А в R — все слова бесконечные (если рассматривать не только ведущие нули, но и после).
Поэтому такой язык с точки зрения алгоритмов неинтересен.
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, GhostCoders, Вы писали:
GC>>Пытаюсь понять что это такое. В универе конечно изучал, но так толком и не понял. Вроде класс задач, который не решается за полиномиальное время.
Кё>Если на пальцах, то NP — это задачи, которые решаются только полным перебором решений,
Это не так. К примеру, результат последних лет — это решения задачи комивояжёра за 2^n (вместо n!).
Есть большое сообщество, которое занимается улучшениями экспоненциальных алгоритмов.
Здравствуйте, GhostCoders, Вы писали:
GC>Мы любое множество можем представить в виде функции, которая возвращает 1, если параметр принадлежит множеству, и 0 иначе. GC>Если так, то да, верно, большое спасибо!
Такая функция называется характеристической. Если мы говорим о вычислимых
функциях (т.е. которые можно вычислить на машине Тьюринга), то это неверно
в общем случае. Но для NP задач — это так.
Здравствуйте, Smal, Вы писали:
S>Такая функция называется характеристической. Если мы говорим о вычислимых S>функциях (т.е. которые можно вычислить на машине Тьюринга), то это неверно S>в общем случае.
Это как? В каком случае неверно?
D>>ты про квантовые вычисления не слышал или прикидываешься? GC>Слышал, но слабо понимаю как они работают
Например, меня смушает, что:
"Квантовая система дает результат, только с некоторой вероятностью являющийся правильным. Но за счет небольшого увеличения операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице."
Так может, быть, преимущества квантовых компьютеров могут быть нивелированны необходимостью их прогонять несколько раз?
Здравствуйте, GhostCoders, Вы писали:
GC>Здравствуйте, Smal, Вы писали:
S>>Такая функция называется характеристической. Если мы говорим о вычислимых S>>функциях (т.е. которые можно вычислить на машине Тьюринга), то это неверно S>>в общем случае. GC>Это как? В каком случае неверно?
Существуют невычислимые множества (например, множество номеров неостанавливающихся машин Тьюринга).
Здравствуйте, GhostCoders, Вы писали:
GC>>Но за счет небольшого увеличения операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице.
GC>И точного решения со 100% вероятности так и не получим?
Реальные классические компьютеры тоже могут давать сбой с небольшой вероятностью.
Здравствуйте, nikov, Вы писали:
N>Реальные классические компьютеры тоже могут давать сбой с небольшой вероятностью.
Но случайность — это сама природа квантовых компьютеров...
N>>Существуют невычислимые множества (например, множество номеров неостанавливающихся машин Тьюринга).
GC>Если машина Тьюринга "зависает", то считается что она возвратила 0 или слово не принадлежит языку. GC>И что тут неверного?
То, что ты не можешь определить, "зависла" она (например, в бесконечном цикле) или остановится через конечное число тактов. Никакие трюки, типа проверки того, что машина 20-ый раз проходит одно и то же состояние, в общем случае не работают.
Здравствуйте, GhostCoders, Вы писали:
N>>Реальные классические компьютеры тоже могут давать сбой с небольшой вероятностью. GC>Но случайность — это сама природа квантовых компьютеров...
С теоретической точки зрения — да. Но на практике разницы нет. Есть определенная вероятность неверного ответа, и мы умеем ее уменьшать до приемлемого для нас уровня.
Здравствуйте, kl, Вы писали:
N>>>Существуют невычислимые множества (например, множество номеров неостанавливающихся машин Тьюринга).
GC>>Если машина Тьюринга "зависает", то считается что она возвратила 0 или слово не принадлежит языку. GC>>И что тут неверного?
kl>То, что ты не можешь определить, "зависла" она (например, в бесконечном цикле) или остановится через конечное число тактов. Никакие трюки, типа проверки того, что машина 20-ый раз проходит одно и то же состояние, в общем случае не работают.
Я бы все-таки прокоменнтировал это.
Тут надо иметь в виду что надо использовать ПОЛНОЕ состояние машины Тьюринга,
а не только состояние управляющего устройство, которое задается множеством Q
полное состояние задается состоянием управляющего устройства плюс полное состояние ленты.
Так как лента бесконечна, и число возможных ее состояний также бесконечно, то число полных состояний машины Тьюринга тоже бесконечно...
Если удается обнаружить, что мы вернулись хотя бы 1 раз в то полное состояние в котором уже были — то да, мы зависли (Я имею в виду здесь обычную детерминированную МТ),
причем это будет не "трюк", а самый что ни на есть строгий факт. И 20 раз проходить одно и тоже состояние ни к чему..
Вся загвоздка в том, что МТ может зависнуть, используя все новые ячейки на ленте... просто например в цикле переходить все время в одну сторону и портить ленту... тут ничего поделать нельзя...
то есть использовать все новые и новые полные состояния и цикла в графе полных состояний просто не будет....
Так, ради заметки, хочу сказать, что если мы ограничим ленту МТ каким-то конечным значением, то определить зависла ли МТ возможно...
но достаточно ресурсоемко, насколько, это зависит от мощности множества полных состояний МТ. Если это значение равно 1000, то мы можем определить заваисла ли МТ за время меньшее или равное 1000 шагам
(и никак не большее).
Еще я хочу добавить, что так как машины Тьюринга — это абстракция, которая имеет бесконечную ленту (читай память),
а недетерминированная МТ имеет еще и бесконечное число параллельных вычислительных устройств,
то определить зависает ли детерминированная МТ, мне кажется, можно на недетерминированной МТ.
То есть, для любой ДМТ можно использовать "сторожевую" НДМТ
Здравствуйте, GhostCoders, Вы писали:
GC>То есть, для любой ДМТ можно использовать "сторожевую" НДМТ
Из любой НМТ можно сделать ДМТ (при этом она может вырасти нехило,
но это нас в данном случае неволнует). Т.е. неважно, на какой
именно МТ определять понятие вычислимости.
Могу привести другой аргумент. Машин Тьюринга — счётное число,
т.к. каждая МТ может быть записана конечной строчкой в некотором
конечном алфавите. Вещественных чисел несчётно (т.е. больше, чем счётно).
Значит есть невычислимые (aka неконструктивные) вещественные числа,
т.е. такие, для которых не существует программ, которые получают на вход
некоторое число n и выдают n-ую цифру этого числа. Таким образом можно
построить пример невычислимой функции, а по ней и невычислимое множество.
GC>Вся загвоздка в том, что МТ может зависнуть, используя все новые ячейки на ленте... просто например в цикле переходить все время в одну сторону и портить ленту... тут ничего поделать нельзя... GC>то есть использовать все новые и новые полные состояния и цикла в графе полных состояний просто не будет....
Вот именно.
GC>Так, ради заметки, хочу сказать, что если мы ограничим ленту МТ каким-то конечным значением, то определить зависла ли МТ возможно... GC>но достаточно ресурсоемко, насколько, это зависит от мощности множества полных состояний МТ. Если это значение равно 1000, то мы можем определить заваисла ли МТ за время меньшее или равное 1000 шагам GC>(и никак не большее).
Да. Только будут вычислимые функции, который такая МТ вычислить не сможет, т.е. они строго вычислительно слабее общих МТ. См. tape-bounded Turing machine.
GC>Еще я хочу добавить, что так как машины Тьюринга — это абстракция, которая имеет бесконечную ленту (читай память), GC>а недетерминированная МТ имеет еще и бесконечное число параллельных вычислительных устройств, GC>то определить зависает ли детерминированная МТ, мне кажется, можно на недетерминированной МТ.
Нет. Как уже написали, недетерминированные МТ *ничего* не добавляют к вычислительной мощности ДМТ.
Здравствуйте, kl, Вы писали:
GC>>Еще я хочу добавить, что так как машины Тьюринга — это абстракция, которая имеет бесконечную ленту (читай память), GC>>а недетерминированная МТ имеет еще и бесконечное число параллельных вычислительных устройств, GC>>то определить зависает ли детерминированная МТ, мне кажется, можно на недетерминированной МТ.
kl>Нет. Как уже написали, недетерминированные МТ *ничего* не добавляют к вычислительной мощности ДМТ.
Это примерно как на НДМТ решать следующую задачу:
есть граф с бесконечным множеством вершин, и для НДМТ стоит задача найти цикл в таком графе....
можно конечно запустить бесконечное число параллельных процессов для обработки каждой вершины, но тут вопрос что больше бесконечность или бесконечность?
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, GhostCoders, Вы писали:
GC>>Здравствуйте, Smal, Вы писали:
S>>>Такая функция называется характеристической. Если мы говорим о вычислимых S>>>функциях (т.е. которые можно вычислить на машине Тьюринга), то это неверно S>>>в общем случае. GC>>Это как? В каком случае неверно?
N>Существуют невычислимые множества (например, множество номеров неостанавливающихся машин Тьюринга).
Есть более простой пример: вероятность останова машины Тьюринга на произвольном алгоритме.
Ясно что меньше 1, но вот какое это число...
Y>Есть более простой пример: вероятность останова машины Тьюринга на произвольном алгоритме. Y>Ясно что меньше 1, но вот какое это число...
ну вообще-то это просто некорректная задача -- на счетном множестве (которым является мн-во машин тьюринга или алгоритмов) не существует ненулевого равномерного распределения вероятности. То есть ты сперва должен задать от фонаря какое-то распределение.
Здравствуйте, dilmah, Вы писали:
Y>>Есть более простой пример: вероятность останова машины Тьюринга на произвольном алгоритме. Y>>Ясно что меньше 1, но вот какое это число...
D>ну вообще-то это просто некорректная задача -- на счетном множестве (которым является мн-во машин тьюринга или алгоритмов) не существует ненулевого равномерного распределения вероятности. То есть ты сперва должен задать от фонаря какое-то распределение.
Эту задачу изучал Грегори Хайтин, ему удалось придать ей корректный вид с помощью самоограничивающихся программ. То есть с помощью бросания монетки создается последовательность 0 и 1, а интерпретатор, считывая ее, сам понимает, где программа кончилась.
Перекуём баги на фичи!
