Back to Subject

Unit 11: More on Lower Bound Theory - Practice Quiz

ECAP538 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the main purpose of using a reduction in lower-bound proofs?

Lower bounds through reductions Easy
A. To generate random inputs for an algorithm
B. To convert an algorithm into source code
C. To remove all constraints from a problem
D. To transfer known difficulty from one problem to another

2 To prove a lower bound for problem using a problem with a known lower bound, which reduction direction is normally required?

Lower bounds through reductions Easy
A. Reduce both problems to themselves
B. Reduce to
C. Reduce to an unrelated problem
D. Reduce to

3 If problem reduces to problem , what does this generally mean?

Lower bounds through reductions Easy
A. Problem always requires more memory than
B. Every input of is also an output of
C. A solution to can be used to solve
D. Problems and have identical algorithms

4 Which problem should usually be chosen as the source of a lower-bound reduction?

Lower bounds through reductions Easy
A. A problem with no defined input
B. A problem with only one instance
C. A problem with a known lower bound
D. A problem with no possible algorithm

5 In a reduction from problem to problem , what does the transformation step do?

Lower bounds through reductions Easy
A. It transforms an algorithm for into random data
B. It transforms an output of into source code
C. It transforms every lower bound into an upper bound
D. It transforms an instance of into an instance of

6 Why should the transformation used in a lower-bound reduction be computationally inexpensive?

Lower bounds through reductions Easy
A. So that it eliminates the target problem
B. So that it does not hide the relevant lower bound
C. So that it increases the number of possible answers
D. So that it always sorts the original input

7 Suppose has a lower bound of and reduces to in linear time without significantly changing the input size. What lower bound can generally be inferred for in the same model?

Lower bounds through reductions Easy
A.
B.
C.
D.

8 A lower-bound proof by reduction commonly uses which style of argument?

Lower bounds through reductions Easy
A. Proof by simulation only
B. Proof by contradiction
C. Proof by diagram
D. Proof by enumeration

9 What would contradict a known lower bound for problem ?

Lower bounds through reductions Easy
A. An algorithm for
B. An algorithm for
C. An algorithm for
D. An algorithm for

10 Which statement best describes a lower bound of ?

Lower bounds through reductions Easy
A. Every algorithm uses exactly operations
B. Every valid algorithm needs at least proportional to work in the stated setting
C. No algorithm can use more than operations
D. Some algorithm always uses fewer than operations

11 Why must a reduction preserve the answer to the original problem?

Lower bounds through reductions Easy
A. So that both problems use the same variable names
B. So that solving the transformed instance correctly solves the original instance
C. So that the transformed instance has no valid solution
D. So that both instances occupy exactly the same memory

12 If reduces to and reduces to , what can generally be obtained by combining the reductions?

Lower bounds through reductions Easy
A. An exact algorithm for only
B. A reduction from to
C. A reduction from to
D. An upper bound for only

13 In a lower-bound reduction, what is the target problem?

Lower bounds through reductions Easy
A. The problem whose lower bound is being established
B. The problem whose lower bound is already known
C. The problem discarded before the proof begins
D. The problem used only to format the final output

14 What does a successful lower-bound reduction show about the target problem?

Lower bounds through reductions Easy
A. It always has the same input as the source problem
B. It can only be solved using a recursive algorithm
C. It has exactly one optimal implementation
D. It is at least as hard as the source problem under the reduction

15 Why is the computational model important in a lower-bound proof?

Lower bounds through reductions Easy
A. Every model assigns identical costs to operations
B. Lower bounds may differ between computational models
C. The model determines the names of input variables
D. Lower bounds apply only to graphical interfaces

16 Which fact must be considered when a reduction changes an input of size into one of size ?

Lower bounds through reductions Easy
A. The transformation cost can always be ignored
B. The target algorithm's time must be measured using
C. The source algorithm's time must always be treated as constant
D. The target input must be renamed to have size

17 Which pair of components forms the total cost of solving through a reduction to ?

Lower bounds through reductions Easy
A. The input-reading cost and the output-printing cost only
B. The reduction cost and the cost of solving
C. The compilation cost and the variable-renaming cost
D. The source lower bound and the target upper bound only

18 What is assumed temporarily in a typical contradiction-based lower-bound reduction?

Lower bounds through reductions Easy
A. The computational model has no permitted operations
B. The reduction changes every yes-answer to a no-answer
C. The source problem has no inputs
D. The target problem has an algorithm that is too fast

