What additional information is required for check algorithm

Assignment Help Other Subject
Reference no: EM132320653

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.

Reference no: EM132320653

How will we collect the data

Create a matrix to focus and plan data collection for your proposed evaluation, providing detailed background information about the program and the evaluation; also providin

Neurophysiological and evolutionary

Provide a framework for the theoretical concepts associated with Donald Hebb the Neurophysiological and Evolutionary write 200-300 cite references

About the psychodynamic therapist

Write briefly in response to the following, using your text and one other reference (preferably from the APUS online library) and citing both in APA format. This assignment

Describe the institution auburn city council

1. Describe the institution ‘Auburn city council'. 2. Assess this institution (auburn city council) against each of the six UK Commission Principles of Good Governance.

Describe the plan you will implement to begin working

Determine what issues were addressed from a counseling perspective for Lisa. Describe the plan you will implement to begin working more effectively with Lisa's three children

Health items that were listed were surprising to you

What health items that were listed were surprising to you, and why? Based on this information, describe in detail 5 things you would consciously look for about the well-bein

Type of reasoning from your friends life

Imagine that your best friend still believes in extrasensory perception, despite research evidence that refutes its existence. Briefly describe each of the four types of fault

Healthcare systems of france and usa

Compare the benefits and liabilities of France's healthcare system. Discuss the differences and similarities compared to the USA's approach and their strengths and weaknesse


Write a Review

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd