Explore BrainMass

NP - Completeness Minimization Problem

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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

© BrainMass Inc. brainmass.com March 21, 2019, 4:05 pm ad1c9bdddf


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.