Combinatorial Problems

Time vs memory ⚔️

Imagine if we had a bit calculator that looks something like this:  

 

The horizontal lines are the inputs to the calculator. The calculator takes the variables \(x\) as input and gives some output. If we wanted to determine the best answer for an output, we would need to run the circuit for all the possible input bitstrings, which is \(T_{bit} = 2^4\) times.

Alternatively, if we wanted to run all the bit strings simultaneously, we would need access to more inputs (more horizontal lines) as well as \(T_{bit} = 2^4\) bit calculators. This would look something like this:  

 

In the first case, we require computational time that is proportional to \(T_{bit}\).

In the second case, we require computational memory that is proportional to \(T_{bit}\).

 

Combinatorial Explosion! 💥

With increasing \(n\), the total number of combinations rises rapidly for the function \(2^n\). If we wanted to compute the best solution for ditstrings, the functions for the larger degrees of freedom \(3^n\),\(4^n\) and \(5^n\) rises more rapidly than for bitstring problems.