One query reducibilities between partial information classes

DOI10.1016/J.TCS.2005.07.006MaRDI QIDQ2575741zbMATH OpenOpenAlexFDO

Authors Sebastian Bab, Arfst Nickelsen

Publication date 6 December 2005

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

Full work available at URL https://doi.org/10.1016/j.tcs.2005.07.006

zbMATH Keywords

cheatable languagepartial information algorithm

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Mathematical Foundations of Computer Science 2004
• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 1848275
• Reducibility classes of P-selective sets
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets

Cites work

• A proof of Beigel's cardinality conjecture
• Approximable sets
• scientific article; zbMATH DE number 1678392 (Why is no real title available?)
• scientific article; zbMATH DE number 1303203 (Why is no real title available?)
• scientific article; zbMATH DE number 512828 (Why is no real title available?)
• scientific article; zbMATH DE number 1543037 (Why is no real title available?)
• scientific article; zbMATH DE number 1834678 (Why is no real title available?)
• scientific article; zbMATH DE number 1848275 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• On self-reducibility and weak P-selectivity
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Polynomial terse sets
• Polynomial-Time Membership Comparable Sets
• Reducibility classes of P-selective sets
• Some connections between bounded query classes and non-uniform complexity.
• Time bounded frequency computations

Cited in

(3)

• scientific article; zbMATH DE number 1848275 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Mathematical Foundations of Computer Science 2005

This page was built for publication: One query reducibilities between partial information classes

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