Transcript 1 0 1 0 1 - bYTEBoss

A NEW ALGORITHM TO SOLVE
OVERDEFINED SYSTEMS
OF LINEAR LOGICAL EQUATIONS
Arkadij Zakrevskij
United Institute of Informatics Problems of NAS of
Belarus
1 / 20
Outline
•
•
•
•
•
•
•
How the problem is stated
How the problem can be solved
Theoretical background
Example
Solving the core equation
Experiments
Results of experiments
2 / 20
How the problem is stated
A system of m linear logical equations (SLLE)
with n Boolean variables :
a11x1  a12x2  … a1nxn = y1 ,
a21x1  a22x2  … a2nxn = y2 ,
…
am1x1  am2x2  … amnxn = ym .
3 / 20
How the problem is stated
Any SLLE can be presented by equation
Ax = y,
A – the matrix of coefficients, x – the vector of unknowns,
y – the vector of free members, all Boolean.
Usually A and y are given, the problem is to find a root a value of vector x satisfying the equation Ax = y.
An SLLE could be
• defined
(having one root), usually m = n,
• undefined (underdefined, several roots), usually m<n,
• overdefined (inconsistent, contradictory - no root),
usually m > n.
4 / 20
How the problem is stated
Finding optimal solutions.
Looking for a shortest root in undefined SLLE :
A
y
1001101101
1
0111001010
0
1100110010
0
0111100010
1
0001011101
1
1 0 0 0 1 0 0 0 0 1 = xT – the shortest root
5 / 20
How the problem is stated
Satisfying maximum number of equations in overdefined SLLE
A
11....
.1.111
.11..1
1.111.
11111.
..1.1.
.1....
.111.1
..1...
.11.1.
1.1...
...1.1
000110
y
0
+
1
not satisfied
0
+
0
+
0
+
0
not satisfied
0
+
1
+
0
+
1
+
0
+
1
+
x* - an optimal solution
e
0
1
0
0
0
1
0
0
0
0
0
0
y*
0
0
0
0
0
1
0
1
0
1
0
1
6 / 20
How the problem is stated
Let m > n, and all columns of matrix A are linear-independent.
Then system Ax = y is consistent for 2n values of vector y
(called suitable) from 2m possible values.
Suppose a suitable vector y* is distorted to y = y*  e, where
e is a distortion vector.
The problem is to restore vector y* (or e) for given A and y.
When y is not too far from y*, that problem can be solved by
finding a suitable value y”, the nearest to y. Then y”= y*.
7 / 20
How the problem can be solved
Matrix A generates a linear vector space M, consisting of
all different sums (modulo 2) of columns from A.
Equation Ax = y is consistent (and y is suitable) iff
y  M.
The problem is to calculate the vector distance d (A, y)
between vector space M and vector y. It could be
regarded as the distortion vector e if its weight w(e)
(the number of 1s) is smaller then   the averaged
shortest Hamming distance between elements in M.
Vector e can be regarded as well as the correction vector.
8 / 20
How the problem can be solved
The value of  is defined by inequality
(m, n, ) < 1  (m, n,  + 1),
where (m, n, k) is the expected number of suitable
values of vector y with weight k in a random
SLLE with parameters m and n:
(m, n, k) =
k
 Cmi 2n-m.
