In the name of ALLAH, the most beneficient, the most merciful

Theory of Computation (CS701)

Subjective, Short Questions from Past Papers

 

Subjective Questions

Question

(Final, 2016, Fall, Marks = 5, Lesson No. )

Prove that DOUBLE-SAT is NP-Complete by reducing from 3SAT.

Answer:

Question

(Final, 2016, Fall, Marks = 5, Lesson No. )

DOMINATING-SET = {}, show that it is NP-complete by giving a reduction from VERTEX-COVER.

Answer:

Question

(Mid, 2015, Fall, Marks = 5, Lesson No. )

Show that the set of all positive real numbers has one-to-one correspondence with the set of all real numbers.

Answer:

Question

(Mid, 2015, Fall, Marks = 5, Lesson No. )

Consider the pair of numbers 64 and 32965. Show that they are relatively prime or not.

Answer:

Question

(Mid, 2015, Fall, Marks = 10, Lesson No. )

In the Silly Post Correspondence Problem (SPCP), the iop string in each pairhas the same length as the bottom string. Show that SPCP is decidable.

Answer:

Question

(Mid, 2015, Fall, Marks = 10, Lesson No. )

Show that some true statements in TH(N, +, x) are not provable.

Answer:

Question

(Mid, 2015, Fall, Marks = 5, Lesson No. )

Show that the set of all odd integers has one-to-one correspondence with the set of all even integers.

Answer:

Question

(Mid, 2015, Fall, Marks = 5, Lesson No. )

Consider the pair of numbers 234 and 399. Show that they are relatively prime or not.

Answer:

Question

(Mid, 2015, Fall, Marks = 10, Lesson No. )

Show that set of provable statements in TH(N, +, x) is turing recognizable.

Answer: