Вот как звучит задача.
Цитата:
Consider the following formula in DNF.

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?
Задача лёгкая, если знать, то чего я не знаю. Что такое шаг? Возьмём к примеру формулу

Тогда у меня получается, что (пишу только атомы)
на 1-м шаге

на 2-м

на 3-м

на 4-м

на 5-м

...
Всего 8 шагов. То есть я прочитал формулу восем раз. И тогда ответ

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