Theory

of Computation

ASSIGNMENT

N0 3

Solved

by:

Student Name: Muhammad Adil

Student Id: MS170401318

Subject cod: CS701

Due Date: 18,

Jan 2018

Question

No. 1 (Part 1 = 10 + Part 2 = 15) = 25 marks)

Part 1.) Suppose a post man is assigned the duty to post cards in every house H,

as shown in undirected graph F. A Hamiltonian path from house H1 to H7 is a

path such that: Post man starts from H1 and ends at H7. Find Hamiltonian path

from H1 to H7, if there are multiple paths then specify it each path and design

the verification algorithm of Hamiltonian paths.

Graph F:

Solution Part 1:

As by definition the Hamiltonian

path is a path in

an undirected Graph or directed graph that visits each vertex exactly once.

Hamilton paths in the given graphs are:

1)

h1,h2,h5,h7,h4,h6,h3

2)

h1,h4,h2,h5,h7,h6,h3

3)

h1, h3,h6,h7,h5,h2,h4

4)

h1, h3,h6,h4,h7,h5,h2

We have found multiple Paths for this graph. For the sake

of proof now we have to use verification algorithm of Hamiltonian path.

Now consider the following theorem:

Theorem:

HAMPATH={

Now we have to this polynomial time algorithm for

HAMPATH. To verify the given Graph has a Hamiltonian path from h1 to

h3.

For this to proof we use verification algorithm>

This algorithm will accept the input of the form

if V0——-Vn indeed a Hamiltonian path from h1 to h3.

1- On input

2- Check if V0= h1.

3- Check if Vn= h3.

4- Check if all vi,s are Distinct and

each vertex of G appears in the list.

5- If i=1 to n-1 Check, If (vi, vi+1) are

connected with an edge of G.

So clearly, this is a polynomial time algorithm.

Part 2. ) Suppose there is a set F of given

numbers {?10, ?3, ?2, 5, 9}. Find all the subsets sums which are same. Verify

this is NP-complete problem and design the algorithm in the subset sum problem

of given set F and a target number T.

Solution

Part 2:

Now let

us consider a set of numbers {?10, ?3, ?2, 5, 9}. This set has subsets. The elements in the

subsets sum to different numbers.

We know that, this set has 2n

1- {} sum

to 0.

2- {-10}

sum to -10

3- {-3} sum

to -3.

4- {-2} sum

to -2

5- {5} sum

to 5

6- .

7- .

8- .

9- .

…………….and so on tell subset 32

In this subset problem we are given a set F of numbers

and a target value T. If such that . We are asked if there is a subset of F whose

elements sum to t.

Formally:

SUBSETSUM= There is such that

Now let us devise a polynomial time verification

algorithm for SUBSETSUM, while considering the given problem. We have to verify

that if a F has a subset T that adds up to t.

We know that the verification algorithm is easy to

design. The algorithm will accept inputs of the form . It

simply checks that, If T is a subset of F and add its elements to see. If they

add up to t, then

1

On

input

2

Check

if T is a subset of F. If not reject.

3

Add

all the elements of T. If they sum to t accept.

Clearly, this is a polynomial time Verification

algorithm.

Now I have to proceed toward the next step and, Verify

this problem as NP-complete problem.

In fact a non-deterministic machine can guess” proof”:

Theorem:

If A has a polynomial time verification algorithm then A

is in NP:

To prove

the given theorem Since A has an polynomial time verification algorithm let us

call that algorithm V. We want to show that A is accepted by some

non-deterministic Turing machine (TM) N, that runs in non-deterministic

polynomial time.

The machine N will use V as a subroutine. Suppose V runs

in time nk.

The

description of N:

1

On

input w of length n.

2

Guess

a certificate c of size at most nk.

3

Run

V on

4

If

V accepts accept. Else reject

Let us note:

1. Clearly if then there is a

c such that V accepts .

2. Since, V run in time O(nk)

hence such c cannot have length more than O(nk).

3. Thus there is at least one branch of N

that accept w. That is the branch correctly guesses c.

On the other hand:

1. If then for all c V reject .

2. So all the branches of N reject w.

Therefore L(N) = A. Now it is easy to see that N runs in

polynomial time since V runs in polynomial time. Then the whole proof can be

summarized in one line:

“We can guess the certificate using the power of

non-determinism, Hence.

Question No. 2 (13+12=25 marks)

How can you differentiate between NUTM and QUTMs as the perspective of

DNA computing? Elaborate it critically in your own words.

Answer

1):

We know that the

theory of computer science is based around universal Turing machines (UTMs):

abstract machines that able to execute all possible algorithms.

The most

important class of problem in computer science is the non-deterministic

polynomial complete problems. Non-deterministic (NUTMs) are theoretically

exponentially faster than both classical Universal Turing Machines (UTMs) and

quantum mechanical UTMs (QUTMs). Here, in the given article demonstration for

the first physical design of an NUTM is discussed.

Now I have to move toward the asked question after

introducing the NUTMs and UTMs (QUTMs).

Differences

between NUTMs and UTMs (QUTMs)

NUTMs

(QUTMs)

1

In an NUTM, the resource limitation is space.

While in QUTMs the

resource limitation is time.

2

The NUTMs is a (UTMs) that can

