CS6515 Exam 3 || 100% Exact Answers.
Search Problem (informal definition) correct answers Problem where we can efficiently verify
solution
What is minimum runtime to validate search problem? correct answers Polynomial time
What is NP? correct answers Class of all search problems. Must be able to validate solution to
problem in polynomial time.
What is P? correct answers P is the class of search problems that are solvable in polynomial time
Is P a subset of NP? If so why correct answers Yes, any problem that can be solved in P can be
solved in NP
What is the benefit of showing P = NP? correct answers We know that if we can verify a solution
for a search problem in polynomial time then we can solve that problem in polynomial time
What is Search Problem (formal definition)? correct answers Given Instance I
- find a solution S for I if one exists
- Output No if I has no solutions
In order to be a search problem. If given I and solution S, then we can verify that S is a solution
to I in polynomial time (polynomial) in |I|
How can you prove that problem is a search problem? correct answers Show/prove that there is
an algorithm that can verify solution in polynomial ||I Time
What does NP stand for? correct answers NP stands for non-deterministic polynomial time (it
does not stand for Not Polynomial lol). Non deterministic machine is one that is allowed to guess
at each step!
Is P a subset of NP? correct answers Yes
What are the intractable problems? correct answers NP-complete problems, can be solved in
non-deterministic polytime but not polytime
Are NP complete problems the hardest problems in NP class? correct answers Yes
If P != NP what does that mean? correct answers If P != NP then all NP-complete problems are
not in P
What does it mean for SAT to be NP-complete? correct answers a) SAT ∈ NP
b) If we can solve SAT in poly-time then we can solve every problem in NP in poly-time
Search Problem (informal definition) correct answers Problem where we can efficiently verify
solution
What is minimum runtime to validate search problem? correct answers Polynomial time
What is NP? correct answers Class of all search problems. Must be able to validate solution to
problem in polynomial time.
What is P? correct answers P is the class of search problems that are solvable in polynomial time
Is P a subset of NP? If so why correct answers Yes, any problem that can be solved in P can be
solved in NP
What is the benefit of showing P = NP? correct answers We know that if we can verify a solution
for a search problem in polynomial time then we can solve that problem in polynomial time
What is Search Problem (formal definition)? correct answers Given Instance I
- find a solution S for I if one exists
- Output No if I has no solutions
In order to be a search problem. If given I and solution S, then we can verify that S is a solution
to I in polynomial time (polynomial) in |I|
How can you prove that problem is a search problem? correct answers Show/prove that there is
an algorithm that can verify solution in polynomial ||I Time
What does NP stand for? correct answers NP stands for non-deterministic polynomial time (it
does not stand for Not Polynomial lol). Non deterministic machine is one that is allowed to guess
at each step!
Is P a subset of NP? correct answers Yes
What are the intractable problems? correct answers NP-complete problems, can be solved in
non-deterministic polytime but not polytime
Are NP complete problems the hardest problems in NP class? correct answers Yes
If P != NP what does that mean? correct answers If P != NP then all NP-complete problems are
not in P
What does it mean for SAT to be NP-complete? correct answers a) SAT ∈ NP
b) If we can solve SAT in poly-time then we can solve every problem in NP in poly-time
