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 Term, Marks = 5, Lesson No. )

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

### Question

(Final Term, Marks = 5, Lesson No. )

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

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

### Question

(Mid Term, Marks = 5, Lesson No. )

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

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

### Question

(Mid Term, Marks = 10, Lesson No. )

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

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

### Question

(Mid Term, Marks = 5, Lesson No. )

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

### Question

(Mid Term, Marks = 10, Lesson No. )

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