1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Debora [2.8K]
1 year ago
11

From the list of problems below, check all that are known to be NP-complete. You do not need to justify your answer. (Set cover)

Given a graphGand an integerk, find a set of verticesUof size at mostksuch that every edge is adjacent to at least one vertex inU. (Max SAT) Given a CNF formula and an integer g, find a truth assignment that satisfies at leastgclauses. (Linear programming) Given am×nmatrixA, and vectorsb∈Rm,c∈Rn, find the solution of maxcTx s.t. Ax≤bx≥0​(MST) Given an undirected, weighted graphG=(V,E)find a minimum spanning tree ofG, or outputs FALSE if such tree does not exist.
Engineering
1 answer:
White raven [17]1 year ago
7 0

Any computing issue that falls within the category of NP-complete problem has yet to find an effective solution algorithm.

<h3>Which problems are NP-complete?</h3>
  • Any of a family of computer problems that have no effective solution algorithm are referred to as NP-complete issues.
  • The traveling salesman problem, satisfiability issues, and graph-covering issues are only a few examples of the significant computer science issues that fall under this category.
  • The difficulty of NP and NP-Complete issues is equal. If a problem is included in both NP and NP-Hard Problems, it is said to be NP-Complete.
  • This statement, "This problem can change into an NP-complete problem on a non-deterministic Turing machine," is untrue for the obvious reason that while any problem in P is also a problem in NP, no problem in P is an NP-complete problem (unless P=NP, of course). If P is an NP problem and all NP problems convert into NP-complete problems, then P must also undergo this transformation.

To learn more about NP-complete problem refer to:

brainly.com/question/17218056

#SPJ4

You might be interested in
Determine (with justification) whether the following systems are (i) memoryless, (ii) causal, (iii) invertible, (iv) stable, and
lina2011 [118]

Answer:

a.

y[n] = x[n] x[n-1]  x[n+1]

(i) Memory-less - It is not memory-less because the given system is depend on past or future values.

(ii) Causal - It is non-casual because the present value of output depend on the future value of input.

(iii) Invertible - It is invertible and the inverse of the given system is \frac{1}{x[n] . x[n-1] x[n+1]}

(iv) Stable - It is stable because for all the bounded input, output is bounded.

(v) Time invariant - It is not time invariant because the system is multiplying with a time varying function.

b.

y[n] = cos(x[n])

(i) Memory-less - It is memory-less because the given system is not depend on past or future values.

(ii) Causal - It is casual because the present value of output does not depend on the future value of input.

(iii) Invertible - It is not invertible because two or more than two input values can generate same output values .

For example - for x[n] = 0 , y[n] = cos(0) = 1

                       for x[n] = 2\pi , y[n] = cos(2\pi) = 1

(iv) Stable - It is stable because for all the bounded input, output is bounded.

(v) Time invariant - It is time invariant because the system is not multiplying with a time varying function.

3 0
2 years ago
Miller Indices:
svetlana [45]

Answer:

A) The sketches for the required planes were drawn in the first attachment [1 2 1] and the second attachment [1 2 -4].

B) The closest distance between planes are d₁₂₁=a/√6 and d₁₂₋₄=a/√21 with  lattice constant a.

C) Five posible directions that electrons can move on the surface of a [1 0 0] silicon crystal are: |0 0 1|, |0 1 3|, |0 1 1|, |0 3 1| and |0 0 1|.

Compleated question:

1. Miller Indices:

a. Sketch (on separate plots) the (121) and (12-4) planes for a face centered cubic crystal structure.

b. What are the closest distances between planes (called d₁₂₁ and d₁₂₋₄)?

c. List five possible directions (using the Miller Indices) the electron can move on the surface of a (100) silicon crystal.

Explanation:

A)To draw a plane in a face centered cubic lattice, you have to follow these instructions:

1- the cube has 3 main directions called "a", "b" and "c" (as shown in the first attachment) and the planes has 3 main coeficients shown as [l m n]

2- The coordinates of that plane are written as: π:[1/a₀ 1/b₀ 1/c₀] (if one of the coordinates is 0, for example [1 1 0], c₀ is ∞, therefore that plane never cross the direction c).

3- Identify the points a₀, b₀, and c₀ at the plane that crosses this main directions and point them in the cubic cell.

