Assignment Help >> Other Subject
Assignment -
1. NP - Given numbers x1, ... xn. Numbers meet n files size and memory disk capacity D. We must understand, can we that files divided into 3 disks. The amount of file size recorded on any disc cannot exceed the disk capacity D. Let's estimate that this computational task belongs to class NP. What is additional information, that in this case is required for check algorithm?
2. From 3-SAT to LINE-INEQ.
We use 3-SAT ≤ LIN-INEQ reduction for such 3-SAT system of conditions:
- F1 = x1 v x2 v x3;
- F1 = ¬x1 v x4 v ¬x5;
- F1 = ¬x2 v x5 v ¬x6;
- F1 = ¬x3 v x6 v ¬x4;
Meaning of symbols: v=OR; ^ = AND; ¬=NOT
Here is 3-SAT ≤ LIN-INEQ reduction:
Formula → system of inequality
Variables x1 ... xm - the same in the formula
(xi = true => x1 = xi = false => xi = 0)
Rules:
(1) 0 ≤ xi, xi ≤ 1
(2) Fi = xj OR xk OR x1 => xj +xk + x1 ≥ 1, where one of three variables must to be 1.
Fi = (NOT xj) OR XK OR x1
↓
(1-xj) + xk + xx1 ≥ 1
Question: What system of inequality we get?
The task consisted of 2 questions. I have solved them and provided typed answers for both. In first question, a BIN packing problem was solved. In second question, some inequalities were to be formed.