Misplaced Pages

#501498

48-461: A disjunctive Datalog program is a collection of rules. A rule is a clause of the form: where b 1 {\displaystyle b_{1}} , ..., b m {\displaystyle b_{m}} may be negated, and may include (in)equality constraints. There are at least three ways to define the semantics of disjunctive Datalog: Disjunctive Datalog can express several NP-complete and NP-hard problems, including

96-405: A decision problem as a formal language in some fixed encoding, the set NPC of all NP-complete problems is not closed under: It is not known whether NPC is closed under complementation , since NPC= co-NPC if and only if NP= co-NP , and since NP=co-NP is an open question . Non-deterministic Turing machine In theoretical computer science , a nondeterministic Turing machine ( NTM )

144-489: 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: The Subgraph Isomorphism problem is NP-complete. The graph isomorphism problem is suspected to be neither in P nor NP-complete, though it is in NP. This is an example of a problem that is thought to be hard , but is not thought to be NP-complete. This class

192-434: A DTM can also be solved by a NTM, and vice versa. However, it is believed that in general the time complexity may not be the same. NTMs include DTMs as special cases, so every computation that can be carried out by a DTM can also be carried out by the equivalent NTM. It might seem that NTMs are more powerful than DTMs, since they can allow trees of possible computations arising from the same initial configuration, accepting

240-438: A Turing Machine's rules might thus be: "If you are in state 2 and you see an 'A', then change it to 'B', move left, and switch to state 3." In a deterministic Turing machine (DTM), the set of rules prescribes at most one action to be performed for any given situation. A deterministic Turing machine has a transition function that, for a given state and symbol under the tape head, specifies three things: For example, an X on

288-402: A nondeterministic Turing machine to perform the whole search. " Complete " refers to the property of being able to simulate everything in the same complexity class . More precisely, each input to the problem should be associated with a set of solutions of polynomial length, the validity of each of which can be tested quickly (in polynomial time ), such that the output for any input is "yes" if

336-428: A polynomial time algorithm, all problems in NP do. The set of NP-complete problems is often denoted by NP-C or NPC . Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly. That is, the time required to solve the problem using any currently known algorithm increases rapidly as the size of the problem grows. As a consequence, determining whether it

384-414: A problem is NP-complete when: The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines , a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for

432-448: A quantum computer can indeed be in a superposition state corresponding to all possible computational branches having been executed at the same time (similar to an NTM), the final measurement will collapse the quantum computer into a randomly selected branch. This branch then does not, in general, represent the sought-for solution, unlike the NTM, which is allowed to pick the right solution among

480-454: A string if any one branch in the tree accepts it. However, it is possible to simulate NTMs with DTMs, and in fact this can be done in more than one way. One approach is to use a DTM of which the configurations represent multiple configurations of the NTM, and the DTM's operation consists of visiting each of them in turn, executing a single step at each visit, and spawning new configurations whenever

528-400: A subroutine that solves Y {\displaystyle \scriptstyle Y} in polynomial time, one could write a program that calls this subroutine and solves X {\displaystyle \scriptstyle X} in polynomial time. This contrasts with many-one reducibility, which has the restriction that the program can only call the subroutine once, and the return value of

SECTION 10

#1732798600502

576-401: Is NP-complete if: C {\displaystyle \scriptstyle C} can be shown to be in NP by demonstrating that a candidate solution to C {\displaystyle \scriptstyle C} can be verified in polynomial time. Note that a problem satisfying condition 2 is said to be NP-hard , whether or not it satisfies condition 1. A consequence of this definition

624-482: Is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it. Therefore, it is useful to know a variety of NP-complete problems. The list below contains some well-known problems that are NP-complete when expressed as decision problems. To the right is a diagram of some of the problems and the reductions typically used to prove their NP-completeness. In this diagram, problems are reduced from bottom to top. Note that this diagram

672-414: Is a cycle or is bipartite is very easy (in L ), but finding a maximum bipartite or a maximum cycle subgraph is NP-complete. A solution of the knapsack problem within any fixed percentage of the optimal solution can be computed in polynomial time, but finding the optimal solution is NP-complete. An interesting example is the graph isomorphism problem , the graph theory problem of determining whether

720-511: Is a many-one reduction that can be computed with only a logarithmic amount of space. Since every computation that can be done in logarithmic space can also be done in polynomial time it follows that if there is a logarithmic-space many-one reduction then there is also a polynomial-time many-one reduction. This type of reduction is more refined than the more usual polynomial-time many-one reductions and it allows us to distinguish more classes such as P-complete . Whether under these types of reductions

