Scribd
Upload
63 views

Algorithm Complexity: Edson Ariel Ticona Zegarra December 17, 2014

This document discusses the complexity of various algorithms. It analyzes the complexity of algorithms for verifying satisfiability of boolean formulas, including a basic algorithm that runs in polynomial time and a non-deterministic algorithm. It also analyzes the relationships between several NP-complete problems, showing that vertex cover, independent set, Hamiltonian path, Hamiltonian cycle, and the traveling salesman problem are all polynomial-time reducible to each other, meaning they are NP-complete.

Uploaded by

xcr33d3493
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
63 views

Algorithm Complexity: Edson Ariel Ticona Zegarra December 17, 2014

This document discusses the complexity of various algorithms. It analyzes the complexity of algorithms for verifying satisfiability of boolean formulas, including a basic algorithm that runs in polynomial time and a non-deterministic algorithm. It also analyzes the relationships between several NP-complete problems, showing that vertex cover, independent set, Hamiltonian path, Hamiltonian cycle, and the traveling salesman problem are all polynomial-time reducible to each other, meaning they are NP-complete.

Uploaded by

xcr33d3493
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Algorithm complexity

Edson Ariel Ticona Zegarra


December 17, 2014

1
Asumming the boolean formula in its conjunctive normal form (CNF) with n
boolean variables, like this:
F = C1 C2 ... Cn
where
Ci = xi1 + xi2 + ... + xin

function V erif y SAT (n, m)


for i = 0 to n do
Xi = 0
for j = 0 to n do
if C[i][j] == 1 then
Xi = 1
break
end if
end for
if Xi == 0 then return 0
end if
end for
return 1
end function

2
function N D V erif y SAT (n, m)
for i = 0 to n do
Xi = 0
if Escolha(xi ) == 0 then return 0
end if
end for
return 1
end function

3
For a constant time t of calls to polynomial-time routines, the total cost will be
of T = t P (n) = P (n), which results into a total polynomial-time. In such a
case that there are polynomial-time calls to polynomial-time subroutines there
might be the case that input size is 2i n for the i-th subroutine call. Then, the
n-th call will be 2n n which is not polynomial time.

4
Each set of variables in a clause of the boolean formula will represent a c-partite
set in the graph, seting and edge between all the variables between clauses but
caring not to connect a variable and its negation from another set.
Each edge represents a possible and compatible choose of variables, then to
have a valid choose of options there must be a closed figure connecting only one
variable from each set (it is needed just one because these are disjunctions),
which actually is the clique problem with size c.

5
It can be proved that V C pol HAM P AT H.

6
HAM P AT H pol HAM CY CLE
Given a hamiltonian path p = v1 , v2 , ..., vn add a new vertex with an edge to
each of the other vertices, then it will be converted to a HAM-PATH
HAM CY CLE pol HAM P AT H
Choose an arbitrary vertex v and split it into two vertex p and q. Copy all the
edges from v to p and q. Since spliting the vertex will break the cycle, a path
will be formed; then p and q are the first and last edges of the HAM-PATH.

7
It can be proved that V C pol IN DSET which will suffice to prove that INDSET is NP-complete. Let U be a vertex cover of size l. U will have connections
to all the edges in the graph. Since the IND-SET problem asks for a set of
vertices that are not connected (no endges between them), then taking the set
of vertex V U guarantees that these verteces are not connected, since all the
ones that had one side of all the edges are gone. The size of S = V U is n l.

8
HAM P AT H pol T SP In order to create an instance of TSP from HAMPATH build the graph G0 = (V, E 0 ) such that the edges in E 0 have weight 1 if
the corresponding edge exists in E or weight 0 otherwise. Then, an instance of
the traveling-salesman problem can be restated as a HAM-PATH over G.
2

You might also like