is this NP-Hard?
in [General Programming]
|
From: Talha Lateef on 24 Apr 2010 15:59 I want to solve a problem in which i have been given a set of integers S and a Result R i need to find expression that equals result R i can use multiply, divide, addition and subtraction or concatenate number to create larger numbers my questions what is the name of this problem? is this NP-Hard?
From: Kai-Uwe Bux on 24 Apr 2010 16:22 Talha Lateef wrote: > I want to solve a problem in which i have been given a set of > integers S and a Result R i need to find expression that equals result > R i can use multiply, divide, addition and subtraction or concatenate > number to create larger numbers my questions > > what is the name of this problem? Don't know. > is this NP-Hard? Looks even NP-complete. Probably, one can reduce the subset-sum problem to the problem above. I don't have a proof, but a first observation would be this: If your set of integers for the subset-sum instance is {a, b, c, ... } you can make R the set {a, -a, b, -b, ... } Now, you can form expressions ( -a +/- a ) + ( -b +/- b ) + .... and depending on whether you choose + or - within a pair of parentheses, you drop the term or add twice the amount. Best Kai-Uwe Bux
From: Pascal J. Bourguignon on 27 Apr 2010 05:37 Kai-Uwe Bux <jkherciueh(a)gmx.net> writes: > Talha Lateef wrote: > >> I want to solve a problem in which i have been given a set of >> integers S and a Result R i need to find expression that equals result >> R i can use multiply, divide, addition and subtraction or concatenate >> number to create larger numbers my questions >> >> what is the name of this problem? > > Don't know. > >> is this NP-Hard? > > Looks even NP-complete. Probably, one can reduce the subset-sum problem to > the problem above. I don't have a proof, but a first observation would be > this: If your set of integers for the subset-sum instance is > > {a, b, c, ... } > > you can make R the set > > {a, -a, b, -b, ... } > > Now, you can form expressions > > ( -a +/- a ) + ( -b +/- b ) + .... > > and depending on whether you choose + or - within a pair of parentheses, you > drop the term or add twice the amount. There's probably the additionnal constraint that each original number must be used only once. (And that perhaps S is not a set but a list, or a multiset). -- __Pascal Bourguignon__ http://www.informatimago.com
From: Pascal J. Bourguignon on 27 Apr 2010 05:58 Talha Lateef <talhal82(a)gmail.com> writes: > I want to solve a problem in which i have been given a set of > integers S and a Result R i need to find expression that equals result > R i can use multiply, divide, addition and subtraction or concatenate > number to create larger numbers my questions > > what is the name of this problem? > is this NP-Hard? Here is a simple algorithm to solve it: cond S = {} ==> there is no solution S = {0} ==> if R = 0 then the solution is 0 else there is no solution else S={x}US' with xâ 0 Let's take x, and /, and apply x/x = 1 -> a Let's take x, and /, and apply x/x = 1 -> b Now, while a < R do let's take a, and b, and +, and appluy a+b â> a The solution is therefore R = x/x + x/x + x/x + ... + x/x Perhaps you want to revise your problem statement? -- __Pascal Bourguignon__ http://www.informatimago.com
From: Talha Lateef on 27 Apr 2010 15:41 On Apr 27, 2:37 pm, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > Kai-Uwe Bux <jkherci...(a)gmx.net> writes: > > Talha Lateef wrote: > > >> I want to solve a problem in which i have been given a set of > >> integers S and a Result R i need to find expression that equals result > >> R i can use multiply, divide, addition and subtraction or concatenate > >> number to create larger numbers my questions > > >> what is the name of this problem? > > > Don't know. > > >> is this NP-Hard? > > > Looks even NP-complete. Probably, one can reduce the subset-sum problem to > > the problem above. I don't have a proof, but a first observation would be > > this: If your set of integers for the subset-sum instance is > > > {a, b, c, ... } > > > you can make R the set > > > {a, -a, b, -b, ... } > > > Now, you can form expressions > > > ( -a +/- a ) + ( -b +/- b ) + .... > > > and depending on whether you choose + or - within a pair of parentheses, you > > drop the term or add twice the amount. > > There's probably the additionnal constraint that each original number > must be used only once. (And that perhaps S is not a set but a list, > or a multiset). > > -- > __Pascal Bourguignon__http://www.informatimago.com you are right about single use of number, from set i meant mathematical set not that of c++. thanks
|
Next
|
Last
Pages: 1 2 3 Prev: Young girls showing off their bodies on personal webcams Next: Style (was Re: on goto) |