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

[bilan]

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

а она так и сформулирована, только другими словами

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

[whitefox]

Вы не правы, это совершенно другая теорема.

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

[bilan]

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

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

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

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

[Xaositect]

Определения Ваши мне непонятны.

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

Обозначение 1: часть конъюнкта, проверяющую на утверждение ребер клики и только их назовем кликоподобной частью.
Обозначение 2: дополнение до кликоподобной части на тех же переменных (отвечающих только за клику) назовем основной частью.
Обозначение 3: часть конъюнкта содержащее все кроме кликоподобной или основной части назовем дополнительной частью.

Что такое "часть конъюнкта, проверяющая на утверждение ребер клики"? Утверждение ребер клики - это бессмысленное словосочетание. Во втором какие переменные имеются в виду? В третьем - как может в конъюнкте быть что-то, кроме кликоподобной части и ее дополнения?

[bilan]

Глубоко уважаемый Xaositect!
Обозначение 1: часть конъюнкта, проверяющую на утверждение ребер клики и только их назовем кликоподобной частью.
то есть это часть конъюнкта состоящая из утверждений переменных. переменные берутся из матрицы смежности. то есть если переменная $=1$, то соответствующее ребро содержится в графе. в конъюнкте мы можем выделить группу утверждений переменных, которые соответствуют клике. их мы и называем кликоподобной частью.
Обозначение 2: дополнение до кликоподобной части на тех же переменных (отвечающих только за клику) назовем основной частью.
дело в том, что если мы рассматриваем группу конъюнктов, то если они содержат только переменные отвечающие за клику и только их и если эта группа равна отрицанию от конъюнкта, который есть кликоподобной частью, то эта группа $OR$ кликоподобная часть тождественно $=1$
в этом смысле основная часть дополнение до 1-цы.
Обозначение 3: часть конъюнкта содержащее все кроме кликоподобной или основной части назовем дополнительной частью.
дело в том, что анализировать конъюнкты удобнее группами. И если взять группу конъюнктов, с общими переменными в кликоподобной части, или основной части, то все остальные утверждения и отрицания остальных переменных мы называем дополнительной частью.
Надеюсь ответил
с глубоким уважением, Билан И.

[Xaositect]

Давайте обозначим переменную, отвечающую за наличие ребра между $i$-й и $j$-й вершиной $x_{ij}$. Правильно ли я понимаю, что кликоподобная часть - это конъюнкция вида $\bigwedge\limits_{i,j\in A} x_{ij}$ для некоторого множества вершин $A$? А дополнительная часть - это все остальные конъюнкции на переменных $x_{ij}$ при $i,j\in A$?

[bilan]

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

Xaositect в сообщении #859445 писал(а):

Давайте обозначим переменную, отвечающую за наличие ребра между $i$-й и $j$-й вершиной $x_{ij}$. Правильно ли я понимаю, что кликоподобная часть - это конъюнкция вида $\bigwedge\limits_{i,j\in A} x_{ij}$ для некоторого множества вершин $A$?

это Вы правильно поняли, если только множество $A$ -- множество вершин клики

Xaositect в сообщении #859445 писал(а):

А дополнительная часть - это все остальные конъюнкции на переменных $x_{ij}$ при $i,j\in A$?

это не дополнительная, а основная часть

А дополнительная часть - это все остальные конъюнкции на переменных $x_{ij}$ при $i,j\notin A$.

при этом дополнительная часть может содержаться в одном конъюнкте вместе с кликоподобной частью, или (тут исключающее или) с основной частью
с глубоким уважением, Билан И.

[Xaositect]

Ок, с этим вроде разобрались. А если в конъюнкте содержится не все переменные $x_{ij}$, $i,j\in A$, а только некоторые?

[bilan]

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

Xaositect в сообщении #859460 писал(а):

А если в конъюнкте содержится не все переменные $x_{ij}$, $i,j\in A$, а только некоторые?

если $x_{ij}$, $i,j\in A$ и $A$ - множество всех вершин графа, а не только клики, то мы добавляем конъюнкты так, чтобы значение ДНФ не изменилось, но они содержались
с глубоким уважением, Билан И.

[Xaositect]

То есть рассматриваются СДНФ?

[bilan]

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

да, рассматриваются СДНФ.

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

[bilan]

Разве вопросов больше нет?

[Xaositect]

Я так и не смог разобраться, какие именно случаи Вы рассматриваете. Можете написать подробнее (случай 1: все команды машины суть OR, случай 2: последние $k$ команд - OR, остальные AND или как-то так) .

[bilan]

глубоко уважаемый Xaositect!
для рисунка 1: последние $s$ команд $OR$ число которых меньше чем $n^h$


для рисунка 2: в каких случаях мы можем использовать $AND$, число $OR$ здесь очевидно.

для рисунка 3, 4, 5: в каких случаях мы не можем использовать $AND$, то есть вынуждены использовать $OR$.

так как $AND$ мы можем использовать только в рисунке 2, то из этого следует оценка трудоемкости.

если хотите, мы можем обсудить это в скайпе.

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

[bilan]

глубоко уважаемый Xaositect!

если я все же не ответил на Ваш вопрос, то предлагаю обсудить в удобное для Вас время в скайпе или иной аналогичной программе.

думаю что это будет намного более эффективно.

пишите в личку, за 2-3 дня до предполагаемого разговора

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