Some remarks on witness functions for nonpolynomial and noncomplete sets in NP

1985/01/01 by Deborah Joseph, Paul Young, Paul R. Young · 3 citations
Computer Science · Mathematics · #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computable function #Computer science #Conjecture #Cryptography and Data Security #Discrete mathematics #Function (biology) #Mathematical proof #Mathematics #Recursion (computer science) #Set (abstract data type) #Witness

paper · doi:10.1016/0304-3975(85)90140-9

crossref issued 1985/01/01 · crossref published 1985/01/01 · crossref published-print 1985/01/01 · openalex publication_date 1985/01/01 · crossref created 2003/05/13 · crossref deposited 2019/03/21 · openalex created_date 2025/10/10 · crossref indexed 2026/05/09 · openalex updated_date 2026/07/23

Citations

• Relativizations of the P = ?NP Question
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of NP and Other Complete Sets

Cited by

• Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
• Reducing the complexity of reductions
• Creative and productive sets [wikipedia]