19 A comparison-based problem is reduced to another problem to transfer a comparison lower bound. What should the reduction avoid?

Lower bounds through reductions Easy
A. Creating a valid target instance
B. Using the target problem's output
C. Performing excessive hidden comparisons
D. Preserving the original answer

20 Which conclusion does a lower-bound reduction provide rather than directly provide?

Lower bounds through reductions Easy
A. A guaranteed fastest implementation of the target problem
B. A sample output for every possible target input
C. A complete list of all algorithms for the target problem
D. A minimum asymptotic resource requirement for the target problem

21 Problem has a lower bound of . An instance of can be transformed into one instance of problem of size in time, and a solution to can be converted back in time. What lower bound follows for ?

Lower bounds through reductions Medium
A.
B.
C.
D.

22 Problem requires time and reduces in linear time to a problem instance of size . Which lower bound for follows in terms of ?

Lower bounds through reductions Medium
A.
B.
C.
D.

23 Element uniqueness has an lower bound in the algebraic decision-tree model. Which reduction direction can establish the same lower bound for comparison sorting?

Lower bounds through reductions Medium
A. Reduce sorting to element uniqueness
B. Reduce sorting to linear scanning
C. Reduce element uniqueness to sorting
D. Reduce searching to element uniqueness

24 To transfer the element-uniqueness lower bound to the one-dimensional closest-pair problem, which property should the reduction use?

Lower bounds through reductions Medium
A. The median distance is zero exactly when duplicates exist
B. The closest distance is zero exactly when duplicates exist
C. The average distance is zero exactly when duplicates exist
D. The farthest distance is zero exactly when duplicates exist

25 Assume the 3SUM conjecture states that 3SUM cannot be solved in time for any constant . A size-preserving reduction transforms 3SUM into problem in time. What conditional conclusion follows?

Lower bounds through reductions Medium
A. cannot be solved in time
B. requires exponential time
C. cannot be solved in time
D. requires exactly time

26 Problem has a lower bound of and reduces to problem , but constructing the instance already takes time. What can this reduction alone prove about the running time of ?

Lower bounds through reductions Medium
A. requires time
B. requires time
C. No nontrivial lower bound for
D. requires time

27 Which condition is essential for a many-one reduction from decision problem to decision problem to transfer a lower bound?

Lower bounds through reductions Medium
A. The transformation makes both problems have identical outputs
B. The transformation maps every input to a strictly smaller instance
C. The transformation preserves yes/no answers and has sufficiently small overhead
D. The transformation uses the same data structure for both problems

28 An algorithm for problem uses calls to problem , each on an instance of size , plus additional work. If requires time, what lower bound is implied for each call to under this cost relation?

Lower bounds through reductions Medium
A.
B.
C.
D.

29 A standard reduction maps numbers to points on a parabola to prove a lower bound for planar convex hull. What information does the convex hull reveal?

Lower bounds through reductions Medium
A. The closest pair of input values
B. The sorted order of the input values
C. The frequencies of all input values
D. The sum of all input values

30 A lower bound is proved for problem in the comparison-tree model, and reduces to problem . When does the same lower bound transfer directly to ?

Lower bounds through reductions Medium
A. Whenever has a polynomial-time algorithm
B. When the algorithm for is restricted to a compatible model
C. Whenever the reduction uses constant extra space
D. Whenever has numeric inputs

31 Problem has an expected-time lower bound of for Las Vegas randomized algorithms. A deterministic, size-preserving reduction makes one call to problem and uses other work. What follows?

Lower bounds through reductions Medium
A. Randomized algorithms for cannot use sublinear space
B. Deterministic algorithms for require exactly time
C. Monte Carlo algorithms for require worst-case time
D. Las Vegas algorithms for require expected time

32 An exact optimization problem reduces to an exact version of problem . Why does this not automatically establish the same lower bound for an approximation algorithm for ?

Lower bounds through reductions Medium
A. An approximate solution to may not determine an exact solution to
B. Approximation algorithms always use randomization
C. Exact reductions always increase instance size
D. Approximation algorithms are outside all computation models

33 Suppose an NP-hard problem reduces in polynomial time to problem . What lower-bound statement follows unconditionally from this fact alone?

Lower bounds through reductions Medium
A. No specific superpolynomial running-time lower bound follows
B. cannot have an approximation algorithm
C. requires at least quadratic time
D. requires exponential time

