Using self-reducibilities to characterize polynomial time

DOI10.1006/INCO.1993.1035MaRDI QIDQ2366567zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 30 August 1993

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL http://digital.library.wisc.edu/1793/58934

zbMATH Keywords

\(p\)-cheatabilitynear-testabilitypolynomial-time computable setsself-reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The effect of a set having a self-reducibility structure is studied. Three variations on the notion of Turing self-reducibility are studied: near-testability, word-decreasing self-reducibility, and \(p\)- cheatability. The complexity class of polynomial-time computable sets is characterized in several non-trivial ways using the above notions. In the concluding section several research questions building upon this work are posed.

Recommendations

• Some results on selectivity and self-reducibility
• Characterizing polynomial complexity classes by reducibilities
• scientific article; zbMATH DE number 4092778
• scientific article; zbMATH DE number 4126690

Cited in

(8)

• Bounded queries to SAT and the Boolean hierarchy
• Some connections between bounded query classes and non-uniform complexity.
• Characterizing polynomial complexity classes by reducibilities
• scientific article; zbMATH DE number 4022646 (Why is no real title available?)
• scientific article; zbMATH DE number 4092778 (Why is no real title available?)
• Constructivizing Membership Proofs in Complexity Classes
• A note on the self-witnessing property of computational problems
• Bi-immunity results for cheatable sets

This page was built for publication: Using self-reducibilities to characterize polynomial time

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