On 1-truth-table-hard languages

Steven Homer, Stuart Kurtz, James S Royer

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

The polynomial-time 1-tt-hard sets for EXP and RE are polynomial-time many-one-hard.

Original languageEnglish (US)
Pages (from-to)383-389
Number of pages7
JournalTheoretical Computer Science
Volume115
Issue number2
DOIs
StatePublished - Jul 19 1993

    Fingerprint

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this