0
$\begingroup$

Intro

Hi, I'm a hobbyist, with no formal education, tinkering with SAT solving and boolean algebra minimization. So expect bad terminology. I hope you will forgive me I'm asking a wrong question in a wrong place. I'll give it a shot.

Question

Essentially I'm trying to find the most "complex"/"chaotic"/"highest entropy" truth tables of some sizes (>32 bits / >5 vars). I'm asking if it would be possible to find such functions without enumeration and how to go about getting there?

Complex in what context? Complexity would mean the size of some representation other than the truth table itself. So let's say the complexity of a function is the size of the function's optimal CNF/DNF or NNF representation with "temp vars"(to avoid the exponential growth in certain cases like XORs).

Number of clauses in case of CNF/DNF, number of temp vars in case of NNF. Don't know if those can be called CNF and NNF anymore but I hope you get what I mean.

I'm more used to a NNF-like representation without ORs. Where (a+b).(a'+b') would be described in the following way:

  • 0 = a'.b'
  • 1 = a.b
  • 2 = 0'.1'

Application / Why I'm asking?

I'm looking for a way to find and analyse cases (preferably similar) where the optimal representation in the And-inverter graph structure would start to grow exponentially as the size of the truth table increases and it would get way bigger than the truth table itself. Just like it happens with XORs in CNF/DNF structure.

$\endgroup$
  • 2
    $\begingroup$ Here is a hint to simplify your search. What you describe in the last part of your question is known under the name "AND-inverter Graph" as the possibility to have intermediate variables basically corresponds to the possibility to have intermediate nodes in a Boolean circuit. Related is also the term "circuit complexity", which you might want to look up on wikipedia or the like. $\endgroup$ – DCTLib Jan 7 '14 at 16:18
3
$\begingroup$

Pick one at random.

If it is random, then there is no way to compress the representation. You have to store the entire truth table.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

$\endgroup$
  • $\begingroup$ Thanks. I guess random is a good alternative for a start, that I didn't think of. $\endgroup$ – Ivarpoiss Jan 7 '14 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.