Effective Search Problems

DOI10.1002/MALQ.19940400209MaRDI QIDQ4304108zbMATH OpenOpenAlexFDO

Authors Martin Kummer, Frank Stephan

Publication date 16 February 1995

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19940400209

zbMATH Keywords

bounded queriesoraclequery complexityrecursive functionssearch problemUlam's game

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatorics in computer science (68R05)

Recommendations

• Quantum and classical query complexities of local search are polynomially related
• Fault-tolerant search algorithms. Reliable computation with unreliable information
• Frequency computation and bounded queries
• scientific article; zbMATH DE number 512828
• Search Problems in the Decision Tree Model

Cited in

(12)

• Extremes in the degrees of inferability
• Optimal series-parallel trade-offs for reducing a function to its own graph
• The query complexity of witness finding
• Nondeterministic query algorithms
• A proof of Beigel's cardinality conjecture
• scientific article; zbMATH DE number 2169749 (Why is no real title available?)
• The complexity of ODD_n^A
• The query complexity of witness finding
• Enumerations of the Kolmogorov function
• Weak cardinality theorems
• Searching games with errors -- fifty years of coping with liars
• Frequency computation and bounded queries

This page was built for publication: Effective Search Problems

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