6: P and NP Reductions

Question 1

What is verification?

Answer 1

Checking that a proposed solution to a problem is correct.

Question 2

?? missing part of lecture slides

Answer 2

??

Question 3

What is a graph clique?

Answer 3

A graph is a clique of size n if it has n nodes and edges connecting each possible pairing of the n nodes.

Question 4

What is a subgraph?

Answer 4

A graph whose nodes and edges are subsets of another parent graph.

Question 5

What does DSPACE mean?

Answer 5

NSPACE is the space used by a deterministic (Turing) machine to solve a certain problem.

Question 6

What is a satisfiability problem?

Answer 6

Given a logical formula, can we assign T/F values to the variables in it such that the value of the whole formula becomes true?

Question 7

?? missing part of lecture slides

Answer 7

??

Question 8

How do you prove a problem is in P?

Answer 8

Provide a proof that it is deterministically solvable within polynomial time - usually just an algorithm to do so.

Question 9

What does P = NP boil down to?

Answer 9

If there are problems that are solvable in polynomial time nondeterministically (and sometimes verifiable in polynomial time deterministically) that cannot be solved within polynomial time deterministically.

Question 10

What are reductions? What are reductions aka?

Answer 10

Using an algorithm for one problem as a subroutine to solve another problem, especially if done to improve the time complexity of doing so, often aiming to reduce it to polynomial time. Reductions are aka transformations.

Question 11

What is Cook’s Theorem?

Answer 11

The Cook–Levin theorem states that SAT (the Boolean Satisfiability problem) is NP-complete.
NP-completeness means that any other problem in NP can be reduced to it, so allows easier proving that other problems are in NP.

Question 12

What are 3-SAT problems?

Answer 12

SAT Problems are satisfiability problems given in CNF format. 3-SAT problems are further restricted SAT problems such that clauses may hold no more than 3 literals. You can also define k-SAT for any such maximum number of k literals per clause.

Question 13

What are Directed Graph Reachability problems?

Answer 13

Finding if there is a path along edges between given end nodes on a given graph.

Question 14

What are polynomial Karp reductions?

Answer 14

Karp reductions change a problem into an instance of another one within polynomial time.

Question 15

Under how many colours are graph-colouring problems “difficult”?

Answer 15

Any planar graph can be coloured with 4 colours, and finding whether any planar graph can be coloured with 2 colours is polynomial.
Finding whether a planar graph is colourable with 3 colours is NP-complete.

Question 16

How do you transform from undirected Hamiltonian Circuit (UHC) problems into directed Hamiltonian Circuit (DHC) problems?

Answer 16

Given an undirected graph, replace every edge (v,w) with 2 new edges: (v, w) and (w, v). The resulting directed graph will have a Hamiltonian Circuit if and only if the original undirected graph did.

Question 17

How do you prove a problem is in NP?

Answer 17

Provide a proof that it is nondeterministically solvable within polynomial time - a certificate to get precomputed output that must, in turn, be checkable within polynomial time.

Question 18

How do you prove a problem is in NP-complete?

Answer 18

Prove that the problem is in NP, and then that any problem in NP can be reduced/transformed to it (in practice only need to show 1 problem can be transformed into it since, in turn, all others must be able to transform into that 1 problem).

Question 19

How do you prove a problem is in NP-hard?

Answer 19

Show a problem is in both NP and NP-complete.

Question 20

What does the Cook-Levin theorem state? What is its significance?

Answer 20

SAT is NP-complete. SAT was the first problem proven to be NP-complete, and seeing if it can be reduced to other problems the allowed for easy checking if other problems are also NP-complete.

Question 21

What is the proof for the Cook-Levin theorem?

Answer 21

Roughly:
Guess a random assignment to variables and then check each clause is true. In other words, a linear-time nondeterministic algorithm.
Alternatively, a linear-length certificate (assignment).

Question 22

What does NSPACE mean?

Answer 22

