Верблюд,

авторПредварительный этап решения заключается в унификации S1 и S2, так как унификация по
принципу действия сохраняет в структурахоперандах все существующие СВН и одновременно
минимизирует упомянутые структуры по числу элементов (строк). очень тяжело его читать, лирика неуместная :-(

он кажется задачу к 2-КНФ сводит (там всё доказано и решено), а как - непонятно

Верблюд,

я и говорю что лирики много, а самого главного нема

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

Верблюд,

но если вы правы, вы такой ящичек откроете, тынц

Верблюд,

а почему C(3, N) а не C(3, N) * 2^3 ?

Верблюд,

я в плане того спрашиваю, что троек то возможных не C(3,N), а в 8 раз больше (с учётом not-вариантов)

Верблюд,

это я пытаюсь понять "Описание алгоритма решения задачи 3-КНФ", что откуда и зачем

из этого текста очень сложно понять, без гугления, что 8 состояний комбинаций для каждой тройки {vi, vj, vk}, это:
{vi | vj | vk}, { vi | vj | vk}, {vi | vj | vk}, ...


в этом блоке осталось осилить
авторВекторы, соответствующие ограничениям 3-КНФ формулы помечаются как удаленные.это какие? которые входят в формулу? зачем удалённые?

Верблюд,

если перефразировать блок "Описание алгоритма решения задачи 3-КНФ" человеческим языком, выходит следующее утверждение

Любую 3-КНФ формулу из n переменных можно представить в виде вектора состоящего из 8 * C(3, N) бит

теперь про то, что вы говорите далее, про операции с эти вектором

Возможно ли, подставив значение N-й переменной, получить однозначное 3-КНФ уравнение из (N-1) переменных ?
и если возможно, то как это сделать

Верблюд,

вот в чём и фигня

(v1, v2, vn) & (v7, v16, vn)

vn = 1

левый можно удалить, куда девать правый?

Верблюд,

но вообще я один способ придумал, можно добавить в уравнение известные переменные, минимально достаточно двух

Верблюд,

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

Верблюд,

ничего особо не увеличит (кардинально во всяком случае), вместо 8*C(3,n) бит потребуется 8*C(3,n + 3)

например добавим 3 переменные (t0 = 0, t1 = 0, t2 =0) - это 7 известных соотношений.

Верблюд,

фактически можно хранить в развёрнутом виде только разницу 8* [C(3,n + 3) - C(3,n)] бит, так как исходные блоки не меняются

Верблюд,

я пытаюсь понять базовые операции, которые нам доступны
вполне очевидно, что понижение уровня уравнения довольно базовая вещь

Собственно невозможность подставки 1 натолкнула на мысль, что можно подставить не конкретно 1 или 0, а переменную.

Потом пришла мысль, что может получиться ситуация (vi, vi, vj) - что недопустимо, и я подумал, а почему бы не добавить соотношение которое однозначно задаёт переменные, количество решений это не увеличивает.
Т.е. это позволяет решить конкретную проблему: понижение уровня уравнения

Пойдём дальше:
из операции видно, что при подстановке всегда будет меняться только часть с включением этих добавленных переменных (помним, что для добавки достаточно 8* [C(3,n + 3) - C(3,n)] бит. ), что очень хорошо. Можно не хранить исходную функцию в развёрнутом виде, а просто помечать те переменные, которые уже найдены\предположены - и это можно сделать гораздо эффективнее (нужно лишь определиться с базовыми операциями).

Теперь вернёмся к тому, что говорит Aleksandr Sharahov
при подстановке у нас получается дробление на 2 ветки, Aleksandr Sharahov утверждает, что возможно задать такое уравнение
что при любой подстановке у вас не обнаружится коллизий и придётся опять дробить на 2. Логично, что в худшем случае вам придётся раздробиться на 2^N решений, что как бы уже относится к NP.

Отсюда следует простой вывод: чтобы не было дроблений, либо их количество было минимально нужен алгоритм определяющий по какой переменной стоит дробиться.

И я как бы не вижу у вас описание решения вопроса, который поднял Aleksandr Sharahov