0

I have to write polynomial time algorithm for the problem which should say accept or reject if the number(s) to the left don't match to the number on right. You can group the numbers also, examples are below

X & Y .......... & N = SUM where X, Y, and N can be any integer

Case 1: 4 & 6 & 10 = 14 , accepts 
So case 1 accepts because first number and the third number together sum up to 14.  
Case 2: 4 & 6 & 10 = 8 rejects
Case 3: 4 & 6 & 10 = 6 , accepts 
Case 4: 4 & 6 & 10 = 11 rejects

Some more test cases:
Case 1: 4 & 6 & 10 = 4 , accepts 
Case 2: 4 & 6 & 10 = 21 rejects
Case 3: 4 & 6 & 10 = 20 , accepts 
Case 4: 4 & 6 & 10 = 17 rejects
Case 5: 4 & 6 & 10 = 16 , accepts 
Case 6: 4 & 6 & 10 = 200 rejects

Case 7: 4 & 6 & 10 = 111 , rejects 
Case 8: 4 & 6 & 10 = 7 rejects

some more test cases 

Case 1 : 1 & 1 & 1 = 3 accepts
Case 2 : 1 & 1 & 1 & 2 & 2 & 22 = 29 accepts

For this how can I write polynomial time algorithm? Is it NP Problem?

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
Arjun
  • 125
  • 1
  • 9
  • 4
    You haven't adequately explained what you're allowed to do with these numbers, but it sounds like the subset sum problem, and NP complete. – user2357112 Apr 28 '17 at 16:45
  • those number indicates values of particular variables. It is a puzzel given to us to solve, asking come up with polynomial time algorithm. But not able to figure out how? In genenral it could be like weight of variable , for example `1 & 2 & 3 = 5 ` here 1 is the weight of the variable. – Arjun Apr 28 '17 at 17:40
  • If it is NP Complete means we can't find any polynomial time algorithm? – Arjun Apr 28 '17 at 17:40
  • Possible duplicate of [Subset Sum algorithm](http://stackoverflow.com/questions/4355955/subset-sum-algorithm) – Paul Hankin Apr 28 '17 at 17:57
  • I agree, it seems to me too that this is the subset sum problem, which is NP-complete (but can be solved in pseudopolynomial time). Check Wikipedia. – blazs Apr 28 '17 at 18:11

1 Answers1

1

It seems to me too that this is the subset sum problem, which is NP-complete (meaning that a polynomial-time solution doesn't exist, unless P=NP) but can be solved in pseudo-polynomial time (i.e. time polynomial both in the number of numbers and the value of the sum) using dynamic programming.

blazs
  • 4,705
  • 24
  • 38
  • Agree , so the solution Pseudo-polynomial time = Polynomial time? I am not getting Why they call Pseudo-polynomial time – Arjun Apr 28 '17 at 19:19
  • I am just thinking can I get polynomial time verifier for it? Do you think randomly selecting and checking against solution could be polynomial time? – Arjun Apr 28 '17 at 19:20
  • It's called [pseudo polynomial](https://en.wikipedia.org/wiki/Pseudo-polynomial_time) because it's not polynomial in the size of the _representation_ (i.e. the number of bits) of the sum but rather polynomial in the sum itself (i.e. in the number that the bits are representing---which is exponential in the size of the representation). – blazs Apr 28 '17 at 19:32
  • 1
    To answer the second question, unless `P=NP` (which many think is unlikely), no polynomial-time verifier exists for your problem. – blazs Apr 28 '17 at 19:32
  • Thank you! I have experience in solving Time Table Generation using Genetic Algorithm; I am just thinking Genetic algorithm to address this. Do you have any opinions on the Genetic algorithm (GA) to write verifiers? That is at first as per GA, I will generate random solutions, then calculate the fitness, later apply crossover, mutation. If solution found stop else repeat the process. – Arjun Apr 28 '17 at 19:42