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. 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.