Using self-reducibilities to characterize polynomial time

DOI10.1006/inco.1993.1035zbMath0776.68044OpenAlexW2034041719MaRDI QIDQ2366567

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

self-reducibility\(p\)-cheatabilitynear-testabilitypolynomial-time computable sets

Mathematics Subject Classification ID

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

Related Items

Bi-immunity results for cheatable sets, Some connections between bounded query classes and non-uniform complexity., Bounded queries to SAT and the Boolean hierarchy