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.

New contributor
Victt is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 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

Victt is a new contributor. Be nice, and check out our Code of Conduct.

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.