What is a hard computational problem?
- 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
How do we formally represent a computationally hard problem?
NP = P or NP != P
What are decision problems?
- 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?
What is a Hamiltonian Cycle problem?
we check if a graph has a cycle, where that cycle goes through every vertex in the graph but only once
What are the two types of problems?
- 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
What is the complexity class P?
The set of decision problems that can be solved at worse case in polynomial time
What is efficient certification?
- 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
What is a boolean circuit?
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
What is Circuit-SAT?
- 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
What is the class co-NP?
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
What does P ⊆ NP ∩ co-NP mean?
It defines polynomials as belonging to the intersection of NP and co-NP problems
How do we define a problem as NP-Hard?
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.
What is NP-completeness?
- 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
Give an example of an NP-hard and NP-complete problem?
Circuit-SAT problem
What is true if L1 -> poly L2 and L2 -> poly L3?
- Transitivity is allowed meaning
- L1 -> poly L3
How do we show if a problem is NP-complete?
- 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
What is Conjunctive Normal Form (CNF)?
- formed of a collection of clauses combined using the operator AND ∧ combined with using the operator OR ∨
- the line above means NOT
What is CNF-SAT?
is there an assignment of boolean values to its variables so that formula evaluates to 1
What is 3-SAT?
where in each clause of the statement there are 3 literals
What is integer programming?
- a collection of inequalities with an objective function
What is subset sum?
- Is there a non-empty subset T belongs to S such that the sum of elements in T = 0
What is the partition problem?
- 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
what are all examples of NP-complete problems?
- Circuit-SAT
- Subset Sum
- Partition problem
- Integer programming
- CNF-SAT
- 3-SAT
- 3-COL
- K-COL (if k >=3)
What is the 3-COL graph problem?
- 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?
