Near-Testable Sets

DOI10.1137/0220033MaRDI QIDQ3978780zbMATH OpenOpenAlexFDO

Authors

Publication date 25 June 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220033

zbMATH Keywords

near-testabilityone-way functionparity polynomial timeself-reducibilitystructural complexity theory

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2011858
• Complete sets and closeness to complexity classes
• On intractability of the classUP
• Polynomial terse sets
• A note on closeness between \(NP\)-hard sets and \(C_= P\)

Cited in

(13)

• Polynomial terse sets
• On sets polynomially enumerable by iteration
• On the size of classes with weak membership properties
• A second step towards complexity-theoretic analogs of Rice's Theorem
• On membership comparable sets
• Study of the bounds on the number of basic sets in a test.
• On Sets with Efficient Implicit Membership Tests
• scientific article; zbMATH DE number 2011858 (Why is no real title available?)
• Strong self-reducibility precludes strong immunity
• Every Set in P Is Strongly Testable Under a Suitable Encoding
• On the power of parity polynomial time
• Sets computable in polynomial time on average
• Reducibility classes of P-selective sets

This page was built for publication: Near-Testable Sets

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