Sperner's lemma states that any admissible coloring of any triangulation of the unit triangle has a three-colored triangle. It is shown that any algorithm to find a three-colored triangle in any admissible coloring that treats the coloring itself as an oracle must be in the worst case linear in n. By making use of such lower bound, a negative answer is obtained for two problems regarding robust oracle machines left open by J. Hartmanis and L. Hemachandra. By making use of techniques similar to those used in that paper, a third open problem is solved.
SPERNER'S LEMMA AND ROBUST MACHINES / P. CRESCENZI; R. SILVESTRI. - STAMPA. - (1993), pp. 194-199. (Intervento presentato al convegno EIGHTH STRUCTURE IN COMPLEXITY THEORY CONFERENCE) [10.1109/SCT.1993.336527].
SPERNER'S LEMMA AND ROBUST MACHINES
CRESCENZI, PIERLUIGI;
1993
Abstract
Sperner's lemma states that any admissible coloring of any triangulation of the unit triangle has a three-colored triangle. It is shown that any algorithm to find a three-colored triangle in any admissible coloring that treats the coloring itself as an oracle must be in the worst case linear in n. By making use of such lower bound, a negative answer is obtained for two problems regarding robust oracle machines left open by J. Hartmanis and L. Hemachandra. By making use of techniques similar to those used in that paper, a third open problem is solved.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
