show/hide this revision's text 2 added 254 characters in body

This problem is clearly in NP (guess which polytopes) and becomes NP-complete if we replace $2/3$ with $1/2$. 1/2$ and make it a decision problem, dropping the promise that such a $p$ exists. In particular we can reduce integer programming feasibility to this problem.

Say we wish to determine whether $Ax = b$ has a solution $x$ which is a zero-one vector. We can define $k = 2n$ polytopes $P_i^j = \{x \mid x_i = j, Ax = b, 0\leq x\leq 1\}$ for integers $1\leq i\leq n$ and $0\leq j\leq 1$. A zero-one solution of $Ax=b$ is the same as a point which lies in $l = n = k/2$ of these polytopes.

I imagine there is a simple reduction showing that the problem is still hard if we use the fraction $2/3$ (or any other fixed fraction) instead of $1/2$. But I'm guessing that you just gave $2/3$ as an example so I haven't thought about it. Similarly I am guessing that the problem is still hard if you somehow know that such a $p$ exists and merely want to find one, but I haven't thought of how to show this either.

show/hide this revision's text 1

This problem is clearly in NP (guess which polytopes) and becomes NP-complete if we replace $2/3$ with $1/2$. In particular we can reduce integer programming feasibility to this problem.

Say we wish to determine whether $Ax = b$ has a solution $x$ which is a zero-one vector. We can define $k = 2n$ polytopes $P_i^j = \{x \mid x_i = j, Ax = b, 0\leq x\leq 1\}$ for integers $1\leq i\leq n$ and $0\leq j\leq 1$. A zero-one solution of $Ax=b$ is the same as a point which lies in $l = n = k/2$ of these polytopes.

I imagine there is a simple reduction showing that the problem is still hard if we use the fraction $2/3$ (or any other fixed fraction) instead of $1/2$. But I'm guessing that you just gave $2/3$ as an example so I haven't thought about it.