No label defined (Q4356579)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1069617
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1069617 |
Statements
23 March 1998
0 references
computational complexity
0 references
polynomial time complexity
0 references
NP problem
0 references
complexity theory of numerical analysis
0 references
polynomial time
0 references
algorithms
0 references
condition number
0 references
0.7969556450843811
0 references
0.7645519375801086
0 references
0.7617629170417786
0 references
The aim of the paper is a thorough discussion on the complexity theory of numerical analysis. According to computer science, an algorithm defined by a Turing machine is in polynomial time if the computing time \(T(y)\) on the input \(y\) satisfies: \[ T(y)\leq K(\text{size}(y))^c,\tag{1} \] where \(\text{size}(y)\) is the number of bits for representing \(y\). A problem is said to be P (or tractable) if there is a polynomial time algorithm (i.e. Turing machine) to solve it. Since in numerical analysis most algorithms are solving problems only approximately, with accuracy \(\varepsilon>0\), or precision \(\log\varepsilon^{-1}\), the paper redefines the ``polynomial complexity'' as: \[ T(y,\varepsilon)\leq K(\mu(y)+ \text{size}(y)- \log\varepsilon)^c,\tag{2} \] where \(y=(y_1,\dots, y_n)\), \(\text{size}(y)= n\), \(y_i\in\mathbb{R}\) representing the input of the numerical problem, and \(\mu(y)\) being the condition number of the particular problem. An estimate of the probability distribution of \(\mu\) takes the form: \[ \text{prob}\{y: \mu(y)\geq K\}\leq\Biggl({1\over K}\Biggr)^c,\tag{3} \] where a probability measure has been put on the space of inputs. Now the complexity theory of numerical analysis is represented by a two-parts scheme: Part 1 is the estimate (2), and Part 2 is the estimate (3) of the condition number. The existence of the corresponding fundamental problem \(\text{P}=\text{NP}\) over the set of real numbers \(\mathbb{R}\) is also investigated. For the entire collection see [Zbl 0868.00024].
0 references