DO WANT TO HIRE TUTOR FOR ORIGINAL SYSTEM OF INEQUALITY ASSIGNMENT SOLUTION? AVAIL QUALITY SYSTEM OF INEQUALITY ASSIGNMENT WRITING SERVICE AT BEST RATES!

System of Inequality Assignment

Question 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?

Solution 1:

We are given numbers x1, ... xn. The numbers meet n files size and memory disk capacity D. The files can be divided into 3 disks. The amount of file size recorded on any disc cannot exceed the disk capacity D. We estimate that this computational task belongs to class NP. We have to find what is the additional information required for check algorithm.

We can construct this problem as an instance of BIN-PACKING (decision) problem where we know that it is NP-Complete.

BIN-Packing Problem:

Let us assume that we are having n objects, each of a given size. Also, we have some bins with equal capacities. Our aim is to assign the objects to the bins using least number of bins. Total size of objects assigned to a single bin<capacity of the bin. We assume the capacity of the bin as ‘1'.
a1,a2,..... <=1 (non-negative numbers)

We have to find the minimum value of ‘k', which denotes minimum number of bins.

The Bin-Packing problem is strongly NP-hard. We can use simple approximation algorithms. Unless P=NP, no algorithm achieves a performance ratio better than 3/2. Unless P=NP, there is no p-factor approximation algorithm for the bin packet problem for any p < 3/2.

So, additional information required for the check algorithm is the p-factor. Only then can we proceed further.

WORK TOGETHER WITH EXPERTSMIND'S TUTOR TO ACHIEVE SUCCESS IN SYSTEM OF INEQUALITY ASSIGNMENT!

Question 2. From 3-SAT to LINE-INEQ.

Question: What system of inequality we get?

Solution 2:

3-SAT to LINE-INEQ
Converting the given formulae into a system of inequality:
x1 + x2 + x3 >= 1
(1-x1) + x4 + (1-x5) >= 1
(1-x2) + x5 + (1-x6) >= 1
(1-x3) + x6 + (1-x4) >= 1
The above 4 inequalities represent a system of inequaities. They can be simplified as follows:
x1 + x2 + x3 >= 1
-x1 + x4 -x5 >= -1
-x2 + x5 -x6 >= -1
-x3 + x6 + -x4 >= -1
This gives the final system of inequalities.

GETTING STUCK WITH SIMILAR SYSTEM OF INEQUALITY ASSIGNMENT? ENROL WITH EXPERTSMINDS'S SYSTEM OF INEQUALITY ASSIGNMENT HELP SERVICES AND GET DISTRESSED WITH YOUR ASSIGNMENT WORRIES!