*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:*