Theory of given numbers {?10, ?3, ?2, 5, 9}.

Theory
of Computation

ASSIGNMENT
N0 3

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

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={: G has a Hamiltonian path}

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 this will simply check
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:         

 

x

Hi!
I'm Dianna!

Would you like to get a custom essay? How about receiving a customized one?

Check it out