# CNF to DNF — conversion is NP Hard

How can i prove that the conversion from CNF to DNF is NP-Hard. I'm not asking for an answer, just some suggestions about how to go about proving it.

-
NP-hardness is usually formulated only for decision problems -- i.e. where the result is single bit rather than a data structure. What is the definition of NP-hardness you seek to apply to CNF-to-DNF? I think there are simple examples where the size of the DNF is exponential in the size of the CNF (or vice versa), but that does not really help you solve an arbitrary NP problem, which is what NP-hard unsually requires. –  Henning Makholm Dec 14 '11 at 15:49
Im sorry I wasn't really clear in my question. Im trying show that the conversion from cnf-SAT to dnf-SAT is np-hard. –  sammy Dec 14 '11 at 16:06
That's doesn't really clear it up. What does it mean for such a conversion to be NP-hard? Or are you asking for a polynomial-time reduction from DNF-SAT to CNF-SAT? I don't think there is one; satisfying a DNF is easy. –  Henning Makholm Dec 14 '11 at 16:13
@HenningMakholm: “NP-hardness is usually formulated only for decision problems”: That claim is too general to be true. Some people prefer to consider Turing reducibility by default (although I do not). NP-hardness under Turing reducibility applies to function problems or relation problems as well as to decision problems. –  Tsuyoshi Ito Dec 14 '11 at 18:42
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8211674690246582, "perplexity": 429.8060225736683}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-22/segments/1432207928486.86/warc/CC-MAIN-20150521113208-00189-ip-10-180-206-219.ec2.internal.warc.gz"}