in which I cover intractability 2 in [[00_Plan]] See also [[Intractability questions]] Only based on Intractability 2

P (Polynomial Time): As name itself suggests, these are the problems which can be solved in polynomial time.

NP (Non-deterministic-polynomial Time): These are the decision problems which can be verified in polynomial time. That means, if I claim that there is a polynomial time solution for a particular problem, you ask me to prove it. Then, I will give you a proof which you can easily verify in polynomial time. These kind of problems are called NP problems. Note that, here we are not talking about whether there is a polynomial time solution for this problem or not. But we are talking about verifying the solution to a given problem in polynomial time.

NP-Hard: These are at least as hard as the hardest problems in NP. If we can solve these problems in polynomial time, we can solve any NP problem that can possibly exist. Note that these problems are not necessarily NP problems. That means, we may/may-not verify the solution to these problems in polynomial time.

NP-Complete: These are the problems which are both NP and NP-Hard. That means, if we can solve these problems, we can solve any other NP problem and the solutions to these problems can be verified in polynomial time.

The crazy thing is NP-complete is actually simpler than NP-hard. See diagram for an even better understanding

![[Pasted image 20221112154925.png]]

• An NP problem also P is solvable in P
• NP hard problem that's NP complete is verifiable in P
• NP complete problems (which are a subset of NP hard)

NP Completeness¶

NP vs NP hard vs NP complete NP: class of decision problems (yes/no) whose "yes" inputs can be verified through a polynomially short certificate which can be verified in polynomial time

Examples: 2d matching, 3d matching is there a path from \(s\) to \(t\) of weight \(\leq k\) or \(\geq k\)

Reductions¶

\(\pi_1 \leq_p \pi_2\) iff there's a polynomial time algorithm R such that - we can convert any input \(x\) into \(\pi_1\) through \(R(x)\) in polynomial time - \(\pi_2(R(x))\) is yes iff \(\pi_2(x)\) is yes Consequently, there exist inputs into \(\pi_2\) that are verifiable in polynomial time

NP Complete¶

\(\pi\) is NP complete if \(\pi \in NP\) and \(\pi\) is at least as hard polynomially as every other problem in NP (NP-hard) we can show this second condition by reducing an NP hard problem (which is harder than any problem in NP) to \(\pi\)

Cook Theorem¶

circuit-sat is NP complete

Later we found 3-SAT also NP complete by reducing from circuit-sat I skipped the proof for now bc my brain is small but i probably want to look into it more Important technique called teichnov reductions or something where we can introduce dummy variables to change the format of CNF without altering the satisfiable solutions

In general, it's been shown that every NP problem can be reduced to 3-SAT which is pretty cool

Non SAT problems¶

Vertex cover¶

Given a graph \(G\) and integer \(k\), is there a subset of vertices such that \(|S| \leq k\) and every edge includes at least one vertex in S? kind of like the inverse of an MST, where we want to find the subset of vertices that include every edge, rather than the subset of edges which cover all vertices

To show VC is NP-hard, we must show \(VC \in NP\), and reduce 3-SAT to \(VC\)

VC is in NP¶

The certificate is the subset of vertices in the vertex cover. For each vertex, we can iterate through the list of edges and identify which are incident to our vertex. Repeat for every vertex to run in \(O(VE) = O(V^3)\) for a FC graph

VC is NP hard¶

We'll try to reduce 3-SAT to VC by posing 3-SAT as a graph Given a CNF formula \(\phi\) with \(n\) variables and \(m\) clauses, we will encode \(\phi\) via a graph and \(k\) such that
\(phi\) is satisfiable iff there's a vertex cover of size \(\leq k\)

Gadget construction¶

• for each variable in the SAT, assign a subgraph of G (a gadget) representing the variable's truth value
• for each clause, assign a gadget to ensure at least one literal is true (since each clause must evaluate to true) How do we create a subgraph representing 1 and 2? 1) assign a subgraph representing the variable's truth value for each variable \(x_i\), create two connected nodes in the graph, \(P_{x_i}, N_{x_i}\) representing the positive or negative truth assignment choosing one node is sufficient to cover their edge, so this guarantees every variable will have an assigned value For a certificate from 3-SAT indicating the truth values of each variable, we only select the node indicating the truth value to be in the vertex cover ![[Pasted image 20221112170830.png]] 2) for every clause, create a 3-clique (fully connected subgraph) where f=first literal, s=second literal, t=third literal ![[Pasted image 20221112170844.png]] Note that this clique does not encode which vertices are part of the clause. Note we can cover the three edges by choosing any two of the three vertices

