Computers and Intractability

In computer science, more computational complexity theory and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson, it was the first book on the theory of NP-completeness and computational intractability. The book features an appendix providing a thorough 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 still in print and is regarded as a classic: in a 2006 study, the CiteSeer search engine listed the book as the most cited reference in computer science literature. Another appendix of the book featured problems for which it was not known whether they were NP-complete or in P; the problems are: Graph isomorphism This problem is known to be in NP, but it is unknown if it is NP-complete. Subgraph homeomorphism Graph genus Chordal graph completion Chromatic index Spanning tree parity problem Partial order dimension Precedence constrained 3-processor scheduling This problem was still open as of 2016.

Linear programming Total unimodularity Composite number Testing for compositeness is known to be in P, but the complexity of the related integer factorization problem remains open. Minimum length triangulationProblem 12 is known to be NP-hard, but it is unknown if it is in NP. Soon after it appeared, the book received positive reviews by reputed researchers in the area of theoretical computer science. In his review, Ronald V. Book recommends the book to "anyone who wishes to learn about the subject of NP-completeness", he explicitly mentions the "extremely useful" appendix with over 300 NP-hard computational problems, he concludes: "Computer science needs more books like this one."Harry R. Lewis praises the mathematical prose of the authors: "Garey and Johnson's book is a thorough and practical exposition of NP-completeness. In many respects it is hard to imagine a better treatment of the subject." He considers the appendix as "unique" and "as a starting point in attempts to show new problems to be NP-complete".

Twenty-three years after the book appeared, Lance Fortnow, editor-in-chief of the scientific journal Transactions on Computational Theory, states: "I consider Garey and Johnson the single most important book on my office bookshelf. Every computer scientist should have this book on their shelves as well. Garey and Johnson has the best introduction to computational complexity I have seen." List of NP-complete problems List of important publications in theoretical computer science

Computational complexity theory

Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. 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 their computational complexity, i.e. the amount of resources needed to solve them, such as time and storage. Other measures of complexity are used, such as the amount of communication, the number of gates in a circuit and the number of processors. One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do; the P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.

Related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kind of problems can, in principle, be solved algorithmically. A computational problem can be viewed as an infinite collection of instances together with a solution for every instance; the input string for a computational problem is referred to as a problem instance, should not be confused with the problem itself.

In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing; the instance is a number and the solution is "yes" if the number is prime and "no" otherwise. Stated another way, the instance is a particular input to the problem, the solution is the output corresponding to the given input. To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. 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. The alphabet is taken to be the binary alphabet, thus the strings are bitstrings; as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary. Though some proofs of complexity-theoretic theorems assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding; this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either yes or no, or alternately either 1 or 0. A decision problem can be viewed as a formal language, where the members of the language are instances whose output is yes, the non-members are those instances whose output is no.

The objective is to decide, with the aid of an algorithm, whether a given input string is a member of the formal language under consideration. 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 decision problem is the following; the input is an arbitrary graph. The problem consists in deciding; the formal language associated with this decision problem is the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings. A function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include the integer factorization problem, it is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not the case, since function problems can be recast as decision problems.

For example, the multiplication of two integers can be expressed as the set of triples such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed; the machine operates on an infinite memory tape divided into discrete "cells". The machine positions its "head" over a cell and "reads" or "scans" the symbol there; as per the symbol and its present place in a "finite table" of user-specified instructions, the machine writes a symbol in the cell either moves the tape one cell left or right either proceeds to a subsequent instruction or halts the computation. The Turing machine was invented in 1936 by Alan Turing, who called it an "a-machine". With this model, Turing was able to answer two questions in the negative: Does a machine exist that can determine whether any arbitrary machine on its tape is "circular", thus by providing a mathematical description of a simple device capable of arbitrary computations, he was able to prove properties of computation in general—and in particular, the uncomputability of the Entscheidungsproblem.

Thus, Turing machines prove fundamental limitations on the power of mechanical computation. While they can express arbitrary computations, their minimalistic design makes them unsuitable for computation in practice: real-world computers are based on different designs that, unlike Turing machines, use random-access memory. Turing completeness is the ability for a system of instructions to simulate a Turing machine. A programming language, Turing complete is theoretically capable of expressing all tasks accomplishable by computers. 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 it is a machine capable of enumerating some arbitrary subset of valid strings of an alphabet. A Turing machine has a tape of infinite length on which it can perform write operations. Assuming a black box, the Turing machine cannot know whether it will enumerate any one specific string of the subset with a given program.

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 further 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, able to simulate any other Turing machine is called a universal Turing machine. A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis; the thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, provide a precise definition of an algorithm or "mechanical procedure". Studying their abstract properties yields many insights into computer science and complexity theory. In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consisted of:...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed.

At any moment there is one symbol in the machine. The machine can alter the scanned symbol, its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. 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 have an innings; the Turing machine mathematically models a machine. On this tape are symbols, which the machine can read and write, one at a time, using a tape head. Operation is determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1. In the original article, Turing imagines not a mechanism, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly. More a Turing machine consists of: A tape divided into cells, one next to the other; each cell contains a symbol from some finite alphabet. The alphabet contains one or more other symbols.

The tape is assumed to be arbitrarily extendable to the left and to the right, i.e. the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written before are assumed to be filled with the blank symbol. In some models the tape has a left e