CS 6515 GA EXAM 3 STUDY GUIDE
Search problem - Answer -A problem is a search problem if, given an and a potential
solution, you can verify the solution is correct in polynomial time. The em must have the
form where you output a valid solution if one exist, and report no otherwise
Decision problem - Answer -Desicion problems are a simplified version of search
problem. They are a the bead rock of NP-C theory because their simple "yes/no" format
makes them easy to use in reductions.
Optimization problems - Answer -Optimization problems take the challenge one step
further. They don't just ask for any solution, they ask for the best one. An optimization
problem seeks to find a solution that maximizes or minimizes som value
Polynomial time - Answer -Considered efficient or inctractable. Te runtime is bounded
by a polynomial function of the input size: O(n), O(n^2) even O(n^3000)
Exponential time - Answer -Considered inefficient or intractable for large inputs. the
runtime grows exponentially with respect to the input size: O(2^n)
Pseudo Polinomial - Answer -A special case that seems efficient but it is not. the
runtime is polynomial in the numeric value of the input, but exponential in the
size(number of bits)of the input
Class P - Answer -P (polynomial time) this class contains all decision problems that can
be solved by deterministic algorithm in polynomial time
Class NP - Answer -NP (Non-deterministic polynomial time) This class contains all
decisions problems where if the answer is "yes " there is a proof at can be verified in
polynomial time
Np-Hard - Answer -These re the problems that are at least as hard as the hardest
problem in NP. A problem is NP-Hard if any problem in NP can be reduced to in in
polynomial time
NP-Complete - Answer -This class represents the hardest NP problems. NPC problems
are equivalent in difficulty. If we find a polynomial time algorithm for any of the NPC
problems. we have found one for all of them. (P=NP)
What make a problem NPC - Answer -1. It is in NP
2. It is in NP-Hard
What are reductions used for? - Answer -A Reduction is a formal way to say that
Problem A is no harder than problem B. We denote it as A <=p B. It's a polynomial-time
algorithm that transform any instance of problem A into an equivalent instances of
problem B
, What is the direction of the reductions: - Answer -Kwon to unkown.
The reduction flow from easier to harder problems in a hierarchical sense. If we say
problem A reduces to problem B, it means that A is no harder than B.
True or False:
Any problem in problem in NP reduces to any problem in NPC - Answer -True.
This is the part of the definition of NPC. It's why NPC problems are considered the
hardest in NP
True or False:
Any problem in NPC reduces to any problem in NP-Hard - Answer -True.
By definition, NP_Hard problems are at least as hard as everything in NP
What does it mean that a problem is known to be in NP - Answer -These are problems
that are confirmed to have polynomial time verifies. This include problems in P and all
NPC
What does it means that problem is NOT known to be in NP - Answer -These are
problems that cannot be part of NP, usually because they are not decision problems or
are proven to be even harder than NP.
Given a example of a problem that is not in NP - Answer -The Halting problem
Steps to prove a problem is NP-Complete - Answer -1 Prove the problem is in NP
1.1 Define the certificate/solution: What information would you need to be convinced the
answer exist.
1.2. Design a verifier: Write an algorithm that takes the problem instance and the
solution.
1.3. Prove the verifier in polynomial time
2 Prove the problem is NP-Hard.
2.1 choose a known NPC problem A
2.2 Construct a transformation
2.3 Prove the transformation is polynomial
2.4 Prove correctness
How to choose a problem to use for reductions: - Answer -- if the problems involves
graph, nodes and connections, a good start Vertex Cover, Clique, Independent Set, or
Rudrata path.
- If the problem involves logic, choices constraints or truth assignment. SAT or 3SAT
- If the problem involves numbers, set, packing, or scheduling, a good choice might be
SSS or knapsack
Define SAT (Inputs, outputs) - Answer -Definition: Decided if a boolean formula CNF is
satisfiable.
Inputs: A boolean formula in CNF
Search problem - Answer -A problem is a search problem if, given an and a potential
solution, you can verify the solution is correct in polynomial time. The em must have the
form where you output a valid solution if one exist, and report no otherwise
Decision problem - Answer -Desicion problems are a simplified version of search
problem. They are a the bead rock of NP-C theory because their simple "yes/no" format
makes them easy to use in reductions.
Optimization problems - Answer -Optimization problems take the challenge one step
further. They don't just ask for any solution, they ask for the best one. An optimization
problem seeks to find a solution that maximizes or minimizes som value
Polynomial time - Answer -Considered efficient or inctractable. Te runtime is bounded
by a polynomial function of the input size: O(n), O(n^2) even O(n^3000)
Exponential time - Answer -Considered inefficient or intractable for large inputs. the
runtime grows exponentially with respect to the input size: O(2^n)
Pseudo Polinomial - Answer -A special case that seems efficient but it is not. the
runtime is polynomial in the numeric value of the input, but exponential in the
size(number of bits)of the input
Class P - Answer -P (polynomial time) this class contains all decision problems that can
be solved by deterministic algorithm in polynomial time
Class NP - Answer -NP (Non-deterministic polynomial time) This class contains all
decisions problems where if the answer is "yes " there is a proof at can be verified in
polynomial time
Np-Hard - Answer -These re the problems that are at least as hard as the hardest
problem in NP. A problem is NP-Hard if any problem in NP can be reduced to in in
polynomial time
NP-Complete - Answer -This class represents the hardest NP problems. NPC problems
are equivalent in difficulty. If we find a polynomial time algorithm for any of the NPC
problems. we have found one for all of them. (P=NP)
What make a problem NPC - Answer -1. It is in NP
2. It is in NP-Hard
What are reductions used for? - Answer -A Reduction is a formal way to say that
Problem A is no harder than problem B. We denote it as A <=p B. It's a polynomial-time
algorithm that transform any instance of problem A into an equivalent instances of
problem B
, What is the direction of the reductions: - Answer -Kwon to unkown.
The reduction flow from easier to harder problems in a hierarchical sense. If we say
problem A reduces to problem B, it means that A is no harder than B.
True or False:
Any problem in problem in NP reduces to any problem in NPC - Answer -True.
This is the part of the definition of NPC. It's why NPC problems are considered the
hardest in NP
True or False:
Any problem in NPC reduces to any problem in NP-Hard - Answer -True.
By definition, NP_Hard problems are at least as hard as everything in NP
What does it mean that a problem is known to be in NP - Answer -These are problems
that are confirmed to have polynomial time verifies. This include problems in P and all
NPC
What does it means that problem is NOT known to be in NP - Answer -These are
problems that cannot be part of NP, usually because they are not decision problems or
are proven to be even harder than NP.
Given a example of a problem that is not in NP - Answer -The Halting problem
Steps to prove a problem is NP-Complete - Answer -1 Prove the problem is in NP
1.1 Define the certificate/solution: What information would you need to be convinced the
answer exist.
1.2. Design a verifier: Write an algorithm that takes the problem instance and the
solution.
1.3. Prove the verifier in polynomial time
2 Prove the problem is NP-Hard.
2.1 choose a known NPC problem A
2.2 Construct a transformation
2.3 Prove the transformation is polynomial
2.4 Prove correctness
How to choose a problem to use for reductions: - Answer -- if the problems involves
graph, nodes and connections, a good start Vertex Cover, Clique, Independent Set, or
Rudrata path.
- If the problem involves logic, choices constraints or truth assignment. SAT or 3SAT
- If the problem involves numbers, set, packing, or scheduling, a good choice might be
SSS or knapsack
Define SAT (Inputs, outputs) - Answer -Definition: Decided if a boolean formula CNF is
satisfiable.
Inputs: A boolean formula in CNF
