What is an optimization problem?
Correct Answer: B. A problem that requires finding the best solution among many feasible solutions
Explanation: An optimization problem involves finding the best solution from all feasible solutions according to a given metric or objective function. Key characteristics: - Multiple possible solutions exist - Solutions can be evaluated and compared - Constraints define what solutions are feasible - Objective function measures solution quality
Which of the following is an example of a combinatorial optimization problem?
Correct Answer: C. Traveling Salesman Problem
Explanation: Combinatorial optimization problems involve finding optimal solutions from a finite set of discrete possibilities: - TSP: Finding shortest route visiting each city exactly once - Other examples: Knapsack, Job Scheduling, Graph Coloring Sorting and binary search are not optimization problems (they have single correct solutions) Graph traversal is a search problem, not an optimization problem
In optimization, the objective function:
Correct Answer: B. Is used to evaluate the quality of a solution
Explanation: The objective function (or cost function): - Quantifies how "good" a solution is - Can be minimized or maximized (e.g., maximize profit or minimize cost) - Works with constraints that define feasible solutions - Different solutions can be compared using the objective function value
Which method is commonly used for solving linear programming optimization problems?
Correct Answer: C. Simplex Method
Explanation: The Simplex Method: - Developed by George Dantzig in 1947 - Efficiently solves linear programming problems - Moves along the edges of the feasible region (a convex polytope) - Worst-case exponential but often performs well in practice - Other LP methods: Interior-point methods, Ellipsoid method
An NP-hard optimization problem:
Correct Answer: C. May not have an optimal solution computable in polynomial time
Explanation: NP-hard problems: - At least as hard as the hardest problems in NP - No known polynomial-time solutions - Includes optimization versions of NP-complete problems - May or may not be in NP (decision vs. optimization versions) - Can be solved exactly for small instances, often require approximation for large instances
The class P consists of:
Correct Answer: A. Problems solvable in polynomial time
Explanation: Complexity class P: - Contains decision problems solvable in polynomial time by a deterministic Turing machine - Examples: Sorting, Shortest Path, Minimum Spanning Tree - Can include both decision and optimization problems (optimization problems often have decision versions in P) - Problems where we can efficiently find solutions
The class NP includes problems that:
Correct Answer: A. Can be verified in polynomial time
Explanation: Class NP (Nondeterministic Polynomial time): - Decision problems where "yes" answers can be verified in polynomial time given a certificate - Includes all problems in P (P ⊆ NP) - Solutions may be hard to find but easy to verify - Open question: Does P = NP? Examples: SAT, Hamiltonian Cycle, Graph Coloring
Which of the following is true?
Correct Answer: A. P ⊆ NP
Explanation: Key relationships in complexity theory: - P ⊆ NP: Any problem solvable in polynomial time can certainly be verified in polynomial time - NP ⊆ P? This is the P vs NP question (unresolved) - NP-complete ⊆ P only if P = NP - NP-hard problems may not be in NP (e.g., optimization versions) - NP-complete = NP ∩ NP-hard
An NP-complete problem is:
Correct Answer: B. In NP and every problem in NP reduces to it
Explanation: NP-complete problems: 1) Are in NP (can be verified in polynomial time) 2) Are NP-hard (all problems in NP can be reduced to them in polynomial time) 3) Are the "hardest" problems in NP 4) Examples: SAT, 3-SAT, Hamiltonian Cycle, Vertex Cover 5) Solving one in polynomial time would solve all in P=NP
Which of the following problems is NP-complete?
Correct Answer: C. Boolean Satisfiability (SAT)
Explanation: Boolean Satisfiability (SAT): - First problem proven to be NP-complete (Cook-Levin theorem) - Asks whether a given boolean formula has a satisfying assignment - Foundation of NP-completeness theory - All other NP-complete problems can be reduced to SAT - Binary Search, Matrix Multiplication, and Bubble Sort are all in P