What is NP?
NP is the set of all decision problems (question with yes-or-no answer) for which the 'yes'-answers can be verified in polynomial time (O(n^k) where n is the problem size, and k is a constant) by a deterministic Turing machine. Polynomial time is sometimes used as the definition of fast or quickly.--------------------------------------------
What is P?
P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since it can solve in polynomial time, it can also be verified in polynomial time. Therefore P is a subset of NP.--------------------------------------------
What is NP-Complete?
A problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x. In other words:- x is in NP, and
- Every problem in NP is reducible to x
--------------------------------------------
What is NP-Hard?
NP-Hard are problems that are at least as hard as the hardest problems in NP. Note that NP-Complete problems are also NP-hard. However not all NP-hard problems are NP (or even a decision problem), despite having 'NP' as a prefix. That is the NP in NP-hard does not mean 'non-deterministic polynomial time'. Yes this is confusing but its usage is entrenched and unlikely to change.
Photo From Wikipedia [1]
--------------------------------------------
P Problem Coding Example:
In Google's CodeJam Africa 2010, Qualification Round, there were a problem called Store Credit. Here the Description of it:
- Problem: You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).
- Input: The first line of input gives the number of cases, N. N test cases follow. For each test case there will be:
- One line containing the value C, the amount of credit you have at the store.
- One line containing the value I, the number of items in the store.
- One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.
- Each test case will have exactly one solution.
- Output: For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first. Limits: 5 ≤ C ≤ 1000, 1 ≤ P ≤ 1000Small dataset: N = 10, 3 ≤ I ≤ 100Large dataset: N = 50, 3 ≤ I ≤ 2000
- Sample:
3
100
3
5 75 25
200
7
150 24 79 50 88 345 3
8
8
2 1 9 4 4 56 90 3
Output:
Case #1: 2 3
Case #2: 1 4
Case #3: 4 5
- C++ Solution:
#include <iostream>
#include <fstream>
#include <vector> //For std::vector
using namespace std;
int main(int argc, char ** argv)
{
std::ifstream infile(argv[1]);
if(!infile) {
std::cout << "could not open " << infile << std::endl;
return 0;
}
std::ofstream outfile(argv[2]);
if(!outfile) {
std::cout << "could not open " << outfile << std::endl;
return 0;
}
/*should be char if c, but with C++ this
will let "infile >>" to read only one digit*/
unsigned short numberOf_testCases;
unsigned short credit, numberOf_Items, itemPrice;
std::vector<unsigned short> allItems;
infile >> numberOf_testCases; //Number of Test Cases
for(unsigned int i=0; i<numberOf_testCases; i++){
infile >> credit; //Credit
infile >> numberOf_Items; //Number of Items
for(unsigned int j=0; j<numberOf_Items; j++){
infile >> itemPrice;
allItems.push_back(itemPrice);
}
bool breakBool = false;
for(unsigned int j=0; j<allItems.size(); j++){
for(unsigned int k=j+1; k<allItems.size(); k++){
if ((allItems[j] + allItems[k]) == credit)
{
outfile << "Case #" << i+1;
outfile << ": " << j+1 << " " << k+1 << endl;
breakBool = true;
break;
}
}
if (breakBool)
break;
}
allItems.clear();
}
return 0;
}
--------------------------------------------
NP Problem Coding Example :
The previous example problem is not an NP problem. The previous solution implementation is of order O(n^2) at worst case.
Now, we will modify the previous problem slightly to make it an NP complete problem (A subset sum problem).
- Problem Modification: From the item list you have created for the store, you should buy items that you can add up to the entire value of the credit.
You will buy any number of items not only two.
- Input Modification: No modifications.
- Output Modification: No Modifications.
- Sample:
2
100
3
5 75 25
8
5
4 2 1 1 5
Output:
Case #1: 2 3
Case #2: 1 2 3 4
- C++ Solution: This solution is using a dynamic programming (a bottom-up approach).
#include <iostream>
#include <fstream>
#include <algorithm> // std::reverse
#include <vector> // std::vector
using namespace std;
std::vector<unsigned short> getIndecesOfSum(
std::vector<unsigned short> numbers, int n, unsigned short sum);
int main(int argc, char ** argv)
{
std::ifstream infile(argv[1]);
if(!infile) {
std::cout << "could not open " << infile << std::endl;
return 0;
}
std::ofstream outfile(argv[2]);
if(!outfile) {
std::cout << "could not open " << outfile << std::endl;
return 0;
}
/*should be char if c, but with C++ this
will let "infile >>" to read only one digit*/
unsigned short numberOf_testCases;
unsigned short credit, numberOf_Items, itemPrice;
std::vector<unsigned short> allItems, selectedItems;
infile >> numberOf_testCases; //Number of Test Cases
for(unsigned int i=0; i<numberOf_testCases; i++){
infile >> credit; //Credit
infile >> numberOf_Items; //Number of Items
for(unsigned int j=0; j<numberOf_Items; j++){
infile >> itemPrice;
allItems.push_back(itemPrice);
}
selectedItems = getIndecesOfSum(allItems,
allItems.size(), credit);
outfile << "Case #" << i+1 << ": ";
for(unsigned int j=0; j<selectedItems.size(); j++){
outfile << selectedItems[j] << " ";
}
outfile << endl;
allItems.clear();
selectedItems.clear();
}
return 0;
}
std::vector<unsigned short> getIndecesOfSum(
std::vector<unsigned short> numbers, int n, unsigned short sum)
{
std::vector<unsigned short> IndecesOfSum;
bool DP_Matrix[sum+1][n+1]; //Dynamic Programming Matrix
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
DP_Matrix[0][i] = true;
// If sum is not 0 and numbers is empty, then answer is false
for (int i = 1; i <= sum; i++)
DP_Matrix[i][0] = false;
// Fill the DP_Matrix table in bottom up manner
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++) //Row then Row
{
/*If DP Matrix element is true,
then next elements in the row is true.*/
DP_Matrix[i][j] = DP_Matrix[i][j-1];
if (i >= numbers[j-1])
DP_Matrix[i][j] = DP_Matrix[i][j] ||
DP_Matrix[i - numbers[j-1]][j-1];
}
}
//Print the Dynamic Programming Matrix
/*for (int i = 0; i <= sum; i++)
{
for (int j = 0; j <= n; j++)
printf ("%4d", DP_Matrix[i][j]);
printf("\n");
}*/
for (int j = n; j >= 1; j--)
{
if(sum - numbers[j-1] >= 0 &&
DP_Matrix[ sum - numbers[j-1] ][j-1])
{
IndecesOfSum.push_back(j);
sum = sum - numbers[j-1];
}
}
std::reverse(IndecesOfSum.begin(), IndecesOfSum.end());
//return DP_Matrix[sum][n];
return IndecesOfSum;
}
--------------------------------------------
A More Difficult Problem:
Now we are going to make this problem more difficult.
- Problem Modification: From the item list you have created for the store, you should list all the combinations of items that you can add up to the entire value of the credit. You will buy any number of items not only two.
- Input Modification: No modifications.
- Output Modification: The program should list all the possible combinations of items that you can bought with the received credit C. Now there is no unique solution for each test case.For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit for the first solution. If there are other solutions, it should be also written after it and be separated with a comma ",".
- Sample:
2
100
3
5 75 25
8
5
4 2 4 1 1
Output:
Case #1: 2 3
Case #2: 1 2 4 5 , 1 3 , 2 3 4 5
- C++ Solution: Think about it. I will post the answer in a coming post though ;-)
- A Question: Now the problem is more difficult, but does it still an NP Complete problem ? Wait for the answer in the coming post.
To compile and use the above codes:
- Add it to a file: D:\Test_Project\main.cpp,
- then make a new patch file: D:\Test_Project\Compile.bat:, with the content:
g++.exe -Wall -c -g main.cpp -o main.oppg++.exe -static -static-libgcc -static-libstdc++ -o "program.exe" main.opppause - Run (Double Click) that patch command to build your executable D:\Test_Project\program.exe.The "pause" command is to hold the CMD window for you to check if the C++ compilation was successful or not.Don't forget to install the a C++ compiler, for the patch file to work correctly.If you are using windows you can install the GNU Compiler by downloading and installing MinGW (Minimalist GNU for Windows).
- Open CMD, then write the following command:D:\Test_Project\program A-large-practice.in A-large-practice.outDon't forget to put the file D:\Test_Project\A-large-practice.in with the input test cases, and to create a new empty file D:\Test_Project\A-large-practice.out.
- Check the results into D:\Test_Project\A-large-practice.out.
