1.
Decision theory
–
Decision theory is the study of the reasoning underlying an agents choices. Decision theory is a topic, studied by economists, statisticians, psychologists, political and social scientists. Empirical applications of this theory are usually done with the help of statistical and econometric methods, especially via the so-called choice models. Estimation of such models is usually done via parametric, semi-parametric and non-parametric maximum likelihood methods, the practical application of this prescriptive approach is called decision analysis, and is aimed at finding tools, methodologies and software to help people make better decisions. In contrast, positive or descriptive decision theory is concerned with describing observed behaviors under the assumption that the agents are behaving under some consistent rules. The prescriptions or predictions about behaviour that positive decision theory produces allow for further tests of the kind of decision-making that occurs in practice, there is a thriving dialogue with experimental economics, which uses laboratory and field experiments to evaluate and inform theory. The area of choice under uncertainty represents the heart of decision theory and he gives an example in which a Dutch merchant is trying to decide whether to insure a cargo being sent from Amsterdam to St Petersburg in winter. In his solution, he defines a utility function and computes expected utility rather than expected financial value, the phrase decision theory itself was used in 1950 by E. L. Lehmann. At this time, von Neumann and Morgenstern theory of expected utility proved that expected utility maximization followed from basic postulates about rational behavior, the work of Maurice Allais and Daniel Ellsberg showed that human behavior has systematic and sometimes important departures from expected-utility maximization. The prospect theory of Daniel Kahneman and Amos Tversky renewed the study of economic behavior with less emphasis on rationality presuppositions. Pascals Wager is an example of a choice under uncertainty. Intertemporal choice is concerned with the kind of choice where different actions lead to outcomes that are realised at different points in time, what is the optimal thing to do. The answer depends partly on factors such as the rates of interest and inflation, the persons life expectancy. Some decisions are difficult because of the need to take into account how people in the situation will respond to the decision that is taken. The analysis of such decisions is more often treated under the label of game theory, rather than decision theory. From the standpoint of game theory most of the treated in decision theory are one-player games. Other areas of decision theory are concerned with decisions that are difficult simply because of their complexity, one example is the model of economic growth and resource usage developed by the Club of Rome to help politicians make real-life decisions in complex situations. Decisions are also affected by whether options are framed together or separately, one example of common and incorrect thought process is the gamblers fallacy, or believing that a random event is affected by previous random events
2.
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
3.
Algorithm
–
In mathematics and computer science, an algorithm is a self-contained sequence of actions to be performed. Algorithms can perform calculation, data processing and automated reasoning tasks, an algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. The transition from one state to the next is not necessarily deterministic, some algorithms, known as randomized algorithms, giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem. In English, it was first used in about 1230 and then by Chaucer in 1391, English adopted the French term, but it wasnt until the late 19th century that algorithm took on the meaning that it has in modern English. Another early use of the word is from 1240, in a manual titled Carmen de Algorismo composed by Alexandre de Villedieu and it begins thus, Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris. Which translates as, Algorism is the art by which at present we use those Indian figures, the poem is a few hundred lines long and summarizes the art of calculating with the new style of Indian dice, or Talibus Indorum, or Hindu numerals. An informal definition could be a set of rules that precisely defines a sequence of operations, which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually, but humans can do something equally useful, in the case of certain enumerably infinite sets, They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. An enumerably infinite set is one whose elements can be put into one-to-one correspondence with the integers, the concept of algorithm is also used to define the notion of decidability. That notion is central for explaining how formal systems come into being starting from a set of axioms. In logic, the time that an algorithm requires to complete cannot be measured, from such uncertainties, that characterize ongoing work, stems the unavailability of a definition of algorithm that suits both concrete and abstract usage of the term. Algorithms are essential to the way computers process data, thus, an algorithm can be considered to be any sequence of operations that can be simulated by a Turing-complete system. Although this may seem extreme, the arguments, in its favor are hard to refute. Gurevich. Turings informal argument in favor of his thesis justifies a stronger thesis, according to Savage, an algorithm is a computational process defined by a Turing machine. Typically, when an algorithm is associated with processing information, data can be read from a source, written to an output device. Stored data are regarded as part of the state of the entity performing the algorithm. In practice, the state is stored in one or more data structures, for some such computational process, the algorithm must be rigorously defined, specified in the way it applies in all possible circumstances that could arise. That is, any conditional steps must be dealt with, case-by-case
4.
Long division
–
In arithmetic, long division is a standard division algorithm suitable for dividing multidigit numbers that is simple enough to perform by hand. It breaks down a division problem into a series of easier steps, as in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a result called the quotient. It enables computations involving arbitrarily large numbers to be performed by following a series of simple steps, the abbreviated form of long division is called short division, which is almost always used instead of long division when the divisor has only one digit. Chunking is a less-efficient form of long division which may be easier to understand, while related algorithms have existed since the 12th century AD, the specific algorithm in modern use was introduced by Henry Briggs c.1600 AD. In English-speaking countries, long division does not use the division slash ⟨∕⟩ or obelus ⟨÷⟩ signs, the divisor is separated from the dividend by a right parenthesis ⟨)⟩ or vertical bar ⟨|⟩, the dividend is separated from the quotient by a vinculum. The combination of two symbols is sometimes known as a long division symbol or division bracket. It developed in the 18th century from an earlier single-line notation separating the dividend from the quotient by a left parenthesis, the process is begun by dividing the left-most digit of the dividend by the divisor. The quotient becomes the first digit of the result, and the remainder is calculated and this remainder carries forward when the process is repeated on the following digit of the dividend. When all digits have been processed and no remainder is left, an example is shown below, representing the division of 500 by 4. The largest number that the divisor 4 can be multiplied by without exceeding 5 is 1, next the 4 under the 5 is subtracted from the 5 to get the remainder,1, which is placed under the 4 under the 5. This remainder 1 is necessarily smaller than the divisor 4, next the first as-yet unused digit in the dividend, in this case the first digit 0 after the 5, is copied directly underneath itself and next to the remainder 1, to form the number 10. This remainder 2 is necessarily smaller than the divisor 4, the next digit of the dividend is copied directly below itself and next to the remainder 2, to form 20. Then the largest number by which the divisor 4 can be multiplied without exceeding 20 is ascertained, then this new quotient digit 5 is multiplied by the divisor 4 to get 20, which is written at the bottom below the existing 20. Then 20 is subtracted from 20, yielding 0, which is written below the 20 and we know we are done now because two things are true, there are no more digits to bring down from the dividend, and the last subtraction result was 0. If the last remainder when we ran out of dividend digits had been something other than 0, there would have been two possible courses of action. Or, we could extend the dividend by writing it as, say,500.000. and continue the process, in order to get a decimal answer, as in the following example. This example also illustrates that, at the beginning of the process, since the first digit 1 is less than the divisor 4, the first step is instead performed on the first two digits 12. Similarly, if the divisor were 13, one would perform the first step on 127 rather than 12 or 1, find the location of all decimal points in the dividend n and divisor m
5.
Turing degree
–
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory, where sets of numbers are often regarded as decision problems. The Turing degree of a set is a measure of how difficult it is to solve the problem associated with the set. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability, the Turing degrees were introduced by Emil Leon Post, and many fundamental results were established by Stephen Cole Kleene and Post. The Turing degrees have been an area of research since then. Many proofs in the area make use of a technique known as the priority method. For the rest of this article, the set will refer to a set of natural numbers. A set X is said to be Turing reducible to a set Y if there is an oracle Turing machine that decides membership in X when given an oracle for membership in Y, the notation X ≤T Y indicates that X is Turing reducible to Y. Two sets X and Y are defined to be Turing equivalent if X is Turing reducible to Y and Y is Turing reducible to X, the notation X ≡T Y indicates that X and Y are Turing equivalent. A Turing degree is a class of the relation ≡T. The notation denotes the class containing a set X. The entire collection of Turing degrees is denoted D, the Turing degrees have a partial order ≤ defined so that ≤ if and only if X ≤T Y. There is a unique Turing degree containing all the sets. It is denoted 0 because it is the least element of the poset D, for any sets X and Y, X join Y, written X ⊕ Y, is defined to be the union of the sets and. The Turing degree of X ⊕ Y is the least upper bound of the degrees of X and Y, the least upper bound of degrees a and b is denoted a ∪ b. It is known that D is not a lattice, as there are pairs of degrees with no greatest lower bound, for any set X the notation X′ denotes the set of indices of oracle machines that halt when using X as an oracle. The set X′ is called the Turing jump of X, the Turing jump of a degree is defined to be the degree, this is a valid definition because X′ ≡T Y′ whenever X ≡T Y. A key example is 0′, the degree of the halting problem, every Turing degree is countably infinite, that is, it contains exactly ℵ0 sets
6.
String (computer science)
–
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, a string is generally understood as a data type and is often implemented as an array of bytes that stores a sequence of elements, typically characters, using some character encoding. A string may also more general arrays or other sequence data types and structures. When a string appears literally in source code, it is known as a literal or an anonymous string. In formal languages, which are used in logic and theoretical computer science. Let Σ be a non-empty finite set of symbols, called the alphabet, no assumption is made about the nature of the symbols. A string over Σ is any sequence of symbols from Σ. For example, if Σ =, then 01011 is a string over Σ, the length of a string s is the number of symbols in s and can be any non-negative integer, it is often denoted as |s|. The empty string is the string over Σ of length 0. The set of all strings over Σ of length n is denoted Σn, for example, if Σ =, then Σ2 =. Note that Σ0 = for any alphabet Σ, the set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σn, Σ ∗ = ⋃ n ∈ N ∪ Σ n For example, if Σ =, although the set Σ* itself is countably infinite, each element of Σ* is a string of finite length. A set of strings over Σ is called a language over Σ. For example, if Σ =, the set of strings with an number of zeros, is a formal language over Σ. Concatenation is an important binary operation on Σ*, for any two strings s and t in Σ*, their concatenation is defined as the sequence of symbols in s followed by the sequence of characters in t, and is denoted st. For example, if Σ =, s = bear, and t = hug, then st = bearhug, String concatenation is an associative, but non-commutative operation. The empty string ε serves as the identity element, for any string s, therefore, the set Σ* and the concatenation operation form a monoid, the free monoid generated by Σ. In addition, the length function defines a monoid homomorphism from Σ* to the non-negative integers, a string s is said to be a substring or factor of t if there exist strings u and v such that t = usv
7.
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
8.
Complexity classes
–
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
9.
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
10.
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
11.
Partial function
–
In mathematics, a partial function from X to Y is a function f, X ′ → Y, for some subset X ′ of X. It generalizes the concept of an f, X → Y by not forcing f to map every element of X to an element of Y. If X ′ = X, then f is called a function and is equivalent to a function. Partial functions are used when the exact domain, X, is not known. Specifically, we say that for any x ∈ X, either. For example, we can consider the square root function restricted to the g, Z → Z g = n. Thus g is defined for n that are perfect squares. So, g =5, but g is undefined, there are two distinct meanings in current mathematical usage for the notion of the domain of a partial function. Most mathematicians, including recursion theorists, use the domain of f for the set of all values x such that f is defined. But some, particularly category theorists, consider the domain of a function f, X → Y to be X. Similarly, the range can refer to either the codomain or the image of a function. Occasionally, a function with domain X and codomain Y is written as f, X ⇸ Y. A partial function is said to be injective or surjective when the function given by the restriction of the partial function to its domain of definition is. A partial function may be both injective and surjective, because a function is trivially surjective when restricted to its image, the term partial bijection denotes a partial function which is injective. An injective partial function may be inverted to a partial function. Furthermore, a function which is injective may be inverted to an injective partial function. The notion of transformation can be generalized to functions as well. A partial transformation is a function f, A → B, total function is a synonym for function
12.
Indicator function
–
It is usually denoted by a symbol 1 or I, sometimes in boldface or blackboard boldface, with a subscript describing the set. The indicator function of a subset A of a set X is a function 1 A, X → defined as 1 A, = {1 if x ∈ A,0 if x ∉ A. The Iverson bracket allows the equivalent notation, to be used instead of 1 A, the function 1 A is sometimes denoted I A, χ A, KA or even just A. The set of all functions on X can be identified with P. This is a case of the notation Y X for the set of all functions f, X → Y. The notation 1 A is also used to denote the identity function of A, the notation χ A is also used to denote the characteristic function in convex analysis. A related concept in statistics is that of a dummy variable, the term characteristic function has an unrelated meaning in probability theory. The indicator or characteristic function of a subset A of some set X and this mapping is surjective only when A is a non-empty proper subset of X. By a similar argument, if A ≡ Ø then 1A =0, in the following, the dot represents multiplication, 1·1 =1, 1·0 =0 etc. + and − represent addition and subtraction. ∩ and ∪ is intersection and union, respectively. More generally, suppose A1, …, A n is a collection of subsets of X, for any x ∈ X, ∏ k ∈ I is clearly a product of 0s and 1s. This product has the value 1 at precisely those x ∈ X that belong to none of the sets Ak and is 0 otherwise and that is ∏ k ∈ I =1 X − ⋃ k A k =1 −1 ⋃ k A k. This is one form of the principle of inclusion-exclusion, as suggested by the previous example, the indicator function is a useful notational device in combinatorics. This identity is used in a proof of Markovs inequality. In many cases, such as theory, the inverse of the indicator function may be defined. This is commonly called the generalized Möbius function, as a generalization of the inverse of the function in elementary number theory. Given a probability space with A ∈ F, the random variable 1 A, Ω → R is defined by 1 A =1 if ω ∈ A. Mean E = P Variance Var = P Covariance Cov = P − P P Kurt Gödel described the function in his 1934 paper On Undecidable Propositions of Formal Mathematical Systems. There shall correspond to each class or relation R a representing function φ =0 if R and φ =1 if ~R, for example, because the product of characteristic functions φ1*φ2*
13.
NP-completeness
–
In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard. The set of NP-complete problems is often denoted by NP-C or NPC, the abbreviation NP refers to nondeterministic polynomial time. That is, the required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether or not it is possible to solve problems quickly. NP-complete problems are addressed by using heuristic methods and approximation algorithms. A problem p in NP is NP-complete if every problem in NP can be transformed into p in polynomial time. NP-complete problems are studied because the ability to quickly verify solutions to a problem seems to correlate with the ability to solve that problem. It is not known whether every problem in NP can be quickly solved—this is called the P versus NP problem, because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general. A decision problem C is NP-complete if, C is in NP, C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard, a consequence of this definition is that if we had a polynomial time algorithm for C, we could solve all problems in NP in polynomial time. The concept of NP-completeness was introduced in 1971, though the term NP-complete was introduced later, at 1971 STOC conference, there was a fierce debate among the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine. This is known as the question of whether P=NP, nobody has yet been able to determine conclusively whether NP-complete problems are in fact solvable in polynomial time, making this one of the great unsolved problems of mathematics. The Clay Mathematics Institute is offering a US $1 million reward to anyone who has a proof that P=NP or that P≠NP. Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete, in 1972, Richard Karp proved that several other problems were also NP-complete, thus there is a class of NP-complete problems. For more details refer to Introduction to the Design and Analysis of Algorithms by Anany Levitin, an interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two graphs. Two graphs are isomorphic if one can be transformed into the other simply by renaming vertices, consider these two problems, Graph Isomorphism, Is graph G1 isomorphic to graph G2. Subgraph Isomorphism, Is graph G1 isomorphic to a subgraph of graph G2, the Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete and this is an example of a problem that is thought to be hard, but is not thought to be NP-complete
14.
Travelling salesman problem
–
It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. TSP is a case of the travelling purchaser problem and the vehicle routing problem. In the theory of computational complexity, the version of the TSP belongs to the class of NP-complete problems. Thus, it is possible that the running time for any algorithm for the TSP increases superpolynomially with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization and it is used as a benchmark for many optimization methods. The TSP has several applications even in its purest formulation, such as planning, logistics, slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. The TSP also appears in astronomy, as observing many sources will want to minimize the time spent moving the telescope between the sources. In many applications, additional constraints such as limited resources or time windows may be imposed, the origins of the travelling salesperson problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, the travelling salesperson problem was mathematically formulated in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman. Hamilton’s Icosian Game was a puzzle based on finding a Hamiltonian cycle. Hassler Whitney at Princeton University introduced the name travelling salesman problem soon after, Dantzig, Fulkerson and Johnson, however, speculated that given a near optimal solution we may be able to find optimality or prove optimality by adding a small amount of extra inequalities. They used this idea to solve their initial 49 city problem using a string model and they found they only needed 26 cuts to come to a solution for their 49 city problem. As well as cutting plane methods, Dantzig, Fulkerson and Johnson used branch, in the following decades, the problem was studied by many researchers from mathematics, computer science, chemistry, physics, and other sciences. Christofides made a big advance in this approach of giving an approach for which we know the worst-case scenario and his algorithm given in 1976, at worst is 1.5 times longer than the optimal solution. As the algorithm was so simple and quick, many hoped it would give way to a optimal solution method. However, until 2011 when it was beaten by less than a billionth of a percent, Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours, great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and others managed to exactly solve instances with up to 2392 cities, using cutting planes and branch-and-bound. In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has used in many recent record solutions
15.
Linear programming
–
Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a case of mathematical programming. More formally, linear programming is a technique for the optimization of an objective function, subject to linear equality. Its feasible region is a polytope, which is a set defined as the intersection of finitely many half spaces. Its objective function is an affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest value if such a point exists, the expression to be maximized or minimized is called the objective function. The inequalities Ax ≤ b and x ≥0 are the constraints which specify a convex polytope over which the function is to be optimized. In this context, two vectors are comparable when they have the same dimensions, if every entry in the first is less-than or equal-to the corresponding entry in the second then we can say the first vector is less-than or equal-to the second vector. Linear programming can be applied to fields of study. It is widely used in business and economics, and is utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications and it has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design. The first linear programming formulation of a problem that is equivalent to the linear programming problem was given by Leonid Kantorovich in 1939. He developed it during World War II as a way to plan expenditures and returns so as to reduce costs to the army, about the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs, Kantorovich and Koopmans later shared the 1975 Nobel prize in economics. Dantzig independently developed general linear programming formulation to use for planning problems in US Air Force, in 1947, Dantzig also invented the simplex method that for the first time efficiently tackled the linear programming problem in most cases. Dantzig provided formal proof in an unpublished report A Theorem on Linear Inequalities on January 5,1948, postwar, many industries found its use in their daily planning. Dantzigs original example was to find the best assignment of 70 people to 70 jobs, the computing power required to test all the permutations to select the best assignment is vast, the number of possible configurations exceeds the number of particles in the observable universe. However, it only a moment to find the optimum solution by posing the problem as a linear program
16.
Operations research
–
Operations research, or operational research in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions. Further, the operational analysis is used in the British military, as an intrinsic part of capability development, management. In particular, operational analysis forms part of the Combined Operational Effectiveness and Investment Appraisals and it is often considered to be a sub-field of applied mathematics. The terms management science and decision science are used as synonyms. Operation research is concerned with determining the maximum or minimum of some real-world objective. Originating in military efforts before World War II, its techniques have grown to concern problems in a variety of industries, nearly all of these techniques involve the construction of mathematical models that attempt to describe the system. Because of the computational and statistical nature of most of these fields, OR also has ties to computer science. In the decades after the two wars, the techniques were more widely applied to problems in business, industry. Early work in research was carried out by individuals such as Charles Babbage. Percy Bridgman brought operational research to bear on problems in physics in the 1920s, modern operational research originated at the Bawdsey Research Station in the UK in 1937 and was the result of an initiative of the stations superintendent, A. P. Rowe. Rowe conceived the idea as a means to analyse and improve the working of the UKs early warning radar system, initially, he analysed the operating of the radar equipment and its communication networks, expanding later to include the operating personnels behaviour. This revealed unappreciated limitations of the CH network and allowed action to be taken. Scientists in the United Kingdom including Patrick Blackett, Cecil Gordon, Solly Zuckerman, other names for it included operational analysis and quantitative management. During the Second World War close to 1,000 men and women in Britain were engaged in operational research, about 200 operational research scientists worked for the British Army. Patrick Blackett worked for different organizations during the war. In 1941, Blackett moved from the RAE to the Navy, after first working with RAF Coastal Command, in 1941, blacketts team at Coastal Commands Operational Research Section included two future Nobel prize winners and many other people who went on to be pre-eminent in their fields. They undertook a number of analyses that aided the war effort. Convoys travel at the speed of the slowest member, so small convoys can travel faster and it was also argued that small convoys would be harder for German U-boats to detect
17.
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
