Padding, commitment and self-reducibility

DOI10.1016/0304-3975(91)90190-DzbMATH Open0732.68041MaRDI QIDQ808694FDOQ808694

Authors: Sanjeev N. Khadilkar, Somenath Biswas 

Publication date: 1991

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

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

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Natural Self-Reducible Sets
• Easily Checked Generalized Self-Reducibility

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)