1.
Computational complexity theory
–
A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Other complexity measures are used, such as the amount of communication, the number of gates in a circuit. One of the roles of computational complexity theory is to determine the limits on what computers can. Closely related fields in computer science are analysis of algorithms. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources, a computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a problem is referred to as a problem instance. In computational complexity theory, a problem refers to the question to be solved. In contrast, an instance of this problem is a rather concrete utterance, for example, consider the problem of primality testing. The instance is a number and the solution is yes if the number is prime, stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input. For this reason, complexity theory addresses computational problems and not particular problem instances, when considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet, as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices and this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the objects of study in computational complexity theory. A decision problem is a type of computational problem whose answer is either yes or no. A decision problem can be viewed as a language, where the members of the language are instances whose output is yes. The objective is to decide, with the aid of an algorithm, if the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input. An example of a problem is the following
2.
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
3.
NP (complexity)
–
In computational complexity theory, NP is a complexity class used to describe certain types of decision problems. Informally, NP is the set of all decision problems for which the instances where the answer is yes have efficiently verifiable proofs, more precisely, these proofs have to be verifiable by deterministic computations that can be performed in polynomial time. Equivalently, the definition of NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. This second definition is the basis for the abbreviation NP, which stands for nondeterministic, however, the verifier-based definition tends to be more intuitive and practical in common applications compared to the formal machine definition. A method for solving a problem is given in the form of an algorithm. In the above definitions for NP, polynomial time refers to the number of machine operations needed by an algorithm relative to the size of the problem. Polynomial time is therefore a measure of efficiency of an algorithm, decision problems are commonly categorized into complexity classes based on the fastest known machine algorithms. As such, decision problems may change if a faster algorithm is discovered. The most important open question in complexity theory, the P versus NP problem, asks whether polynomial time algorithms actually exist for solving NP-complete and it is widely believed that this is not the case. The complexity class NP is also related to the complexity class co-NP, whether or not NP = co-NP is another outstanding question in complexity theory. The complexity class NP can be defined in terms of NTIME as follows, alternatively, NP can be defined using deterministic Turing machines as verifiers. In particular, the versions of many interesting search problems. In this example, the answer is yes, since the subset of integers corresponds to the sum + +5 =0, the task of deciding whether such a subset with sum zero exists is called the subset sum problem. To answer if some of the integers add to zero we can create an algorithm which obtains all the possible subsets, as the number of integers that we feed into the algorithm becomes larger, the number of subsets grows exponentially and so does the computation time. However, notice that, if we are given a subset, we can easily check or verify whether the subset sum is zero. So if the sum is indeed zero, that particular subset is the proof or witness for the fact that the answer is yes, an algorithm that verifies whether a given subset has sum zero is called verifier. More generally, a problem is said to be in NP if there exists a verifier V for the problem. Given any instance I of problem P, where the answer is yes, there must exist a certificate W such that, given the ordered pair as input, furthermore, if the answer to I is no, the verifier will return no with input for all possible W
4.
Decision problem
–
In computability theory and computational complexity theory, a decision problem is a question in some formal system that can be posed as a yes-no question, dependent on the input values. For example, the given two numbers x and y, does x evenly divide y. is a decision problem. The answer can be yes or no, and depends upon the values of x and y. A method for solving a problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the problem given two numbers x and y, does x evenly divide y. would give the steps for determining whether x evenly divides y. One such algorithm is long division, taught to school children. If the remainder is zero the answer produced is yes, otherwise it is no, a decision problem which can be solved by an algorithm, such as this example, is called decidable. The field of computational complexity categorizes decidable decision problems by how difficult they are to solve, difficult, in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of theory, meanwhile, categorizes undecidable decision problems by Turing degree. A decision problem is any arbitrary yes-or-no question on a set of inputs. Because of this, it is traditional to define the decision problem equivalently as and these inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet or over some other finite set of symbols. The subset of strings for which the problem returns yes is a formal language, alternatively, using an encoding such as Gödel numberings, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. A classic example of a decision problem is the set of prime numbers. It is possible to decide whether a given natural number is prime by testing every possible nontrivial factor. Although much more efficient methods of primality testing are known, the existence of any method is enough to establish decidability. A decision problem A is called decidable or effectively solvable if A is a recursive set, a problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Problems that are not decidable are called undecidable, the halting problem is an important undecidable decision problem, for more examples, see list of undecidable problems. Decision problems can be ordered according to many-one reducibility and related to feasible reductions such as polynomial-time reductions
5.
Turing machine
–
Despite the models simplicity, given any computer algorithm, a Turing machine can be constructed that is capable of simulating that algorithms logic. The machine operates on an infinite memory tape divided into discrete cells, the machine positions its head over a cell and reads the symbol there. The Turing machine was invented in 1936 by Alan Turing, who called it an a-machine, thus, Turing machines prove fundamental limitations on the power of mechanical computation. Turing completeness is the ability for a system of instructions to simulate a Turing machine, a Turing machine is a general example of a CPU that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a capable of enumerating some arbitrary subset of valid strings of an alphabet. Assuming a black box, the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program and this is due to the fact that the halting problem is unsolvable, which has major implications for the theoretical limits of computing. The Turing machine is capable of processing an unrestricted grammar, which implies that it is capable of robustly evaluating first-order logic in an infinite number of ways. This is famously demonstrated through lambda calculus, a Turing machine that is able to simulate any other Turing machine is called a universal Turing machine. The thesis states that Turing machines indeed capture the notion of effective methods in logic and mathematics. Studying their abstract properties yields many insights into computer science and complexity theory, at any moment there is one symbol in the machine, it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, however, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings, the Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can read and write, one at a time, in the original article, Turing imagines not a mechanism, but a person whom he calls the computer, who executes these deterministic mechanical rules slavishly. If δ is not defined on the current state and the current tape symbol, Q0 ∈ Q is the initial state F ⊆ Q is the set of final or accepting states. The initial tape contents is said to be accepted by M if it eventually halts in a state from F, Anything that operates according to these specifications is a Turing machine. The 7-tuple for the 3-state busy beaver looks like this, Q = Γ = b =0 Σ = q 0 = A F = δ = see state-table below Initially all tape cells are marked with 0. In the words of van Emde Boas, p.6, The set-theoretical object provides only partial information on how the machine will behave and what its computations will look like. For instance, There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and writing symbols indefinitely
6.
Formal language
–
In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it. The alphabet of a language is the set of symbols, letters. The strings formed from this alphabet are called words, and the words belong to a particular formal language are sometimes called well-formed words or well-formed formulas. A formal language is defined by means of a formal grammar such as a regular grammar or context-free grammar. The field of language theory studies primarily the purely syntactical aspects of such languages—that is. Formal language theory sprang out of linguistics, as a way of understanding the syntactic regularities of natural languages. The first formal language is thought to be the one used by Gottlob Frege in his Begriffsschrift, literally meaning concept writing, axel Thues early semi-Thue system, which can be used for rewriting strings, was influential on formal grammars. The elements of an alphabet are called its letters, alphabets may be infinite, however, most definitions in formal language theory specify finite alphabets, and most results only apply to them. A word over an alphabet can be any sequence of letters. The set of all words over an alphabet Σ is usually denoted by Σ*, the length of a word is the number of letters it is composed of. For any alphabet there is one word of length 0, the empty word. By concatenation one can combine two words to form a new word, whose length is the sum of the lengths of the original words, the result of concatenating a word with the empty word is the original word. A formal language L over an alphabet Σ is a subset of Σ*, that is, sometimes the sets of words are grouped into expressions, whereas rules and constraints may be formulated for the creation of well-formed expressions. In computer science and mathematics, which do not usually deal with natural languages, in practice, there are many languages that can be described by rules, such as regular languages or context-free languages. The notion of a formal grammar may be closer to the concept of a language. By an abuse of the definition, a formal language is often thought of as being equipped with a formal grammar that describes it. The following rules describe a formal language L over the alphabet Σ =, Every nonempty string that does not contain + or =, a string containing = is in L if and only if there is exactly one =, and it separates two valid strings of L. A string containing + but not = is in L if, no string is in L other than those implied by the previous rules
7.
Polynomial
–
In mathematics, a polynomial is an expression consisting of variables and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents. An example of a polynomial of a single indeterminate x is x2 − 4x +7, an example in three variables is x3 + 2xyz2 − yz +1. Polynomials appear in a variety of areas of mathematics and science. In advanced mathematics, polynomials are used to construct polynomial rings and algebraic varieties, central concepts in algebra, the word polynomial joins two diverse roots, the Greek poly, meaning many, and the Latin nomen, or name. It was derived from the binomial by replacing the Latin root bi- with the Greek poly-. The word polynomial was first used in the 17th century, the x occurring in a polynomial is commonly called either a variable or an indeterminate. When the polynomial is considered as an expression, x is a symbol which does not have any value. It is thus correct to call it an indeterminate. However, when one considers the function defined by the polynomial, then x represents the argument of the function, many authors use these two words interchangeably. It is a convention to use uppercase letters for the indeterminates. However one may use it over any domain where addition and multiplication are defined, in particular, when a is the indeterminate x, then the image of x by this function is the polynomial P itself. This equality allows writing let P be a polynomial as a shorthand for let P be a polynomial in the indeterminate x. A polynomial is an expression that can be built from constants, the word indeterminate means that x represents no particular value, although any value may be substituted for it. The mapping that associates the result of substitution to the substituted value is a function. This can be expressed concisely by using summation notation, ∑ k =0 n a k x k That is. Each term consists of the product of a number—called the coefficient of the term—and a finite number of indeterminates, because x = x1, the degree of an indeterminate without a written exponent is one. A term and a polynomial with no indeterminates are called, respectively, a constant term, the degree of a constant term and of a nonzero constant polynomial is 0. The degree of the polynomial,0, is generally treated as not defined
8.
De Morgan's laws
–
In propositional logic and boolean algebra, De Morgans laws are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathematician, the rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation. Applications of the rules include simplification of logical expressions in computer programs, De Morgans laws are an example of a more general concept of mathematical duality. The negation of conjunction rule may be written in sequent notation, the negation of disjunction rule may be written as, ¬ ⊢. De Morgans laws are shown in the compact form above, with negation of the output on the left. A clearer form for substitution can be stated as, ≡ ¬, ≡ ¬ and this emphasizes the need to invert both the inputs and the output, as well as change the operator, when doing a substitution. In set notation, De Morgans laws can be remembered using the mnemonic break the line, De Morgan’s laws commonly apply to text searching using Boolean operators AND, OR, and NOT. Consider a set of documents containing the words “cars” and “trucks”, Document 3, Contains both “cars” and “trucks”. Document 4, Contains neither “cars” nor “trucks”, to evaluate Search A, clearly the search “” will hit on Documents 1,2, and 3. So the negation of that search will hit everything else, which is Document 4, evaluating Search B, the search “” will hit on documents that do not contain “cars”, which is Documents 2 and 4. Similarly the search “” will hit on Documents 1 and 4, applying the AND operator to these two searches will hit on the documents that are common to these two searches, which is Document 4. A similar evaluation can be applied to show that the two searches will return the same set of documents, Search C, NOT, Search D. The laws are named after Augustus De Morgan, who introduced a version of the laws to classical propositional logic. De Morgans formulation was influenced by algebraization of logic undertaken by George Boole, nevertheless, a similar observation was made by Aristotle, and was known to Greek and Medieval logicians. For example, in the 14th century, William of Ockham wrote down the words that would result by reading the laws out, jean Buridan, in his Summulae de Dialectica, also describes rules of conversion that follow the lines of De Morgans laws. Still, De Morgan is given credit for stating the laws in the terms of formal logic. De Morgans laws can be proved easily, and may seem trivial. Nonetheless, these laws are helpful in making inferences in proofs
9.
P versus NP problem
–
The P versus NP problem is a major unsolved problem in computer science. Informally speaking, it asks whether every problem whose solution can be verified by a computer can also be quickly solved by a computer. The underlying issues were first discussed in the 1950s, in letters from John Nash to the National Security Agency and it is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution. The general class of questions for which some algorithm can provide an answer in time is called class P or just P. For some questions, there is no way to find an answer quickly. The class of questions for which an answer can be verified in polynomial time is called NP, consider the subset sum problem, an example of a problem that is easy to verify, but whose answer may be difficult to compute. Given a set of integers, does some nonempty subset of them sum to 0, for instance, does a subset of the set add up to 0. The answer yes, because the subset adds up to zero can be verified with three additions. There is no algorithm to find such a subset in polynomial time. An answer to the P = NP question would determine whether problems that can be verified in polynomial time, like the subset-sum problem, can also be solved in polynomial time. Although the P versus NP problem was defined in 1971, there were previous inklings of the problems involved, the difficulty of proof. In 1955, mathematician John Nash wrote a letter to the NSA, if proved this would imply what we today would call P ≠ NP, since a proposed key can easily be verified in polynomial time. Another mention of the problem occurred in a 1956 letter written by Kurt Gödel to John von Neumann. The most common resources are time and space, in such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic and sequential, arguably the biggest open question in theoretical computer science concerns the relationship between those two classes, Is P equal to NP. In 2012,10 years later, the poll was repeated. To attack the P = NP question, the concept of NP-completeness is very useful, NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time. That is, any NP problem can be transformed into any of the NP-complete problems, informally, an NP-complete problem is an NP problem that is at least as tough as any other problem in NP
10.
PSPACE
–
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. PSPACE is a superset of the set of context-sensitive languages. It turns out that allowing the Turing machine to be nondeterministic does not add any extra power, because of Savitchs theorem, NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a non-deterministic Turing machine without needing much more space. Also, the complements of all problems in PSPACE are also in PSPACE and it is widely suspected that all are strict. The containments in the line are both known to be strict. The first follows from direct diagonalization and the fact that PSPACE = NPSPACE via Savitchs theorem, the second follows simply from the space hierarchy theorem. The hardest problems in PSPACE are the PSPACE-Complete problems, see PSPACE-Complete for examples of problems that are suspected to be in PSPACE but not in NP. The class PSPACE is closed under union, complementation. An alternative characterization of PSPACE is the set of problems decidable by an alternating Turing machine in polynomial time, a logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order logic with the addition of a transitive closure operator. A full transitive closure is not needed, a transitive closure. It is the addition of this operator that distinguishes PSPACE from PH, a major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular interactive proof system, the one defining the class IP. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language, PSPACE can be characterized as the quantum complexity class QIP. PSPACE is also equal to PCTC, problems solvable by classical computers using closed curves, as well as to BQPCTC. PSPACE-complete problems are of importance to studying PSPACE problems because they represent the most difficult problems in PSPACE. Finding a simple solution to a PSPACE-complete problem would mean we have a solution to all other problems in PSPACE because all PSPACE problems could be reduced to a PSPACE-complete problem. An example of a PSPACE-complete problem is the quantified Boolean formula problem, introduction to the Theory of Computation. Chapter 19, Polynomial space, pp. 455–490, introduction to the Theory of Computation. Chapter 8, Space Complexity Complexity Zoo, PSPACE
11.
Transitive closure
–
In mathematics, the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive. Informally, the transitive closure gives you the set of all places you can get to from any starting place. More formally, the closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R. If the binary relation itself is transitive, then the closure is that same binary relation, otherwise. A relation R on a set X is transitive if, for all x, y, z in X, whenever x R y and y R z then x R z. Examples of transitive relations include the equality relation on any set, the less than or equal relation on any ordered set. Symbolically, this can be denoted as, if x < y and y < z then x < z, one example of a non-transitive relation is city x can be reached via a direct flight from city y on the set of all cities. The transitive closure of this relation is a different relation, namely there is a sequence of direct flights that begins at city x, every relation can be extended in a similar way to a transitive relation. An example of a relation with a less meaningful transitive closure is x is the day of the week after y. The transitive closure of this relation is some day x comes after a day y on the calendar, for any relation R, the transitive closure of R always exists. To see this, note that the intersection of any family of transitive relations is again transitive, furthermore, there exists at least one transitive relation containing R, namely the trivial one, X × X. The transitive closure of R is then given by the intersection of all transitive relations containing R, for finite sets, we can construct the transitive closure step by step, starting from R and adding transitive edges. This gives the intuition for a general construction. R ⊆ R +, R + contains all of the R i, so in particular R + contains R. R + is minimal, Let G be any transitive relation containing R, we want to show that R + ⊆ G. It is sufficient to show that for every i >0, R i ⊆ G. Well, and since G is transitive, whenever R i ⊆ G, R i +1 ⊆ G according to the construction of R i and what it means to be transitive. Therefore, by induction, G contains every R i, the intersection of two transitive relations is transitive. The union of two transitive relations need not be transitive, to preserve transitivity, one must take the transitive closure. This occurs, for example, when taking the union of two equivalence relations or two preorders, to obtain a new equivalence relation or preorder one must take the transitive closure
12.
BPP (complexity)
–
BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in time with a deterministic machine. Alternatively, BPP can be defined using only deterministic Turing machines, for some applications this definition is preferable since it does not mention probabilistic Turing machines. In practice, a probability of 1⁄3 might not be acceptable, however. It can be any constant between 0 and 1⁄2 and the set BPP will be unchanged and this makes it possible to create a highly accurate algorithm by merely running the algorithm several times and taking a majority vote of the answers. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1⁄2100, besides the problems in P, which are obviously in BPP, many problems were known to be in BPP but not known to be in P. The number of problems is decreasing, and it is conjectured that P = BPP. For a long time, one of the most famous problems that was known to be in BPP, in other words, is there an assignment of values to the variables such that when a nonzero polynomial is evaluated on these values, the result is nonzero. It suffices to choose each variables value uniformly at random from a subset of at least d values to achieve bounded error probability. If the access to randomness is removed from the definition of BPP, in the definition of the class, if we replace the ordinary Turing machine with a quantum computer, we get the class BQP. Adding postselection to BPP, or allowing computation paths to have different lengths, BPPpath is known to contain NP, and it is contained in its quantum counterpart PostBQP. A Monte Carlo algorithm is an algorithm which is likely to be correct. Problems in the class BPP have Monte Carlo algorithms with polynomial bounded running time and this is compared to a Las Vegas algorithm which is a randomized algorithm which either outputs the correct answer, or outputs fail with low probability. Las Vegas algorithms with polynomial bound running times are used to define the class ZPP, alternatively, ZPP contains probabilistic algorithms that are always correct and have expected polynomial running time. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time and it is known that BPP is closed under complement, that is, BPP = co-BPP. BPP is low for itself, meaning that a BPP machine with the power to solve BPP problems instantly is not any more powerful than the machine without this extra power. The relationship between BPP and NP is unknown, it is not known whether BPP is a subset of NP, NP is a subset of BPP or neither. If NP is contained in BPP, which is considered unlikely since it would imply practical solutions for NP-complete problems, then NP = RP and it is known that RP is a subset of BPP, and BPP is a subset of PP
13.
Boolean satisfiability problem
–
In computer science, the Boolean Satisfiability Problem is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable, on the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula a AND NOT b is satisfiable because one can find the values a = TRUE and b = FALSE, in contrast, a AND NOT a is unsatisfiable. SAT is one of the first problems that was proven to be NP-complete and this means that all problems in the complexity class NP, which includes a wide range of natural decision and optimization problems, are at most as difficult to solve as SAT. g. Artificial intelligence, circuit design, and automatic theorem proving, a propositional logic formula, also called Boolean expression, is built from variables, operators AND, OR, NOT, and parentheses. A formula is said to be if it can be made TRUE by assigning appropriate logical values to its variables. The Boolean satisfiability problem is, given a formula, to whether it is satisfiable. This decision problem is of importance in various areas of computer science, including theoretical computer science, complexity theory, algorithmics, cryptography. There are several cases of the Boolean satisfiability problem in which the formulas are required to have a particular structure. A literal is either a variable, then called positive literal, or the negation of a variable, a clause is a disjunction of literals. A clause is called a Horn clause if it contains at most one positive literal, a formula is in conjunctive normal form if it is a conjunction of clauses. The formula is satisfiable, choosing x1 = FALSE, x2 = FALSE, and x3 arbitrarily, since ∧ ∧ ¬FALSE evaluates to ∧ ∧ TRUE, and in turn to TRUE ∧ TRUE ∧ TRUE. In contrast, the CNF formula a ∧ ¬a, consisting of two clauses of one literal, is unsatisfiable, since for a=TRUE and a=FALSE it evaluates to TRUE ∧ ¬TRUE and FALSE ∧ ¬FALSE, different sets of allowed boolean operators lead to different problem versions. As an example, R is a clause, and R ∧ R ∧ R is a generalized conjunctive normal form. This formula is used below, with R being the operator that is TRUE just if exactly one of its arguments is. Using the laws of Boolean algebra, every propositional logic formula can be transformed into an equivalent conjunctive normal form, for example, transforming the formula ∨ ∨. ∨ into conjunctive normal form yields ∧ ∧ ∧ ∧, ∧ ∧ ∧ ∧, while the former is a disjunction of n conjunctions of 2 variables, the latter consists of 2n clauses of n variables
14.
Christos Papadimitriou
–
Christos Harilaos Papadimitriou is a Greek theoretical computer scientist, and professor of Computer Science at the University of California, Berkeley. Papadimitriou studied at the National Technical University of Athens, where in 1972 he received his Bachelor of Arts degree in Electrical Engineering. He continued to study at Princeton University, where he received his MS in Electrical Engineering in 1974 and his PhD in Electrical Engineering, Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, and UCSD, and is currently the C. Lester Hogan Professor of Electrical Engineering and Computer Science at U. C, in 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. He became fellow of the U. S. National Academy of Engineering for contributions to complexity theory, database theory, in 2009 he was elected to the US National Academy of Sciences. During the 36th International Colloquium on Automata, Languages and Programming, in 2012, he, along with Elias Koutsoupias, was awarded the Gödel Prize for their joint work on the concept of the price of anarchy. Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of complexity theory. He has also co-authored the textbook Algorithms with Sanjoy Dasgupta and Umesh Vazirani, and his name was listed in the 19th position on the CiteSeer search engine academic database and digital library. In 2011, Papadimitriou received a honoris causa from the National Technical University of Athens. In 2013, Papadimitriou received a honoris causa from the École polytechnique fédérale de Lausanne. Papadimitriou was awarded the IEEE John von Neumann Medal in 2016, the EATCS Award in 2015, the Gödel Prize in 2012, elements of the Theory of Computation. Prentice-Hall,1982, second edition September 1997, Greek edition Combinatorial Optimization, Algorithms and Complexity. Prentice-Hall,1982, second edition, Dover,1998, the Theory of Database Concurrency Control. A compilation of articles written for the Greek newspaper To Vima, mcGraw-Hill, September 2006 Logicomix, An Epic Search for Truth. Bloomsbury Publishing and Bloomsbury USA, September 2009 and he co-authored a paper with Bill Gates, co-founder of Microsoft. At UC Berkeley, in 2006, he joined a professor-and-graduate-student band called Lady X and The Positive Eigenvalues
15.
Computers and Intractability
–
It was the first book exclusively on the theory of NP-completeness and computational intractability. The book features an appendix providing a compendium of NP-complete problems. The book is now outdated in some respects as it does not cover more recent development such as the PCP theorem. It is nevertheless still in print and is regarded as a classic, in a 2006 study, another appendix of the book featured problems for which it was not known whether they were NP-complete or in P. Minimum length triangulation As of 2015, only problem 1 has yet to be classified, problem 12 is known to be NP-hard, but it is unknown if it is in NP. Soon after it appeared, the received positive reviews by reputed researchers in the area of theoretical computer science. Book recommends the book to anyone who wishes to learn about the subject of NP-completeness and he concludes, Computer science needs more books like this one. Harry R. Lewis praises the prose of the authors, Garey and Johnsons book is a thorough, clear. In many respects it is hard to imagine a better treatment of the subject, also, he considers the appendix as unique and as a starting point in attempts to show new problems to be NP-complete. Every computer scientist should have this book on their shelves as well, Garey and Johnson has the best introduction to computational complexity I have ever seen. List of NP-complete problems List of important publications in computer science
16.
International Standard Book Number
–
The International Standard Book Number is a unique numeric commercial book identifier. An ISBN is assigned to each edition and variation of a book, for example, an e-book, a paperback and a hardcover edition of the same book would each have a different ISBN. The ISBN is 13 digits long if assigned on or after 1 January 2007, the method of assigning an ISBN is nation-based and varies from country to country, often depending on how large the publishing industry is within a country. The initial ISBN configuration of recognition was generated in 1967 based upon the 9-digit Standard Book Numbering created in 1966, the 10-digit ISBN format was developed by the International Organization for Standardization and was published in 1970 as international standard ISO2108. Occasionally, a book may appear without a printed ISBN if it is printed privately or the author does not follow the usual ISBN procedure, however, this can be rectified later. Another identifier, the International Standard Serial Number, identifies periodical publications such as magazines, the ISBN configuration of recognition was generated in 1967 in the United Kingdom by David Whitaker and in 1968 in the US by Emery Koltay. The 10-digit ISBN format was developed by the International Organization for Standardization and was published in 1970 as international standard ISO2108, the United Kingdom continued to use the 9-digit SBN code until 1974. The ISO on-line facility only refers back to 1978, an SBN may be converted to an ISBN by prefixing the digit 0. For example, the edition of Mr. J. G. Reeder Returns, published by Hodder in 1965, has SBN340013818 -340 indicating the publisher,01381 their serial number. This can be converted to ISBN 0-340-01381-8, the check digit does not need to be re-calculated, since 1 January 2007, ISBNs have contained 13 digits, a format that is compatible with Bookland European Article Number EAN-13s. An ISBN is assigned to each edition and variation of a book, for example, an ebook, a paperback, and a hardcover edition of the same book would each have a different ISBN. The ISBN is 13 digits long if assigned on or after 1 January 2007, a 13-digit ISBN can be separated into its parts, and when this is done it is customary to separate the parts with hyphens or spaces. Separating the parts of a 10-digit ISBN is also done with either hyphens or spaces, figuring out how to correctly separate a given ISBN number is complicated, because most of the parts do not use a fixed number of digits. ISBN issuance is country-specific, in that ISBNs are issued by the ISBN registration agency that is responsible for country or territory regardless of the publication language. Some ISBN registration agencies are based in national libraries or within ministries of culture, in other cases, the ISBN registration service is provided by organisations such as bibliographic data providers that are not government funded. In Canada, ISBNs are issued at no cost with the purpose of encouraging Canadian culture. In the United Kingdom, United States, and some countries, where the service is provided by non-government-funded organisations. Australia, ISBNs are issued by the library services agency Thorpe-Bowker
17.
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
18.
ACC0
–
ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity, a field of theoretical computer science. The class is defined by augmenting the class AC0 of constant-depth alternating circuits with the ability to count, specifically, a problem belongs to ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC0 corresponds to computation in any solvable monoid, more formally, a language belongs to AC0 if it can be computed by a family of circuits C1, C2. A language belongs to ACC0 if it belongs to AC0 for some m, in some texts, ACCi refers to a hierarchy of circuit classes with ACC0 at its lowest level, where the circuits in ACCi have depth O and polynomial size. The class ACC0 can also be defined in terms of computations of nonuniform deterministic finite automata over monoids. In this framework, the input is interpreted as elements from a fixed monoid, the class ACC0 is the family of languages accepted by a NUDFA over some monoid that does not contain an unsolvable group as a subsemigroup. This inclusion is strict, because a single MOD-2 gate computes the parity function, more generally, the function MODm can not be computed in AC0 for prime p unless m is a power of p. The class ACC0 is included in TC0 and it is conjectured that ACC0 is unable to compute the majority function of its inputs, but this remains unresolved as of July 2014. Every problem in ACC0 can be solved by circuits of depth 2, with AND gates of polylogarithmic fan-in at the inputs, the proof follows ideas of the proof of Todas theorem. Williams proves that ACC0 does not contain NEXPTIME, the proof uses many results in complexity theory, including the time hierarchy theorem, IP = PSPACE, derandomization, and the representation of ACC0 via SYM+ circuits. It is known that computing the permanent is impossible for logtime-uniform ACC0 circuits, which implies that the complexity class PP is not contained in logtime-uniform ACC0