Characterizations and existence of easy sets without hard subsets

DOI10.3233/FI-2011-546MaRDI QIDQ3100945zbMATH OpenOpenAlexFDO

Authors Nicholas Q. Tran

Publication date 22 November 2011

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2011-546

zbMATH Keywords

\(\mathcal C\)-scant sets\(C\)-hollow setseasy setshard subsets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 3984573
• scientific article; zbMATH DE number 1008513
• Reductions to sets of low information content (extended abstract)
• Easy sets and hard certificate schemes
• OnP-subset structures

Cited in

(1)

• On the existence of n but not n + 1 easy combinators

This page was built for publication: Characterizations and existence of easy sets without hard subsets

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