34 Problem requires time. A reduction constructs one instance of of size using time. What lower bound for follows in terms of ?

Lower bounds through reductions Medium
A.
B.
C.
D.

35 A reduction solves problem using two calls to problem on instances of size , plus work. If has a lower bound of , which bound is consistent for ?

Lower bounds through reductions Medium
A. for instances of size
B. for instances of size
C. for instances of size
D. for instances of size

36 Problem has an lower bound. A reduction to a size- instance of takes time before calling . Which conclusion is justified?

Lower bounds through reductions Medium
A. The reduction proves no nontrivial lower bound for
B. has an lower bound
C. has an lower bound
D. The reduction proves that is unsolvable

37 Suppose problem reduces efficiently to problem , and has a lower bound of . What does this reduction direction imply about ?

Lower bounds through reductions Medium
A. must have a lower bound of
B. and must have identical complexity
C. must be strictly harder than
D. It gives no such lower bound for from the lower bound of

38 The decision version of problem has a lower bound of . One call to the search version of , followed by work, can answer the decision version. What follows about the search version?

Lower bounds through reductions Medium
A. It requires only time
B. It requires exactly time
C. It has a lower bound of
D. It has no relation to the decision version

39 Problem must explicitly output items. It reduces to problem , but converting the answer from into the output for takes time. What does the output-size lower bound establish for ?

Lower bounds through reductions Medium
A. It establishes an lower bound for
B. It establishes no nontrivial lower bound for
C. It establishes an lower bound for
D. It establishes an lower bound for

40 Problem has a lower bound of . There is a size-preserving reduction from to and another size-preserving reduction from to . What lower bound follows for ?

Lower bounds through reductions Medium
A.
B.
C.
D.

41 Problem on inputs of size has a lower bound of . A reduction transforms each instance of in time into an instance of problem of size , and converts the answer back in time. What lower bound follows for ?

Lower bounds through reductions Hard
A. on every syntactically valid instance of
B. because transformation and recovery are composed
C. only when the reduction is bijective
D. on the instances produced by the reduction

42 To prove that problem is at least as hard as problem , which reduction direction is required?

Lower bounds through reductions Hard
A. Transform every instance of into an instance of
B. Transform arbitrary instances of both problems into a third problem
C. Transform every instance of into an instance of
D. Transform only the no-instances of into instances of

43 Problem requires time. A reduction from to preserves input size but itself takes time, excluding the call to . What unconditional asymptotic lower bound on follows from these facts alone?

Lower bounds through reductions Hard
A. No nonconstant asymptotic lower bound follows
B. A lower bound of follows
C. A lower bound of follows
D. A lower bound of follows

44 Problem has lower bound . A reduction creates an instance of having size with overhead. What lower bound is obtained for in terms of ?

Lower bounds through reductions Hard
A.
B.
C.
D.

45 An oracle reduction solves a size- instance of using calls to , each on size instances, plus work. If requires time, what is the strongest lower bound forced on the worst-case time of at least one oracle call?

Lower bounds through reductions Hard
A.
B.
C.
D.

46 Which reduction correctly transfers the algebraic computation-tree lower bound for Element Uniqueness to planar Closest Pair?

Lower bounds through reductions Hard
A. Map each number to and test whether every distance is positive
B. Map each number to and test whether the minimum distance is one
C. Map each number to and test whether the minimum distance is zero
D. Map each number to and test whether the closest points are consecutive

47 Distinct real numbers are mapped to points . Suppose a planar convex-hull algorithm returns hull vertices in cyclic order. Why can this establish an lower bound for convex hull construction?

Lower bounds through reductions Hard
A. The parabola mapping converts comparisons into constant-time orientation tests only
B. The cyclic hull order yields the numbers in sorted or reverse-sorted order
C. The upper hull contains no input points, so sorting requires no comparisons
D. The hull area uniquely determines every input number and its original index

48 A comparison-based algorithm constructs an arbitrary binary search tree containing distinct input keys. Which postprocessing operation makes the sorting lower bound applicable to tree construction?

Lower bounds through reductions Hard
A. Rotate the root to a leaf in time
B. Perform an inorder traversal in time
C. Compute the tree height in time
D. Perform a preorder traversal in time

49 Let return the minimum value of an optimization problem, and let ask whether that value is at most . If one call to and extra work solve , which conclusion is valid?