768-449: Is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine . NTMs are sometimes used in thought experiments to examine the abilities and limits of computers. One of the most important open problems in theoretical computer science

816-407: Is called NP-Intermediate problems and exists if and only if P≠NP. At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size. The vertex cover problem has O ( 1.2738 k + n k ) {\displaystyle O(1.2738^{k}+nk)} for some k > 0 {\displaystyle k>0} and it

864-508: Is called the P versus NP problem . But if any NP-complete problem can be solved quickly, then every problem in NP can, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time). 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 {\displaystyle \scriptstyle C}

912-426: Is common to omit the stationary (0) output, and instead insert the transitive closure of any desired stationary transitions. Some authors add an explicit reject state, which causes the NTM to halt without accepting. This definition still retains the asymmetry that any nondeterministic branch can accept, but every branch must reject for the string to be rejected. Any computational problem that can be solved by

960-440: Is known, however, that AC reductions define a strictly smaller class than polynomial-time reductions. According to Donald Knuth , the name "NP-complete" was popularized by Alfred Aho , John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms". He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with

1008-411: Is misleading as a description of the mathematical relationship between these problems, as there exists a polynomial-time reduction between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest. There is often only a small difference between a problem in P and an NP-complete problem. For example, the 3-satisfiability problem, a restriction of

SECTION 20

#1732798600502

