Input: Some fixed $k>1$, vectors $x^i,y^i\in\mathbb R^k$ for $1\le i\le n$. Output: A subset $I\subset\{1,\dots,n\}$ of maximal size such that $(x^i-x^j)^T(y^i-y^j) \ge 0$ for all $i,j\in I$. Question: Can this be computed in polynomial time in $n$? Remarks: For $k=1$ this is equivalent to the p...

I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question): Given a list of Persons, and two arbitrary Persons out of that list, we need to find the minimum nth-degree relationship between them. Here are the definitions of Person a...