сколько шагов КНФ-алгоритма?

[gefest_md]

Вот как звучит задача.

Цитата:

Consider the following formula in DNF.

$$(A_1\wedge B_1)\vee(A_2\wedge B_2)\vee\dots\vee(A_n\wedge B_n)$$

Given this formula as input, how many steps will it take the CNF algorithm to halt and output a formula in CNF? Is this algorithm polynomial-time?

Задача лёгкая, если знать, то чего я не знаю. Что такое шаг? Возьмём к примеру формулу

$$(A_1\wedge B_1)\vee(A_2\wedge B_2)\vee(A_3\wedge B_3)$$

Тогда у меня получается, что (пишу только атомы)
на 1-м шаге $A_1A_2A_3$
на 2-м $A_1A_2B_3$
на 3-м $A_1B_2A_3$
на 4-м $A_1B_2B_3$
на 5-м $B_1...$
...
Всего 8 шагов. То есть я прочитал формулу восем раз. И тогда ответ $2^n$ и алгоритм не "polynomial-time". Правильно?

Рассуждал также следующим образом. Беру первые два конъюнкта и составляю из них маленькую КНФ. Дальше «поглощаю» третий конъюнкт и получаю новую КНФ и так с каждым последующим конъюнктом.