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

Technician A says that the starter solenoid switches the high current on and off. Technician B says that the solenoid on the sta

jek_recluse [69]

Technician A is incorrect so that means Technician B is correct.

3 0

3 years ago

What is the tolerance of number 4?

Kamila [148]

Answer:

Answer: ±0.02 units or 20±0.02 units or 19.98-20.02 units depending on how they prefer its written (typically the first or second one)

Explanation:

says on the sheet. Unless otherwise stated 0.XX = ±0.02 tolerance

(based on image sent in other post)

5 0

3 years ago

Consider a single crystal of nickel oriented such that a tensile stress is applied along a [001] direction. If slip occurs on a

Elena L [17]

Answer:

$\mathbf{\tau_c =5.675 \ MPa}$

Explanation:

Given that:

The direction of the applied tensile stress =[001]

direction of the slip plane = [ $\bar 1$ 01]

normal to the slip plane = [111]

Now, the first thing to do is to calculate the angle between the tensile stress and the slip by using the formula:

$cos \lambda = \Big [\dfrac{d_1d_2+e_1e_2+f_1f_2}{\sqrt{(d_1^2+e_1^2+f_1^2)+(d_2^2+e_2^2+f_2^2) }} \Big]$

where;

$[d_1\ e_1 \ f_1]$ = directional indices for tensile stress

$[d_2 \ e_2 \ f_2]$ = slip direction

replacing their values;

i.e $d_1$ = 0 , $e_1$ = 0 $f_1$ = 1 & $d_2$ = -1 , $e_2$ = 0 , $f_2$ = 1

$cos \lambda = \Big [\dfrac{(0\times -1)+(0\times 0) + (1\times 1) }{\sqrt{(0^2+0^2+1^2)+((-1)^2+0^2+1^2) }} \Big]$

$cos \ \lambda = \dfrac{1}{\sqrt{2}}$

Also, to find the angle $\phi$ between the stress [001] & normal slip plane [111]

Then;

$cos \ \phi = \Big [\dfrac{d_1d_3+e_1e_3+f_1f_3}{\sqrt{(d_1^2+e_1^2+f_1^2)+(d_3^2+e_3^2+f_3^2) }} \Big]$

replacing their values;

i.e $d_1$ = 0 , $e_1$ = 0 $f_1$ = 1 & $d_3$ = 1 , $e_3$ = 1 , $f_3$ = 1

$cos \ \phi= \Big [ \dfrac{ (0 \times 1)+(0 \times 1)+(1 \times 1)} {\sqrt {(0^2+0^2+1^2)+(1^2+1^2 +1^2)} } \Big]$

$cos \phi= \dfrac{1} {\sqrt{3} }$

However, the critical resolved SS(shear stress) $\mathbf{\tau_c}$ can be computed using the formula:

$\tau_c = (\sigma )(cos \phi )(cos \lambda)$

where;

applied tensile stress $\sigma =$ 13.9 MPa

∴

$\tau_c =13.9\times ( \dfrac{1}{\sqrt{2}} )( \dfrac{1}{\sqrt{3}})$

$\mathbf{\tau_c =5.675 \ MPa}$

3 0

3 years ago

The difference between an initial condition and a boundary condition for conduction in a solid is:___________

leva [86]

Answer:

c. an initial condition specifies the temperature at the start of the problem and a boundary condition provides information about temperatures on the boundaries.

Explanation:

Conduction refers to the transfer of thermal energy or electric charge as a result of the movement of particles. When the conduction relates to electric charge, it is known as electrical conduction while when it relates to thermal energy, it is known as heat conduction.

In the process of heat conduction, thermal energy is usually transferred from fast moving particles to slow moving particles during the collision of these particles. Also, thermal energy is typically transferred between objects that has different degrees of temperature and materials (particles) that are directly in contact with each other but differ in their ability to accept or give up electrons.

Any material or object that allow the conduction (transfer) of electric charge or thermal energy is generally referred to as a conductor. Conductors include metal, steel, aluminum, copper, frying pan, pot, spoon etc.

Hence, the difference between an initial condition and a boundary condition for conduction in a solid is that an initial condition specifies the temperature at the start of the problem and a boundary condition provides information about temperatures on the boundaries.

7 0

3 years ago

Consider tests of an unswept wing that spans the wind tunnel and whose airfoil section is NACA 23012. Since the wing model spans

Dominik [7]

Answer:

Check the explanation

Explanation:

to know the lift per unit span (N/m) that is expected to be measured when the wing attack angle is 4°

as well as the corresponding section lift coefficient and die moment coefficient .

Kindly check the attached image below to see the step by step explanation to the above question.

3 0

3 years ago