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.
SPERNER'S LEMMA AND ROBUST MACHINES / P. CRESCENZI; R. SILVESTRI. - In: COMPUTATIONAL COMPLEXITY. - ISSN 1016-3328. - STAMPA. - 7:(1998), pp. 163-173. [10.1007/s000370050008]
SPERNER'S LEMMA AND ROBUST MACHINES
CRESCENZI, PIERLUIGI;
1998
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
