Subset sum¶

Description¶

This example tries to solve the well-known NP-complete problem of subset sum, by means of the so called simple Kernel P systems (skP systems).

Model¶

The corresponding P-Lingua file is the following:

@model<simple_kernel_psystems>

def main()
{
  call subset_sum();
}

def subset_sum()
{
  call init_cells();
  call init_multisets();
  call init_rules();
}

def init_cells()
{
  @mu = [[]'1 []'2]'0;
}

def init_multisets()
{
  @ms(1) = S;
  @ms(2) = A{1};
  @ms(2) += v{i}*w{i} : 1<=i<=n;

  /* Environment alphabet: */
}

def init_rules()
{
  /* C1 */
  /* r1,1 */ @guard {>=+T} ? [S]'1 --> [yes]'0;
  /* r1,2 */ @guard {>=+F} && {>=-T} ? [S]'1 --> [no]'0;

  /* C2 */
  /* r2,i */ [A{i}]'2 |--> [B{i},A{i+1}]'2 [A{i+1}]'2 : 1<=i<n;
  /* r2,n */ [A{n}]'2 |--> [B{n},X]'2 [X]'2;
  /* r2,n+i */ @guard {=+B{i}}&&{=+X} ? [v{i}]'2 --> [v]'2 : 1<=i<=n;
  /* r2,2n+1 */ [X]'2 --> [Y]'2;
  /* r2,2n+2 */ @guard {=-v*k} ? [Y]'2 --> [F]'1;
  /* r2,2n+3 */ @guard {=+v*k} ? [Y]'2 --> [T]'1;
}

Files¶

Custom application, defining the needed input and output tables for subset sum problem.
Model file, P-Lingua file with the parametrized file specifying the family of P systems for solving the subset sum problem. The custom interface enable the user to introduce the data corresponding to each different scenario.
Scenario file, for a specific instance of the problem (that is, a specific graph to colour), for a specific instance of the problem.

References¶