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
I need a thesis statement about Engineers as Leaders.
algol [13]

Answer:

Engineers are a very beneficial contribution in which offers great solutions to national problems.

5 0
3 years ago
Write two scnr.nextInt statements to get input values into birthMonth and birthYear. Then write a statement to output the month,
aalyn [17]

Answer:

import java.util.Scanner;

public class InputExample {

   public static void main(String[] args) {

       Scanner scnr = new Scanner(System.in);

       int birthMonth;

       int birthYear;

       birthMonth = scnr.nextInt();

       birthYear = scnr.nextInt();

       System.out.println(birthMonth+"/"+birthYear);

   }

}

3 0
3 years ago
) A shaft encoder is to be used with a 50 mm radius tracking wheel to monitor linear displacement. If the encoder produces 256 p
andrey2020 [161]

Answer:

number of pulses produced =  162 pulses

Explanation:

give data

radius = 50 mm

encoder produces = 256 pulses per revolution

linear displacement = 200 mm

solution

first we consider here roll shaft encoder on the flat surface without any slipping

we get here now circumference that is

circumference = 2 π r .........1

circumference = 2 × π × 50

circumference = 314.16 mm

so now we get number of pulses produced

number of pulses produced = \frac{linear\ displacement}{circumference} × No of pulses per revolution .................2

number of pulses produced = \frac{200}{314.16} × 256

number of pulses produced =  162 pulses

5 0
3 years ago
How would you describe what would happen to methane if the primary bonds were to break?
erastova [34]

Answer:

All the bonds in methane (CH4CH4) are equivalent, and all have the same dissociation energy.

The product of the dissociation is methyl radical (CH3CH3). All the bonds in methyl radical are equivalent, and all have the same dissociation energy.

The product of that dissociation is methylene (CH2CH2). All the bonds in methylene are equivalent, and all have the same dissociation energy.

The product of that dissociation is methyne (CHCH) .

The C-H bonds in methane do not have the same dissociation energy as C-H bonds in methyl radical, which in turn do not have the same dissociation energy as the C-H bonds in methylene, which are again different from the C-H bond in methyne.

If (by some miracle) you were able to get all four bonds in methane to dissociate absolutely simultaneously, they would all show the same dissociation energy… but that energy, per bond broken, would be different than the energy required to break just one C-H bond in methane, because the products are different.

(In this case, it’s CH4→C+4HCH4→C+4H versus CH4→CH3+HCH4→CH3+H.)

To alter hydrocarbons you add enough energy to break a C-H bond. Why does only one bond break? What concentrates the energy on one C-H bond?

the weakest CH bond is the one that breaks. in plain alkanes it has to do with the molecular orbital interactions between neighboring carbon atoms. look at propane for example. the middle carbon has two C-C bonds, and each of those C-C bonds is strengthened by slight electron delocalization from the C-H bonds overlapping with the antibonding orbitals of the adjacent carbons.

since the C-H bonds on the middle carbon donate electron density to both of its neighbors, those two are weakest.

one of them will break preferentially.

which one actually breaks depends on the reaction conditions (kinetics). frankly it's whichever one ramdomly approaches a nucleophile first. when the nucleophile pulls of one of the H's, the other C-H bonds start to share (delocalize) the negative charge across the whole molecule. so while the middle C feels the majority of the negative charge character, the other two C's take on a fair amount as well...

by the way, alkanes don't really like to break and form anions like that.

a better example would be something like isopropyl iodide, where the C-I bond breaks and the I carries away the electron pair, forming a carbocation (also not particularly stable, but more so than the carbanion).

7 0
3 years ago
A design team is working on creating a new energy-efficient light. They have completed the following steps:
Anastaziya [24]
I believe that it is to produce a product
7 0
3 years ago
Read 2 more answers
Other questions:
  • Cng containers need to be inspected
    7·1 answer
  • What is pixel's intensity ?​
    8·1 answer
  • Which term defines the amount of mechanical work an engine can do per unit of heat energy it uses?
    5·1 answer
  • What is an ip<br> Number
    12·1 answer
  • Compare electromagnets and solenoids
    9·1 answer
  • Water flows at a rate of 10 gallons per minute in a new horizontal 0.75?in. diameter galvanized iron pipe. Determine the pressur
    8·1 answer
  • How to identify this fossil
    9·1 answer
  • A hot-water stream at 80°C enters a mixing chamber with a mass flow rate of 0.46 kg/s where it is mixed with a stream of cold wa
    14·1 answer
  • If you log into the admin account on windows 10, will the admin be notified ? ​
    14·2 answers
  • Which of the following sensors is used to provide suspension control module with feedback regarding vehicle cornering​ forces?
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!