Skip to content
- P Problems, NP Problems, NP Hard Problems, NP Complete Problems
- Proofs of NP Complete Problems
- Prove that SAT is NP Complete
- Prove that 3SAT is NP Complete.
- Prove that Clique is NP Complete
- Prove that Vertex Cover is NP Complete.
- What is Approximation Algorithms?
- How Approx Vertex Cover algorithm works?
- Prove that Approx Vertex Cover is polynomial time 2 approximation algorithm?
- How Approx TSP works?
- Approximation algorithm for Bin Packing.
- Prove that Approx TSP is polynomial time 2 approximation algorithm?
NP Completeness.
Proof that 3CNF SAT is NP Complete
Proof that Clique is NPC
CLEQUE, VC and Ind Set
Approximation algorithm
Approximation algorithm for Bin Packing
Approximation Algorithm