Padding, commitment and self-reducibility

DOI10.1016/0304-3975(91)90190-DMaRDI QIDQ808694zbMATH OpenFDO

Authors 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 classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• scientific article; zbMATH DE number 4096780
• scientific article; zbMATH DE number 522855
• Random-Self-Reducibility of Complete Sets
• Easily Checked Generalized Self-Reducibility
• Natural Self-Reducible Sets

Cites work

• scientific article; zbMATH DE number 3845080 (Why is no real title available?)
• scientific article; zbMATH DE number 4022646 (Why is no real title available?)
• scientific article; zbMATH DE number 3594673 (Why is no real title available?)
• A Note on Sparse Complete Sets
• Natural Self-Reducible Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On helping by robust oracle machines
• On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis

Cited in

(4)

• scientific article; zbMATH DE number 4096780 (Why is no real title available?)
• Easily Checked Generalized Self-Reducibility
• Natural Self-Reducible Sets
• scientific article; zbMATH DE number 522855 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808694)