Description

a) 2 = ()
• True: As () = , any input , a constant can always be found such that 0 ≤ 2 ≤ . For example, consider = 2 and 0 = 1,
() ≤ (())
2 ≤ 2()
2(1) ≤ 2(1)
2 ≤ 2 for all ≥ 1
b) 2 = ()
• False: Since 2 grows faster than , 2 dominates the growth of () = 2. Therefore, 2 cannot be bounded by (), making 2 = () false.
c) 3 = 2()
• True: According to the book, when the symbol occurs in an exponent, as in the expression () = 2(), the exponent dominates the expression, thus representing an upper bound of 2. This means that 2 is an upper bound for 3, and ≥ 0 there are 3 <= 2cn. Hence, it can be conclude that 3 = 2().
Problem 2: (15 points) Answer each part TRUE or FALSE (Small ).
a) = (2)
• False: grows at the same rate as 2, which means that as approaches infinity, the ratio

remains constant when the small definition requires that as approaches infinity, the
2
ratio () approaches zero. This would indicate that () = () when the definition
()
requires () < () for any real number > 0, there exists a real number 0 for all > 0. However, this can be violated with = for any value of .
b) 2 = (2)
• True: 2 grows slower than 2, which means that as approaches infinity, the ratio ratio 22 approaches zero, which satisfies the small definition.

c) = ( ) • False: grows slower than , which means that as approaches infinity, the ratio log () approaches infinity, not zero as required by the small definition.
Problem 3: (10 points) Is the following pair of numbers relatively prime? Show the calculations that led to your conclusion.
a) 1274 and 10505
• Yes, this pair of values are relatively prime. Since Two numbers are relatively prime if 1 is the largest integer that evenly divides them both. We can calculate this using the Euclidean algorithm to find gcd(1274,10505). Our Process is as follows:
1) Using Division Algorithm, find q and r to write a=bq+r
2) Do step 1 again, but now use as your new , and use as your new 3) Stop when your = 0. Your from the last step is your final answer.
• Proof:
Step 1: Using Division Algorithm, find q and r to write a = bq + r
▪ = +
▪ 1274 = 10505 +
▪ 1274 = 10505(0) + 1274
Step 2: Do step 1 again, but now use as your new , and use as your new
▪ = +
▪ 10505 = 1274 +
▪ 10505 = 1274(8) + 313
Step 3: Do step 1 again, but now use as your new , and use as your new
▪ = +
▪ 1274 = 313 +
▪ 1274 = 313(4) + 22
Step 4: Do step 1 again, but now use as your new , and use as your new
▪ = +
▪ 313 = 22 +
▪ 313 = 22(14) + 5
Step 5: Do step 1 again, but now use as your new , and use as your new
▪ = +
▪ 14 = 5 +
▪ 14 = 5(2) + 4
Step 6: Do step 1 again, but now use as your new , and use as your new
▪ = + ▪ 5 = 4 +
▪ 5 = 4(1) + 1
Step 7: Do step 1 again, but now use as your new , and use as your new
▪ = + ▪ 4 = 1 +
▪ 4 = 1(4) + 0
Step 8: Stop when your = 0. Your from the last step is your final answer.
▪ gcd(1274,10505) = 1
❖ By definition, two numbers are relatively prime if 1 is the largest integer that evenly divides them both. Thus, in order to prove that 1274 and 10505 are relatively prime, I calculated their greatest common divisor (gcd) using the Euclidean algorithm, and obtained gcd(1274,10505) = 1. As such, I have successfully prove that 1274 and 10505 have no common divisors other than 1, and therefore they are relatively prime.
Problem 4: (10 points) Is the following formula satisfiable? Why?
(⋁)⋀(⋁̅)⋀(̅⋁)⋀(̅⋁̅)
First, lets review the Boolean truth values
∧ and
conjunction (intersection) ∨ or
disjunction (union)
0 ∧ 0 0 0 ∨ 0 0
0 ∧ 1 0 0 ∨ 1 1
1 ∧ 0 0 1 ∨ 0 1
1 ∧ 1 1 1 ∨ 1 1
¬
not negation (complement)
¬0 1
¬1 0
According to our textbook, a Boolean formula is satisfiable if some assignment of 0s and 1s to the variables makes the formula evaluate to 1.
Therefore, to test the satisfiability of this equation, we can try different combinations of 0 and 1 to check if any of them evaluate to the value of 1. There are two possible scenarios to consider: = 1 and = 0, or = 0 and = 1. It is not necessary to test the scenarios where and have the same value since they are represented by the same symbol.
• Scenario 1: =1 and =0
(⋁)⋀(⋁̅)⋀(̅⋁)⋀(̅⋁̅)
(1⋁0)⋀(1⋁0̅)⋀(1̅⋁0)⋀(1̅⋁0̅)
(1⋁0)⋀(1⋁1)⋀(0⋁0)⋀(0⋁1)
(1)⋀(1)⋀(0)⋀(1)
(1)⋀(0)⋀(1)
(0)⋀(1)
(0)
Scenario 1 evalutates to 0 and, as such, we know that = 1 and = 0 can not be the correct values to prove this formulas satisfiability.
• Scenario 2: =0 and =1
(⋁)⋀(⋁̅)⋀(̅⋁)⋀(̅⋁̅)
(0⋁1)⋀(0⋁1̅)⋀(0̅⋁1)⋀(0̅⋁1̅)
(0⋁1)⋀(0⋁0)⋀(1⋁1)⋀(1⋁0)
(1)⋀(0)⋀(1)⋀(1)
(0)⋀(1)⋀(1)
(0)⋀(1)
(0)
After testing Scenario 2, I have shown that it also evaluates to 0. Therefore, none of the possible assignments of 0s and 1s to the variables can make the formula evaluate to 1. This proves that the Boolean equation (⋁)⋀(⋁̅)⋀(̅⋁)⋀(̅⋁̅) is not satisfiable.
Problem 5: (10 points) What is P-Problem? What is NP-Problem? What is NP-Complete problem?

