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.

Improve this question
$\endgroup$
1
  • 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, 2014 at 16:18

1 Answer 1

Reset to default
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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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