OKlibrary  0.2.1.6
Measures.hpp File Reference

Investigations regarding measurements for pigeonhole clause-sets. More...

Go to the source code of this file.


Detailed Description

Investigations regarding measurements for pigeonhole clause-sets.

Todo:
Basic statistics
  • Implemented formulas:
    for n : 0 thru 10 do block([m:n+1], print(n,nvar_php(m,n),ncl_list_weak_php(m,n),ncl_weak_php(m,n),deficiency_weak_php(m,n)));
    0 0 [[0,1]] 1 1
    1 2 [[1,2],[2,1]] 3 1
    2 6 [[2,9]] 9 3
    3 12 [[2,18],[3,4]] 22 10
    4 20 [[2,40],[4,5]] 45 25
    5 30 [[2,75],[5,6]] 81 51
    6 42 [[2,126],[6,7]] 133 91
    7 56 [[2,196],[7,8]] 204 148
    8 72 [[2,288],[8,9]] 297 225
    9 90 [[2,405],[9,10]] 415 325
    10 110 [[2,550],[10,11]] 561 451
       
  • The numbers of satisfying assignments for satisfiable instances:
    for m : 0 thru 4 do print(m,satprob_weak_php(m,m)*2^(m*m));
    0 1
    1 1
    2 2
    3 6
    4 24
       
Todo:
Conflict-independence number
  • Computed via
    for n : 0 thru 6 do print(n,independence_number_m_cs(weak_php_cs(n+1,n)));
    0 1
    1 2
    2 6
    3 18
    4 40
    5 75
    6 126
       
  • We should be able to figure this out; see below.
Todo:
Conflict-partition_number
  • The conflict-partition_number as upper-bounded by the length of hitting_decomposition_m_cs(weak_php_cs(n+1,n)) seems to be the same as the conflict-independence number:
    for n : 0 thru 6 do print(n,partition_number_m_cs(weak_php_cs(n+1,n)));
    0 1
    1 2
    2 6
    3 18
    4 40
    5 75
    6 126
       
  • Perhaps the conflict-graph is even perfect?!
  • In general: Is the hermitian deficiency actually an upper bound on the conflict-partition-number ?!?
Todo:
Hermitian rank
  • Data on hermitian rank and deficiency:
    for n : 0 thru 6 do block([F:weak_php_cs(n+1,n),h],h:hermitian_rank_cs(F),print(n,h,ncl_cs(F)-h));
    0 0 1
    1 1 2
    2 3 6
    3 4 18
    4 5 40
    5 6 75
    6 7 126
       
  • We should be able to figure this out:
    1. hermitian_rank(weak_php_fcs(m+1,m)) = m+1
    2. hermitian_deficiency and conflict_independence_number follow suit.
  • Analogously to "eigensharp", we can create a notion for clause-sets where the conflict-indepence-number equals the hermitian defect, and show that weak_php is an instance (while not being eigensharp).
Todo:
Characteristic polynomial
  • Data:
    for n : 0 thru 6 do print(n, ":",charpoly_cs(weak_php_cs(n+1,n)));
    0 : -x
    1 : -x^3 + 2*x
    2 : -x^9 + 12*x^7 - 36*x^5 + 32*x^3
    3 : x^22 - 36*x^20 + 432*x^18 - 2160*x^16 + 3888*x^14
    4 : -x^45 + 80*x^43 - 2400*x^41 + 34560*x^39 - 241920*x^37 + 663552*x^35
    5 : -x^81 + 150*x^79 - 9000*x^77 + 280000*x^75 - 4800000*x^73 + 43200000*x^71 - 160000000*x^69
    6 : -x^133 + 252*x^131 - 26460*x^129 + 1512000*x^127 - 51030000*x^125 + 1020600000*x^123 - 11226600000*x^121 + 52488000000*x^119
       
  • For n >= 2 there seem to be n+2 monomials, with the powers forming an arithmetic progression with distance 2, and coefficients alternating in sign.
  • These clause-sets seem to have non-zero eigenvalues of the form +- a, +- b, so that we altogether get 4 different values here?

Definition in file Measures.hpp.