Здравствуйте, _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% вероятности так и не получим?
Реальные классические компьютеры тоже могут давать сбой с небольшой вероятностью.
