On 1-truth-table-hard languages

Steven Homer, Stuart Kurtz, James Royer

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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
Issue number2
StatePublished - Jul 19 1993

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On 1-truth-table-hard languages'. Together they form a unique fingerprint.

Cite this