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.

Course Link: Click Here


Theory of Computation Week 8 Nptel Assignment Answers
Theory of Computation Week 8 Nptel Assignment Answers

Theory of Computation Week 8 Nptel Assignment Answers (July-Dec 2024)


  1. 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


  1. 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}


  1. 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


  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
See also  Theory of Computation Week 4 Nptel Assignment Answers

Answer: C) ∀x∈Σ∗,x∈L⟺∀y∈Σ∗ such that |y|≤c⋅|x|k and V(x,y)=1


  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


  1. 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


  1. 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


  1. 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)))


  1. 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


  1. 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


  1. 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
See also  Theory of Computation | Week 1

Answer: C) Problems to which all problems in NP are reducible in polynomial time


  1. 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

All Weeks of Theory of Computation: Click here

For answers to additional Nptel courses, please refer to this link: NPTEL Assignment Answers