Минимальная экспоненция цепи дополнения

Я знаю, что это было доказано NP-Complete, и это нормально. Я в настоящее время решаю его с филиалом и связанным, где я устанавливаю начальный верхний предел на количестве умножений, он взял бы обычный двоичный квадрат / многоразовый алгоритм, и он дает правильные ответы, но я не удовлетворен бегом Время (это может занять несколько секунд для численности около 200). Это проблема с НП-полной проблемой, я не ожидаю ничего впечатляющего; Но часто есть трюки, чтобы несколько контролировать время.

Есть ли более быстрые способы сделать это на практике? Если так, то, что они?