1.
Complexity class
–
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form, the set of problems that can be solved by an abstract machine M using O of resource R, Complexity classes are concerned with the rate of growth of the requirement in resources as the input n increases. It is a measurement, and does not give time or space in requirements in terms of seconds or bytes. The O is read as order of, for the purposes of computational complexity theory, some of the details of the function can be ignored, for instance many possible polynomials can be grouped together as a class. The resource in question can either be time, essentially the number of operations on an abstract machine. The simplest complexity classes are defined by the factors, The type of computational problem. However, complexity classes can be defined based on problems, counting problems, optimization problems, promise problems. The resource that are being bounded and the bounds, These two properties are usually stated together, such as time, logarithmic space, constant depth. Many complexity classes can be characterized in terms of the logic needed to express them. Bounding the computation time above by some function f often yields complexity classes that depend on the chosen machine model. For instance, the language can be solved in time on a multi-tape Turing machine. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that the complexities in any two reasonable and general models of computation are polynomially related. This forms the basis for the complexity class P, which is the set of problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of problems is FP. The Blum axioms can be used to define complexity classes without referring to a computational model. Many important complexity classes can be defined by bounding the time or space used by the algorithm, some important complexity classes of decision problems defined in this manner are the following, It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitchs theorem. #P is an important complexity class of counting problems, classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems, many complexity classes are defined using the concept of a reduction

2.
AND gate
–
The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results if both the inputs to the AND gate are HIGH. If neither or only one input to the AND gate is HIGH, in another sense, the function of AND effectively finds the minimum between two binary digits, just as the OR function finds the maximum between two binary digits. Therefore, the output is always 0, except all the inputs are 1. There are three symbols for AND gates, the American symbol and the IEC symbol, as well as the deprecated DIN symbol, for more information see Logic Gate Symbols. The AND gate with inputs A and B and output C implements the logical expression C = A ⋅ B, an AND gate is usually designed using N-channel or P-channel MOSFETs. The digital inputs a and b cause the output F to have the result as the AND function. If no specific AND gates are available, one can be made from NAND or NOR gates, because NAND and NOR gates are considered the universal gates, AND gates are available in IC packages. 7408 IC is a famous QUAD 2-Input AND GATES and contains four independent gates each of which performs the logic AND function, OR gate NOT gate NAND gate NOR gate XOR gate XNOR gate IMPLY gate Boolean algebra Logic gate

3.
OR gate
–
The OR gate is a digital logic gate that implements logical disjunction – it behaves according to the truth table to the right. A HIGH output results if one or both the inputs to the gate are HIGH, if neither input is high, a LOW output results. In another sense, the function of OR effectively finds the maximum between two digits, just as the complementary AND function finds the minimum. There are two symbols of OR gates, the American symbol and the IEC symbol, as well as the deprecated DIN symbol, for more information see Logic Gate Symbols. OR Gates are basic logic gates, and as such they are available in TTL, the standard 4000 series CMOS IC is the 4071, which includes four independent two-input OR gates. The ancestral TTL device is the 7432, there are many offshoots of the original 7432 OR gate, all having the same pinout but different internal architecture, allowing them to operate in different voltage ranges and/or at higher speeds. In addition to the standard 2-Input OR Gate, 3- and 4-Input OR Gates are also available, if no specific OR gates are available, one can be made from NAND or NOR gates in the configuration shown in the image below. Any logic gate can be made from a combination of NAND or NOR gates, with active low open collector logic outputs, as used for control signals in many circuits, an OR function can be produced by wiring together several outputs. This arrangement is called a wired OR and this implementation of an OR function typically is also found in integrated circuits of N or P-type only transistor processes. AND gate NOT gate NAND gate NOR gate XOR gate XNOR gate Boolean algebra Logic gate

