Deciding whether a graph contains a complete balanced bipartite graph Is it known whether the following problem is in P or is NP-complete?

Problem: given an input graph $G$ on $n$ vertices, decide whether $G$ contains a complete $n/2 \times n/2$ bipartite graph.
If the vertex pair $(u, v)$ is not in $E$ then they can't be on opposite sides of the partition, so they must be in the same half. Create a union-find data structure and merge every vertex pair which is not an edge. Then you just need to solve the partition (subset-sum) problem to group some disjoint sets into a set of size $\frac{|V|}{2}$. The union-find phase can be done in $O(V^2 \alpha(V))$ and the pseudo-polynomial algorithm for subset sum takes $O(V^2)$ so this is in P. (Thank you to those who corrected an earlier error).

In the other direction, an oracle for balanced bipartite subgraph would give a pseudo-polynomial algorithm for the partition problem.

FWIW the generalisation which takes a parameter $K$ and asks whether there's a subgraph of $G$ which is a complete $K \times K$ bipartite graph is NP-complete by reduction from CLIQUE. Hat tip to Mohammad Al-Turkistany who cited a reference which proves this even when $G$ is known a priori to be bipartite: David S. Johnson, The NP-completeness column: An ongoing guide. Journal of Algorithms, 8(3):438–448, 1987.