Skip to main content
MathOverflow

Return to Question

added 3 characters in body
Source Link
Valera
Valera
  • 113
  • 1
  • 5

Are there any methods to "solve" large systems of boolean equations?

$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$

For example $$x_{1}\vee x_{2}\vee x_{5} = 0$$ $$x_{1}\vee x_{3}\vee x_{4} = 1$$ $$x_{2}\vee x_{3}\vee x_{5} = 1$$ $$x_{1}\vee x_{4}\vee x_{5} = 1$$ $$x_{1}\vee x_{2}\vee x_{3} = 0$$ $$...$$

The problem is to find $x$, that satisfies the most of equalitiessatisfies the most of equations. I couldn't employ any maxsat-like method, or integer linear programming to solve this problem.

Are there any methods to "solve" large systems of boolean equations?

$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$

For example $$x_{1}\vee x_{2}\vee x_{5} = 0$$ $$x_{1}\vee x_{3}\vee x_{4} = 1$$ $$x_{2}\vee x_{3}\vee x_{5} = 1$$ $$x_{1}\vee x_{4}\vee x_{5} = 1$$ $$x_{1}\vee x_{2}\vee x_{3} = 0$$ $$...$$

The problem is to find $x$, that satisfies the most of equalities. I couldn't employ any maxsat-like method, or integer linear programming to solve this problem.

Are there any methods to "solve" large systems of boolean equations?

$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$

For example $$x_{1}\vee x_{2}\vee x_{5} = 0$$ $$x_{1}\vee x_{3}\vee x_{4} = 1$$ $$x_{2}\vee x_{3}\vee x_{5} = 1$$ $$x_{1}\vee x_{4}\vee x_{5} = 1$$ $$x_{1}\vee x_{2}\vee x_{3} = 0$$ $$...$$

The problem is to find $x$, that satisfies the most of equations. I couldn't employ any maxsat-like method, or integer linear programming to solve this problem.

added 199 characters in body
Source Link
Valera
Valera
  • 113
  • 1
  • 5

Are there any methods to "solve" large systems of boolean equations?

$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$

For example $$x_{1}\vee x_{2}\vee x_{5} = 0$$ $$x_{1}\vee x_{3}\vee x_{4} = 1$$ $$x_{2}\vee x_{3}\vee x_{5} = 1$$ $$x_{1}\vee x_{4}\vee x_{5} = 1$$ $$x_{1}\vee x_{2}\vee x_{3} = 0$$ $$...$$

The problem is to find $x$, that satisfies the most of equalities. I couldn't employ any maxsat-like method, or integer linear programming to solve this problem.

Are there any methods to "solve" large systems of boolean equations?

$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$

The problem is to find $x$, that satisfies the most of equalities. I couldn't employ any maxsat-like method, or integer linear programming to solve this problem.

Are there any methods to "solve" large systems of boolean equations?

$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$

For example $$x_{1}\vee x_{2}\vee x_{5} = 0$$ $$x_{1}\vee x_{3}\vee x_{4} = 1$$ $$x_{2}\vee x_{3}\vee x_{5} = 1$$ $$x_{1}\vee x_{4}\vee x_{5} = 1$$ $$x_{1}\vee x_{2}\vee x_{3} = 0$$ $$...$$

The problem is to find $x$, that satisfies the most of equalities. I couldn't employ any maxsat-like method, or integer linear programming to solve this problem.

Source Link
Valera
Valera
  • 113
  • 1
  • 5

System of boolean equations, Satisfiability

Are there any methods to "solve" large systems of boolean equations?

$$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$

The problem is to find $x$, that satisfies the most of equalities. I couldn't employ any maxsat-like method, or integer linear programming to solve this problem.