NSPACE is the space used by a nondeterministic (Turing) machine to solve a certain problem.

Question 23

?? missing part of lecture slides

Answer 23

??

Question 24

?? missing part of lecture slides

Answer 24

??

Question 25

What does Savitch’s theorem state?

Answer 25

NSPACE is a subset of (less than or equal to) DSPACE: if an NTM can decide a problem in f(n) space, a DTM can in [f(n)]^2 space: the same amount squared. The speedup given is, therefore, much less than exponential.

Question 26

?? missing part of lecture slides

Answer 26

??

Question 27

What are graph-colouring problems? How are they notated?

Answer 27

Finding whether a colour can be assigned to each node in a graph such that two adjacent nodes (attached with an edge) are never the same colour, for a given graph and number of unique colours.

Question 28

How do you transform from 3-SAT to k-COL problems?

Answer 28

Create n x nodes, n ¬x nodes, n y nodes, and k C nodes, where n = the number of variables in the 3-SAT problem and k = the number of clauses in the 3-SAT problem.
Each xi node is connected to each ¬xi; each y node is connected to every other y node; each node yi is connected to each xj and ¬xj for all j != i; each Ci node is connected to each x or ¬x literal not in the equivalent ith clause in the input 3-SAT problem. The number of colours in the resultant k-COL problem is the number of variables in the input 3-SAT problem 1.

Question 29

How do you transform from SAT to clique problems?

Answer 29

Add a vertex for each literal in each clause. Connect all vertices to all others in the resulting graph, except for those in the same clause or of the same value (whether or not one or both are negated) as the original SAT literal the vertex represents.

Question 30

What is a vertex cover problem?

Answer 30

To find minimum size vertex cover, given an undirected graph. A vertex cover of an undirected graph is a subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in the vertex cover.

Question 31

How do you transform from clique to vertex cover problems?

Answer 31

Convert the graph in the clique problem to have the same vertices but edges only where the original graph does not. The clique area on the new graph will be a vertex cover, and vice versa for the opposite transformation. The original graph will have a clique size of at least k if and only if the altered graph has a vertex cover of the size ≤ the number of vertices - k, where k = the minimum size of the clique.

Question 32

What is a Hamiltonian Circuit?

Answer 32

A route which visits every vertex once, without using an edge more than once, and returns to its starting point.

Question 33

What are Hamiltonian Circuit problems?

Answer 33

Finding whether a given graph contains a Hamiltonian circuit.

Question 34

What is an undirected graph?

Answer 34

All edges are bidirectional: you can go either way along them. When directed you may only move along edges in 1 direction.

Question 35

How do you transform from vertex cover to undirected Hamiltonian Circuit problems?

Answer 35

Put all the edges at vertex v in G into order, say (v, w1), …, (v, wd).
• In GH, link each ai to vw1,1, vw1,6 to vw2,1, and so on, and vwd,6 is linked to all the ai.
• Now, a Hamiltonian circuit of GH must go through all the ai, and so we can split it up into k pieces.
• Each piece must start at ai, then to some vw1,1 and end at vwd,6. We call v (a vertex in G) the key vertex of that piece.
• The piece will visit all the vwi on the way. It may also visit some of the wvi (provided v,w is an edge).
• Now, since every vertex of GH is visited, every edge e of G must be connected to one of the key vertices, which therefore form a vertex cover.

Question 36

What is the proof for Savitch’s theorem?

Answer 36

??

Question 37

?? missing part of lecture slides

Answer 37

??

Question 38

?? missing part of lecture slides

Answer 38

??

Question 39

?? missing part of lecture slides

Answer 39

??

Question 40

?? missing part of lecture slides

Answer 40

??

Question 41

What is a graph clique? What is a clique problem?

Answer 41

A clique is a subset of a graph that is fully connected, i.e. all distinct pairs of nodes in it are adjacent. A clique problem is finding whether a clique of a set size exists in a given graph.