A P-Problem is a problem that is efficiently decidable in polynomial, such as , time on a deterministic single-tape Turing machine. These problems are considered “tractable” and the class of problems that are realistically solvable can computed using the function:
= ⋃ ()

“union of all polynomial time functions”
NP-Complete refers to a class of problems whose “individual complexity is related to that of the entire class.” In other words, if an efficient, polynomial time algorithm exists for solving a problem within the class, then an efficient algorithm exists for solving all problems in NP. An example of an NP-Complete problem includes the Boolean satisfiability problem.
Problem 6: (20 points) Show that NP is closed under union
(Hint: For any two languages L1 and L2, let M1 and M2 be the NTM that decides them in polynomial time.
Construct a NTM M’ that decided L1UL2 in polynomial time.)
To show that NP is closed under union, I need to prove that for any two languages 1and 2 in NP, their union 1 ∪ 2 is also in NP. To do this, I will begin by constructing a non-deterministic Turing machine (NTM) ′ that decides 1 ∪ 2 in polynomial time. This process is shown below:
o ′ non-deterministically guesses whether an input string, , belongs to 1 or 2 o Instead of following a set of predefined steps, the ′ select one of the languages and verify whether the guess is correct or not.
o if belongs to 1, ′ simulates the NTM 1: if 1 accepts : then ′ accepts else ′ rejects .
o else if belongs to 2, ′ simulates the NTM 2: if 2 accepts : then ′ accepts else ′ rejects .
o else is not in either 1 or 2, ′ rejects .
Since 1 and 2 decide their languages in NP, and the non-deterministic guess of or can be made in NP, I can conclude that ′ also runs in NP. This process shows that ′ decides since it accepts a string iff either 1 or 2 accepts . Since this implies that is in NP, I have shown that NP is closed under union.
Problem 7: (10 points) Prove that 3SAT is polynomial reducible to CLIQUE.

To prove that 3SAT is polynomial reducible to CLIQUE, I can utilize the polynomial time reduction to construct a graph that has a -clique iff the 3SAT formula is a satisfiable 3cnf-formula; Let be a formula with clauses such as:

Assuming that is satisfiable, we can form a -clique in by selecting one node from each triple that corresponds to literal in a clause of . Each triple of nodes in the graph corresponds to a clause in the
formula. For example, if the 3SAT formula contains the clauses and , then there would be two corresponding groups of triple nodes in the graph: and ¬ ,
The edges of connect nodes that do not belong to the same triple, such that would not connect to , and do not have contradictory labels, such that 1 would not connect to a node ¬ . By selecting one node from each triple, one true literal from each clause is selected, which results in a satisfying assignment for .
Furthermore, if has a -clique, then each triple must contain exactly one node from the -clique. Since each node corresponds to a literal in , we can assign truth values to the literals in by setting each one corresponding to a node in the -clique to true. Therefore, each clause contains a literal that is assigned True, and we have a satisfying assignment for .