LN8 Closest points Flashcards
What is a problem reduction in the context of algorithms?
A reduction involves transforming a problem X into another problem Y, allowing an algorithm designed for Y to solve instances of X.
Give an example of a reduction between two problems.
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.
What are the two main purposes of reductions in algorithms?
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.
Define polynomial-time reducibility.
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.
What is a decision problem in computational complexity?
A decision problem is a problem with a yes/no answer, such as determining if a graph contains a clique of size k.
How is the Clique problem formally defined?
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.
Describe the Independent Set problem in graph theory.
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.
What is the relationship between the Clique and Independent Set problems?
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.
Explain the concept of a Vertex Cover in a graph.
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.
How can Independent Set and Vertex Cover be reduced to each other?
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.
What is the complexity class P
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.
Define the complexity class NP.
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.
What does NP-completeness signify for a problem?
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.
What would it imply if P = NP?
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.
Explain the transitivity of polynomial-time reducibility.
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.
Describe the SAT (Satisfiability) problem in computational complexity.
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.
How is SAT related to NP-completeness?
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.
What does a CNF (Conjunctive Normal Form) in SAT look like?
In CNF, a Boolean formula is represented as a conjunction of clauses, where each clause is a disjunction of literals.
How can we use reductions to show problem hardness?
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.
Why are reductions important in comparing problem difficulty?
Reductions allow us to determine if one problem is at least as difficult as another, guiding where to focus efforts for finding efficient algorithms.
What is Interval Scheduling, and how is it related to Independent Set?
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.
Why can’t all problems be reduced to Interval Scheduling?
Many graphs cannot be represented as interval graphs, meaning not every independent set problem can be reduced to Interval Scheduling.
