|
Square-root Sum Problem
The square-root sum problem (SRS) is a computational decision problem from the field of numerical analysis, with applications to computational geometry. Definitions SRS is defined as follows:Given positive integers a_1,\ldots,a_k and an integer ''t'', decide whether \sum_^k \sqrt \leq t.An alternative definition is:Given positive integers a_1,\ldots,a_k and b_1,\ldots,b_k, decide whether \sum_^k \sqrt \leq \sum_^k \sqrt. The problem was posed in 1981, and likely earlier. Run-time complexity SRS can be solved in polynomial time in the Real RAM model. However, its run-time complexity in the Turing machine model is open, as of 1997. The main difficulty is that, in order to solve the problem, the square-roots should be computed to a high accuracy, which may require a large number of bits. The problem is mentioned in the Open Problems Garden. Blomer presents a polynomial-time Monte Carlo algorithm for deciding whether a sum of square roots equals zero. The algorithm applies more ... [...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] |
Subspace Theorem
In mathematics, the subspace theorem says that points of small height in projective space lie in a finite number of hyperplanes. It is a result obtained by . Statement The subspace theorem states that if ''L''1,...,''L''''n'' are linearly independent linear forms in ''n'' variables with algebraic coefficients and if ε>0 is any given real number, then the non-zero integer points ''x'' with :, L_1(x)\cdots L_n(x), 0 is any given real number, then there are only finitely many rational ''n''-tuples (''x''1/y,...,''x''''n''/y) with :, a_i-x_i/y, [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomials
In mathematics, a polynomial is a mathematical expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer powers, and has a finite number of terms. An example of a polynomial of a single indeterminate is . An example with three indeterminates is . Polynomials appear in many areas of mathematics and science. For example, they are used to form polynomial equations, which encode a wide range of problems, from elementary word problems to complicated scientific problems; they are used to define polynomial functions, which appear in settings ranging from basic chemistry and physics to economics and social science; and they are used in calculus and numerical analysis to approximate other functions. In advanced mathematics, polynomials are used to construct polynomial rings and algebraic varieties, which are central concepts in algebra and a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Positive Semidefinite Matrix
In mathematics, a symmetric matrix M with real entries is positive-definite if the real number \mathbf^\mathsf M \mathbf is positive for every nonzero real column vector \mathbf, where \mathbf^\mathsf is the row vector transpose of \mathbf. More generally, a Hermitian matrix (that is, a complex matrix equal to its conjugate transpose) is positive-definite if the real number \mathbf^* M \mathbf is positive for every nonzero complex column vector \mathbf, where \mathbf^* denotes the conjugate transpose of \mathbf. Positive semi-definite matrices are defined similarly, except that the scalars \mathbf^\mathsf M \mathbf and \mathbf^* M \mathbf are required to be positive ''or zero'' (that is, nonnegative). Negative-definite and negative semi-definite matrices are defined analogously. A matrix that is not positive semi-definite and not negative semi-definite is sometimes called ''indefinite''. Some authors use more general definitions of definiteness, permitting the matrices to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semidefinite Programming
Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods. All linear programs and (convex) quadratic programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming ha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stochastic Games
In game theory, a stochastic game (or Markov game) is a repeated game with probabilistic transitions played by one or more players. The game is played in a sequence of stages. At the beginning of each stage the game is in some state. The players select actions and each player receives a payoff that depends on the current state and the chosen actions. The game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. The procedure is repeated at the new state and play continues for a finite or infinite number of stages. The total payoff to a player is often taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs. Stochastic games were introduced by Lloyd Shapley in the early 1950s. They generalize Markov decision processes to multiple interacting decision makers, as well as strategic-form games to dynamic situations in which the environment changes in response to t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Euclidean Traveling Salesman
In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem, the vehicle routing problem and the ring star problem are three generalizations of TSP. The decision version of the TSP (where given a length ''L'', the task is to decide whether the graph has a tour whose length is at most ''L'') belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (but no more than exponentially) with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minimum Spanning Tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. There are many use cases for minimum spanning trees. One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weight ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kurt Mehlhorn
Kurt Mehlhorn (born 29 August 1949) is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science. Education and career Mehlhorn graduated in 1971 from the Technical University of Munich, where he studied computer science and mathematics, and earned his Ph.D. in 1974 from Cornell University under the supervision of Robert Constable. Since 1975 he has been on the faculty of Saarland University in Saarbrücken, Germany, where he was chair of the computer science department from 1976 to 1978 and again from 1987 to 1989. Since 1990 has been the director of the Max Planck Institute for Computer Science, also in Saarbrücken. He has been on the editorial boards of ten journals, a trustee of the International Computer Science Institute in Berkeley, California, and a member of the board of governors of Jacobs University Bremen. He also served on the Engineering and Computer Science ju ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Numerical Analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods that attempt to find approximate solutions of problems rather than the exact ones. Numerical analysis finds application in all fields of engineering and the physical sciences, and in the 21st century also the life and social sciences like economics, medicine, business and even the arts. Current growth in computing power has enabled the use of more complex numerical analysis, providing detailed and realistic mathematical models in science and engineering. Examples of numerical analysis include: ordinary differential equations as found in celestial mechanics (predicting the motions of planets, stars and galaxies), numerical linear algebra in data analysis, and stochastic differential equations and Markov chains for simulati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can be solved by Turing machines using ''O''(''f''(''n'')) space for some function ''f'' of the input size ''n'', then we can define PSPACE formally asArora & Barak (2009) p.81 :\mathsf = \bigcup_ \mathsf(n^k). It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,Arora & Barak (2009) p.85 NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a nondeterministic Turing machine without needing much more space (even though it may use much more time).Arora & Barak (2009) p.86 Also, the complements of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE PSPACE. Relation among other classes The following re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Counting Hierarchy
In complexity theory, the counting hierarchy is a hierarchy of complexity classes. It is analogous to the polynomial hierarchy, but with NP replaced with PP. It was defined in 1986 by Klaus Wagner. More precisely, the zero-th level is C0P = P, and the (''n''+1)-th level is C''n''+1P = PPC''n''P (i.e., PP with oracle C''n''). Thus: * C0P = P * C1P = PP * C2P = PPPP * C3P = PPPPPP * ... The counting hierarchy is contained within PSPACE. By Toda's theorem, the 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. ... PH is entirely contained in PPP, and therefore in C2P = PPPP. References Further reading * {{compsci-stub Complexity classes Hierarchy ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