4.
Inverter (logic gate)
–
In digital logic, an inverter or NOT gate is a logic gate which implements logical negation. The truth table is shown on the right, an inverter circuit outputs a voltage representing the opposite logic-level to its input. Its main function is to invert the input signal applied, if the applied input is low then the output becomes high and vice versa. Inverters can be constructed using a single NMOS transistor or a single PMOS transistor coupled with a resistor, since this resistive-drain approach uses only a single type of transistor, it can be fabricated at low cost. However, because current flows through the resistor in one of the two states, the configuration is disadvantaged for power consumption and processing speed. Alternatively, inverters can be constructed using two complementary transistors in a CMOS configuration and this configuration greatly reduces power consumption since one of the transistors is always off in both logic states. Processing speed can also be improved due to the low resistance compared to the NMOS-only or PMOS-only type devices. Inverters can also be constructed with bipolar junction transistors in either a resistor–transistor logic or a transistor–transistor logic configuration, digital electronics circuits operate at fixed voltage levels corresponding to a logical 0 or 1. An inverter circuit serves as the logic gate to swap between those two voltage levels. Implementation determines the voltage, but common levels include for TTL circuits. The inverter is a building block in digital electronics. Multiplexers, decoders, state machines, and other sophisticated digital devices may use inverters, the hex inverter is an integrated circuit that contains six inverters. If no specific NOT gates are available, one can be made from NAND or NOR gates, because NAND and NOR gates are considered the universal gates, digital inverter quality is often measured using the voltage transfer curve, which is a plot of output vs. input voltage. From such a graph, device parameters including noise tolerance, gain, ideally, the VTC appears as an inverted step function – this would indicate precise switching between on and off – but in real devices, a gradual transition region exists. The VTC indicates that for low voltage, the circuit outputs high voltage, for high input. The slope of this region is a measure of quality – steep slopes yield precise switching. The tolerance to noise can be measured by comparing the input to the maximum output for each region of operation

5.
Dyck language
–
In the theory of formal languages of computer science, mathematics, and linguistics, the Dyck language is the language consisting of balanced strings of square brackets. It is important in the parsing of expressions that must have a nested sequence of brackets. It is named after the mathematician Walther von Dyck, let Σ = be the alphabet consisting of the symbols and let Σ ∗ denote its Kleene closure. Transitivity is clear from the definition, the equivalence relation partitions the language Σ ∗ into equivalence classes. If we take ϵ to denote the empty string, then the corresponding to the equivalence class Cl is called the Dyck language. An alternative definition of the Dyck language can be formulated when we introduce the i m b a l a n c e, Σ ∗ → function, imbalance = | u | for any u ∈ Σ ∗. Where | u | are respectively the number of in u, i. e. imbalance counts the imbalance of, if imbalance is positive then u has more. Now, the Dyck language can be defined as the language The Dyck language is closed under the operation of concatenation. By treating Σ ∗ as a monoid under concatenation we see that the monoid structure transfers onto the quotient Σ ∗ / R. The class Cl will be denoted 1, the syntactic monoid of the Dyck language is not commutative, if u = Cl and v = Cl then u v = Cl =1 ≠ Cl = v u. With the notation above, u v =1 but neither u nor v are invertible in Σ ∗ / R, the syntactic monoid of the Dyck language is isomorphic to the bicyclic semigroup by virtue of the properties of Cl and Cl described above. The Dyck language with two types of brackets can be recognized in the complexity class T C0. We can define an equivalence relation L on the Dyck language D, for u, v ∈ D we have ∈ L if and only if | u | = | v |, i. e. u and v have the same length. This relation partitions the Dyck language D / L = D0 ∪ D2 ∪ D4 ∪ … = ⋃ n =0 ∞ D n where D n =, note that D n is empty for odd n. There are 14 words in D8, i. e, having introduced the Dyck words of length n, we can introduce a relationship on them. For every n ∈ N we define a relation S n on D n, for u, v ∈ D n we have ∈ S n if, a proper swap in a word u ∈ D n swaps an occurrence of ][ with. For each n ∈ N the relation S n makes D n into an ordered set. The following table illustrates that σ n is strictly monotonic with respect to proper swaps, hence σ n − σ n =2 >0 so σ n < σ n when there is a proper swap that takes u into u ′

6.
AC0
–
AC0 is a complexity class used in circuit complexity. It is the smallest class in the AC hierarchy, and consists of all families of circuits of depth O and polynomial size, with unlimited-fanin AND gates and it thus contains NC0, which has only bounded-fanin AND and OR gates. Integer addition and subtraction are computable in AC0, but multiplication is not, in 1984 Furst, Saxe, and Sipser showed that calculating the parity of an input cannot be decided by any AC0 circuits, even with non-uniformity. It follows that AC0 is not equal to NC1, because a family of circuits in the class can compute parity. More precise bounds follow from switching lemma, using them, it has been shown that there is an oracle separation between the polynomial hierarchy and PSPACE