What's the relationship between the Ham Sandwich Theorem and the PPAD Complexity Class?

Question

Wiki says:

"The Ham sandwich theorem is known to lie in PPAD but it remains an open question as to whether or not it is PPAD-complete."

What is the computational problem based on the Ham Sandwich Theorem to which this sentence refers? Intuitively, I would think the problem would be "find a ham sandwich cut for a set of points in $\mathbb{R}^n$," but that can't be right - we know how to solve the problem in linear time in the two-dimensional case, which would seem pretty strong evidence that this problem is not PPAD-complete.

EDIT: I found a claim here that the problem is:

"Given n sets of 2n points (each) in n dimensions, is there a single hyperplane that bisects each set (i.e divides it into two sets of size n)."

If this is true, then my question becomes: how can this problem be PPAD-complete? I thought PPAD-complete problems were search problems (such as End-Of-The-Line, 2-Nash, etc.) and not decision problems.

Answer 1

These sources are probably referring to the original paper by Christos Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf

The problem is:

Discrete ham sandwich. Given $2n^2$ points in generic position in $n$ dimensions, separated into $n$ groups with $2n$ points each, find a hyperplane dividing all groups in half.

(The paper says "seperate them" instead of "separated", but that doesn't seem to make any sense.)

Papadimitriou also notes that the problem is in FP for any fixed dimension.