We consider the following Colourful generalization of Linear Programming: given sets of points Sl,..., Sk ⊂ ℝd, referred to as colours, and a point b ∈ ℝd, decide whether there is a colourful T = {sl,..., sk} such that b ∈ conv (T), and if there is one, find it. Linear Programming is obtained by taking k = d + 1 and S1 = ... = Sd+1. If k = d + 1 and b ∈ ∩i=1d+1conv (S)i) then a solution always exists: we describe an efficient iterative approximation algorithm for this problem, that finds a colourful T whose convex hull contains a point ε close to b, and analyze its real arithmetic and Turing time complexities. In contrast, we show that Colourful Linear Programming is strongly NP-complete. We consider a class of linear algebraic relatives of Colourful Linear Programming, and give a computational complexity classification of the related decision and counting problems that arise. We also introduce and discuss the complexity of a hierarchy of (w1,w2)-Matroid-Basis-Nonbasis problems, and give an application of Colourful Linear Programming to the algorithm problems of Tverberg's theorem in combinatorial geometry.
