Algorithms For Dummies

  Performing Local Search 

     349

Computer circuits are composed of a series of connected components, each one 

opening or closing a circuit based on its inputs. Such elements are called logic gates 

(physically, their role is played by transistors) and if you build a circuit with many 

logic gates, you need to understand whether electricity can pass through it and 

under what circumstances.

Chapter 14 discusses the internal representation of a computer, based on zeros 

(absence  of  electricity  in  the  circuit)  or  ones  (presence  of  electricity).  You  can 

render  this  0/1  representation  from  a  logical  perspective,  turning  signals  into 

False

 (there isn’t electricity in the circuit) or 

True

 (there is indeed electricity) 

conditions.  Chapter  4  examines  the  Boolean  operators  (

AND

, 

OR

, and 

NOT

),  as 

shown in Figure 18-4, which work on 

True

 and 

False

 conditions as inputs and 

transform them into a different output. All these concepts help you represent a 

physical  electric circuit as a sequence of Boolean operators defining logic gates. 

The combination of all their conditions determines whether the circuit can carry 

electricity.

This logic representation is a Boolean combinational circuit, and the test to verify its 

functionality is the circuit satisfiability. In the easiest scenario, the circuit consists 

of only 

NOT

 conditions (called inverters) that accept one wire input, and 

OR

 condi-

tions that accept two wires as inputs. This is a satisfiability-two (2-SAT) scenario, 

and if the algorithm were to go through it using an exhaustive search, it would 

take at worst 

2

k

 trials (having k as the number of input wires) to find a set of con-

ditions that makes electricity pass through the whole circuit. There are even more 

complex versions of the problem, accepting more inputs for each OR logic gate 

and using AND gates, but they are beyond the scope of this book.