2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 По поводу решаемости задачи SAT
Сообщение18.05.2009, 23:06 
Для любой булевой функции (БФ) Y(x1,…, xi,…,xm) существует «интегральная функция»,
с помощью которой можно за 2*m шагов получить одно из решений уравнения
Y(x1,…, xi,…,xm) = 1
и за один шаг определить, имеет ли данная БФ хоть одно ненулевое значение.
Данная БФ принадлежит к классу, для которого существует "приемлемо компактная" форма представления. Предполагается, что ее «интегральная функция» также имеет "приемлемо компактную" форму представления.
Для бесповторных БФ это уже доказано.
Для небесповторных БФ вопрос компактной формы «интегральной функции» следует искать в области упрощения символьных выражений (компьютерная алгебра), где утверждается, что не существует общего метода упрощения для всех классов символьных выражений.
http://www.diary.ru/~Organon/p68635357.htm
Это имеет какую-то научную ценность?

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group