Theory of Computation Week 8 Nptel Assignment Answers
Are you looking for Theory of Computation Week 8 Nptel Assignment Answers? You’ve come to the right place! Access the latest and most accurate solutions for your Assignment 8 in the Theory of Computation course. Our detailed answers are designed to help you understand key concepts and excel in your studies.
Theory of Computation Week 8 Nptel Assignment Answers
Theory of Computation Week 8 Nptel Assignment Answers (July-Dec 2024)
The class NP is defined as the class of problems that A) Can be solved in polynomial time by a nondeterministic Turing Machine B) Cannot be solved in polynomial time by a deterministic Turing Machine C) Can be solved in polynomial time by a deterministic Turing Machine D) Cannot be solved in polynomial time by a nondeterministic Turing Machine
Answer: A) Can be solved in polynomial time by a nondeterministic Turing Machine
The class coNP is defined as A) {L∣L¯∈NP} B) {L∣L∉NP} C) {L¯∣L⊆L′∈NP} D) {L¯∣L∉NP}
Answer: A) {L∣L¯∈NP}
L∈NP if there exists constants c>0 and k≥0, and a polynomial time Turing Machine V, such that A) ∃x∈Σ∗,x∈L⟺∀y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1 B) ∀x∈Σ∗,x∈L⟺∃y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1 C) ∀x∈Σ∗,x∈L⟺∀y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1 D) ∃x∈Σ∗,x∈L⟺∃y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1
Answer: B) ∀x∈Σ∗,x∈L⟺∃y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1
L∈coNP if there exists constants c>0 and k≥0, and a polynomial time Turing Machine V, such that A) ∃x∈Σ∗,x∈L⟺∀y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1 B) ∀x∈Σ∗,x∈L⟺∃y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1 C) ∀x∈Σ∗,x∈L⟺∀y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1 D) ∃x∈Σ∗,x∈L⟺∃y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1
Answer: C) ∀x∈Σ∗,x∈L⟺∀y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1
Which of the following problems is not known to be in the complexity class P? A) Deciding whether a natural number is even B) Deciding whether a boolean formula is satisfiable C) Deciding whether a graph is connected D) Deciding whether a binary string has an even number of 1’s
Answer: B) Deciding whether a boolean formula is satisfiable
These are Theory of Computation Week 8 Nptel Assignment Answers
Which of the following problems is known to be in the complexity class coNP? A) Deciding whether a natural number is prime B) Deciding whether a boolean formula is satisfiable C) Deciding whether a graph has a Hamiltonian path D) Deciding whether two graphs are isomorphic
Answer: A) Deciding whether a natural number is prime
Let L be a language in the complexity class P. Which of the following is not known? A) L∈NP B) L∈coNP C) L∈NP∩coNP D) L∈NP-complete
Answer: D) L∈NP-complete
If L∈NTIME(f(n)), then A) L∈DTIME(f(n)) B) L∈DTIME(logf(n)) C) L∈DTIME(f(n)²) D) L∈DTIME(2^O(f(n)))
Answer: D) L∈DTIME(2^O(f(n)))
The class NP is not known to be closed under which of the following operations? A) Union B) Intersection C) Concatenation D) Complementation
Answer: D) Complementation
If coNP ⊆ NP then which of the following is true? A) NP = coNP B) P = NP C) P ≠ NP D) NP ≠ coNP
Answer: A) NP = coNP
The class NP-hard is defined as the set of A) Problems which are reducible in polynomial time to some NP complete problem B) Problems which are reducible in polynomial space to some NP complete problem C) Problems to which all problems in NP are reducible in polynomial time D) Problems to which all problems in NP are reducible in polynomial space
Answer: C) Problems to which all problems in NP are reducible in polynomial time
If a decision problem A is polynomial time reducible to another decision problem B, then which of the following statements is necessarily true? A) If A is NP-hard then B is also NP-hard B) If B is NP-hard then A is also NP-hard C) If A is in NP then B is also in NP D) If A is NP-complete then B is also NP-complete
Answer: A) If A is NP-hard then B is also NP-hard
These are Theory of Computation Week 8 Nptel Assignment Answers
