Element uniqueness problem
- Element uniqueness problem
The element uniqueness problem is a fundamental problem in computational complexity theory, being a problem for which a direct proof exists [ [http://ru-linux-geek.livejournal.com/35523.html A proof I will never forget: An algorithms story] ] that its time complexity is Θ("n" log "n"), i.e., both the upper and lower bounds on its time complexity are of order of the linearithmic function, under a rather general model of computation called algebraic decision tree model. In other words, an asymptotically optimal algorithm of linearithmic time complexity is known for this problem.
The general problem is stated as follows:
*Given a collection of "n" objects, decide whether there are any identical ones.
The algebraic decision tree model basically means that the allowable algorithms are only the ones that can perform polynomial operations of bounded degree on the input data and comparisons of the results of these computations.
Lower bounds on computational complexity of a number of algorithmic problems are proved by reducing the element uniqueness problem to the problem in question, i.e., by demonstrating that the solution of the element uniqueness problem may be quickly found after solving the problem in question.
Restrictions
Decision tree models are inapplicable for determining lower bounds for algorithmic problems for objects that have some "a priori" properties which can be exploited in construction of algorithms. For example, if it is known that the "n" objects are integer numbers from the range [1.."n"] , then the element uniqueness problem may be solved in O("n") time by a modification of bucket sort.
References
Wikimedia Foundation.
2010.
Look at other dictionaries:
Closest pair of points problem — Closest pair of points shown in red The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. Its two… … Wikipedia
Finite element method — The finite element method (FEM) (sometimes referred to as finite element analysis) is a numerical technique for finding approximate solutions of partial differential equations (PDE) as well as of integral equations. The solution approach is based … Wikipedia
Word problem (mathematics) — In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements, is the algorithmic problem of deciding whether two given representatives represent the same element of the set.… … Wikipedia
Burnside's problem — The Burnside problem, posed by William Burnside in 1902 and one of the oldest and most influential questions in group theory, asks whether a finitely generated group in which every element has finite order must necessarily be a finite group. In… … Wikipedia
Hamburger moment problem — In mathematics, the Hamburger moment problem, named after Hans Ludwig Hamburger, is formulated as follows: given a sequence { αn : n = 1, 2, 3, ... }, does there exist a positive Borel measure μ on the real line such that:alpha n = int {… … Wikipedia
Meta element — Meta elements are the HTML or XHTML <meta … > element used to provide structured metadata about a Web page. Multiple elements are often used on the same page: the element is the same, but its attributes are different. Meta elements can be… … Wikipedia
Elliptic boundary value problem — In mathematics, an elliptic boundary value problem is a special kind of boundary value problem which can be thought of as the stable state of an evolution problem. For example, the Dirichlet problem for the Laplacian gives the eventual… … Wikipedia
Asymptotically optimal — In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly… … Wikipedia
Proximity problems — is a class of problems in computational geometry which involve estimation of distances between geometric objects. A subset of these problems stated in terms of points only are sometimes referred to as closest point problems[1], although the term… … Wikipedia
Nearest neighbor graph — A nearest neighbor graph of 100 points in the Euclidean plane. The nearest neighbor graph (NNG) for a set of n objects P in a metric space (e.g., for a set of points in the plane with Euclidean distance) is a directed graph with P being its… … Wikipedia
