Как я могу доказать, что преобразование из CNF в DNF является NP-Hard? Я не прошу ответа, просто несколько советов о том, как это
Аппликативный порядок: всегда полностью оценивайте аргументы функции перед оценкой самой функции, например: (λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x....
Я понимаю, что контекстно-свободные грамматики могут использоваться для представления контекстно-свободных языков. Это может иметь неоднозначность. У нас также есть нормальные формы, такие как нормальная форма Хомского и Грейбаха . Я не мог понять необходимость этого. Почему они важны в теории...
Относительно потока, Доказывающего, что преобразование из CNF в DNF является NP-Hard (и связанный математический поток ): Как насчет другого направления, от DNF до CNF? Это легко или сложно? На странице 2 этой статьи они, похоже, намекают на то, что оба направления одинаково трудны, когда говорят:...