![[Pasted image 20221112171144.png]] With no additional edges, the smallest possible vertex cover includes one node for each variable (n), and two nodes for each clause (2m), such that the minimum k is 2m + n. But now we need to encode relationships between variables and clauses! What's a girl to do?

For every clause, we draw an edge between the first variable that appears in the clause (\(fc_i\)) and the positive or negative node of that variable, depending on if its a positive or negative literal! ![[Pasted image 20221112171634.png]] If a literal \(P_{x_i}\) in the clause evaluates to true in 3-SAT, then the blue edge connecting \(P_{x_i}\) to \(c_j\) will also be covered by \(P_{x_i}\) Then to cover the other three edges in the clique and other two blue edges, we can simply add those two vertices to the vertex cover.

Covering a blue edge from a variable node (\(P_x\) or \(n_x\)) corresponds to a variable literal which satisfies the clause

Potentially notably, each vertex in the clause gadget will have degree 3, but there's no guarantee on the variable gadgets

Correctness¶

Remember that for correctness, we need to show that the reduced problems are equivalent in both directions. 1) if a transformed certificate in VC is YES, then the certificate in 3-SAT is YES 2) if a certificate in 3-SAT is YES, then the transformed certificate in VC is YES.
Claim 1: If there exists a VC of size k = 2m + n, then 3-SAT problem is satisfiable Proof: We've shown that a VC of size 2m+n is minimal. In order for our transformation to have a vertex cover of size 2m+n, it must use exactly one vertex from each variable gadget and exactly two vertices from each clause gadget this is because we must use two vertices in each clause gadget to cover all the clause gadet edges, and we need one vertex in the variable gadget to cover the gadget edge. If there's exactly one vertex in the variable gadget, then we set that variable to true, and we know the corresponding clause will be satisfied note that it could be both vertices in the variable gadget are in our vertex cover if one clause includes the positive literal and another clause the negative literal

Why do we know the corresponding clause will be satisfied? ![[Pasted image 20221112175653.png]] Claim 2: if the 3-SAT problem is satisfied, there exists a vertex cover of size k ![[Pasted image 20221112175730.png]]

Tips¶

To show something is NP complete, first we must show that \(\pi \in NP\) by showing what a polynomially-short certificate would be for this, and that verification of this would be in polynomial time

• during a reduction, we must show that an arbitrary NP-hard problem's certificate can be reduced to our problem of interest.
  • I thought we could reduce vertex cover to half-vertex cover simply by letting k=|V|/2, but the point is k can be anything and the graph can be anything.
  • we need to show that, given any vertex cover problem (any graph and k), we can construct a half-vertex cover problem where the answer is yes iff the answer to the vertex cover problem is yes.
• just because a problem is a special case of an NP-hard problem does not make it NP-hard.
  • however, it typically does make sense to reduce the general problem into the special case

![[Pasted image 20221114213502.png]] - got this one completely wrong, despite being confident about it!! - important insights: we must show that we can transform the graph into another graph whose solution to the new problem gives the same answer as the solution the old problem. - i thought wrongly that 1) if k > |V|/2, we could just attach new vertices to the old ones and add them to the vertex cover - but now if you imagine if we're checking a vertex cover that's exactly size k, then the new problem would indeed have |V'|/2=k, BUT we the examined vertex cover would no longer be valid because we must add in additional vertices!! - instead, we can just add on unattached vertices to the graph such that |V'|/2=k, but the edges we must cover remain the same - if k < |V|/2, i wrongly thought we would have access to the prospective set cover. But that's not a transformation of the input, since i guess the input includes the graph itself, not the proposed set cover...? - in the actual answer, we add a clique of isolated triangles to increase the number of vertices in the set by 3, and the number of vertices in the set cover by 2.

• takeaways: to prove something is NP-complete, there's three steps
  • 1) prove it's in NP (a certificate must be validated in polynomial time)
  • 2) show a reduction of an NP-hard problem to ours (the hardest part)
  • 3) correctness: prove in both directions that the reduction is valid for any given input (will only output yes if the corresponding problem is also yes)
• commonly in reductions from known general questions (like 3-sat to 4-sat or vertex cover to half-vertex cover), the challenge is simply to make the problem into the format of the prospective problem, which typically requires dummy variables
  • in 3-sat, we introduce dummy variables that can take any value without affecting the satisfiability
  • in vertex cover, we introduce triangle cliques to increase the number of vertices by 3 but only the vertex cover size by 2, and by introducing vertices that are disconnected from the rest of the graph