Здравствуйте.

Есть "большое" булевское дерево - в узлах операции, а листья - события. 
Надо, пробежав по дереву, построить булевское выражение.

Есть базовый реккурсивный алгоритм, он реализован и прекрасно работает на "маленьких" деревьях.

Проблема: "Последние" операторы AND, где приходится перемножать уже большие выражения, например 2000 термов на 3000 термов, то есть получается 6 миллионов, а это уже жрет приличное время.

Вопрос: Существуют ли какие-нибудь оптимизированные алгоритмы на подобный случай?

Спасибо.

А какое булево выражение вы хотите получить? В смысле какие к нему требования? Если любой корректный вид, то просто запишите дерево и все. А вот если Вам нужны Дизъюнктивная или Конъюнктивная нормальная форма, тогда все веселее.
Какое у Вас число независимых переменных? Поскольку Конъюнктивная нормальная форма может содержать до 2^n слагаемых, где n - число независимых переменных.

Уточните задачу, а еще лучше приведите пример маленького дерева и правильного ответа 

Почему перемножать то? Когда сложение должно быть.