P = NP, a question that has tantalized mathematicians, complexity theorists and computer scientist for decades. If there is a problem that has a solution and that solution is easily verified by a computer, then can that same problem be solved quickly by a computer? The method of studying circuit complexity is proving to be the best ace in the hole for many computer scientists. Circuit complexity theory may become the instrument used to solve the most significant question placed by Clay Mathematics Institute, P = NP, and many other hard problems.
The purpose of this research is to explain the basics of circuit complexity so that a lay person will understand why it is used, survey a brief history of it, explain some of the more prominent uses of the theory and current standing concerning this technique with the P = NP problem. This will be accomplished by first giving a brief introduction to the methodology by identifying and explaining key terms and phrases. Then, giving a brief history of the study, how it could be used to solve P = NP and finally explaining the forays into various abstract applications. The methodology used to complete this study will be simple: peer reviewed articles will be used in explaining key terms, and textbooks on the subject will be utilized in explaining the possible P = NP proof. Multiple sources will be used to find current and future applications which will include secondary sources, e.g., related articles in the magazine Popular Mechanics.
The English mathematician George Boole may never have known the fingerprint he would leave on the future. Do we have giants in library and information science ? George Boole was a self-taught mathematician  who was indeed an intellectual giant. By the age of twenty-four he had already submitted papers to various mathematical journals . The Royal Society awarded him a metal at the age of twenty-nine in 1844. Boole was a strong supporter for unionizing the field of formula Logic and mathematics in which he wrote his paper Mathematical Analysis of Logic . He believed that the study of logic was more closely associated with mathematics rather than metaphysics and philosophy.
In 1938, Claude E. Shannon was an aspiring research assistant at MIT (Massachusetts Institute of Technology) he began studying the similarities between Boolean algebra and telephone switching circuits. Telephone switching was a process which was done manually by an operator. They would make a physical connection between two parties so that they could communicate with each other. Boolean algebra has a couple main differences compare to conventional algebra. Boolean algebra has only two symbols to represent the language: 1 and 0. The other main difference is that the + symbol is analogized with an AND and an OR. The AND is exclusive to idea that both values must be true in order to result in a true statement. The OR operator formulates the idea that only one of the values needs to be true in order to make the statement true. The final operator is formulated with a NOT symbol which is represented with a bar over the representative value indicating the opposite of the value. The principles of Boolean algebra and telephone switching became known as algebraic circuits .
Boolean circuits seemingly expand across the infinite possibilities of the reaches of mathematical models. Specifically, a Boolean circuit is an aggregation of gates, inputs and outputs. Boolean circuits have one of the unique traits of being simple yet continuously complex. An entire expanse of study as evolved around them, insomuch that circuit complexity has because a field of study. Circuit complexity has volumes of books such that an entire library section could be devoted to it. This study will remain in the breadth of this subject, and allow the reader to devote their own time to researching the
depth of its possibilities.
The genesis of circuit complexity is based on the size of a circuit, depth of a circuit and circuit families. The size of a circuit is simply the number of gates in a circuit. The depth is the longest wire from an input to the output. A family arises due to the problem of having a fixed number of inputs for a specific circuit. Therefore, any particular circuit can handle only inputs of some fixed length, whereas a language may contain strings of different lengths. So instead of using a single circuit to test language membership, we use an entire [family] of circuits, one for each input length, to perform this task . The heart of circuit complexity lies in classifying problems into complexity classes. There is a plethora of complexity classes.
The main complexity classes concerned with this study will all be time complexity classes. The primary ones discussed are polynomial time, nondeterministic polynomial time, and AC. AC is a complexity class that exists for circuit complexity and consists of all problems that are recognized by a Boolean circuit with a circuit depth of O(login). It has a polynomial number of unlimited fan-in AND, OR and NOT gates. A fan-in gate of 3 would be a gate, e.g., an AND gate that has 3 inputs. Polynomial time problems exist in everyday natural life. It essential concerns problems that take a reasonable amount of time to solve on a computer. Essentially, a non-determinist polynomial time problem is one that takes an exorbitantly long time to solve on a computer. A classic example of this is factoring a given number. This is simple at first but becomes very hard for very large numbers. It is important to classify problems into their respect categories because understanding problems’ complexity classes gives insight to the problem.
Circuit complexity acts as a tool to classify problems. There are many parts of circuit complexity that this study will not have time to discuss. It is strongly recommended that the reader take time to understand a little more about circuit complexity. Such that they can more fully comprehend the incompleteness of this brief survey.
There are various practical reasons for studying circuits. They give one the ability to talk about finite measurements of a problem. For example, Let INTEGER − FACTORING1024 be the problem of finding a prime factorization of a given 1024-bit integer n. After the encoding of numbers and factorizations have been fixed, it is sensible to ask: what is CU2(INTEGER − FACTORING1024)? Is it at most 1010 ? This gives one the ability to discuss problems with a finite input. In contrast if one were to discuss a finite problem given to a Turing machine to solve, the Turing machine could simply solve the problem in linear time. It could simply embed a huge lookup table for each instance of the problem in the transition table of the Turing machine .
Another benefit of circuit complexity is the separation of complexity classes through discovering lower bounds of circuits. Essentially, if there is a problem with easy functions that still require very large circuits we can classify the complexity of the problem. Likewise, the upper bound of a circuit can also classify a problem if the given problem has very hard functions, but the circuits are small then one can classify the problems’ complexity. There are many reasons to use circuit complexity, and likewise there are various methods to using it. The main methods used in circuit complexity are restriction methods, polynomial methods and brute force methods.
Brute force methods are the simplest in idea. To brute force something one must begin without any prior help or knowledge, and then begin trying all the permutations in hopes of finding a solution. A function or problem is made that is intended to not be computable by a circuit with the same complexity. If one can prove that a circuit with the same complexity cannot compute a problem of the same complexity, then it can be induced that the problem in not in that complexity class. This is an iterative process where a function is given to a circuit and if that circuit can compute it then a slightly harder version is given until the circuit cannot compute it, i.e., return an output of TRUE.
The polynomial method works by constructing a circuit that has polynomial complexity. Once this is done then one uses this circuit to compute polynomial problems. If the problem cannot be computed, i.e., the circuit returns a FALSE then the problem is proven to not be in the polynomial time complexity class. The restriction method works by using multiple functions on a circuit and then simplifying the circuit. The n-bit functions are selected and related to k-bits such that k ¡ n. Some of the n-bits are set to a constant value, and then the circuit is simplified through means such as gate elimination.
This is simply when a gate is eliminated from the circuit whilst causing the circuit to still yield equivalent results. Essentially, this process continues until the circuit becomes too simple to compute a function on k-bits. Hence, the circuit is restricted in what if can compute.
P v. NP
What does circuit complexity have to do with P (polynomial time) and NP (non-determinist polynomial time)? The simple answer is; it has everything to do with P vs. NP. Circuit complexity has very strong techniques that have been utilized to figuratively chip away at the P vs. NP question. In order to fully appreciate this conundrum a short discussion will give concerning it.
The biggest implications of P vs. NP are currently in the field of security. Specifically, computer security. RSA is an encryption algorithm that is in the class of NP. This means that there is currently no known solution to RSA that can be done in any reasonable amount of time on a computer. Although there is no known solution, it is not yet proven. For this reason, it remains possible that there might still be a solution to RSA. Most of the scientific community believes that P != NP as noted in the following quote by Sipser:
This is the situation with so called exhaustive search problems, including: the minimization of Boolean functions, the search for proofs of finite length, the determination of the isomorphism of graphs, etc. All of these problems are solved by trivial algorithms entailing the sequentized scanning of all possibilities. The operating time of the algorithm is, however, exponential, and mathematicians nurture the conviction that it is impossible to find simpler algorithms .
There are a variety of problems that are assumed to be in the class NP and if they were found to not be in NP then the results would be immense. G¨odel presented this same idea to von Neumann:
Since you now, as I hear, are feeling stronger, I would like to allow myself to write you about a mathematical problem, of which your opinion would very much interest me: One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let Ψ(F, n) be the number of steps the machine requires for this and let φ(n) = maxFΨ(F, n). The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k · n. If there really were a machine with φ(n) ∼ k · n (or even ∼ k · n2), this would have consequences of the greatest importance 
If it were possible that RSA was not in NP then encrypted bank account information could be gathered easily, confidential business acquisition could be discovered and of course classified government communication could be easily eavesdropped. Circuit Complexity was once thought of as the means to an end. Unfortunately, after much research and inadequate results most believe that circuit complexity is no longer the path to an answer. Most researches have turned to a technique called approximation methods in order to try analyze circuits and hopefully come to a conclusion regarding NP class problems.