Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ 1 сообщение ] |
|
Автор | Сообщение | |
---|---|---|
gefest |
|
|
Цитата: Consider the following formula in DNF. [math](A_1\wedge B_1)\vee(A_2\wedge B_2)\vee\dots\vee(A_n\wedge B_n)[/math] 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? Задача лёгкая, если знать, то чего я не знаю. Что такое шаг? Возьмём к примеру формулу [math](A_1\wedge B_1)\vee(A_2\wedge B_2)\vee(A_3\wedge B_3)[/math] Тогда у меня получается, что (пишу только атомы) на 1-м шаге [math]A_1A_2A_3[/math] на 2-м [math]A_1A_2B_3[/math] на 3-м [math]A_1B_2A_3[/math] на 4-м [math]A_1B_2B_3[/math] на 5-м [math]B_1...[/math] ... Всего 8 шагов. То есть я прочитал формулу восем раз. И тогда ответ [math]2^n[/math] и алгоритм не "polynomial-time". Правильно? Рассуждал также следующим образом. Беру первые два конъюнкта и составляю из них маленькую КНФ. Дальше «поглощаю» третий конъюнкт и получаю новую КНФ и так с каждым последующим конъюнктом. |
||
Вернуться к началу | ||
[ 1 сообщение ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |