Ask question

Ask question

All categories

3 years ago

7

Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The 2-SAT problem is a SAT variant in whi

ch each clause contains at most two literals. 2-SAT is known to have a polynomial-time algorithm. Is each of the following statements true or false?
1. 3-SAT ≤p TSP.2. If P ¹ NP, then 3-SAT ≤p 2-SAT.3. If P ¹ NP, then no NP-complete problem can be solved in polynomial time.

1 answer:

Hitman42 [59]3 years ago

7 0

3-SAT ≤p TSP

If P ¹ NP, then no NP-complete problem can be solved in polynomial time.

both the statements are true.

<u>Explanation:</u>

3-SAT ≤p TSP due to any complete problem of NP to other problem by exits of reductions.
If P ¹ NP, then 3-SAT ≤p 2-SAT are the polynomial time algorithm are not for 3-SAT. In P, 2-SAT is found, 3- SAT polynomial time algorithm implies the exit of reductions. 3 SAT does not have polynomial time algorithm when P≠NP.
If P ¹ NP, then no NP-complete problem can be solved in polynomial time. because for the NP complete problem individually gets the polynomial time algorithm for the others. It may be in P for all the problems, the implication of latter is P≠NP.

You might be interested in

The mean of 10 numbers is 9, then the sum (total) of these numbers will be

qwelly [4]

Answer:

90

Explanation:

mean is basically taking the sum of all numbers and then dividing the sum with the number of all given numbers..

here, the mean is 9, total numbers are 10.. so the sum will be 9 multiplied by 10, that is 90.

5 0

3 years ago

Read 2 more answers

Dampness or moisture introduces ____ into the weld, which causes cracking when some metals are welded.

N76 [4]

Answer: Dampness or moisture introduces hydrogen into the weld, which causes cracking when some metals are welded.

Explanation:

<em>This moisture (hydrogen) is a major cause of weld cracking and porosity. </em>

5 0

2 years ago

Hot carbon dioxide exhaust gas at 1 atm is being cooled by flat plates. The gas at 220 °C flows in parallel over the upper and l

sergeinik [125]

The local convection heat transfer coefficient at 1 m from the leading edge is $0.44 \frac{W}{m^{2} \times K}$ , the average convection heat transfer coefficient over the entire plate is $0.293 \frac{W}{m^{2} \times K}$ and the total heat flux transfer to the plate is $61.6 KJ$ .

Explanation:

It is case of heat and mass transfer in which due to temperature difference between gas and surface. Further temperature boundary layer will developed on flat plate in longitudinal direction.

Hot carbon dioxide exhaust gas

physical properties

$r= 1.05 \frac{kg}{m^{3}}$

$c_p = 1.02 \frac{kJ}{Kg \times K}$

$m= 231 \times 10^{7} \frac{N \times s }{m^2}$

υ = $21.8 \times 10^{6} \frac{m^2}{s}$

$k = 32.5 \times 10^{3} \frac{W}{m \times K}$

$\alpha = 30.1 \times 10^{6} \frac{m^{2}}{s}$

$Pr = 0.725$

Apart from these other data arr given below,

$v= 3 \frac{m}{s} \\ p= 1 atm \\ L_c = 1.5m \\T_g= 220 C \\ T_s = 80 C$

To find the local convection heat transfer coefficient at 1 m from the leading edge, we use correlation used for laminar flow over flat plate,

$Nu = \frac{ h \times L }{k} = 0.332 \times (Re^{\frac{1}{2} }) \times (Pr^{\frac{1}{3} })$

where h= Average heat transfer coefficient

L= Length of a plate

k= Thermal Conductivity of carbon dioxide

Re = Reynold's Number

Pr = Prandtle Number

(a) Convection heat transfer coefficient at 1 m from the leading edge

is referred as local convection heat transfer coefficient.

To find convection heat transfer coefficient at 1 m from leading edge,

$Nu = \frac{ h_local \times L }{k} = 0.332 \times (Re^{\frac{1}{2} }) \times (Pr^{\frac{1}{3} })$

Here, first we have to find Re and Pr,

$Re = \frac{r \times v \times L}{m}$

$Re = \frac{1.0594 \times 3 \times 1}{231 \times 10^{7}}$

$Re = 20.63 \times 10^{-10}$

Pr number is take from physical property data and Pr is 0.725.

Putting value of Re and Pr in main equation,

we get

$Nu = \frac{ h_local \times 1 }{32.5 \times 10^{3}} = 0.332 \times ( (20.63 \times 10^{-10})^{\frac{1}{2} }) \times (0.725^{\frac{1}{3} })$

$h_local = 32.5 \times 10^{3} \times 0.332 \times ( (20.63 \times 10^{-10})^{\frac{1}{2} }) \times (0.725^{\frac{1}{3} })$

$h_local = 0.44 \frac{W}{m^{2} \times K}$

(b) To find average convection heat transfer coefficient,

it can be find out as case (a), only difference is that instead of L=1 m, L=1.5 m would come,

Therefore,

$Nu = \frac{ h \times 1.5 }{32.5 \times 10^{3}} = 0.332 \times ( (20.63 \times 10^{-10})^{\frac{1}{2} }) \times (0.725^{\frac{1}{3} })$

Finally,

$h = \frac{0.44}{1.5}$

$h = 0.293 \frac{W}{m^{2} \times K}$

(C) Total heat flux transfer to the plate is found out by,

$Q = h \times (T_g - T_s)$

$Q = 0.293 \times (220-80) \\ Q= 0.293 \times 140 \\ Q= 61.6 KJ$

8 0

3 years ago

The aluminum rod AB (G 5 27 GPa) is bonded to the brass rod BD (G 5 39 GPa). Knowing that portion CD of the brass rod is hollow

Temka [501]

Answer:

Qcd=0.01507rad

QT= 0.10509rad

Explanation:

The full details of the procedure and answer is attached.

7 0

3 years ago

Working with which of these systems requires a technician that has been certified in an EPA-approved course?

makvit [3.9K]

EPA Regulations provides a certified course for the technicians involved in the Air-conditioning system.

Answer: Option (b)

<u>Explanation:</u>

The EPA regulation has implemented an act called the "Clean Air Act" under the "section of 609".

This act provides some basic requirements for EPA Regulation such as follows;

Refrigerant: This unit must be approved by EPA Regulations before being implemented into the atmosphere.
Servicing: This system provides a certified course for technicians in service and also approve them with proper refrigerant equipment.
Reuse Refrigerants: The use of recycled refrigerants must be properly monitored before it comes in to serve.

6 0

4 years ago