On 1-truth-table-hard languages

DOI10.1016/0304-3975(93)90126-EzbMath0780.68041MaRDI QIDQ1261477

James S. Royer, Homer, Steven, Stuart A. Kurtz

Publication date: 3 October 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

EXP\(1-tt\)-complete setmany-one complete

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Almost every set in exponential time is P-bi-immune ⋮ Every polynomial-time 1-degree collapses if and only if P = PSPACE ⋮ Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Nontriviality for exponential time w.r.t. weak reducibilities ⋮ Non-uniform reductions ⋮ Two queries ⋮ Almost complete sets. ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Special issue: 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Seattle, WA, USA, June 1--3, 1998 ⋮ Almost every set in exponential time is P-bi-immune

Cites Work

• Unnamed Item
• Unnamed Item
• A comparison of polynomial time completeness notions
• On one-way functions and polynomial-time isomorphisms
• Collapsing degrees
• Indexings of subrecursive classes
• A comparison of polynomial time reducibilities
• Complete Problems and Strong Polynomial Reducibilities

This page was built for publication: On 1-truth-table-hard languages