Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 468
  • Last Modified:

CNF->DNF: exponential blowup?

I am looking for a small (about 5 atoms/variables) and simple CNF (Conjunctive Normal Form) expression that (obviously?) blows up exponentially when converting to DNF. There should be no equivalent DNF that is small. I know that the CNF I am looking for exists.
0
alberthendriks
Asked:
alberthendriks
  • 2
1 Solution
 
d-glitchCommented:
This paper suggests that one candidate would be the conjunction of parity functions.

See Section 2 -- Functions with Large Blowup

                            http://eccc.uni-trier.de/eccc-reports/2003/TR03-017/Paper.pdf
0
 
alberthendriksAuthor Commented:
It seems more difficult than I thought. Could you (or someone else) write out this CNF? I'm not sure if I could work it all out (maybe with the help of Google but that would take time), but all I really want is one such CNF. (points increased).
0
 
alberthendriksAuthor Commented:
Never mind. A conjunction of parity functions is not so difficult.
+ = or
* = and
! = not

(a+b) * (!a+!b) * (c+d) * (!c+!d) * (e+f) * (!e+!f)

And (ofcourse) is blows up indeed.
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now