Computing variance for interval data is NP-hard

When we have only interval ranges [ x i , x i ] of sample values x 1 ,…, x n , what is the interval [ V, V ] of possible values for the variance V of these values? We prove that the problem of computing the upper bound V is NP-hard. We provide a feasible (quadratic time) algorithm for computing the lower bound V on the variance of interval data. We also provide a feasible algorithm that computes V under reasonable easily verifiable conditions.