Time complexity

Question 1

how to 3-Sat <=p VERTEX-COVER

Answer 1

we start with the reduction :
map a boolean formula Φ to graph G and value K :
top-level : variable gadget:
for each x in Φ connect it to 2 vertices
such that x in the left and x̅ in the right
bottom-level: clause gadgets :
composed of the triple vertex that represents the 3 literals of Φ, they connected with each other and connected to each similar value from the top level
K = m +2L (k nodes of vertex cover)

Φ satisfiable => | vertex cover (G) |= k
select the true node in the variable gadget, then
select one true literal in every clause and put the remaining in the vertex cover, that obviously covers the graph since the clause nodes are connected to each other and connected to variable gadget node that corresponds to them, hence G has k vertices

vertex cover (G) |= k =>Φ satisfiable
we construct the satisfying assignment that corresponds to it, it should contain one node in every variable gadget and two in every clause gadget
we assign to the gadget’s variables that are in the vertex cover the corresponding literal true, that clearly satisfies Φ

Question 2

how to 3-Sat <= hamiltonian path

Answer 2

the ham path, asks whether there exists a path between two node s and t such that it passes al the nodes of graph G :
Reduction :

variable gadget :
for a boolean formula Φ
{ x1 , x2 ..xi } : variable
{C1 , C2 , C3 …ci } : clauses

is represented like a diamond with horizontal nodes C1…Cj and variables xi ..xn on the top

Clause gadget:
is simply represented by a single node C1..Cj
we get this :
S
.
.
xi
/ \
/ \
/ \
c1 c2 …..ci Cj
. .
. .
T

for the variable gadget :
xi.ci = cj means xi.ci we link it to cj

xi = True => Zig zag  over horizontal nodes 
xj = False Zag zig over nodes 

Φ satisfiable |=> ham path from S to T
knowing that when the variable is either true or false, we can detour into the correct direction and going through the nodes once, which means the hamiltonian path is kept

ham path from S to T |=> Φ satisfiable
if the path zig-zag we assign the variable TRUE else FALSE
the path should be normal else we violate the construction such that if it is not normal it may jump from one node to another

Question 3

what time complexity

Answer 3

for M that halts on all inputs, f(n) in N–> N is the number of steps that M used for a given input of length n

Question 4

when can we define f(n) = g(n)

Answer 4

when lim∞ f(n)/g(n) = 0

Question 5

explain: every t(n) time MTTM has an equivalent O(t(n)^2) STuring STTM

Answer 5

this can be proved by studying the complexity of the MLTTM using STTM

Question 6

Explain why DTM –> NDTM is Exponential

Answer 6

because the size of NDTM branches is exponential 2^f(n)

Question 7

what is the class P

Answer 7

class P concerns the problem that decidable in polynomial time

Question 8

prove that PATH in P

Answer 8

on an input for
put a mark on s
repeat, till all nodes are marked:
scan edges, if an edge (a,b), where a is
marked and not b then mark b
if t is marked accept else reject
after analyzing the stages, PATH is polynomial time

Question 9

prove RelPrime in P

Answer 9

E= euclidean algorithm
M = on input
run E on
if the result is 1 accept else reject

E runs in polynomial time hence M too

Question 10

what is a verifier

Answer 10

a verifier for a languge A is an algorithm V such
A = { w| V accepts for a string c }
c is a certificate

for in HAMPATH we can use a path from s to t as a certificate

Question 11

what is the class NP?

Answer 11

it is the class that is polynomially verifiable, 
remember that p ∈ NP

Question 12

prove: A language is in NP if it is decided by some NDPTM

Answer 12

converting polynomial-time-verifier to equivalent NDTM :
on input w of length n
non-deterministically choose a string c of length n^k
run V on
if 0 then 0 else 1
the other direction
Simulate n on input w by relying on o the branches of ndtm

Question 13

prove: CLIQUE in NP

Answer 13

on input
non-deterministically choose a subset c of G of size k
test whether G containers all edges connecting nodes in c
if 1 then 1 else 0

Question 14

prove subset-sum is in NP

Answer 14

on input
non-deterministically choose a subset c from S
test if the numbers in c sum to t
it 1 then 1 else 0

