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.
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.