<p>Pick one at random. </p>

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

<p><a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow">http://en.wikipedia.org/wiki/Kolmogorov_complexity</a></p>

CC BY-SA 3.0
2014-01-07T17:39:17.150Z
Thanks. I guess random is a good alternative for a start, that I didn't think of.
Ivarpoiss
CC BY-SA 4.0
2024-03-04T23:27:55.127Z
What is the function space? You can't pick a random function from an infinite space. This is not well defined!?
mti
CC BY-SA 3.0
2014-01-07T16:35:30.520Z
2014-01-07T16:35:30.520Z
Chad Brewbaker
<p><strong>Intro</strong></p>

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

<p><strong>Question</strong></p>

<p>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?</p>

<p><strong>Complex in what context?</strong> 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). </p>

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

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

<ul>
<li>0 = a'.b'</li>
<li>1 = a.b </li>
<li>2 = 0'.1'</li>
</ul>

<p><strong>Application / Why I'm asking?</strong></p>

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

CC BY-SA 3.0
2014-01-07T16:18:46.397Z
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.
DCTLib
<sat><boolean-functions><gr.group-theory>
How to go about finding the most "complex" function?
Ivarpoiss
# How to go about finding the most "complex" function?

(Asked by: username_0 on 2014-01-07)

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

**Tags:** sat, boolean-functions, gr.group-theory

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-01-07. Score: 3

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>

> **Comments:**
> **username_0**: Thanks. I guess random is a good alternative for a start, that I didn't think of.  
> **username_3**: What is the function space? You can't pick a random function from an infinite space. This is not well defined!?  

---

