User Name Remember Me? Password

 Complex Analysis Complex Analysis Math Forum

 February 12th, 2015, 02:48 AM #1 Newbie   Joined: Feb 2015 From: Armenia Posts: 2 Thanks: 0 Systems of Boolean Equations Hey guys -- , I need help to solve my problem). Here is the problem. Given a system of linear boolean equations . It looks like this c11*X1 + c12*X2 + ... + c1n*Xn = 1 c21*X1 + c22*X2 + ... + c2n*Xn = 1 . . . cn1*X1 + cn2*X2 + ... + cnn*Xn = 1 Cij = 0 or 1. The problem is how to find at least 1 solution with polynomial algorithm. I haven't found any topics about this problem.There are something about existence of solutions , but nothing about concrete solution. Do you have any ideas or known solutions ? February 12th, 2015, 01:36 PM #2 Senior Member   Joined: Dec 2013 From: Russia Posts: 327 Thanks: 108 You could solve it as an ordinary system of equations, but in $\Bbb Z_2$ instead of $\Bbb R$. March 3rd, 2015, 05:48 AM #3 Newbie   Joined: Feb 2015 From: Armenia Posts: 2 Thanks: 0 If someone is interested in , I've found some solution of this problem . In the first step algorithm represents X1 with other ones (X1 or Xi , which one exists) and replace it in other equations except the first . Lets assume in first equation c11 = 1. Then X1 = c12*X2 + ... + c1n*Xn + 1 . this equation marked as first.Then algorithm finds equation which contains X2 (or next variable with lowest index) , and so on . in the last equation we have 1 equation to solve , which is independent from others . After we solve that equation we are going up , solving next equation , and so on , finally we will reach the first equation. As we can see , algorithm has polynomial complexity. Here is the example x_1+ x_2+ x_5=1 x_2+ x_3+x_4 + x_5=1 x_1+ x_2+x_3=1 The first step is to find X1 from first equation and replace it in other ones (if it exists). x_1= x_2+ x_5+1 x_3+ x_2+x_4 + x_5=1 x_2+ x_5+1+ x_2+x_3=1 => x_1= x_2+ x_5+1 x_3+ x_2+x_4 + x_5=1 x_3+x_5=0 Now lets find X2 from the second equation . x_1= x_2+ x_5+1 x_3= x_2+x_4 + x_5+1 x_3+x_5=0 => x_1= x_2+ x_5+1 x_3= x_2+x_4 + x_5+1 x_2+x_4 + x_5+1+x_5=0 => x_1= x_2+ x_5+1 x_3= x_2+x_4 + x_5+1 x_2+x_4 =1 Now the second step of the algorithm. It starts with solving 3-th equation. It has 2 solutions (1,0) and (0,1) . Firstly , lets take (1,0) ; x_2=1 ,x_4=0 Then we have x_3= x_5 This equation has 2 solutions as well , lets take (1,1) x_3= 1 ,x_5=1 Finally , in first equation we have x_1= 1 One solution is x_1= 1,x_2=1 ,x_3= 1 ,x_4 =0,x_5=1 As we can it is suffices the equation . Lets find all solutions . Now Lets take x_3= 0 ,x_5=0 we will have x_1= 0 x_1= 0,x_2=1 ,x_3= 0 ,x_4 =0,x_5=0 Going down on 3-th equation. x_2=0 ,x_4 =1 Second equation will be the same x_3= x_5 Firstly , we will solve with (0,0) then (1,1) and we will have x_1=1 x_1=0 Finally x_1= 1,x_2=0 ,x_3= 0 ,x_(4 )=1,x_5=0 x_1= 0,x_2=0 ,x_3= 1 ,x_(4 )=1,x_5=1 x_1= 0,x_2=1 ,x_3= 0 ,x_(4 )=0,x_5=0 x_1= 1,x_2=1 ,x_3= 1 ,x_(4 )=0,x_5=1 Last edited by Karlen; March 3rd, 2015 at 05:53 AM. Tags boolean, equations, systems Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post Cloud Linear Algebra 2 October 13th, 2014 06:00 PM jojoluvsu2 Applied Math 1 August 7th, 2012 08:43 PM HellBunny Algebra 5 April 21st, 2012 09:41 PM boomer029 Algebra 2 December 27th, 2011 05:52 AM rawr-ree Linear Algebra 4 May 31st, 2010 03:54 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.      