Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Сколько шагов КНФ-алгоритма?
СообщениеДобавлено: 06 дек 2012, 12:45 
Не в сети
Одарённый
Зарегистрирован:
06 дек 2012, 12:40
Сообщений: 173
Откуда: Кишинёв
Cпасибо сказано: 2
Спасибо получено:
57 раз в 52 сообщениях
Очков репутации: 32

Добавить очки репутацииУменьшить очки репутации
Вот как звучит задача.
Цитата:
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". Правильно?

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ 1 сообщение ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задачка на минимальное количество шагов

в форуме Интересные задачи участников форума MHP

Abra-Kadabra

38

1823

17 июн 2015, 03:44

Двойной обход произвольного треугольника за 10 шагов

в форуме Размышления по поводу и без

bitango

0

67

04 фев 2024, 16:19

Cемь шагов вокруг совершенного кирпича

в форуме Дискуссионные математические проблемы

3axap

135

4110

26 май 2019, 19:34

Верена ли классификация алгоритма

в форуме Информатика и Компьютерные науки

crub34

2

288

04 июн 2021, 08:54

Delphi Составление алгоритма

в форуме Информатика и Компьютерные науки

Ha1t

5

553

18 авг 2014, 13:52

Не понимаю алгоритма решения

в форуме Алгебра

drinke81

16

264

13 дек 2022, 16:13

Оценка сложности алгоритма сравнения

в форуме Численные методы

sscarecrow

0

209

23 сен 2018, 16:37

Составить блок схему алгоритма(2)

в форуме Пределы числовых последовательностей и функций, Исследования функций

PavelSH

1

58

31 окт 2023, 17:23

Составить блок схему алгоритма

в форуме Пределы числовых последовательностей и функций, Исследования функций

PavelSH

0

59

31 окт 2023, 17:21

Сумма ряда для анализа алгоритма

в форуме Ряды

sunflower

6

306

28 фев 2017, 21:48


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved