Results 1 to 2 of 2

Math Help - np problem

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    1

    np problem

    Hi.
    Given set X={a/ a =(a_1,a_2,....a_n) and  a_i={0,1,2};i=0,1,..}
    and sum operation by mod3.
    Denote S subset of X.
    1)if a,b belong to S then -(a+b) doesn't belong to S;//-(1,2) = (2,1)
    2)if a,b,c belong to S then a+b+c=0:
    I must write a programm wich will find the count of S for specific n:
    this is a np problem:
    From 1) and 2) I understand that if I already got A I don't consider -A:

    I want to to find solution of this problem and optimize it and need your help.

    thank's for any advice
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    You really need to fix your notation. So X is the set of all n-tuples mod 3?
    Are a,b,c n-tuples? Please clarify.

    From your description, I would guess this is something like the subset sum problem (or atleast easily has a polynomial time reduction to subset sum) and this is well studied with many optimized algorithms.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum