What additional information is required for check algorithm
Course:- Other Subject
Reference No.:- EM132320653

Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
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)


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


Verified Expert

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.

Put your comment

Ask Question & Get Answers from Experts
Browse some more (Other Subject) Materials
In what ways did the circumstances of Jesus' birth (according to the Gospels) fulfill the Jewish expectation of a Messiah and the Kingdom of God?
Describe the character in adequate detail so that the reader knows who you are discussing; provide a sense of the character's disorder. Identify the personality disorder diag
Explain how you would approach a health education program for Weight-Loss Interventions for Hispanic Populations: The Role of Culture. Journal of Obesity you have written ab
What do you feel are the two greatest challenges in the pubic safety administration field today? Explain the reasons behind your selection. What can be done to meet these
Design a correlational and experimental study investigating the relationship between these two variables time spent playing video games and aggression. Design an experimental
Did you remember any feelings of inferiority when you were in that stage (ages 6-12) and how did you conquer it? Did you receive any help from specific adults and in what fo
What dynamics are operating at this stage of life? How do biological imperatives and social demands interact to drive your psychological growth? How is generativity expresse
In your post, discuss some of the methodological issues unique to this psychological research. State the topic you selected and then write two potential research questions tha