4- Join the points.

<u>In this case, for [1 2 1]:</u>

l=1=1/a_0 \rightarrow a_0=1

m=2=2/b_0 \rightarrow b_0=0.5

n=1=1/c_0 \rightarrow c_0=1

<u>for </u>[1 2 \overline{4}]<u>:</u>

l=1=1/a_0 \rightarrow a_0=1

m=2=2/b_0 \rightarrow b_0=0.5

n=\overline{4}=-4/c_0 \rightarrow c_0=-0.25

B) The closest distance between planes with the same Miller indices can be calculated as:

With \pi:[l m n] ,the distance is d_{lmn}= \displaystyle \frac{a}{\sqrt{l^2+m^2+n^2}} with lattice constant a.

<u>In this case, for [1 2 1]:</u>

<u />d_{121}= \displaystyle \frac{a}{\sqrt{1^2+2^2+1^2}}=\frac{a}{\sqrt{6}}=0.41a<u />

<u>for </u>[1 2 \overline{4}]<u>:</u>

d_{12\overline{4}}= \displaystyle \frac{a}{\sqrt{1^2+2^2+(-4)^2}}=\frac{a}{\sqrt{21}}=0.22a

C) The possible directions that electrons can move on a surface of a crystallographic plane are the directions contain in that plane that point in the direction between nuclei. In a silicon crystal, an fcc structure, in the plane [1 0 0], we can point in the directions between the nuclei in the vertex (0 0 0) and e nuclei in each other vertex. Also, we can point in the direction between the nuclei in the vertex (0 0 0) and e nuclei in the center of the face of the adjacent crystals above and sideways. Therefore:

dir₁=|0 0 1|

dir₂=|0 0.5 1.5|≡|0 1 3|

dir₃=|0 1 1|

dir₄=|0 1.5 0.5|≡|0 3 1|

dir₅=|0 0 1|

5 0
3 years ago
Fast plz-The mirror check may involve ______________.
barxatty [35]

Answer:

Realigning the mirror

Explanation:

mirrors should be aligned to minimize blind spots, not look at the tires.

6 0
2 years ago
The melting point of Pb (lead) is 327°C, is the processing at 20°C hot working or cold working?
bonufazy [111]

Answer:

Explained

Explanation:

Cold working: It is plastic deformation of material at temperature below   recrystallization temperature. whereas hot working is deforming material above the recrystallization temperature.

Given melting point temp of lead is 327° C and lead recrystallizes at about

0.3 to 0.5 times melting temperature which will be higher that 20°C. Hence we can conclude that at 20°C lead will under go cold working only.

6 0
3 years ago
What are the indicators of ineffective systems engineering?
liberstina [14]

Answer:

Indicators for ineffective system engineering are as follows

1.Requirement trends

2.System definition change backlog trends

3.interface trends

4.Requirement validation trends

5.Requirement verification trends

6.Work product approval trends

7.Review action closure trends

8.Risk exposure trends

9.Risk handling trends

10.Technology maturity trends

11.Technical measurement trends

12.System engineering skills trends

13.Process compliance trends

7 0
3 years ago
Other questions:
  • Let suppose, you are going to develop a web-application for school management system. Then what architectural pattern will you u
    9·1 answer
  • In this lab, your task is to configure the external vEthernet network adapter with the following IPv6 address: Prefix: 2620:14F0
    14·1 answer
  • How do I cancel my subscription
    12·2 answers
  • An 80-percent-efficient pump with a power input of 20 hp is pumping water from a lake to a nearby pool at a rate of 1.5 ft3/s th
    14·1 answer
  • Compute the volume percent of graphite, VGr, in a 2.5 wt% C cast iron, assuming that all the carbon exists as the graphite phase
    9·1 answer
  • The ________________ attraction between the Earth and the moon is ______________ on the side of the Earth that happens to be ___
    5·1 answer
  • 4 points
    13·1 answer
  • Dndbgddbdbhfdhdhdhhfhffhfhhddhhdhdhdhdhd​
    11·2 answers
  • How can input from multiple individuals improve design solutions for problems that occur because of a natural disaster, such as
    5·1 answer
  • What lump sum of money must be deposited in a bank account at present time so that Php 500 monthly can be withdrawn for five yea
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!