Time complexity Flashcards
how to 3-Sat <=p VERTEX-COVER
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 Φ
how to 3-Sat <= hamiltonian path
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
what time complexity
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
when can we define f(n) = g(n)
when lim∞ f(n)/g(n) = 0
explain: every t(n) time MTTM has an equivalent O(t(n)^2) STuring STTM
this can be proved by studying the complexity of the MLTTM using STTM
Explain why DTM –> NDTM is Exponential
because the size of NDTM branches is exponential 2^f(n)
what is the class P
class P concerns the problem that decidable in polynomial time
prove that PATH in P
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
prove RelPrime in P
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
what is a verifier
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
what is the class NP?
it is the class that is polynomially verifiable, remember that p ∈ NP
prove: A language is in NP if it is decided by some NDPTM
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
prove: CLIQUE in NP
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
prove subset-sum is in NP
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
what is an NP-complete problem
is the problem whose individual complexity corresponds to the complexity of the entire class Example: SAT problem
what is COOK levin theorem
SAT ϵ P if P = NP
explain w ϵ A <==> f(w) ϵ B
f is a polynomial-time reduction function from A to B
A ≤p B
prove when A ≤p B and B in P then A in p
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
literals and clause
literal is x or -x
a clause is several literals connected by ⋁
prove that 3SAT ≤p CLIQUE
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
explain when the language is np-complete
a language B is nop-complete if :
B is in NP
and every A in NP , A ≤p B
prove that SAT is np-complete
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)
3SAT <=p Subset-SUM
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}
define big-O notation
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)
what is the relationship between multi-tape Turing machine and a single tape turning machine
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
what is the relationship between a deterministic Turing machine and a n deterministic turning machine?
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
what is the class P
is the class of languages that are decided in polynomial time turning machine
when can we say that a language is in NP?
we can say that a language is in NP if it is decided by a polynomial-time deterministic turning machine
