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
Please write the following code in Python 3. Also please show all output(s) and share your code.
maksim [4K]

Answer:

sum2 = 0

counter = 0

lst = [65, 78, 21, 33]

while counter < len(lst):

   sum2 = sum2 + lst[counter]

   counter += 1

Explanation:

The counter variable is initialized to control the while loop and access the numbers in <em>lst</em>

While there are numbers in the <em>lst</em>,  loop through <em>lst</em>

Add the numbers in <em>lst</em> to the sum2

Increment <em>counter</em> by 1 after each iteration

6 0
3 years ago
You hang a heavy ball with a mass of 42 kg from a silver rod 2.7 m long by 1.9 mm by 2.6 mm. You measure the stretch of the rod,
nadezda [96]

Answer:

Explanation:

cross sectional area  A = 1.9 x 2.6 x 10⁻⁶ m²

= 4.94 x 10⁻⁶ m²

stress = 42 x 9.8 / 4.94 x 10⁻⁶

= 83.32 x 10⁶ N/m²

strain = .002902 / 2.7

= 1.075 x 10⁻³

Young's modulus = stress / strain

= 83.32 x 10⁶ / 1.075 x 10⁻³

= 77.5 x 10⁹ N/m²

5 0
3 years ago
Engineers will redesign their products when they find flaws. TRUE O False​
nataly862011 [7]

Answer:

true

Explanation:

6 0
3 years ago
A CL soil is being used for compacted fill on a project. A sample of the compacted soil with a total volume of 1/30 ft3 weighs 4
Genrish500 [490]

Answer:

A. 0.4

B. 1.003

C. 0.83

Explanation:

The void ratio of a mixture is defined as the ratio of the volume of voids to volume of solids.

Total volume of soil = 1/30 ft3

= 1 ft3/30 * 0.0283 m3/1 ft3

= 9.43 x 10^-4 m3

Mass of water is in the soil = 20% * 4.8

= 0.96 pounds of water

= 0.96 * 0.454

= 0.44 kg

SG = density of substance/density of water

= 2.66 * 1 kg/l

Density of the soil = 2.660 kg/l

Mass of solid = 80 %

= 80% * 4.8 * 0.454

= 1.74 kg

Volume of solids = mass/density

= 1.74/2.66

= 6.63 l

= 6.63 x 10^-4 m3.

The volume of voids is found by adding the volume of water and the volume of air.

Total volume of soil = volume of (solids + voids)

9.43 x 10^-4 = 6.63 x 10^-4 + voids

Volume of voids = 2.8 x 10^-4 m3

A.

Void ratio = volume of void : volume of solids

= 2.8 : 6.63

= 0.4

B.

Y = (1 + w) * Gs * Yw * (1 + e)

Y = moist unit weight

Yw = unit weight of water

w = moisture content of the material

Gs = pecific gravity of the solid

e = void ratio

= (1 + 0.2) * 2.66 * 0.44 * (1 + 0.4)

= 1.003.

C.

gd = Y/(1 + w)

Or

= Gs * Yw * 1/(1 + e)

= 0.83.

6 0
3 years ago
Hey answr this sajida Yusof
Allisa [31]
What do u need? Rusbaisuwvwbs
5 0
3 years ago
Read 2 more answers
Other questions:
  • A cylindrical tank is required to contain a gage pressure 520 kPa . The tank is to be made of A516 grade 60 steel with a maximum
    6·1 answer
  • "The office personnel at Garden Glory use a database application to record services and related data changes in this database. F
    9·1 answer
  • A completely mixed activated-sludge process is being designed for a wastewater flow of 10,000 m3/d (2.64 mgd) using the kinetics
    6·1 answer
  • One who is trained in math, science and physics in order to work in a branch of engineering
    7·2 answers
  • As described in "A Note About Bacterial Reproduction -- and the "Culture Bias,"" the organism Epulopisciumdoes not divide by bin
    12·1 answer
  • Ten dollars per hour is about how much income per year
    5·2 answers
  • A landowner and a contractor entered into a written contract under which the contractor agreed to build a building and pave an a
    14·1 answer
  • Identify five safety hazards that should be included in the design of the school
    6·1 answer
  • I will mark brainliest.
    6·2 answers
  • You need to lift a 2012 toyota highlander and haven't done so in a while. which of these are reliable sources for checking the c
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!