доказательство NP ≠ P в Eastern European Scientific Journal

[whitefox]

Вам, как раз, и нужно показать, что для полиномиальной задачи утверждение

bilan в сообщении #857127 писал(а):

ее ДНФ строится L-машиной за полиномиальное время.

следует из

bilan в сообщении #857127 писал(а):

она решается L-машиной за полиномиальное время

Ибо

bilan в сообщении #857127 писал(а):

размер ДНФ для полиномиальной задачи может быть експоненциальным

[bilan]

Глубоко уважаемый whitefox!
так как полиномиально решаемая задача полиномиально решается L-машиной, то из ячеек-начальных-данных, и их отрицаний с помощью $OR$ и $AND$
так как $AND$ дает умножение числа конъюнктов, то даже при полиномиальной сложности вычислений L-машиной возможна експоненциальная по размеру ДНФ ячейки ответа.
а в данной проблеме $\text{Клика}$ использование $AND$ затруднено, что и освещается в доказательстве, приходится в данной проблеме $\text{Клика}$ слишком часто использовать $OR$, что и дает более чем полиномиальную трудоемкость.
а если есть полиномиальный алгоритм L-машины, то он сам и является доказательством того, что ДНФ ответа строится за полиномиальное время
с глубоким уважением Билан И.

[bilan]

Глубоко уважаемый whitefox!
я понял, что Вы спрашиваете, но по моему сказать по ДНФ ответа полиномиально или нет решение -- это отдельная нетривиальная проблема для каждой задачи.
такая задача передо мною не стояла, я просто доказал неполиномиальность проблемы Клика.
с глубоким уважением Билан И.

[whitefox]

Если бы Вы доказали, что рассмотренная Вами задача не принадлежит классу сложности
$P/poly$, то из этого и следовало бы что $NP\ne P$.

Но Ваша теорема, всего лишь, утверждает экспоненциальную сложность, соответствующей Вашей задачи, ДНФ. Из чего совершенно не возможно сделать вывод об экспоненциальной сложности самой задачи.

[bilan]

глубоко уважаемый whitefox!
дело в том, что я и Коваль доказали, что построить такую ДНФ ответа за полиномиальное время невозможно из чего и следует что NP не равно P, так как проблема Клика есть NP-полная.
почему Вы привязываетесь к ДНФ? ДНФ в моем случае, в этом доказательстве, лишь инструмент.
а доказательство рассматривает L-машину которая полиномиальным образом эквивалентна машине Тьюринга. и доказывается, что эта L-машина не может за полиномиальное время получить ответ, то есть построить ДНФ ответа, или другими словами получить переменную, у которой ее значение равно ДНФ ответа.
с глубоким уважением Билан И.

[whitefox]

bilan в сообщении #858492 писал(а):

я и Коваль доказали, что построить такую ДНФ ответа за полиномиальное время невозможно из чего и следует что NP не равно P

Ещё раз — второе из первого не следует.

А чтобы следовало — нужно доказать, что для всякой полиномиальной задачи можно построить ДНФ за полиномиальное время. Что в принципе не возможно, ибо

bilan в сообщении #857127 писал(а):

размер ДНФ для полиномиальной задачи может быть експоненциальным

[bilan]

Глубоко уважаемый whitefox!
экспоненциальную ДНФ можно построить и за полиномиальное время! пример:в графе содержится клика, и все остальные ребра кроме клики отсутствуют.
размер ДНФ ответа -- експоненциальный, а алгоритм, который ее строит очевидный.
Коротко опишу для Вас, уважаемый whitefox, суть доказательства. В L-машине которая использует лишь $AND$ $OR$ $NOT$, и переменные в которых хранятся результаты вычислений, отсутствует условный переход, тем не мение она полиномиально еквивалентна машине Тьюринга.
Так вот, в этой L-машине также полиномиальным образом можно отказаться от $NOT$, если будут присутствовать отрицания от всех переменных-начальных-данных.
Таким обраом мы получаем, что при детерминированном процесе вычислений каждой переменной (точнее ее значению) будет соответствовать ВСЕГДА ОДНА И ТА ЖЕ ДНФ ОТ НАЧАЛЬНЫХ ДАННЫХ ПРИ ЛЮБЫХ ЗНАЧЕНИЯХ ЭТИХ НАЧАЛЬНЫХ ДАННЫХ.
используя $AND$ и $OR$ мы должны получить ДНФ ответа.
так как $AND$ использовать у нас не получается, то $OR$ дает более чем полиномиальную сложность, так как ДНФ ответа экспоненциальна.
Если бы можно было бы использовать $AND$ более широко, то была бы полиномиальная сложность.
а если есть любой алгоритм то он строит ДНФ ответа. То есть если алгоритм полиномиальный -- то за полиномиальное время строится ДНФ ответа.
к тому же мы строим ДНФ НЕ в лоб, по коньюнктам, прошу это учесть.
с глубоким уважением Билан И.

[whitefox]

bilan в сообщении #858553 писал(а):

экспоненциальную ДНФ можно построить и за полиномиальное время

bilan в сообщении #858553 писал(а):

к тому же мы строим ДНФ НЕ в лоб, по коньюнктам

Видимо Вы считаете, что утверждение

bilan в сообщении #857127 писал(а):

размер ДНФ для полиномиальной задачи может быть експоненциальным

касается исключительно совершенных ДНФ, но минимальная ДНФ при этом остаётся полиномиальной и может быть построена за полиномиальное время.

Это далеко не так, речь идёт именно о минимальных ДНФ. И экспоненциальны они потому, что состоят из экспоненциального числа простых импликант.

[bilan]

Глубоко уважаемый whitefox!

whitefox в сообщении #858672 писал(а):

