3 Replies - 3390 Views - Last Post: 09 March 2014 - 03:17 PM

#1 John.Flanders.Third   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-March 14

Questions about Subset sum problem and NP-Complete

Posted 09 March 2014 - 02:43 PM

The Subset sum problem is a NP-Complete problem, and there is not yet know algorithm that can solve this problem effectively (polynomial time) when either N (number of variable) is large and P (number of place values to state the problem) is large, while in the other hand, if some of those values is small we can do an exhaustive search or use a dynamic programming approach to find a solution.

if N is small, then, exhaustive search (brute-force approach) can do the work, as the number of subsets in the input set could be properly managed by a modern computer in a reasonable time, i.e:

- N=5 = 2^5-1 = 31
- N=10 = 2^10-1 = 1023
- N=20 = 2^20-1 = 1.048.575
- N=21 = 2^30-1 = 1.073.741.823

However, when N becomes large the number of subsets increase exponentially thus they cannot be properly managed in a reasonable amount of time, or to say in other words, it could take thousand of years to process (following a exhaustive search process)

- N=100 = 2^100 = 1,26765E+30
- N=1000 = 2^1000 = 1,0715E+301

Let's say there is a mathematical way to process the a subset sum problem instance in a reasonable amount of time (in polynomial) with large input variable, (large means >100>200>400>800>1600>3200>6400>12800>25600 input variables).

How will be the expected measured time execution to demonstrate it runs in polynomial time with the given input variables?

For instance, each time you duplicate the input variables it takes 3 times the previous run:

T(2N) = 3T(N) = O(N*log(3))

.. or better than this, each time you duplicate the input variables it takes 2 times the previous run:

T(2N) = 2T(N) = O(N*log(2))

For the shake of clarity let's say there is no trick in the input value range. The input values range must be in 0 to 2^32, that is 0 to 4294967295 (integer value).


Feel free to correct the above statements, the formulas, the O notation or whatever you believe could be wrong

John

Is This A Good Question/Topic? 0
  • +

Replies To: Questions about Subset sum problem and NP-Complete

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12634
  • View blog
  • Posts: 45,800
  • Joined: 27-December 08

Re: Questions about Subset sum problem and NP-Complete

Posted 09 March 2014 - 02:49 PM

Quote

How will be the expected measured time execution to demonstrate it runs in polynomial time with the given input variables?

Computational complexity doesn't depend on implementation. It depends on the underlying algorithm. Sure, C++ might shave off a constant factor in comparison to Java. The algorithm analysis is what's important in demonstrating polynomial time.

NP Completeness also states that any other language (read- problem) in NP can be reduced to an NP Complete problem. This includes other NP Complete languages.

Note- in your hypothetical, log(2) and log(3) are constants, so are dropped.
Was This Post Helpful? 0
  • +
  • -

#3 John.Flanders.Third   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-March 14

Re: Questions about Subset sum problem and NP-Complete

Posted 09 March 2014 - 03:13 PM

View Postmacosxnerd101, on 09 March 2014 - 02:49 PM, said:

Quote

How will be the expected measured time execution to demonstrate it runs in polynomial time with the given input variables?

Computational complexity doesn't depend on implementation. It depends on the underlying algorithm. Sure, C++ might shave off a constant factor in comparison to Java. The algorithm analysis is what's important in demonstrating polynomial time.

NP Completeness also states that any other language (read- problem) in NP can be reduced to an NP Complete problem. This includes other NP Complete languages.

Note- in your hypothetical, log(2) and log(3) are constants, so are dropped.


Hi,

Didn't try to focus on the implementation as I'm not talking about any specific programming language, obviously c++ will run faster in terms of measured time than java or .net but algorithm will have a similar time complexity, if I'm not wrong.

Maybe the O expression I depicted were not right at all, so allow me to ask next questions to clarify this:

if every time you double the input it takes three times to solve the problem is right to use next expression?

T(3N) = 3T(N)?

what will be the right expression in big O notation?
what will be the related complexity time for this progression?

100->1
200->3
400->9
800->27
1600->81
...

John
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12634
  • View blog
  • Posts: 45,800
  • Joined: 27-December 08

Re: Questions about Subset sum problem and NP-Complete

Posted 09 March 2014 - 03:17 PM

It's linear, so O(n) for 3T(n) = T(3n). The sequence you are describing in your second example is exponential, with complexity O(a^n).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1