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?

Put your comment

Ask Question & Get Answers from Experts
Browse some more (Other Subject) Materials
Compare marketplaces with marketspaces. What are the advantages and limitations of each? What is your favorite marketspace and why? What is the impact of your favorite ma
What type of PICOT question would you create for each of these scenarios and write a PICOT statement in an area of interest to you, which is applicable to your proposed capst
What are the potential obstacles to using complementary and alternative therapies by conventional practitioners? How could you, as a future nurse effect some changes in this a
How do Western habits of childcare in individual 'nuclear' families differ from practices of many other cultures? what are some possible benefits and drawbacks of Western pa
Provide four reasons for obeying the law or ethical principles that do not involve punishment or reward. Is there a difference between people who obey the law out of fear a
Identify at least three processes (capabilities) that are needed in order to keep track of your collection. Identify the input data required for each of the processes.
There are 4 novels - Thriller, Mystery, Romance and Science Fiction - writen by Ambrose, Richards, Hooper and Walsh, and published by Alpha, Beta, Gamma and Theta not in nec
Most pets become classically conditioned to a variety of stimuli associated with their feeding. If you have a pet now, see if you can identify examples of your pet's condition