L22-23 (Simplex Example, Search Problems, P and NP)

Question 1

Describe the complexity classes of:
- P problems
- NP problems

Is one of them a subset of the other?

Answer 1

• P is the class of decision problems (problems with a yes or no answer) that can be solved by a deterministic Turing machine in polynomial time.

In other words, P is the class of all search problems that can be solved in polynomial time

• NP is the class of decision problems for which a proposed solution can be verified as correct or incorrect by a deterministic Turing machine in polynomial time.

In other words, NP is the class of all well-defined search problems

• P is a subset of NP, as problems solvable in polynomial time can also be verified in polynomial time. The open question is whether P equals NP or not.

Question 2

A problem is NP-complete if it satisfies two conditions. What are they?

Answer 2

1. It is in NP, meaning a proposed solution can be verified as correct or incorrect in polynomial time.
2. Any problem in NP can be reduced to it in polynomial time, meaning it is at least as hard as the hardest problems in NP.

Question 3

Under what case does P = NP?

Answer 3

If a problem takes polynomial time to be verified on a non-deterministic TM (problem is in NP) implies that one can build a deterministic TM which would solve the same problem also in polynomial time (problem is in P).

Question 4

What does it mean for a problem to be NP-hard?

Answer 4

A problem is NP-hard if it is at least as hard as the hardest problems in NP.

It’s essential to note that NP-hard problems are not necessarily in NP themselves and may not have a polynomial-time verification algorithm.

Question 5

What is a polynomial-time reduction?

Answer 5

A polynomial-time reduction is a transformation of one problem (A) into another problem (B) such that the transformation and its inverse both take polynomial time.

If problem A can be reduced to problem B in polynomial time, it implies that any solution for problem B can be used to solve problem A in polynomial time. Polynomial-time reductions are crucial in proving NP-completeness.

Question 6

What’s the definition of a Search Problem?

What is the Decision Problem?

Answer 6

Search Problem: Given a problem instance “I”, find a solution “S” or determine that no such solution exists

Decision Problem: Given a solution “S”, verify that it is a valid solution to “I”

Question 7

What does it mean for a search problem to be “Well-defined”?

Answer 7

Two things:

1. S has a length (size) that is bounded by a polynomial relative to the input size n
2. There is a polynomial-time algorithm that takes as input “I” and “S” and can verify whether or not “S” is a solution to “I”

Question 8

What is the traveling salesman problem? (TSP)

Answer 8

Given an undirected graph G = (V,E) along with edge lengths l,

find a tour (a cycle that visits each vertex) in G exactly once and that has the minimum length

Question 8

What is the traveling salesman problem? (TSP)

Answer 8

Given an undirected graph G = (V,E) along with edge lengths l,

find a tour (a cycle that visits each vertex) in G exactly once and that has the minimum length

Question 9

With TSP, there is a “optimization” problem variant and a “search” problem variant. What are they?

Answer 9

Optimization problem variant:
Find an optimized tour in G that visits each vertex exactly once and minimizes the length

Search problem variant:
Given a budget b > 0, find a tour that visits each vertex exactly once and has length <= b, or determine that no such tour exists

Question 10

How does one prove that problem X is in NP-Complete?

Answer 10

1. Show that X is in NP by demonstrating a polynomial-time verification algorithm for proposed solutions.
2. Choose a known NP-complete problem Y.
3. Demonstrate a polynomial-time reduction from problem Y to problem X, meaning any instance of problem Y can be transformed into an equivalent instance of problem X in polynomial time.

Question 11

What’s the Hamiltonian cycle problem?

What category of NP completeness does it fall under?

Answer 11

Given an undirected graph (not necessarily complete), find a tour that visits each vertex exactly once - or determine that no such tour exists

This problem is NP-complete (no known polynomial-time algorithm can solve it)

Question 12

What is a reduction?

Answer 12

A reduction is a transformation of one problem (A) into another problem (B) in such a way that a solution for problem B can be used to solve problem A.

Using reductions we can show that two problems are exactly the same, just stated in different ways - and can group together problems in NP

Question 13

How would you define a reduction as a polynomial-time algorithm?

Answer 13

1. A polynomial-time algorithm f that transforms any instance i of A into instance f(i) of B
2. A polynomial-time algorithm h that maps any solution S of f(i) back into a solution h(S) of i

Question 14

What are Hamiltonian cycle path reductions?

What is an example?

Answer 14

• Hamiltonian cycle path reductions are transformations of other problems into the Hamiltonian cycle problem.
• These reductions are instrumental in proving the NP-completeness of other problems.
• If a problem can be reduced to the Hamiltonian cycle problem in polynomial time, it is at least as hard as the Hamiltonian cycle problem.
• An example of a problem that’s reducible to the Hamiltonian cycle problem is the traveling salesman problem

Question 15

What is a Tree of Reductions?

What is it used for?

Answer 15

A tree of reductions is a hierarchical representation of the relationships between problems based on reductions. The root of the tree represents a known NP-complete or NP-hard problem, such as the Boolean satisfiability problem (SAT).

• The children of a node in the tree are problems that can be reduced to the problem represented by the parent node.
• The tree of reductions helps visualize the connections between problems and is a useful tool for understanding the relative hardness or complexity of problems in computational complexity theory.

Question 16

Given an undirected graph, what’s the difference between a hamiltonian cycle and a hamiltonian path?

Can a reduction be made?

Answer 16

Hamiltonian Cycle: Is there a cycle that passes through each vertex exactly once?

Hamiltonian Path: Given vertices ‘s’ and ‘t’, is there a path from ‘s’ to ‘t’ that passes through each vertex exactly once?

A reduction can be made from HP to HC or also from HC to HP

Question 17

In terms of NP-Completeness, what category do the following problems fall into:
1. SAT (Boolean Satisfiability Problem)
2. 3SAT (3-CNF Satisfiability Problem)
3. 2SAT (2-CNF Satisfiability Problem)
4. Hamiltonian cycle
5. Hamiltonian path
6. Traveling salesman problem

Answer 17

1. NP-Complete
2. NP-Complete
3. P
4. NP-Complete
5. NP-Complete
6. NP-Hard

Question 18

What are the overlaps between P, NP, NP-Complete and NP-Hard subsets?

Answer 18

.

NP-Hard

Question 19

What is the fundamental difference between P, NP, NP-Complete and NP-Hard problems?

Answer 19

P
P is a complexity class that represents the set of all decision problems that can be solved in polynomial time.

NP
NP is a complexity class that represents the set of all decision problems for which the solution instances can be verified in polynomial time.

NP-Complete
NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP-Complete problem Y to X in polynomial time.

NP-Hard
Intuitively, these are the problems that are at least as hard as the NP-complete problems (or harder). Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.