i=0
9 / 20
Theoretical background
Changing some column ai of matrix A for its sum
with another column aj we obtain some matrix A+
equivalent to initial one (generating the same
linear vector space M)
Affirmation 1. Vector distance d (A+, y) = d (A, y).
Changing vector y in system (A, y) for its sum with
arbitrary column aj from matrix A we obtain z+.
Affirmation 2. Vector distance d (A, y+) = d (A, y).
10 / 20
Theoretical background
Using introduced operations, we canonize system (A, y):
1) select n linearly independent rows in matrix A;
2) in every of them delete all 1s except one (put into
position i for i-th of the selected rows);
3) delete 1s in corresponding components of vector z.
After that the obtained system (A+, y+) is reduced in size:
4) all selected rows are deleted from matrix A+, as well as
the corresponding components of vector y. The remaining
rows and components constitute Boolean ((m – n)  n)matrix B and (m – n)-vector u.
11 / 20
Theoretical background
Affirmation 3. The task of restoration (finding vector d (A, y))
is reduced to solving the core equation Bx = u):
To find a column subset C in matrix B, which minimizes the
arithmetic sum w(c) + w(s). In that case d (A, y) = (c, s),
the concatenation of vectors c and s.
c - the Boolean n-vector indicating columns from B
entering C;
w(c) - the number of 1s in c;
(C) - the mod 2 sum of columns in C;
s = (C)  u;
w(s) - the number of 1s in s.
12 / 20
Example
A
1000
1011
1100
0111
1111
0101
1000
1110
0100
1101
0100
0010
1101
0110
0101
y
0
1
0
0
1
0
1
1
0
0
1
0
0
0
1
b
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
A+
1000
0100
0010
0110
1110
0001
1000
0101
1010
1001
1010
0111
1001
1101
0001
y+
0
0
0
1
0
0
1
0
0
0
1
1
0
1
1
B

u
0110
1110
1000
0101
1010
1001
1010
0111
1001
1101
0001
1
0
1
0
0
0
1
1
0
1
1
13 / 20
Example
Restoring the initial system:
1. Solving system B x = u, i. e. finding a value c of
x which minimizes function (Bx  u) + w (x).
2. Obtaining d (A, y) = (c, Bc  u), which could be
accepted as distortion (correction) vector e .
3. Calculating, if needed, suitable vector y* = y  e,
then solving consistent system A x = y* and
finding x*.
14 / 20
Example
B
u
Bc  u
e
y
y*
0110
1110
1000
0101
1010
1001
1010
0111
1001
1101
0001
1
0
1
0
0
0
1
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
1
0
0
1
0
0
0
1
1
0
0
0
1
1
1
1
1
0
1
1
0
0
1
c = 1101
A
1000
1011
1100
0111
1111
0101
1000
1110
0100
1101
0100
0010
1101
0110
0101
x* = 1 1 1 0
15 / 20
Solving the core equation B x = u
The suggested method can be applied when w(e) < .
As soon as w(c, s) <  for a current subset C from B,
vector (c, s) could be accepted as vector e.
The subsets C are checked one by one while increasing
number of columns in C up to L - the level of search.
The run-time T strongly depends on L, which, in its turn,
depends statistically on m, n and w(e), with a great
dispersion.
16 / 20
Solving the core equation B x = u
It follows from here that efficient algorithms can
be constructed which solve the problem in the
quasi-parallel mode using a set of many (q)
canonical forms of system (A, y) with different
basics selected at random.
17 / 20
Solving the core equation B x = u
Additional acceleration in finding a short solution can be
achieved by randomization.
q different canonical forms are prepared, which have
various basics selected at random.
Then the solution is searched in parallel over all these
forms, at levels of exhaustive search 0, 1, etc., until at a
current level L a solution with weight w, satisfying
condition w <   1 will be recognized.
With raising q this level L can be reduced, as well as
the run-time T, which powerfully depends on L.
18 / 20
Experiments
10 random overdefined SLLEs (A, y) were prepared with
m = 1000, n = 100, and w(e) = 100. Each of them was
solved. The level of search was minimized by:
randomization – constructing q random equivalent forms
(A+, y+) and transforming them to (B, u),
solving systems (B, u) in parallel, gradually raising the level
of search,
restricting the search by recognizing short solutions.
Conducting the experiments for q = 1, q = 10 and q = 100
to see how the run-time T depend on q.
19 / 20
Results of experiments (m=1000, n=100, w(e)=100)
q=1
№
1
2
3
4
5
6
7
8
9
10
L
q = 10
q = 100
T
L
T
L
T
10
2y
12 112y
10
2y
12 112y
10
2y
14 5000y
9
69d
4
12s
6
1h
10
2y
3
8
7
5
5
7
6
4
4
5
10s
27d
4d
33m
1h
3d
3h
25s
2m
52m
3
3
3
4
3
2
4
4
4
5
6m
6m
7m
12m
7m
6m
15m
8m
9m
1h
20 / 20