(e) T F The set of all NP-hard problems is the same as the set of...

(e) T F The set of all NP-hard problems is the same as the set of all NP-complete problems.

(f) T F The dynamic programming technique can be used to solve any optimization problem.

(g) T F If A ≤p B and A is NP-Complete, then B is also NP-Complete.

(h) T F If a problem is in P, then it can be solved in polynomial time nondeterministically

with brief explaination

Expert Solution

Answer:----------

(e) T F The set of all NP-hard problems is the same as the set of all NP-complete problems.
False, NP-Complete set is a subset of NP-Hard set and A problem is NP-Complete iff it is NP-Hard and it is in NP itself.

(f) T F The dynamic programming technique can be used to solve any optimization problem.
False, because Dynamic programming (DP) can be used to solve certain optimization problems. For example Rod Cutting, Chained Matrix Multiplication etc.

(g) T F If A ≤p B and A is NP-Complete, then B is also NP-Complete.
True,
Proof:-
Let f be a polynomial-time reducibility function from A to B.
Let M be a polynomial-time nondeterministic TM that decides A.
NTM M′ to decide membership in B:
On input w:
• Compute x = f(w); |x| is bounded by a polynomial in |w|.
• Run M on x and accept/reject (on each branch) if M does.
– Polynomial time-bounded NTM.
– Decides membership in B:
• M′ has an accepting branch on input w
iff M has an accepting branch on f(w), by definition of M′,
iff f(w) ∈ A, since M decides A,
iff w ∈ B , since A ≤p B using f.
– So M′ is a poly-time NTM that decides B, B∈ NP.

(h) T F If a problem is in P, then it can be solved in polynomial time nondeterministically.
False, because If a problem is in P, then it can be solved in polynomial time deterministically.

venereology answered 1 month ago

Using a suitable Venn diagram, describe the relationship between NP, NP-Hard, and NP-Complete problems from

E ::= E + T | T T ::= T * F | F F ::=...

E ::= E + T | T T ::= T * F | F F ::= num | (E) Num ::= 0 | 1 | 2 | 3 | 4 | 5 | . . . . . . . Question: 1 a. Show the Left-most derivation for the expression: 5 * 7 + 6 * (1 + 2). b. Show the Right-most derivation for the expression: 5 * 7 + 6 * (1 + 2).

What is NP? What is P? What is NP-complete? What is NP- hard?

What is NP? What is P? What is NP-complete? What is NP- hard? Give brief definitions. Give an example of an NP- complete problem. Is P equal to NP?

Give the grammar following: E --> E + T | T T --> T* F |...

Give the grammar following: E --> E + T | T T --> T* F | F F --> (E) | id Eliminating the left recursion rules and getting a non-left recursive equivalent grammar.

Consider the following grammar G: E -> E + T | T T -> T F...

Consider the following grammar G: E -> E + T | T T -> T F | F F -> F* | a | b This grammar can be used to generate regular expressions over the alphabet {a,b} with standard precedence rules. Show your solution for each of the following 5 points: 1. Remove left recursion and write the resulting grammar G1. 2. For the grammar G1, compute and write the sets FIRST for every right hand side...

The position vector F(t) of a moving particle at time t[s] is given by F(t)= e^t...

The position vector F(t) of a moving particle at time t[s] is given by F(t)= e^t sin(t)i-j+e^t cos(t)k a) Calculate the acceleration a(t). b) Find the distance traveled by the particle at time t = 3π/2, if the particle starts its motion at time t = π/2. c) Find the unit tangent vector of this particle at time t = 3π/2. d) Find the curvature of the path of this particle at time t = 3π/2.

T/F Which of the following are true? _ All proteins with the same (highly similar) 3D...

T/F Which of the following are true? _ All proteins with the same (highly similar) 3D structure will have the same function. _ All proteins with the same function will have the same (highly similar) 3D structure. _ Functional homologs may share structure, catalytic, and ligand binding sites. _ Functional homologs may not share sequence similarity

Let f(t) =t^2−1 and g(t) =e^t. (a) Graph f(g(t)) and g(f(t)). (b) Which is larger,f(g(5)) or...

Let f(t) =t^2−1 and g(t) =e^t. (a) Graph f(g(t)) and g(f(t)). (b) Which is larger,f(g(5)) or g(f(5))? Justify your answer. (c) Which is larger, (f(g(5)))′or g(f(5))′? Justify your answer.

Problems in this set involve e ffusion and/or partial pressure. Several of the problems are repeats....

Problems in this set involve e ffusion and/or partial pressure. Several of the problems are repeats. (Mm(SF 6) = 146.06 g/mol; Mm(UF6) = 352.02 g/mol; Mm(CH4) = 16.04 g/mol; and Mm(C2H6)= 30.07 g/mol.) A sample contains an unknown ratio of methane, CH4,t o ethane,C2H6. This sample is placed into a first effusion apparatus and the effused gas is collected. This effused gas is placed into a second apparatus and allowed to effuse a second time. The mole percent of effused...

Example 1.8. Fix a domain D, and let V be the set of all functions f(t)...

Example 1.8. Fix a domain D, and let V be the set of all functions f(t) defined on D. Define addition and scalar multiples as with polynomials for all t ∈ D: (f + g)(t) = f(t) + g(t) (cf)(t) = cf(t) Then V is a vector space as well, the axioms are verified similarly to those for Pn. Verify that V in the previous example satisfies the axioms for a vector space.

Question