Question 15

what is an NP-complete problem

Answer 15

is the problem whose individual complexity corresponds to the complexity of the entire class 
Example: SAT problem

Question 16

what is COOK levin theorem

Answer 16

SAT ϵ P if P = NP

Question 17

explain w ϵ A <==> f(w) ϵ B

Answer 17

f is a polynomial-time reduction function from A to B

A ≤p B

Question 18

prove when A ≤p B and B in P then A in p

Answer 18

N = on input w compute f(w)
run M on f(w) and output whatever it outputs
whenever w in A f(w) is in B because A is reducible to B

Question 19

literals and clause

Answer 19

literal is x or -x

a clause is several literals connected by ⋁

Question 20

prove that 3SAT ≤p CLIQUE

Answer 20

we construct a graph such that :
every clause is represented by a triple of nodes that corresponds to literals
we connect all nodes to each other except for nodes of the same tripe and nodes with contradictory label
phy is satisfiable ==> graph has k-clique: we choose a true node literal from each triple and knowing that nodes with contradictory label and nodes of the same triple are not connected hence we obtain a k-clique

graph has K-clique ==> phy is satisfiable, we know that is a graph has k-clique mean there is one node in each triple is connected to another triple if we denote that one node to true then we obtain a satisfiable formula

Question 21

explain when the language is np-complete

Answer 21

a language B is nop-complete if :
B is in NP
and every A in NP , A ≤p B

Question 22

prove that SAT is np-complete

Answer 22

we construct a machine a receives w and produces a phy formulas by simulating an NP machine
1- assume that N is NDTM that decides A in n^k
2- we have a tableau n^k * n^k, each row corresponds to a branch configuration of N on input w
3-we construct a formula
phy-cell ∧ phy-start ∧ phy-move∧phy-accept

phy-cell : corresponds to placing a symbol s in cell[i,j]
0<i></i>
phy-start : forces the first row to contained exectly the initial configuration
phy-accept : the accepting configuration
phy-move represents an infinite number of legal windows, a window is legal is it doesn’t violate the move configuration

all the formulas are of polynomial-size, also considering that each subformula in CNF form except for move formula(this can be tackled by the distribution low)

Question 23

3SAT <=p Subset-SUM

Answer 23

we’ll have a table such that :
x1,x2 …xl . {c1,c2, …ck}
the first row composed : LEft: 1 …l Right: c1…k
each X is composed of yi, zi
row yi ==> cj= 1 if Xi in Cj
row zi ==>cj =1 if -Xi in Cj
bottom row : there are pair (gi,hi) where gi = hi , and contains only 0 but 1 that is associated to correct clause
if Φ is statisfiable, we construct Y such that
if(yi)=1 add it to yi else add zi
complete the construction such that :
if one literal is true add gi,yi
if two literals are true add either of them
if three are true add none
if we supposed that Yi exist :

if we assume that Y exists:
digits in S are 0 || 1
so F(xi) = 0 if yi in Y else 1 in zi in Y
knowing that the clause should contains at least three values, one of them should at least evaluate to true, and the rows in the lower lever can generate values {0,1,2}

Question 24

define big-O notation

Answer 24

it can be defined by function such that

for n and c in N then there exist a function such that f(n)<=cg(n)

Question 25

what is the relationship between multi-tape Turing machine and a single tape turning machine

Answer 25

Theorem. Let t(n) be a function, where t(n)≥n. Then every t(n) time nondeterministic
single-tape Turing machine has an equivalent 2^O(t(n)) time deterministic single-tape Turing
machine.
this can be proved by simulating the turning machine on each branch

Question 26

what is the relationship between a deterministic Turing machine and a n deterministic turning machine?

Answer 26

Theorem. Let t(n) be a function, where t(n)≥n. Then every t(n) time nondeterministic
single-tape Turing machine has an equivalent 2^O(t(n)) time deterministic single-tape Turing
machine.
this can be proved by simulating the turning machine on each branch of the NDTM

Question 27

what is the class P

Answer 27

is the class of languages that are decided in polynomial time turning machine

Question 28

when can we say that a language is in NP?

Answer 28

we can say that a language is in NP if it is decided by a polynomial-time deterministic turning machine