Padding, commitment and self-reducibility

DOI10.1016/0304-3975(91)90190-DzbMath0732.68041MaRDI QIDQ808694

Sanjeev N. Khadilkar, Somenath Biswas

Publication date: 1991

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

zbMATH Keywords

commitabilityd-self-reducibilityNP setspaddability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On helping by robust oracle machines
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
• A Note on Sparse Complete Sets
• Natural Self-Reducible Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Padding, commitment and self-reducibility