## Subjective Questions

*Question*

(Final Term, Marks = 5, Lesson No. )
Prove that DOUBLE-SAT is NP-Complete by reducing from 3SAT.

*Answer:*

*Question*

(Final Term, Marks = 5, Lesson No. )
DOMINATING-SET = {

*Answer:*

*Question*

(Mid Term, 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 Term, Marks = 5, Lesson No. )
Consider the pair of numbers 64 and 32965. Show that they are relatively prime or not.

*Answer:*

*Question*

(Mid Term, 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 Term, Marks = 10, Lesson No. )
Show that some true statements in TH(N, +, x) are not provable.

*Answer:*

*Question*

(Mid Term, 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 Term, Marks = 5, Lesson No. )
Consider the pair of numbers 234 and 399. Show that they are relatively prime or not.

*Answer:*

*Question*

(Mid Term, Marks = 10, Lesson No. )
Show that set of provable statements in TH(N, +, x) is turing recognizable.