Complexity of computing topological degree of lipschitz functions in n dimensions
Terrance E. Boult, Kris Sikorski · Journal of Complexity · 1986
We find lower and upper bounds on the complexity, comp(deg), of computing the topological degree of functions defined on the n -dimensional unit cube C n , f : C n → R n , n ≥ 2, which satisfy a Lipschitz condition with constant K and whose infinity norm at each point on the boundary of C n is at least d , d > 0, and such that K 8d ≥ 1 . A lower bound, comp low ≅ 2n( K 8d ) n−1 (c + n) is obtained for comp(deg), assuming that each function evaluation costs c and elementary arithmetic operations and comparisons cost unity. We prove that the topological degree can be computed using A = (⌊ K 2d + 1⌋ + 1) n − (⌊ K 2d + 1⌋ − 1) n function evaluations. It can be done by an algorithm ϕ ∗ due to Kearfott, with cost given by comp (ϕ ∗ ) ≅ A (c + ( n 2 2 )(n − 1)!) . Thus for small n, say n ≤ 5, and small K 2d , say K 2d ≤ 9 , the degree can be computed in time at most 10 5 ( c + 300). For large n and/or large K 2d the problem is intractable.