Explore BrainMass

NP - Completeness Minimization Problem

Please show me the detailed solution and explanation to the question attached.


Solution Preview

The basic idea of my algorithm is binary search. Suppose A(x,k) is the algorithm that solves the decision version of P with instance x and size k. We define the cost function with instance x and size n as follows:

int CostOfP(x, n)
// The cost of instance x is between 1 and n^4
start = 1;

Solution Summary

Determines algorithm's complexity and completes response to questions.