Electronic Resource
Springer
Computational complexity
7 (1998), S. 163-173
ISSN:
1420-8954
Keywords:
Key words. Sperner's lemma; robust Turing machines.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract. Sperner's lemma states that any admissible coloring of any triangulation of the unit triangle has a 3‐colored triangle. In this paper, we first show that any algorithm to find this 3‐colored triangle that treats the coloring itself as an oracle must be in the worst case linear in the size of the triangulation. Successively, we apply this lower bound to solve three open questions on robust machines posed by Hartmanis and Hemachandra.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s000370050008
Permalink
|
Location |
Call Number |
Expected |
Availability |