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:
- F_{1} = x_{1} v x_{2} v x_{3};
- F_{1} = ¬x_{1} v x_{4} v ¬x_{5};
- F_{1} = ¬x_{2} v x_{5} v ¬x_{6};
- F_{1} = ¬x_{3} v x_{6} v ¬x_{4};
Meaning of symbols: v=OR; ^ = AND; ¬=NOT
Here is 3-SAT ≤ LIN-INEQ reduction:
Formula → system of inequality
Variables x_{1} ... x_{m} - the same in the formula
(x_{i} = true => x_{1} = x_{i} = false => x_{i} = 0)
Rules:
(1) 0 ≤ x_{i}, x_{i} ≤ 1
(2) F_{i} = x_{j} OR x_{k} OR x_{1} => x_{j} +x_{k} + x_{1} ≥ 1, where one of three variables must to be 1.
F_{i} = (NOT x_{j}) OR X_{K} OR x_{1}
↓
(1-x_{j}) + x_{k} + x_{x}1 ≥ 1
Question: What system of inequality we get?