Randomized Boolean decision trees: Several remarks

DOI10.1016/S0304-3975(98)00071-1zbMath0916.68146OpenAlexW2048106445MaRDI QIDQ1275008

Nikolai K. Vereshchagin

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00071-1

zbMATH Keywords

randomized algorithmBoolean decision treesdirectional algorithmsundirectional algorithms

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Lower bounds on probabilistic linear decision trees
• Complexity classes without machines: on complete languages for UP

This page was built for publication: Randomized Boolean decision trees: Several remarks