1056-805: Is not obvious. The Cook–Levin theorem states that the Boolean satisfiability problem is NP-complete, thus establishing that such problems do exist. In 1972, Richard Karp proved that several other problems were also NP-complete (see Karp's 21 NP-complete problems ); thus, there is a class of NP-complete problems (besides the Boolean satisfiability problem). Since the original results, thousands of other problems have been shown to be NP-complete by reductions from other problems previously shown to be NP-complete; many of these problems are collected in Garey & Johnson (1979) . The easiest way to prove that some new problem

1104-524: Is possible to solve these problems quickly, called the P versus NP problem , is one of the fundamental unsolved problems in computer science today. While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using heuristic methods and approximation algorithms . NP-complete problems are in NP ,

1152-476: Is sometimes a misconception that quantum computers are NTMs. However, it is believed by experts (but has not been proven) that the power of quantum computers is, in fact, incomparable to that of NTMs; that is, problems likely exist that an NTM could efficiently solve that a quantum computer cannot and vice versa. In particular, it is likely that NP-complete problems are solvable by NTMs but not by quantum computers in polynomial time. Intuitively speaking, while

1200-406: Is that if we had a polynomial time algorithm (on a UTM , or any other Turing-equivalent abstract machine ) for C {\displaystyle \scriptstyle C} , we could solve all problems in NP in polynomial time. The concept of NP-completeness was introduced in 1971 (see Cook–Levin theorem ), though the term NP-complete was introduced later. At the 1971 STOC conference, there

1248-458: Is that, for deterministic Turing machines, the transition relation is a function rather than just a relation. Configurations and the yields relation on configurations, which describes the possible actions of the Turing machine given any possible contents of the tape, are as for standard Turing machines, except that the yields relation is no longer single-valued. (If the machine is deterministic,

1296-499: Is the P versus NP problem , which (among other equivalent formulations) concerns the question of how difficult it is to simulate nondeterministic computation with a deterministic computer. In essence, a Turing machine is imagined to be a simple computer that reads and writes symbols one at a time on an endless tape by strictly following a set of rules. It determines what action it should perform next according to its internal state and what symbol it currently sees . An example of one of

1344-416: Is to say that the machine is the "luckiest possible guesser"; it always picks a transition that eventually leads to an accepting state, if there is such a transition. The other is to imagine that the machine " branches " into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree". If at least one branch of

1392-409: Is unknown whether there are any faster algorithms. The following techniques can be applied to solve computational problems in general, and they often give rise to substantially faster algorithms: One example of a heuristic algorithm is a suboptimal O ( n log ⁡ n ) {\displaystyle O(n\log n)} greedy coloring algorithm used for graph coloring during

1440-426: The register allocation phase of some compilers, a technique called graph-coloring global register allocation . Each vertex is a variable, edges are drawn between variables which are being used at the same time, and colors indicate the register assigned to each variable. Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application. In

1488-468: The travelling salesman problem , graph coloring , maximum clique problem , and minimal vertex cover . These problems are only expressible in Datalog if the polynomial hierarchy collapses. The DLV ( D ata L og with Disjunction, where the logical disjunction symbol V is used) system implements the disjunctive stable model semantics. NP-completeness In computational complexity theory ,

Disjunctive Datalog - Misplaced Pages Continue

1536-461: The Boolean satisfiability problem, remains NP-complete, whereas the slightly more restricted 2-satisfiability problem is in P (specifically, it is NL-complete ), but the slightly more general max. 2-sat. problem is again NP-complete. Determining whether a graph can be colored with 2 colors is in P, but with 3 colors is NP-complete, even when restricted to planar graphs . Determining if a graph

1584-454: The constructed DTM effectively performs a breadth-first search of the NTM's computation tree, visiting all possible computations of the NTM in order of increasing length until it finds an accepting one. Therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is believed to be a general property of simulations of NTMs by DTMs. The P = NP problem ,

1632-527: The definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions. All currently known NP-complete problems remain NP-complete even under much weaker reductions such as A C 0 {\displaystyle AC_{0}} reductions and N C 0 {\displaystyle NC_{0}} reductions. Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections. It

1680-403: The definition of NP-complete given above, the term reduction was used in the technical meaning of a polynomial-time many-one reduction . Another type of reduction is polynomial-time Turing reduction . A problem X {\displaystyle \scriptstyle X} is polynomial-time Turing-reducible to a problem Y {\displaystyle \scriptstyle Y} if, given

1728-407: The machine into an accepting state. When simulating the many branching paths of an NTM on a deterministic machine, we can stop the entire simulation as soon as any branch reaches an accepting state. As a mathematical construction used primarily in proofs, there are a variety of minor variations on the definition of an NTM, but these variations all accept equivalent languages. The head movement in

1776-573: The most famous unresolved question in computer science, concerns one case of this issue: whether or not every problem solvable by a NTM in polynomial time is necessarily also solvable by a DTM in polynomial time. An NTM has the property of bounded nondeterminism. That is, if an NTM always halts on a given input tape T then it halts in a bounded number of steps, and therefore can only have a bounded number of possible configurations. Because quantum computers use quantum bits , which can be in superpositions of states, rather than conventional bits, there

1824-436: The other. 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 ( Millennium Prize ) to anyone who has a formal proof that P=NP or that P≠NP. The existence of NP-complete problems

1872-408: The output of the transition relation is often encoded numerically instead of using letters to represent moving the head Left (-1), Stationary (0), and Right (+1); giving a transition function output of ( Q × Σ × { − 1 , 0 , + 1 } ) {\displaystyle \left(Q\times \Sigma \times \{-1,0,+1\}\right)} . It

1920-458: The possible computations are all prefixes of a single, possibly infinite, path.) The input for an NTM is provided in the same manner as for a deterministic Turing machine: the machine is started in the configuration in which the tape head is on the first character of the string (if any), and the tape is all blank otherwise. An NTM accepts an input string if and only if at least one of the possible computational paths starting from that string puts

1968-479: The results of a poll he had conducted of the theoretical computer science community. Other suggestions made in the poll included " Herculean ", "formidable", Steiglitz 's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the P versus NP problem went, could stand for "provably exponential time" or "previously exponential time". The following misconceptions are frequent. Viewing

Disjunctive Datalog - Misplaced Pages Continue

2016-429: The set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a non-deterministic Turing machine . A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time. It is not known whether every problem in NP can be quickly solved—this

2064-458: The solution set is non-empty and "no" if it is empty. The complexity class of problems of this form is called NP , an abbreviation for "nondeterministic polynomial time". A problem is said to be NP-hard if everything in NP can be transformed in polynomial time into it even though it may not be in NP. A problem is NP-complete if it is both in NP and NP-hard. The NP-complete problems represent the hardest problems in NP. If some NP-complete problem has

2112-405: The subroutine must be the return value of the program. If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger. Another type of reduction that is also often used to define NP-completeness is the logarithmic-space many-one reduction which

2160-492: The tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5. In contrast to a deterministic Turing machine, in a nondeterministic Turing machine ( NTM ) the set of rules may prescribe more than one action to be performed for any given situation. For example, an X on the tape in state 3 might allow the NTM to: or How does the NTM "know" which of these actions it should take? There are two ways of looking at it. One

2208-402: The transition relation defines multiple continuations. Another construction simulates NTMs with 3-tape DTMs, of which the first tape always holds the original input string, the second is used to simulate a particular computation of the NTM, and the third encodes a path in the NTM's computation tree. The 3-tape DTMs are easily simulated with a normal single-tape DTM. In the second construction,

2256-401: The tree halts with an "accept" condition, the NTM accepts the input. A nondeterministic Turing machine can be formally defined as a six-tuple M = ( Q , Σ , ι , ⊔ , A , δ ) {\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )} , where The difference with a standard (deterministic) Turing machine

2304-422: Was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine . John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or

#501498