Results 1 to 2 of 2

Thread: np problem

  1. #1
    Oct 2010

    np problem

    Given set $\displaystyle 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
    Dec 2010
    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