I'm studying query complexity and I'm trying to understand Bernstein-Vazirani's problem (https://en.wikipedia.org/wiki/Bernstein%E2%80%93Vazirani_algorithm) and Simon's problem (https://en.wikipedia.org/wiki/Simon%27s_problem). However, I've only seen the query complexity model defined for functions $f\colon\left\{0,1\right\}^n\to\left\{0,1\right\}$ (for example, in the survey by Buhrman and de Wolf [1]) and I can't use it for those problems, since they are defined as functions $f\colon\left\{0,1\right\}^n\to\left\{0,1\right\}^m$ (more specifically, $n=2^m$ and $m\geq 1$ for these particular problems).

Do you know any references where they define the query complexity model for functions $f\colon\left\{0,1\right\}^n\to\left\{0,1\right\}^m$?

[1] Harry Buhrman and Ronald De Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21–43, 2002.

  • 3
    $\begingroup$ The Boolean-output case ($\{0,1\}$) easily generalizes to non-Boolean case. What prevents you from generalizing by yourself mentally? $\endgroup$ – Lwins May 22 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.