Title: Some remarks on polynomial time isomorphisms
Abstract: Joseph and Young [JY-85] hypothesized that the Berman-Hartmanis isomorphism conjecture fails if there exists a k-completely creative set in NP with no p-invertible p-completely productive functions. We verify this hypothesis for DEXT based on new results of p-creative sets in [Wan-89]. In particular, we prove that the isomorphism conjecture for DEXT fails iff there is a p-creative set for P in DEXT with no p-invertible p-productive functions.
Publication Year: 1990
Publication Date: 1990-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 9
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot