NP COMPLETE PROBLEM

Definition of NP

• Definition 1 of NP: A problem is said to be Non deterministically Polynomial (NP) if we can find a non deterministic Turing machine that can solve the problem in a polynomial number of non deterministic moves.
• For those who are not familiar with Turing machines, two alternative definitions of NP will be developed.
• Definition 2 of NP: A problem is said to be NP if
1. its solution comes from a finite set of possibilities, and
2. it takes polynomial time to verify the correctness of a candidate solution
• Remark: It is much easier and faster to "grade" a solution than to find a solution from scratch.
• We use NP to designate the class of all non deterministically polynomial problems.
• Clearly, P is a subset of NP
• A very famous open question in Computer Science:

P = NP ?

• An NP algorithm is an algorithm that has 2 stages:
1. The first stage is a guessing stage that uses choose() to find a solution to the problem.
2. The second stage checks the correctness of the solution produced by the first stage. The time of this stage is polynomial in the input size n.

KNAPSACK  PROBLEM

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

The problem often arises in resource allocation where there are financial constraints and is studied in fields such as combinatorics,computer science,complexity theory, cryptography and applied mathematics.

The knapsack problem has been studied for more than a century, with early works dating as far back as 1897. It is not known how the name "knapsack problem" originated, though the problem was referred to as such in the early works of mathematician Tobias Dantzig (1884–1956), suggesting that the name could have existed in folklore before a mathematical problem had been fully defined.

A 1998 study of the Stony Brook University Algorithm Repository showed that, out of 75 algorithmic problems, the knapsack problem was the 18th most popular and the 4th most needed after kd-trees, suffix trees, and the bin packing problem.

Knapsack problems appear in real-world decision-making processes in a wide variety of fields, such as finding the least wasteful way to cut raw materials, selection of investments and portfolios, selection of assets for asset-backed securitization, and generating keys for the Merkle–Hellman knapsack cryptosystem.

• The goal is to maximize the value of a knapsack that can hold at most W units (i.e. lbs or kg) worth of goods from a list of items I₀, I₁, … I_n-1.

•       Each item has 2 attributes:

1)      Value – let this be v_i for item I_i

2)      Weight – let this be w_i for item I_i

Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? A multiple constrained problem could consider both the weight and volume of the boxes.

(Solution: if any number of each box is available, then three yellow boxes and three grey boxes; if only the shown boxes are available, then all but the green box.

The following is pseudo code for the knapsack problem:

// Input:

// Values (stored in array v)

// Weights (stored in array w)

// Number of distinct items (n)

// Knapsack capacity (W)

for w from 0 to W do

  m[0, w] := 0

end for

for i from 1 to n do

  for j from 0 to W do

    if j >= w[i] then

      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

    else

      m[i, j] := m[i-1, j]

    end if

  end for

end for