Question

Assume that the Boolean circuit satisfiability program works in linear time Θ(m), where m is the number of gates and/or wires in the Boolean circuit. How fast can you determine if a formula with n connectives is satisfiable? Justify.

Answer 1

An example of the boolean circuit is attached below

Explanation:

A boolean formula can be expressed with some information which are as follows:

· Number of input and output

· Number of gates

The input wires can be expressed as input boolean variables. The output decision of both circuit evaluation and boolean formula evaluation will be same.

Since the circuit evaluation can be done in the linear time Θ(n). Thus, the boolean formula of size n can also be evaluated in the linear time Θ(n).

For example: The following boolean circuit will be evaluated as follows:

The AND operation of input wires a1 and a2 will be the result of output wire o1. Similarly, its boolean formula can be expressed as follows:

01 = a1 ∧ a2

The boolean circuit and boolean formula will take same time for their respective evaluations. The time taken to evaluate a circuit depends upon the number of gates/ or wires. The time taken to evaluate a boolean formula depends upon the number of connectivities or wires.

Since both implementations depends upon the number of connections in the circuit. Thus, a boolean formula of size n will be evaluated in the same time i.e., Θ(n) as of the boolean circuit.