LN8 Closest points

Question 1

What is a problem reduction in the context of algorithms?

Answer 1

A reduction involves transforming a problem X into another problem Y, allowing an algorithm designed for Y to solve instances of X.

Question 2

Give an example of a reduction between two problems.

Answer 2

To multiply two integers a and b, we can reduce this to the problem of squaring by using the formula ab = ((a + b)² - (a - b)²) / 4, utilizing a squaring algorithm.

Question 3

What are the two main purposes of reductions in algorithms?

Answer 3

1) To solve problem X using an algorithm for a different problem Y, and 2) to show that one problem Y is at least as hard as another problem X.

Question 4

Define polynomial-time reducibility.

Answer 4

Problem X is polynomial-time reducible to problem Y if we can transform instances of X to Y in polynomial time, ensuring that Y’s solution can be translated back to a solution for X.

Question 5

What is a decision problem in computational complexity?

Answer 5

A decision problem is a problem with a yes/no answer, such as determining if a graph contains a clique of size k.

Question 6

How is the Clique problem formally defined?

Answer 6

Given an undirected graph G, the Clique problem asks whether there exists a subset of nodes K where every two nodes are connected by an edge, with K containing at least k nodes.

Question 7

Describe the Independent Set problem in graph theory.

Answer 7

Given a graph G, the Independent Set problem seeks the largest subset of nodes such that no two nodes in this subset share an edge.

Question 8

What is the relationship between the Clique and Independent Set problems?

Answer 8

Clique and Independent Set are complementary: finding a k-clique in a graph G is equivalent to finding an independent set of size k in the complement graph of G.

Question 9

Explain the concept of a Vertex Cover in a graph.

Answer 9

A vertex cover in a graph is a subset of vertices such that each edge in the graph is connected to at least one vertex in this subset.

Question 10

How can Independent Set and Vertex Cover be reduced to each other?

Answer 10

For any graph G, a subset C is a vertex cover if and only if the complement set V \ C is an independent set, allowing a reduction by setting the threshold accordingly.

Question 11

What is the complexity class P

Answer 11

P is the class of decision problems that can be solved in polynomial time, meaning there exists an algorithm that can solve the problem in O(p(n)) time, where p is a polynomial.

Question 12

Define the complexity class NP.

Answer 12

NP is the class of decision problems for which a given solution can be verified in polynomial time, assuming an “advice” (like a solution) is provided.

Question 13

What does NP-completeness signify for a problem?

Answer 13

An NP-complete problem is one of the hardest problems in NP; if any NP-complete problem is solved in polynomial time, all problems in NP can be solved in polynomial time.

Question 14

What would it imply if P = NP?

Answer 14

If P = NP, every problem that can be verified quickly (NP) can also be solved quickly (P), which would mean polynomial-time algorithms exist for all NP problems.

Question 15

Explain the transitivity of polynomial-time reducibility.

Answer 15

If problem X reduces to problem Y in polynomial time and Y reduces to problem Z in polynomial time, then X reduces to Z in polynomial time.

Question 16

Describe the SAT (Satisfiability) problem in computational complexity.

Answer 16

SAT asks whether a Boolean formula, made up of literals connected by logical operators, has an assignment of truth values that makes the formula true.

Question 17

How is SAT related to NP-completeness?

Answer 17

SAT was the first problem proven to be NP-complete, and it serves as a basis for showing the NP-completeness of other problems via reductions.

Question 18

What does a CNF (Conjunctive Normal Form) in SAT look like?

Answer 18

In CNF, a Boolean formula is represented as a conjunction of clauses, where each clause is a disjunction of literals.

Question 19

How can we use reductions to show problem hardness?

Answer 19

By showing that a known hard problem (like an NP-complete problem) can be reduced to another problem in polynomial time, we infer the latter problem’s hardness.

Question 20

Why are reductions important in comparing problem difficulty?

Answer 20

Reductions allow us to determine if one problem is at least as difficult as another, guiding where to focus efforts for finding efficient algorithms.

Question 21

What is Interval Scheduling, and how is it related to Independent Set?

Answer 21

Interval Scheduling, which seeks a set of non-overlapping intervals, is a special case of Independent Set when intervals are converted to an interval graph.

Question 22

Why can’t all problems be reduced to Interval Scheduling?

Answer 22

Many graphs cannot be represented as interval graphs, meaning not every independent set problem can be reduced to Interval Scheduling.