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₁ = x₁ v x₂ v x₃;
• F₁ = ¬x₁ v x₄ v ¬x₅;
• F₁ = ¬x₂ v x₅ v ¬x₆;
• F₁ = ¬x₃ v x₆ v ¬x₄;

Meaning of symbols: v=OR; ^ = AND; ¬=NOT

Here is 3-SAT ≤ LIN-INEQ reduction:

Formula → system of inequality

Variables x₁ ... x_m - the same in the formula

(x_i = true => x₁ = x_i = false => x_i = 0)

Rules:

(1) 0 ≤ x_i, x_i ≤ 1

(2) F_i = x_j OR x_k OR x₁ => x_j +x_k + x₁ ≥ 1, where one of three variables must to be 1.

F_i = (NOT x_j) OR X_K OR x₁

↓

(1-x_j) + x_k + x_x1 ≥ 1

Question: What system of inequality we get?