Loading...
Please wait, while we are loading the content...
Similar Documents
Comparison of Complexity over the Real vs . Complex Numbers
| Content Provider | Semantic Scholar |
|---|---|
| Author | Scheiblechner, Peter |
| Copyright Year | 2010 |
| Abstract | We compare complexity questions over the reals with their corresponding versions over the complex numbers. We argue in particular that the problem of deciding membership to a subspace arrangement is strictly harder over C than over R. There exist decision trees of polynomial depth over R deciding this problem, whereas certain complex arrangements have no polynomial depth decision trees. This follows from a new lower bound for the decision complexity of a complex algebraic set X in terms of the sum of its (compactly supported) Betti numbers bc(X), which is for the first time better than logarithmic in bc(X). On the other hand, the existential theory over R is strictly harder than that over C. This follows from the observation that the former cannot be solved by a complex BSS-machine. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.scheiblechner.ch/files/realComplex-extAbs.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