касается исключительно совершенных ДНФ, но минимальная ДНФ при этом остаётся полиномиальной и может быть построена за полиномиальное время.

Это далеко не так, речь идёт именно о минимальных ДНФ. И экспоненциальны они потому, что состоят из экспоненциального числа простых импликант.

рассмотрите внимательней пример:
пример:в графе содержится клика, и все остальные ребра кроме клики отсутствуют.
размер ДНФ ответа -- експоненциальный, а алгоритм, который ее строит очевидный.
и Вы все поймете

[bilan]

Глубоко уважаемый whitefox!
Исключительно ради Вас, и в доказательство моего расположения к Вам, приведу разбор примера:
пусть клика размером $n$ содержится в графе размером $6n$. Остальные ребра отсутствуют.
размер ДНФ ответа -- $C_{6n}^{n}$ конъюнктов.
ДНФ не упрощается, т.к. клика от клики отличается как минимум на $n$ переменных.
возможно доказать что ДНФ ответа минимальна.
алгоритм, который проверяет, является ли граф указанного вида, очевиден:
1) находим первую вершину с ребрами.
2) если ребер у этой вершины не $n-1$, то граф не указанного вида.
3)эти $n$ вершин должны образовывать клику, проверяем это.
4) остальные ребра в графе должны отсутствоваль, проверяем это.
5) если все это так, печатаем $1$.


с глубоким уважением, Билан И.

[whitefox]

Вас не смущает, что рассмотренный Вами пример не является массовой проблемой? Мы здесь, всё таки, обсуждаем алгоритмы и их сложности.

Видимо Вы хотели привести пример полиномиальной задачи с экспоненциальной ДНФ.

Так как Вы делаете одолжение лично мне, то с меня достаточно будет если Вы поясните свою идею на простом примере, пусть даже и не отвечающем этим критериям. Например, на следующей проблеме: "Определить имеет ли n-вершинный граф 3-клику".

Хочу только (ещё "на берегу") предупредить — строить нужно именно ДНФ, а не схему из логических элементов AND, OR, NOT.

[bilan]

Глубоко уважаемый whitefox!
мы не строим ДНФ.
мы строим ход решения L-машины, у которой ячейка с ответом принимает значения, которые равны некоторой ДНФ от переменных-начальных-данных.
и так как ДНФ ответа имеет строго определенный вид, то на этом мы и играем.

whitefox в сообщении #859334 писал(а):

"Определить имеет ли n-вершинный граф 3-клику".

тут просто перебираем все клики и соединяем их с помощью $OR$ сложность $C_{n}^{3}$
то есть для данной задачи нам достаточно В ЛОБ, по конъюнктам построить ДНФ.
то есть пример абсолютно не показательный.
с глубоким уважением, Билан И.

[whitefox]

bilan в сообщении #859375 писал(а):

мы не строим ДНФ.

Рад, что смог открыть Вам на это глаза

Если бы Вы, доказали свою теорему не для ДНФ, а для схем, то тогда Ваш Вывод о $P\ne NP$ был бы законным. О чём писал выше http://dxdy.ru/post858270.html#p858270

Но для ДНФ он не верен, так как ДНФ Вы не строите. И, более того, для полиномиальной задачи построить ДНФ за полиномиальное время в общем случае не возможно так как

bilan в сообщении #857127 писал(а):

размер ДНФ для полиномиальной задачи может быть експоненциальным

bilan в сообщении #859375 писал(а):

мы строим ход решения L-машины, у которой ячейка с ответом принимает значения, которые равны некоторой ДНФ от переменных-начальных-данных.

Правильнее сказать: "которые равны некоторой булевой функции от переменных — начальных-данных". И то, что таким образом Вы строите — это схема из логических элементов AND, OR, NOT, реализующая указанную булеву функцию. Но нижнюю-то границу сложности Вы доказываете не для схем, а для ДНФ. Поэтому сделанный Вами вывод и не законен.

bilan в сообщении #859375 писал(а):

тут просто перебираем все клики и соединяем их с помощью $OR$ сложность $C_{n}^{3}$
то есть для данной задачи нам достаточно В ЛОБ, по конъюнктам построить ДНФ.
то есть пример абсолютно не показательный.

Рад, что Вы поняли, что таким способом можно за полиномиальное время построить только полиномиальную ДНФ.

[bilan]

Глубоко уважаемый whitefox!

whitefox в сообщении #859396 писал(а):

Правильнее сказать: "которые равны некоторой булевой функции от переменных — начальных-данных". И то, что таким образом Вы строите — это схема из логических элементов AND, OR, NOT, реализующая указанную булеву функцию. Но нижнюю-то границу сложности Вы доказываете не для схем, а для ДНФ. Поэтому сделанный Вами вывод и не законен.

мы рассматриваем булеву функцию, значение которой равно некой ДНФ.
При этом переход от булевой функции к ДНФ ей равной вполне законен.
То есть мы контролируем схему из логических элементов AND, OR, NOT, реализующую указанную булеву функцию с помощью ДНФ-ов каждой переменной (указанной булевой функцией).
и показываем, что схема из логических элементов AND, OR, NOT, реализующая указанную булеву функцию не может быть построена за полиномиальное время.

whitefox в сообщении #859396 писал(а):

Рад, что Вы поняли, что таким способом можно за полиномиальное время построить только полиномиальную ДНФ

а как же:

whitefox в сообщении #859334 писал(а):

Видимо Вы хотели привести пример полиномиальной задачи с экспоненциальной ДНФ.

с глубоким уважением, Билан И.

[whitefox]

bilan в сообщении #859399 писал(а):

и показываем, что схема из логических элементов AND, OR, NOT, реализующая указанную булеву функцию не может быть построена за полиномиальное время.

Вот так Вам и нужно сформулировать свою теорему.