Необходимо сгенерировать случайную систему нелинейных булевых уравнений от n  переменных (n>50), которая имела бы единственное или некоторое фиксированное количество (2, 3,..., m) известных решений. Хотя бы в общих чертах опишите, как это можно сделать. Перебор исключаем 

Очень просто.

пишем

x1x2=0
x2x3=1
x3x4=0
...
и т.д.


единственное решение
x1=0
x2=1
x3=1
x4=0
...

Во-первых, как таком подходе создать систему, имеющую, например 2 решения.
Во-вторых, решение задано изначально, например, не 0110, а 1111.
В-третьих,  системы, получаемые таким образом будут довольно однообразны, а необходимы как можно более случайные. То есть, к примеру на одно решение 10101010 в одном случае нужно 2 конъюнкции в первом уравнении, а в другом 100. С этим, понятное дело, можно будет бороться в процессе реализации, но все-таки...
Есть идея изначально представлять систему в виде векторов 
10011010
10110010
10100110
а затем как-то хитро переводить ее в другую форму
Только дальше идеи как-то не двигается :(

можно в форме ДНФ искать, тогда будет любое нужное число решений.

Дело в том, что я всей задачи не знаю.
Тут могут быть разные условия.

Например, может быть так, вполне допускается решать одно уравнение или несколько.
Тогда можно это одно или несколько уравнений сгенерировать так случайно как надо.
Решить. Посчитать количество решений. А остальные уравнения подогнать, используя какую-нибудь простую схему.

Или может быть эвристический поиск подойдёт. Одно сгенерировали, решили, посчитали количество решений, дальше  строим следующее уравнение.
Дальше решаем уже систему. Если решений стало меньше чем нужно, второе уравнение убираем. И так пока не будет ровно столько сколько нужно решений.

Ещё вариант построить какую-то линейную систему с одним решением и начать её усложнять, внося нелинейность.

Тут задача не поставлена до конца. Какие-то идеи я бросил, а так может быть и совсем подругому. 

Я пытался построить в форме ДНФ примерно так:
строим вектор со значениям x и f вначале одинаково по натуральному порядку(чтобы гарантированно получить разные значения функций, хотя натуральный порядок не принципиален):
x1x2x3|f1 f2 f3
0  0  0 |0  0  0 |
0  0  1 |0  0  1 |
0  1  0 |0  1  0 |
...        |...        |
1  1  1 |1  1  1 |
Затем случайно перемешиваем значения функций и выбираем "понравившееся решение"
x1x2x3|f1 f2 f3
0  0  0 |0  0  1 |
0  0  1 |0  1  1 |
0  1  0 |0  0  0 |
...        |...        |
1  1  1 |1  0  1 |
Заменяем еще несколько (сколько надо) значений функций на набор из нашего решения
x1x2x3|f1 f2 f3
0  0  0 |0  0  1 |
0  0  1 |0  1  1 |
0  1  0 |0  0  0 |
...        |...        |
1  1  1 |0  1  1 |
Строим ДНФ и как-нибудь малость минимизируем. Получаем примерно так:

x1-x3 v x2x3 v -x1x2-x3=0
x1x2 v x1-x3 v x2-x3=1
-x1x3 v x2-x3=1
Только вышло довольно громоздко: время на генерацию зашкаливает, а генерация вектора с наборами x при n>24 вышибает программу... Можно ли как-то оптимизировать такой подход

Да прям случайно выбираем решение.
Например, выбралось 1010 и 0110.
И пишем ответ: x1-x2x3-x4 v -x1x2x3-x4=1.

Дальше можно заполнить систему мусором. Например, так,

x1x2x3x4 = 0
x1-x2x3-x4 + x1x2x3x4= 1
-x1x2x3-x4 + 1 = 0

Ну и продолжать по каким-то алгоритмам до того пока не набирётся требуемое колличество конъюнкций.

Не факт, что если не придумать какой-то хитрый алгоритм отслеживания верных решений, что какое-то из них не просочиться. Забить мусором тоже не так-то просто - в конечном итоге получиться закономерность как у Вас - повторение определенных наборов (и последнее уравнение не верно на наборе 1, если, это конечно не случайность). Я сейчас использую довольно простую схему - создаю левую часть системы, вгоняю нужный набор, получаю правую часть и почти гарантированное получаю более одного решения.

Да я там ошибся.
Надо аккуратнее.

x1x2x3x4 = 0
(x1-x2x3-x4 v -x1x2x3-x4) + x1x2x3x4= 1
(x1-x2x3-x4 v -x1x2x3(1-x4)) + 1 = 0

Вы просили оптимизировать. Схема с забиванием мусором не простая, зато очень быстрая. Используя всякие разные тождества можно получить сколь угодно длинные формулы.


Это сообщение отредактировал(а) nworm - 12.9.2009, 16:41

"Небольшая" поправочка - вместо операции дизъюнкции в уравнениях берется сложение mod 2. Т.е. 
не х1х2 v x2x3, а х1х2 + x2x3. Итого используются только операции &, - и +

для замусоривания это хорошо.
будет не
х1х2 v x2x3, а значительно длиннее
х1х2 + x2x3 + (х1х2 & x2x3)

поскольку
x v y = x + y + xy

но может у Вас там какая-то минимизация нужна (хотя и не полна, иначе бы Вы просто случайные решения выписывали.)

а так да, задача не поставлена пока, нет математической постановки задачи.

Задача вкратце вот в чем - был написан алгоритм (генетический), который позволяет находить решения СНБУ. Алгоритм был опробован на различных системах и при определенных структурах решения и вида левой части системы позволяет находить ответ за полиномиальное время для систем до 60 переменных(дальше пока не вижу смысла двигаться, пока не решу проблему генератора). Но при определенных исходных алгоритм "встает"(например, не нравится ему почему-то решения, имеющие закономерности в последовательностях 0 и 1). Вот и хотелось бы создать генератор, позволяющий составлять системы 
1 с определенным видом и количеством решений. 
2 с определенным, так скажем, "состоянием линеаризации" уравнений 
3 наличие минимальных функций в качестве уравнений и я думаю со временем еще чего-нибудь
и уже затем производить оптимизацию, изучение, оценки и тп. Глобально задача стоит в экспериментальном рассмотрении свойств пространства, на котором ведется поиск решения, но это уже далеко "потом". В общем-то время терпит, никуда не тороплюсь, поэтому пока интересен пункт 1.

Добавлено @ 16:25
Не от руки же их вбивать 

Это сообщение отредактировал(а) dengalf - 16.9.2009, 16:39

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

хотя может кто-то что-нибудь поинтереснее предложит...

Модератор:  вопрос про решение системы выделен сюда: http://forum.vingrad.ru/forum/topic-283920.html