Hey Everyone, Post your answers to the Feb 22 In-Class Exercise here. Best, Chris

-- Feb 22 In-Class Exercise

We can show that a possible solution to the clustering problem is verifiable in polynomial time. Given a set partition of X, we can in @BT@O(n^2)@BT@ invocations of the distance function compute the distances between all members of the component of the set partition. If any two members are found to be further than B apart, we can immediately reject the partition as unsatisfactory. Otherwise, if we go through each component of the partition without running into the above situation, then the partition is satisfactory.

-- Feb 22 In-Class Exercise

On input @BT@X@BT@, we can non-deterministically guess @BT@k@BT@ subsets. We can then go on to verify whether the distance between points in the subsets @BT@X_{0}...X_{k} \leq B@BT@ or not in polynomial time.

-- Feb 22 In-Class Exercise

Assuming that calculating distance between any two points in the set X is polynomial time. To calculate distance between all possible pairs, it takes n*(n-1) time which is O(n^2) time. To verify whether disjoint sets satisfy the condition that distance between any two points in a cluster is < B, it takes at most O(n^2) time to check all possible pairs. Hence this problem turns out to be polynomial time problem.

-- Feb 22 In-Class Exercise

Since there are at most n points, there can be at most n^2 distances between them. Therefore (assuming that we can check the distance between the points in polynomial time n^k) we can verify this in n^(k+2).

-- Feb 22 In-Class Exercise

Since we have a finite set of points X, we can compute the distance between each pair of points in X and verify whether the distance is less than or greater than B. Depending on this result we can decide which partitions are valid or otherwise in polynomial time.

-- Feb 22 In-Class Exercise

X is a finite set containing n points. the distance d(x,y) can be calculted in n*(n-1)*t t-time taken to calculate each distance. Based on the result we can compare the calculated distance with k and decide the partitions in a polynomial time.

-- Feb 22 In-Class Exercise

Given that the distance function runs at most some polynomial time, we can take the results from the k-cluster subset of X and check if these results are less than B in polynomial time as well. Therefore this solution is verifiable in NP time.