Deutsch–Jozsa promise

Let $n\ge 1$, let $N:=2^n$, and let $f:\{0,1{\}}^n\to \{0,1\}$ be the total function of a Promise query instance and oracle family. The Deutsch–Jozsa promise is the decision task with YES set consisting of constant functions and NO set consisting of functions taking each value $0$ and $1$ exactly $N\mathrm{/}2$ times. The required output is constant or balanced, respectively. Here $n$ is the address width, and $N$ is the number of addresses, as supplied by Big-endian bit-string indices are bijective and The cardinality $\mid A\mid$ of a finite set. Encode an instance by its $N$-bit truth table in lexicographic address order; its encoded input size is therefore $N$, not $n$, under Input encoding and size for algorithmic tasks. In the query-instance convention, the length-$N$ family has address width $a(N)=n$ and reply width $b(N)=1$; the public parameter $n$ determines the registers, while the unknown truth table is supplied through oracle queries. Lengths that are not powers of two at least two have empty promise.