|
NP-easy
In complexity theory, the complexity class NP-easy is the set of function problems that are solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP. In other words, a problem X is NP-easy if and only if there exists some problem Y in NP such that X is polynomial-time Turing reducible to Y., p. 117, 120. This means that given an oracle for Y, there exists an algorithm that solves X in polynomial time (possibly by repeatedly using that oracle). NP-easy is another name for FPNP (see the function problem article) or for FΔ2P (see the polynomial hierarchy article). An example of an NP-easy problem is the problem of sorting a list of strings. The decision problem "is string A greater than string B" is in NP. There are algorithms such as quicksort that can sort the list using only a polynomial number of calls to the comparison routine, plus a polynomial amount of additional work. Therefore, sorting is NP-easy. There are also ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-equivalent
In computational complexity theory, the complexity class NP-equivalent is the set of function problems that are both NP-easy and NP-hard. NP-equivalent is the analogue of NP-complete for function problems. For example, the problem FIND-SUBSET-SUM is in NP-equivalent. Given a set of integers, FIND-SUBSET-SUM is the problem of finding some nonempty subset of the integers that adds up to zero (or returning the empty set if there is no such subset). This optimization problem is similar to the decision problem SUBSET-SUM. Given a set of integers, SUBSET-SUM is the problem of finding whether there exists a subset summing to zero. SUBSET-SUM is NP-complete. To show that FIND-SUBSET-SUM is NP-equivalent, we must show that it is both NP-hard and NP-easy. Clearly it is NP-hard. If we had a black box that solved FIND-SUBSET-SUM in unit time, then it would be easy to solve SUBSET-SUM. Simply ask the black box to find the subset that sums to zero, then check whether it returned a nonem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Complexity Theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. 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 also used, such as the amount of communication (used in communication complexity), the number of logic gate, gates in a circuit (used in circuit complexity) and the number of processors (used in parallel computing). O ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complexity Class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and space complexity, memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time complexity, time or space complexity, memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P (complexity), P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. Counting problem (complexity), counting problems and function problems) and using other models of computation (e.g. probabil ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Function Problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'. Definition A functional problem P is defined by a relation R over strings of an arbitrary alphabet \Sigma: : R \subseteq \Sigma^* \times \Sigma^*. An algorithm solves P if for every input x such that there exists a y satisfying (x, y) \in R, the algorithm produces one such y, and if there are no such y, it rejects. A promise function problem is allowed to do anything (thus may not terminate) if no such y exists. Examples A well-known function problem is given by the Functional Boolean Satisfiability Problem, FSAT for short. The problem, which is closely related to the SAT decision problem, can be formulated as follows: :Given a boolean formula \varphi with variables x_1, \ldots, x_n, find an as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is gener ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deterministic Turing Machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm. The machine operates on an infinite memory tape divided into discrete cells, each of which can hold a single symbol drawn from a finite set of symbols called the alphabet of the machine. It has a "head" that, at any point in the machine's operation, is positioned over one of these cells, and a "state" selected from a finite set of states. At each step of its operation, the head reads the symbol in its cell. Then, based on the symbol and the machine's own present state, the machine writes a symbol into the same cell, and moves the head one step to the left or the right, or halts the computation. The choice of which replacement symbol to write, which direction to move the head, and whether to halt is based on a finite table that specif ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Oracle Machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used. Oracles An oracle machine can be conceived as a Turing machine connected to an oracle. The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or a function problem. The problem does not have to be computable; the oracle is not assumed to be a Turing machine or computer program. The oracle is simply a "black box" that is able to produce a solution for any instance of a given computational problem: * A decision problem is represented as a set ''A'' of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Decision Problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natural number is prime. Another example is the problem, "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?" A decision procedure for a decision problem is an algorithmic method that answers the yes-no question on all inputs, and a decision problem is called decidable if there is a decision procedure for it. For example, the decision problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?" is decidable since there is a decision procedure called long division that gives the steps for determining whether ''x'' evenly divides ''y'' and the correct answer, ''YES'' or ''NO'', accordingly. Some of the most important problems in mathematics are undecidable, e.g. the halting problem. The field of computational ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP (complexity)
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the Set (mathematics), set of decision problems for which the Computational complexity theory#Problem instances, problem instances, where the answer is "yes", have mathematical proof, proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.''Polynomial time'' refers to how quickly the number of operations needed by an algorithm, relative to the size of the problem, grows. It is therefore a measure of efficiency of an algorithm. * NP is the set of decision problems ''solvable'' in polynomial time by a nondeterministic Turing machine. * NP is the set of decision problems ''verifiable'' in polynomial time by a deterministic Turing machine. The first definition is the basis for the abbreviation NP; "Nondeterministic alg ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
If And Only If
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both statements are true or both are false. The connective is biconditional (a statement of material equivalence), and can be likened to the standard material conditional ("only if", equal to "if ... then") combined with its reverse ("if"); hence the name. The result is that the truth of either one of the connected statements requires the truth of the other (i.e. either both statements are true, or both are false), though it is controversial whether the connective thus defined is properly rendered by the English "if and only if"—with its pre-existing meaning. For example, ''P if and only if Q'' means that ''P'' is true whenever ''Q'' is true, and the only case in which ''P'' is true is if ''Q'' is also true, whereas in the case of ''P if Q ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time Turing Reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second. A polynomial-time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. By contraposition, if no efficient algorithm exists for the first problem, none exists for the second either. Polynomial-time reductions are frequently used in complexity theory for defining both complexity classes and complete problems ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial Hierarchy
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH. Classes within the hierarchy have complete problems (with respect to polynomial-time reductions) that ask if quantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level. Definitions There are multiple equivalent definitions of the classes of the polynomial hierarchy. Oracle definition For the oracle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
