Podcast
Questions and Answers
In the context of reductions, what does it mean for a problem A to be reducible to problem B ($A \leq^P B$)?
In the context of reductions, what does it mean for a problem A to be reducible to problem B ($A \leq^P B$)?
- Problem A can be solved in polynomial time if and only if problem B can be solved in exponential time.
- There exists an algorithm that transforms instances of B into instances of A in polynomial time.
- There exists an algorithm that transforms instances of A into instances of B in polynomial time. (correct)
- Problem B is inherently easier to solve than problem A.
What is a key characteristic of NP-hard problems?
What is a key characteristic of NP-hard problems?
- If any NP-hard problem can be solved in polynomial time, then P = NP. (correct)
- They are easier than problems in P.
- They are a subset of P problems.
- They can be solved in polynomial time.
Given a Conjunctive Normal Form (CNF) formula, what is a 3-clause?
Given a Conjunctive Normal Form (CNF) formula, what is a 3-clause?
- A clause with exactly 3 literals. (correct)
- A clause with any number of literals.
- A clause with at most 3 literals.
- A clause with exactly 2 literals.
What does it mean for a 3SAT problem to be NP-hard?
What does it mean for a 3SAT problem to be NP-hard?
In the reduction of CircuitSAT to 3SAT, what is the purpose of transforming a circuit into a 3-CNF Boolean formula?
In the reduction of CircuitSAT to 3SAT, what is the purpose of transforming a circuit into a 3-CNF Boolean formula?
What does it imply if 3SAT has a polynomial-time algorithm?
What does it imply if 3SAT has a polynomial-time algorithm?
In the context of graph theory, what defines an independent set S in a graph G = (V, E)?
In the context of graph theory, what defines an independent set S in a graph G = (V, E)?
What is the MAX-INDSET problem?
What is the MAX-INDSET problem?
Given a 3SAT formula φ, what is the strategy for reducing it to MAX-INDSET?
Given a 3SAT formula φ, what is the strategy for reducing it to MAX-INDSET?
How is a clause $y_i$ represented when reducing 3SAT to MAX-INDSET?
How is a clause $y_i$ represented when reducing 3SAT to MAX-INDSET?
In the reduction from 3SAT to MAX-INDSET, what do edges between vertices representing literals $x_i$ and $\overline{x_i}$ signify?
In the reduction from 3SAT to MAX-INDSET, what do edges between vertices representing literals $x_i$ and $\overline{x_i}$ signify?
If a 3SAT formula φ with k clauses has a solution, what does this correspond to in the reduced MAX-INDSET instance?
If a 3SAT formula φ with k clauses has a solution, what does this correspond to in the reduced MAX-INDSET instance?
What is the overall goal of reducing 3SAT to MAX-INDSET?
What is the overall goal of reducing 3SAT to MAX-INDSET?
Consider the reduction $A \leq^p B$. If problem B can be solved efficiently (in polynomial time), what can be inferred about problem A?
Consider the reduction $A \leq^p B$. If problem B can be solved efficiently (in polynomial time), what can be inferred about problem A?
Which of the following statements best describes the relationship between NP-complete and NP-hard problems?
Which of the following statements best describes the relationship between NP-complete and NP-hard problems?
Consider a circuit K with n inputs. During the reduction of CircuitSAT to 3SAT, the circuit is transformed such that each gate has at most two inputs. Why is this step necessary?
Consider a circuit K with n inputs. During the reduction of CircuitSAT to 3SAT, the circuit is transformed such that each gate has at most two inputs. Why is this step necessary?
Suppose you are given that 3SAT is NP-complete. What is the direct implication of this fact concerning the broader study of NP problems?
Suppose you are given that 3SAT is NP-complete. What is the direct implication of this fact concerning the broader study of NP problems?
Given the formula $a = b \land c$, which of the following CNF clause(s) correctly represents this expression for conversion during a reduction?
Given the formula $a = b \land c$, which of the following CNF clause(s) correctly represents this expression for conversion during a reduction?
In the context of reductions, what does it signify if problem A reduces to problem B, and problem B is known to be solvable in polynomial time?
In the context of reductions, what does it signify if problem A reduces to problem B, and problem B is known to be solvable in polynomial time?
During the reduction from CircuitSAT to 3SAT, a critical step involves transforming each gate in the circuit into a CNF formula. What is the primary purpose of this transformation?
During the reduction from CircuitSAT to 3SAT, a critical step involves transforming each gate in the circuit into a CNF formula. What is the primary purpose of this transformation?
What condition must be met for 3SAT to be considered NP-complete?
What condition must be met for 3SAT to be considered NP-complete?
What key property does an independent set in a graph possess?
What key property does an independent set in a graph possess?
Why is the MAX-INDSET problem considered challenging?
Why is the MAX-INDSET problem considered challenging?
While reducing 3SAT to MAX-INDSET, an edge is added between any two vertices representing literals $x_i$ and $\overline{x_i}$. What is the purpose of this setup?
While reducing 3SAT to MAX-INDSET, an edge is added between any two vertices representing literals $x_i$ and $\overline{x_i}$. What is the purpose of this setup?
Consider the situation when reducing a 3SAT instance to MAX-INDSET and you have a satisfying assignment in the 3SAT problem. How does this correlate to the maximum independent set in the produced graph?
Consider the situation when reducing a 3SAT instance to MAX-INDSET and you have a satisfying assignment in the 3SAT problem. How does this correlate to the maximum independent set in the produced graph?
How is the MAX-INDSET problem formally defined?
How is the MAX-INDSET problem formally defined?
In a reduction from 3SAT to MAX-INDSET what is the purpose of ensuring that for each clause in 3SAT, a triangle (complete graph of three vertices) is formed in MAX-INDSET?
In a reduction from 3SAT to MAX-INDSET what is the purpose of ensuring that for each clause in 3SAT, a triangle (complete graph of three vertices) is formed in MAX-INDSET?
Given a 3SAT formula φ, what does it mean if MAX-INDSET returns an independent set of size k. Assume k is the number of clauses in φ.
Given a 3SAT formula φ, what does it mean if MAX-INDSET returns an independent set of size k. Assume k is the number of clauses in φ.
What is the logical explanation for why you add an edge between literal xi and literal ¬xi, in the 3SAT to MAX-INDSET reduction?
What is the logical explanation for why you add an edge between literal xi and literal ¬xi, in the 3SAT to MAX-INDSET reduction?
During the reduction from 3SAT to MAX-INDSET, what information about each clause in the 3SAT formula does the constructed MAX-INDSET graph directly encode?
During the reduction from 3SAT to MAX-INDSET, what information about each clause in the 3SAT formula does the constructed MAX-INDSET graph directly encode?
The Cook-Levin theorem’s significance arises from its proof of NP-completeness of the CIRCUIT-SAT problem. How does establishing that CIRCUIT-SAT is NP-complete influence the examination of problems within NP?
The Cook-Levin theorem’s significance arises from its proof of NP-completeness of the CIRCUIT-SAT problem. How does establishing that CIRCUIT-SAT is NP-complete influence the examination of problems within NP?
Suppose algorithm σ transforms problem A into problem B. Which of the following is TRUE if this transformation is a polynomial time reduction?
Suppose algorithm σ transforms problem A into problem B. Which of the following is TRUE if this transformation is a polynomial time reduction?
Suppose you have an algorithm that finds the solution to CIRCUIT-SAT. Which one of these is something that you would now know?
Suppose you have an algorithm that finds the solution to CIRCUIT-SAT. Which one of these is something that you would now know?
During reduction from 3SAT to MAX-INDSET why is it critical that this reduction run in polynomial time?
During reduction from 3SAT to MAX-INDSET why is it critical that this reduction run in polynomial time?
To verify that we’ve made a correct CNF for $a = b \lor c$, what can we do?
To verify that we’ve made a correct CNF for $a = b \lor c$, what can we do?
Flashcards
Umbreytingar (Transformations)
Umbreytingar (Transformations)
A transformation maps instances of type A to instances of type B. If x of type A is 'yes', then the transformation of x, (\sigma(x)), is also 'yes'.
NP-hard
NP-hard
NP-hard problems are problems A such that if A is solvable in polynomial time, then P = NP.
NP-Complete
NP-Complete
A problem in NP is also in NP-Complete if every other problem in NP can be reduced to it in polynomial time.
3SAT
3SAT
Signup and view all the flashcards
3SAT difficulty
3SAT difficulty
Signup and view all the flashcards
MAX-INDSET
MAX-INDSET
Signup and view all the flashcards
Study Notes
- Umbreytingar (reductions) occur when A and B are decision problems.
- if there is an algorithm, σ, that maps instances of type A to instances of type B in polynomial time.
- σ: A → B
- x is yes ⇔ σ(x) is yes
- The reduction must work for every instance of A, and it must correctly translate each instance of A to the appropriate instance of B.
NP-hard
- NP-hard problems are problems A, such that if A is solvable in polynomial time, then P=NP.
- CircuitSAT is NP-hard (Cook-Levin 1971).
3SAT
- CNF (Conjunctive Normal Form)
- (Xi ∨ Xj ∨ Xk)
- 3-clause
- 3-SAT Boolean formula: y1 ∧ y2 ∧ ... ∧ ym
- where yi = li1 ∨ li2 ∨ li3, li = {xi, xi}
- (x1 ∨ x3 ∨ x5) ∧ (x1 ∨ x2 ∨ x4) ∧ ..., until a value of x1,...,xn is true,
- 3SAT is NP-hard
- This is proven by showing that 3SAT is harder than CircuitSAT.
- To prove that 3SAT is NP-hard, CircuitSAT instances are transformed into 3SAT instances, which provide a ‘yes’ answer.
- Uppskrift (recipe) takes an example that is (Civiliter)
- NP-estitt and transforms it into a new task.
- To transform a K circuit with inputs x1, ..., xn:
- If and/or has multiple inputs, it is split up
- the outcome is a k' path where all inputs ≤ 2
- Convert k' to halen formula
- 王 = ((...)) ∧ Z
- circuit nodes translating the circuit
- Z is the output node Piece by piece (y1 = x2 ∨ x4) ∧ (y2 = y1 ∧ x2)
- a = b ∧ c → (a ∨ b ∨ c) ∧ (a ∨ b) ∧ (a ∨ c)
- a = b ∨ c → (a ∨ b ∨ c) ∧ (a ∨ b) ∧ (a ∨ c)
- a = b → (a ∨ b) ∧ (a ∨ b)
- a ∨ b → (a ∨ b ∨ x) ∧ (a ∨ b ∨ x)
- Z → (Z ∨ x ∨ y) ∧ (Z ∨ x ∨ y) ∧ (Z ∨ x ∨ y) ∧ (Z ∨ x ∨ y)
- where x and y are new variables
- The K circuit (Circuit SAT context) is transformed into a 3-CNF Boolean formula 王, which is derived from the circuit Z,
- The formulations both have same values, if some x1,...,xn inputs, i.e if the circuit K yields an input, then formula 王 also yields an input, and vice versa.
- CircuitSAT ≤ p 3-SAT
- If 3-SAT had a P-algorithm, it would be a “cheap” P-algorithm for Circuit SAT, but then P=NP (Cook-Levin), which indicates that 3-SAT is NP-estitt.
MAX-INDSET
- Given a net G = (V, E), set S is independent if (u, v) ∉ E for all u, v ∈ S, that is, there are no legs between elements in S.
- Is there a set of size > k?
- The MAX-INDSET task is to find the largest independent set and is NP-hard.
- Converts for 3-SAT.
- 3SAT ≤ P MAX-INDSET
- Let φ = y1 ∧ y2 ∧ ... ∧ yk
- yi = li1 ∨ li2 ∨ li3
- lij ∈ alik
- For each clause yi, a triangle is built
- Connects all unique elements
- xi vid xi
- The net is called G
- Netid G contains a distinct set K.
- ppae φ has a solution (y-svar)
- k fjöldi clause in φ
- ⇐ If φ has a solution, this leads to a value xi,...xu for all elements in the clauses which are selfsame/equal.
- Every clause has at least one literal (x, x) that is selfsame, select one of them in S, 1S1=k
- This means the selection in S is id.
- Select one so that there will be no existing blue legs between elements in S.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
