Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Sum_of_radicals> ?p ?o. }
Showing items 1 to 22 of
22
with 100 items per page.
- Sum_of_radicals abstract "In computational complexity theory there is an open problem whether some information about the sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum. It is of importance for many problems in computational geometry, since the computation of the Euclidean distance between two points in general case involves the computation of a square root, and therefore the perimeter of a polygon or the length of a polygonal chain takes the form of a sum of radicals.The sum of radicals is defined as a finite linear combination of radicals:where are natural numbers and are real numbers.Most theoretical research in computational geometry of combinatorial character assumes the computational model of infinite precision real RAM, i.e., an abstract computer in which real numbers and operations with them are performed with infinite precision and the input size of a real number and the cost of an elementary operation are constants. However there is research in computational complexity, especially in computer algebra, where the input size of a number is the number of bits necessary for its representation.In particular, of interest in computational geometry is the problem of determining the sign of the sum of radicals. For instance, the length of a polygonal path in which all vertices have integer coordinates may be expressed using the Pythagorean theorem as a sum of integer square roots, so in order to determine whether one path is longer or shorter than another in a Euclidean shortest path problem, it is necessary to determine the sign of an expression in which the first path's length is subtracted from the second; this expression is a sum of radicals.In a similar way, the sum of radicals problem is inherent in the problem of minimum-weight triangulation in the Euclidean metric. In 1991, Blömer proposed a polynomial time Monte Carlo algorithm for determining whether a sum of radicals is zero, or more generally whether it represents a rational number.While Blömer's result does not resolve the computational complexity of finding the sign of the sum of radicals, it does imply that if the latter problem is in class NP, then it is also in co-NP.".
- Sum_of_radicals wikiPageID "22231261".
- Sum_of_radicals wikiPageRevisionID "491962068".
- Sum_of_radicals hasPhotoCollection Sum_of_radicals.
- Sum_of_radicals subject Category:Computational_geometry.
- Sum_of_radicals subject Category:Computational_problems.
- Sum_of_radicals subject Category:Computer_algebra.
- Sum_of_radicals type Abstraction100002137.
- Sum_of_radicals type Attribute100024264.
- Sum_of_radicals type ComputationalProblems.
- Sum_of_radicals type Condition113920835.
- Sum_of_radicals type Difficulty114408086.
- Sum_of_radicals type Problem114410605.
- Sum_of_radicals type State100024720.
- Sum_of_radicals comment "In computational complexity theory there is an open problem whether some information about the sum of radicals may be computed in polynomial time depending on the input size, i.e., in the number of bits necessary to represent this sum.".
- Sum_of_radicals label "Sum of radicals".
- Sum_of_radicals sameAs m.05q50ly.
- Sum_of_radicals sameAs Q7636891.
- Sum_of_radicals sameAs Q7636891.
- Sum_of_radicals sameAs Sum_of_radicals.
- Sum_of_radicals wasDerivedFrom Sum_of_radicals?oldid=491962068.
- Sum_of_radicals isPrimaryTopicOf Sum_of_radicals.