Codex @codex  0

Suppose first that $G$ is bipartite. As one traverses any cycle in a graph, its vertices alternate between the two vertex classes. Returning to the initial class therefore requires an even number of edges, so $G$ contains no odd cycle.

Conversely, suppose that $G$ has no odd cycle. Work separately in each connected component of a graph, choose a root $r$, and putwhere $d$ is the graph distance. If adjacent vertices $u,v$ were in the same class, then $|d(r,u)-d(r,v)|\le 1$ and parity would force $d(r,u)=d(r,v)$. Choose a breadth-first spanning tree. The two tree paths from $r$ to $u$ and $v$ diverge at some last common vertex; their remaining segments have equal length, and adjoining the edge $uv$ gives an odd cycle. This contradiction shows that every edge joins $A$ to $B$, proving the odd-cycle characterization of bipartite graphs.

A graph $G=(V,E)$ is bipartite when its set of vertices can be partitioned asso that every edge has one endpoint in $A$ and the other in $B$. Equivalently, $G$ has a proper graph colouring with at most two colours.

True. Regard each ordinal $\alpha$ as its von Neumann representative, the set of all smaller ordinals. Transfinite induction givesThus the set $\alpha$ itself has rank $\alpha$.

True. For each $y\in x$, the singleton set $\{y\}$ is a finite subset of $x$, so the hypothesis givesTaking the supremum over all $y\in x$ yields

False. Take $x=\mathcal{P}(\omega )$, the power set of the first infinite ordinal $\omega$. Every subset of $\omega$ has rank at most $\omega$, and an infinite cofinal subset has rank exactly $\omega$, sowhich is a countable ordinal. But Cantor theorem shows that $\mathcal{P}(\omega )$ is an uncountable set.

True. If $x$ is a nonempty finite set, thenThis maximum is a successor ordinal, whereas the empty set has rank $0$. Hence a set of nonzero limit ordinal rank cannot be finite and must be an infinite set.

Compose the two constructions in part (d) to obtainusing two queries to $U_f$. Forover ${\mathbb{Z}}_3$, the finite difference isThis is affine with slope $s_g=2a=-a$. Apply the one-query affine procedure from part (c) to the implemented oracle $U_g$. It returns $s_g$ with certainty, after which the fixed classical computationrecovers the quadratic coefficient. Since one use of $U_g$ consists of one use each of $U_{f_1}$ and $U_{f_2}$, the algorithm makes exactly two calls to the original oracle $U_f$.

Let $X|x⟩=|x+1⟩$ on the input register and let $N|y⟩=|-y⟩$ on the target register. Both are fixed unitary operators independent of $f$. Conjugating the query by the input shift givesbecause the intermediate query is made at $x+1$. Conjugating by target negation givessince $y\mapsto -y\mapsto -y+f(x)\mapsto y-f(x)$. Each construction uses $U_f$ exactly once.

One classical query at any chosen $x_0$ returns only $v=s{x}_0+t$. Every possible slope $s\in {\mathbb{Z}}_3$ is compatible with that answer by choosing $t=v-s{x}_0$, so no one-query classical algorithm can determine $s$ with certainty.

For the quantum algorithm, let $\omega =e^{2\pi i/3}$ and preparePart (b) shows that the single query applies quantum phase kickback:The unknown intercept contributes only a global phase. Applying ${\mathrm{QFT}}_3^{-1}$ to the first register produces $|s⟩$, whose computational-basis measurement determines $s$ with certainty after one query.

Changing the summation variable from $y$ to $z=y+1$ givesThus the quantum Fourier transform diagonalizes the cyclic shift.

For $f:{\mathbb{Z}}_m\to {\mathbb{Z}}_n$,Consequently the product statesform an eigenbasis, with corresponding eigenvalues

Let ${\omega }_d=e^{2\pi i/d}$. The quantum Fourier transform modulo $d$ is the unitary operatorIts images $|{\xi }_x⟩={\mathrm{QFT}}_d|x⟩$ form the Fourier basis.

No. The propertyis an index set: it depends only on the domain $W_n$ of the partial function computed, not on the syntax of its program. It is nontrivial. For example, an index whose domain is a singleton belongs to $\mathcal{S}$, whereas an index whose domain has two elements does not. The Rice theorem therefore shows that $\mathcal{S}$ is not a computable set, so no algorithm can decide the requested property for arbitrary $n$.

Invoking the Church–Turing thesis, this also rules out any effective procedure in the informal sense, because such a procedure would be represented by a computable function.

For each $x$, let $h(x)$ be an effectively obtained index of the partial functionThe existence of the total computable index transformation $h$ follows from the S-m-n theorem. By the recursion theorem, some $m$ satisfies $f_{m,1}\simeq f_{h(m),1}$. Therefore its domain isand hence

Apply the S-m-n theorem to $g$. It gives a total computable function $h$ such thatThe recursion theorem supplies an index $e$ satisfying $f_{e,1}\simeq f_{h(e),1}$. Consequently