scientific article; zbMATH DE number 18631

DOI10.1007/BFB0029617MaRDI QIDQ3976034zbMATH OpenFDO

Authors Lane A. Hemaspaandra, Albrecht Hoene, William Gasarch

Publication date 26 June 1992

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0029617

zbMATH Keywords

characteristic vectormultiple queries

Mathematics Subject Classification ID

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

Review text

[For the entire collection see Zbl 0731.00026.] The authors introduce a notion of a characteristic vector of pairs of queries to an oracle and answers to them as well as a notion of a characteristic vector cost (CVC) of a special class \(C\) of so called interesting languages. The characteristic cost for an arbitrary language \(L\) belonging to \(C\) and an integer \(k\) is equal to the minimal number of queries sufficient to solve for every characteristic vector of the size \(k\) whether it coincides with \(L\) or not. A series of results concerning the coincidence of classes of languages and the Boolean hierarchies over them in terms of CVC are obtained.

Recommendations

• On checking versus evaluation of multiple queries
• Bounded Query Classes
• Oracles That Compute Values
• scientific article; zbMATH DE number 223336
• Queries and concept learning

Cited in

(2)

• On checking versus evaluation of multiple queries
• The complexity class θp2: Recent results and applications in AI and modal logic

This page was built for publication:

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