Deterministic query complexity is a simplified model of computation where the resource measured is only the number of questions to the input to get information about individual input bits, while all other operations are for free. In the randomized model the queries can be chosen probabilistically, and in the quantum model they can be in superposition. While we have made significant progress in understanding all three models, numerous important questions (some of them over 40 years old) remain still unsolved.
展开▼
