Week 10

Question 1

What is a hard computational problem?

Answer 1

• a problem that we can’t solve in polynomial time complexity
• we don’t have proof these problems can’t be solved polynomnially but no one has been able to solve this yet

Question 2

How do we formally represent a computationally hard problem?

Answer 2

NP = P or NP != P

Question 3

What are decision problems?

Answer 3

• a problem that given it’s input, the output that is the answer to this problem is not a solution but an answer of yes or not
• for example, does this property hold?

Question 4

What is a Hamiltonian Cycle problem?

Answer 4

we check if a graph has a cycle, where that cycle goes through every vertex in the graph but only once

Question 5

What are the two types of problems?

Answer 5

• Decision problems: where the output is yes or no to some property
• Optimisation problems: where the answer is the optimal to some property, so either the maximum or minimum of something

Question 6

What is the complexity class P?

Answer 6

The set of decision problems that can be solved at worse case in polynomial time

Question 7

What is efficient certification?

Answer 7

• say we have an answer of yes for solving the NP-hard problem in polynomial time then we can check that this answer is optimal/correct against the problem criteria and if it is we say that this subset/answer is a certificate for the decision problem
• an efficient certification is used to define the class of problems called NP

Question 8

What is a boolean circuit?

Answer 8

A directed graph where each node is called a logic gate and corresponds to a simple boolean function either AND, OR, NOT
- the incoming edges for a logic gate correspond to inputs for its boolean function and the outgoing edge corresponds to inputs for its boolean function and the outgoing edge corresponds to its output

Question 9

What is Circuit-SAT?

Answer 9

• Given a boolean circuit with a single output node, is there an assignment of values to the inputs so that the output value is 1
• this problem in the NP class

Question 10

What is the class co-NP?

Answer 10

The set of problems NP consists of those that have efficient verification methods for when the answer to a decision problem is yes
- the set co-NP is the set of decision problems where we have a certification of polynomial time but the answer is no

Question 11

What does P ⊆ NP ∩ co-NP mean?

Answer 11

It defines polynomials as belonging to the intersection of NP and co-NP problems

Question 12

How do we define a problem as NP-Hard?

Answer 12

We say a decision problem is NP-hard if every other problem L in NP is polynomial time reducible to M
- the problem M is so hard that if I can solve problem M efficiently in polynomial time then I can solve every problem from the NP class in polynomial time due to polynomial time reduction.

Question 13

What is NP-completeness?

Answer 13

• if a problem M is NP-hard and it belongs to the NP class iteself then M is also NP-complete
• NP-complete problems are some of the hardest problems in the NP class

Question 14

Give an example of an NP-hard and NP-complete problem?

Answer 14

Circuit-SAT problem

Question 15

What is true if L1 -> poly L2 and L2 -> poly L3?

Answer 15

• Transitivity is allowed meaning
• L1 -> poly L3

Question 16

How do we show if a problem is NP-complete?

Answer 16

• we show it belongs to the class NP by finding an efficient certifier for it
• we take another known NP-complete problem and demonstrate a polynomial time reduction from it to our problem and if that problem reduces to our problem then by transitivity, all other NP problems are polynomial time reducible to our problem

Question 17

What is Conjunctive Normal Form (CNF)?

Answer 17

• formed of a collection of clauses combined using the operator AND ∧ combined with using the operator OR ∨
• the line above means NOT

Question 18

What is CNF-SAT?

Answer 18

is there an assignment of boolean values to its variables so that formula evaluates to 1

Question 19

What is 3-SAT?

Answer 19

where in each clause of the statement there are 3 literals

Question 20

What is integer programming?

Answer 20

• a collection of inequalities with an objective function

Question 21

What is subset sum?

Answer 21

• Is there a non-empty subset T belongs to S such that the sum of elements in T = 0

Question 22

What is the partition problem?

Answer 22

• related to the subset sum problem. This problem is where given a set of positive integers, does there exist a partition of this set into two sets, such that the sum elements in s1 = sum of elements in two

Question 23

what are all examples of NP-complete problems?

Answer 23

• Circuit-SAT
• Subset Sum
• Partition problem
• Integer programming
• CNF-SAT
• 3-SAT
• 3-COL
• K-COL (if k >=3)

Question 24

What is the 3-COL graph problem?

Answer 24

• is G 3-colourable? is there an assignment of labels 1-3 of the vertices in G, so that any two vertices that are adjacent are assigned different labels?