reproduce itself, and thereby follow all computational paths in parallel,

with the computation ending when one path reaches to the accepting

state.

While QUTM has one input

state and multiple output states.

3

The NUTMs are theoretically exponentially faster than both

classical UTMs, and QUTMs.

While the classical QUTMs are

slow as compare to NUTMs

4

The mechanism of the NUTM depends on the specificity of

molecular binding. As like living organisms.

–

5

The use of error-correcting codes is directly ported to NUTMs.

While the

use of error-correcting codes are used

ubiquitously in electronic computers, and are also essential for QUTMs.

The repetition of computations.

6

The use of a polynomial number of repetitions does not

affect the fundamental speed advantage of NUTMs over classical QUTMs.

While in QUTMs it affects the speed, because to reduce

the noise a repeat computations, either spatially or

temporally required here.

The use of restriction endow nucleases and/or

CRISPR/CAS9

7

The ability to cut DNA sequences is useful for NUTM

error correction.

While the ability to cutting

DNA sequences is not that much useful for QUTMs error correction as much like

NUTMs

Checking certificates:

8

When NP problem is solved by an NUTM, the answer can be

efficiently checked by using an electronic computer in P time. This

means that an NUTM is required to succeed with a small probability of success.

While QUTM is

required more probability for

their success, and efficiency check.

9

The question of

NUTM computation is reversible in P time is still unclear.

While Computation in a QUTM is in principle reversible,

i.e. there is no lower bound on the amount of energy required per operation.

10

The relationship between BPP (bounded-error probabilistic

polynomial-time) and NP is unknown in NUTM.

While it would seem computationally useful to generate an

exponential number of randomized QUTMs in P time.

Conclusion: The NUTMs and QUTMs both use

exponential parallelism. But their advantages and disadvantages are different.

NUTMs use general parallelism, which take up a physical space. While in QUTM

the parallelism is restricted. In principle therefore, it would seem to be

possible to engineer an NUTM capable of utilizing an exponential number of QCs

in P time.

Part 2): what functionalities

have been expressed in figure 1(part a and part b)? Elaborate it critically of

given figures in your own words.

Fig1: part (a )- Shows

that Computational complexity of feasibility thesis asserts, that

there is a fundamental qualitative difference between algorithms runs in

polynomial time and algorithms that run in exponential time (EXP time): Example

of polynomial time algorithm is (schoolbook multiplication) and example of Exponential time algorithm is

(e.g. position evaluation in a generalized game). The fig shows that as the size to the problem increase the polynomial

algorithm still have hold on and have efficient result in feasible problem. While

on the other hand the Exponential algorithm (EXP time) don’t have such quality.

Moreover the feasibility thesis also assets that NP algorithms can’t feasibly

be executed this is still less clear to assumes P=NP.

Now

to further explain fig1 part (a ): A function is the class of

P. if there is an algorithm computing f and a positive constants like A, k,

such that for every n and every algorithm

computes f(x) in at most A nK steps.

The

most important thing in computational complexity theory is the class of

non-deterministic polynomial time (NP) problems. This is the class of decision

problem where the solution is verified in P time. Moreover, a decision problem

C is in the class NP if there is a function such and a constant k.

1- If Then

2- If Then we have

Many problems belong to NP classes

e.g (graph isomorphism, Boolean satisfiability, travelling Salesman, graph

coloring, and so on ). NP complete problems are enough difficult, and so all NP

problems can be reduced to P time. This shows that if we can solve any NP complete problem in P time then one can solve

all NP problems in P time.

The standard NP complete problem is

3SAT problems. In 3SAT problems, the problem is to find an assignment of

Boolean variables to convince an expression of the this form This Eq show

finding a way to assign a values True or False to each variable up to Vn.

For example, to make the overall expression true. It can easily

be observed first to verifying that the solution is P time. Only the values can

evaluate the expression by filling them. However there is no such a P time

algorithm exists to find the solution. We know that 3SAT is NP complete because

it has been proved possible to transform any NP problem into a 3SAT problem in

P time (Polynomial time). This implies that if one could solve arbitrary 3SAT

problems in P time (Polynomial Time) then one could solve any NP

(Non-deterministic Polynomial) problem in P time.

So the NP (Non-deterministic

polynomial) class is commonly considered as a strict superset of P. If e,g then it would seem harder

to find a solution to a problem, to verify it as a correct solution.

In Fig 1: (part b):

The part (b) of fig 1: Shows that, it

has never been proved, that the question is the

most important open problem in mathematics. This problem has also a massive

practical importance for if . We also have a shocking result for activities that

depend on cryptography for security, such as the banking system, the Internet, and

so on….

This is very important to

differentiate in mathematical problem of the true or falsehood of the given proposition, further the practical problem of solving NP (Non-deterministic

Polynomial) problems in P time (Polynomial Time). The mathematical problem is

constrained by a given set of axioms and proof methods, whereas all feasible

available physical connotes may be used for the solution of the given practical

problem. This paper doesn’t address the P=NP as mathematical problem. But this

paper presents the physical design for a computer. Which is exponentially more

accelerate or (dominate) the conventional computers on NP complete problems.

The

basic difference between Algorithms that run in polynomial time and the

algorithm that run in exponential time. Now I have to move toward the Figure to

discuss the case in more detail: