Back to matchesWe found a matchYour institution may have access to this item. Find your institution then sign in to continue.TitleDTML IS LOGSPACE HARD UNDER NC<sup>1</sup> REDUCTIONS.AuthorsSARNATH, R.AbstractThe Different Than Majority Labeling (DTML) problem has a simple polynomial time algorithm, but is not known to be in NC. In this paper, we show that the DTML problem is extremely unlikely to have an NC1 algorithm.PublicationParallel Processing Letters, 1992, Vol 2, Issue 2/3, p189ISSN0129-6264Publication typeArticleDOI10.1142/S0129626492000313