|
UP (complexity)
In complexity theory, UP (unambiguous non-deterministic polynomial-time) is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input. UP contains P and is contained in NP. A common reformulation of NP states that a language is in NP if and only if a given answer can be verified by a deterministic machine in polynomial time. Similarly, a language is in UP if a given answer can be verified in polynomial time, and the verifier machine only accepts at most ''one'' answer for each problem instance. More formally, a language ''L'' belongs to UP if there exists a two-input polynomial-time algorithm ''A'' and a constant ''c'' such that :if x in ''L'' , then there exists a unique certificate ''y'' with , y, = O(, x, ^c) such that :if x is not in ''L'', there is no certificate ''y'' with , y, = O(, x, ^c) such that :algorithm ''A'' verifies ''L'' in polynomial time. UP (and its complement c ... [...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] |
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] |
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] |
Unambiguous Turing Machine
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. An unambiguous Turing machine is a special kind of non-deterministic Turing machine, which, in some sense, is similar to a deterministic Turing machine. Formal definition A ''non-deterministic Turing machine'' is represented formally by a 6-tuple, M=(Q, \Sigma, \iota, \sqcup, A, \delta), as explained in the page ''non-deterministic Turing machine''. An ''unambiguous Turing machine'' is a non-deterministic Turing machine such that, for every input w=a_1,a_2,...,a_n, there exists at most one sequence of configurations c_0,c_1,...,c_m with the following conditions: # c_0 is the initial configuration with input w # c_ is a successor of c_i and # c_m is an accepting configuration. In other words, if w is accepted by M, there is exactly one accepting computation. Expressivity The ''language'' of an unambiguous Turing ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(''n''O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or " tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb. Definition A language ''L'' is in P if and only if there exists a deterministic Turing machine ''M'', such that * ''M'' runs for polynomial time on all inputs * For all ''x'' in ''L'', ''M'' outputs 1 * For all ''x'' not in ''L'', ''M'' outputs 0 P can also be viewed as a uniform family of Boolean circuits. A language ''L'' is in P if and only if there exists a polynomial-time uniform family of Boolean circuits \, such that * For all n \in ... [...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] |
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the ''yes'' and ''no'' answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. For example, one important problem is whether a number is a prime number. Its complement is to determine whether a number is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. There is a Turing reduction from every problem to its complement problem. The complement operation is an involution, meaning it "undoes itself", or the complement of the complement is the original problem. One can generalize this to the complement of a complexity class, called the complement class, which is the set of complements of every problem in the class. If a class is called C, its complement is conventionally labelled co-C. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integer Factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a composite number, or it is not, in which case it is a prime number. For example, is a composite number because , but is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example . Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem. To factorize a small integer using mental or pen-and-paper arithmetic, the simplest method is trial division: checking if the number is divisible by prime numbers , , , and so on, up to the square root of . For larger numbers, especially when using a computer, various more sophis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Parity Game
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owner of the node that the token falls on selects the successor node (does the next move). The players keep moving the token, resulting in a (possibly infinite) path, called a play. The winner of a finite play is the player whose opponent is unable to move. The winner of an infinite play is determined by the priorities appearing in the play. Typically, player 0 wins an infinite play if the largest priority that occurs infinitely often in the play is even. Player 1 wins otherwise. This explains the word "parity" in the title. Parity games lie in the third level of the Borel hierarchy, and are consequently determined. Games related to parity games were implicitly used in Rabin's proof of decidability of the monadic second-order theory of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Valiant–Vazirani Theorem
The Valiant–Vazirani theorem is a theorem in computational complexity theory stating that if there is a polynomial time algorithm for Unambiguous-SAT, then NP = RP. It was proven by Leslie Valiant and Vijay Vazirani in their paper titled ''NP is as easy as detecting unique solutions'' published in 1986. The Valiant–Vazirani theorem implies that the Boolean satisfiability problem, which is NP-complete, remains a computationally hard problem even if the input instances are promised to have at most one satisfying assignment. Proof outline Unambiguous-SAT is the promise problem of deciding whether a given Boolean formula that has at most one satisfying assignment is unsatisfiable or has exactly one satisfying assignment. In the first case, an algorithm for Unambiguous-SAT should reject, and in the second it should accept the formula. If the formula has more than one satisfying assignment, then there is no condition on the behavior of the algorithm. The promise prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Promise Problem
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the ''yes'' instances (the inputs for which an algorithm must return ''yes'') and ''no'' instances do not exhaust the set of all inputs. Intuitively, the algorithm has been ''promised'' that the input does indeed belong to set of ''yes'' instances or ''no'' instances. There may be inputs which are neither ''yes'' nor ''no''. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt. Definition A decision problem can be associated with a language L \subseteq \^*, where the problem is to accept all inputs in L and reject all inputs not in L. For a promise problem, there are two languages, L_ and L_, which must be disjoint, which means L_ \cap L_ = \varnothing, such that all the inputs in L_ are to b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