Lower bounds through reductions Hard
A. A lower bound for transfers automatically to
B. Neither formulation can be related without a bijective reduction
C. A lower bound for transfers to
D. Both formulations always have identical upper and lower bounds

50 A reduction maps problem to a promise problem . Which condition is essential for using a lower bound for to derive one for algorithms solving under its promise?

Lower bounds through reductions Hard
A. Every reduced instance must satisfy the promise of
B. Every possible instance of must encode an instance of
C. The reduction must map yes-instances to promise violations
D. The promise must be decidable faster than problem

51 A comparison-tree lower bound for sorting is used in a reduction to a target problem whose inputs are machine integers. Why does the reduction not automatically establish the same lower bound in the word-RAM model?

Lower bounds through reductions Hard
A. Word-RAM algorithms are required to preserve the comparison sequence of the reduction
B. The word-RAM model cannot represent the inputs produced by a comparison reduction
C. The target may exploit arithmetic and bit operations unavailable to comparison trees
D. Comparison-tree lower bounds apply only when the target output is a Boolean value

52 Problem has a distributional lower bound against deterministic algorithms under distribution . A deterministic reduction maps samples from to size- instances of with overhead. What does the argument directly establish?

Lower bounds through reductions Hard
A. An expected lower bound for under the uniform distribution
B. A worst-case lower bound for under every input distribution
C. A deterministic lower bound for only on no-instances
D. A distributional lower bound for under the induced distribution

53 Assume the 3SUM conjecture: no algorithm solves 3SUM in time for any constant . A reduction maps 3SUM instances of size to problem instances of size in time. Which algorithm for would refute the conjecture?

Lower bounds through reductions Hard
A. An algorithm for all sufficiently large
B. An algorithm for a fixed
C. An algorithm for every fixed
D. An algorithm using only linear auxiliary space

54 Assume APSP requires time. A reduction maps an -vertex APSP instance to an instance of of size using time. Which running time for would contradict this assumption?

Lower bounds through reductions Hard
A. for some constant
B. for all sufficiently large
C. for all sufficiently large
D. for some constant

55 Problem has lower bound . A reduction maps to with size and overhead. A second reduction maps to with size and overhead. What lower bound does the composed reduction imply for ?

Lower bounds through reductions Hard
A.
B.
C.
D.

56 A reduction from reaches only a restricted subset of valid instances of . If it establishes an bound on solving instances in , what worst-case conclusion about is justified?

Lower bounds through reductions Hard
A. Instances outside are asymptotically harder than instances inside
B. The average-case complexity of is at least
C. Every valid instance of requires time
D. The worst-case complexity of is at least

57 Numbers are mapped to parabola points to reduce sorting to convex hull. Suppose the target specification returns only the unordered set of hull vertices, and every mapped point is a hull vertex. Why does the standard sorting reduction fail?

Lower bounds through reductions Hard
A. The parabola contains collinear triples that make the hull vertex set undefined
B. The transformation requires quadratic time when the output order is unspecified
C. The returned set necessarily omits the points with minimum and maximum coordinates
D. The returned set contains no order from which the sorted sequence can be recovered

58 Must a many-one reduction used for a lower-bound proof be injective on source instances?

Lower bounds through reductions Hard
A. Yes, because distinct source instances must always produce distinct target instances
B. No, but only when all source instances have the same correct answer
C. Yes, unless both problems have exactly the same number of possible inputs
D. No, provided the target answer permits recovery of the correct source answer

59 A reduction maps yes-instances of to no-instances of and no-instances of to yes-instances of , with linear overhead and size preservation. Can it transfer a lower bound from to ?

Lower bounds through reductions Hard
A. No, because reductions must preserve yes-answers without changing their truth value
B. Yes, but only if both problems have equal numbers of yes-instances
C. Yes, because negating the answer of recovers the answer to
D. No, because complementing an answer requires an additional oracle invocation

60 A worst-case lower bound for is transferred to through a deterministic, size-preserving reduction. Which stronger claim generally does not follow without additional distributional analysis?

Lower bounds through reductions Hard
A. Problem has the same lower bound on average under the uniform distribution
B. A sufficiently fast algorithm for would accelerate problem
C. Problem has a corresponding worst-case lower bound
D. Problem has at least one hard family of reduced instances
Previous MCQ
Unit 10
Next MCQ
Unit 12