The defining characteristic of NP is that if the answer is 'Yes', there is a proof that can be checked by a deterministic Turing machine in polynomial time.
Incorrect! Try again.
20The Traveling Salesperson Problem (TSP) is an example of what kind of problem?
Optimization Problems
Easy
A.An optimization problem
B.A sorting problem
C.A linear programming problem
D.A constant time problem
Correct Answer: An optimization problem
Explanation:
TSP seeks to find the shortest possible route that visits every city exactly once and returns to the origin city, minimizing the total distance.
Incorrect! Try again.
21What is the result of using modular exponentiation?
Modular Arithmetic
Medium
A.4
B.2
C.3
D.1
Correct Answer: 4
Explanation:
Using Fermat's Little Theorem, . Thus, . Since , .
Incorrect! Try again.
22What is the time complexity of the Extended Euclidean Algorithm for two integers and ?
Greatest Common Divisor
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The Extended Euclidean Algorithm has the same time complexity as the standard Euclidean algorithm, which halves the input value at least every two steps, resulting in a logarithmic time complexity.
Incorrect! Try again.
23Suppose and . According to the Chinese Remainder Theorem, what is the smallest positive integer that satisfies these congruences?
Chinese Remainder Theorem
Medium
A.13
B.8
C.11
D.17
Correct Answer: 8
Explanation:
Checking the options: and . Thus, is the smallest positive solution.
Incorrect! Try again.
24What is the modular inverse of ?
Modular Arithmetic
Medium
A.4
B.2
C.7
D.5
Correct Answer: 4
Explanation:
We need to find such that . Testing the options, . So, the inverse is 4.
Incorrect! Try again.
25Which of the following best describes a problem in the NP class?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Medium
A.A problem whose solution can be verified in polynomial time by a deterministic Turing machine.
B.A problem that can be solved in polynomial time by a deterministic Turing machine.
C.A problem that can only be solved in exponential time.
D.A problem that cannot be solved by any Turing machine.
Correct Answer: A problem whose solution can be verified in polynomial time by a deterministic Turing machine.
Explanation:
NP stands for Nondeterministic Polynomial time. It contains decision problems where a 'yes' answer can be verified by a deterministic Turing machine in polynomial time given a suitable certificate.
Incorrect! Try again.
26If a problem is NP-complete, which of the following statements must be true?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Medium
A.It is NP-hard but not in NP.
B.It is in NP and every problem in NP is polynomial-time reducible to it.
C.It can be solved in polynomial time.
D.It is in P and every problem in NP is polynomial-time reducible to it.
Correct Answer: It is in NP and every problem in NP is polynomial-time reducible to it.
Explanation:
By definition, an NP-complete problem is in NP and is NP-hard (every problem in NP reduces to it in polynomial time).
Incorrect! Try again.
27Given and , what are the coefficients such that using the Extended Euclidean Algorithm?
Greatest Common Divisor
Medium
A.(-4, 11)
B.(2, -7)
C.(-4, 15)
D.(4, -15)
Correct Answer: (-4, 15)
Explanation:
The . Using the Extended Euclidean Algorithm, . Thus, .
Incorrect! Try again.
28What is the primary condition for a system of linear congruences to have a unique solution modulo using the Chinese Remainder Theorem?
Chinese Remainder Theorem
Medium
A.The moduli must all be prime.
B.The moduli must be even numbers.
C.The moduli must be pairwise coprime.
D.The congruences must have the same remainder.
Correct Answer: The moduli must be pairwise coprime.
Explanation:
The Chinese Remainder Theorem guarantees a unique solution modulo if and only if all the moduli are pairwise coprime (i.e., for all ).
Incorrect! Try again.
29How many elements are in the multiplicative group of integers modulo 15, ?
Modular Arithmetic
Medium
A.14
B.8
C.15
D.7
Correct Answer: 8
Explanation:
The number of elements in is given by Euler's totient function . For , .
Incorrect! Try again.
30Which of the following complexity class relationships is generally believed to be true, although unproven?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Medium
A.NP P
B.NP-complete = P
C.P = NP
D.P NP
Correct Answer: P NP
Explanation:
It is widely believed that P is a strict subset of NP (i.e., P NP), meaning there are problems whose solutions can be verified quickly but not found quickly.
Incorrect! Try again.
31In the context of algorithm design, what characterizes an optimization problem?
Optimization Problems
Medium
A.It asks for a simple 'yes' or 'no' answer.
B.It is always solvable in polynomial time.
C.It seeks to find the best solution from all feasible solutions.
D.It only requires verifying a given solution.
Correct Answer: It seeks to find the best solution from all feasible solutions.
Explanation:
An optimization problem involves finding the maximum or minimum value among a set of feasible solutions, unlike decision problems which ask for a yes/no answer.
Incorrect! Try again.
32If an NP-hard problem is solved in polynomial time, what is the consequence?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Medium
A.NP-complete problems become unsolvable
B.P = NP
C.P = PSPACE
D.NP = EXPTIME
Correct Answer: P = NP
Explanation:
If any NP-hard problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time (since they all reduce to the NP-hard problem), implying P = NP.
Incorrect! Try again.
33What is the ?
Greatest Common Divisor
Medium
A.35
B.21
C.7
D.14
Correct Answer: 21
Explanation:
Using the Euclidean algorithm: . Next, . Finally, . The last non-zero remainder is 21.
Incorrect! Try again.
34Which of the following is equivalent to ?
Modular Arithmetic
Medium
A.4
B.2
C.3
D.-2
Correct Answer: 3
Explanation:
In modular arithmetic, the remainder must be non-negative. , so .
Incorrect! Try again.
35What is the primary difference between NP-complete and NP-hard problems?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Medium
A.There is no difference; the terms are synonymous.
B.NP-complete problems must be in NP, while NP-hard problems do not have to be in NP.
C.NP-hard problems must be in NP, while NP-complete problems do not have to be.
D.NP-complete problems are solvable in polynomial time, NP-hard problems are not.
Correct Answer: NP-complete problems must be in NP, while NP-hard problems do not have to be in NP.
Explanation:
A problem is NP-hard if every problem in NP reduces to it. If an NP-hard problem is also in NP, it is classified as NP-complete.
Incorrect! Try again.
36To solve and using the Chinese Remainder Theorem, one computes and where . What is the next step?
Chinese Remainder Theorem
Medium
A.Find the modular inverse of and .
B.Find the modular inverse of and .
C.Multiply and directly.
D.Calculate .
Correct Answer: Find the modular inverse of and .
Explanation:
The formula involves finding such that and such that . These are the modular inverses of .
Incorrect! Try again.
37Which of the following problems is a classic example of an NP-hard optimization problem?
Optimization Problems
Medium
A.Finding the minimum spanning tree using Kruskal's algorithm.
B.Finding the shortest path in a graph using Dijkstra's algorithm.
C.The Traveling Salesperson Problem (Optimization version).
D.Sorting an array of integers.
Correct Answer: The Traveling Salesperson Problem (Optimization version).
Explanation:
The optimization version of the Traveling Salesperson Problem asks for the shortest possible route that visits every city exactly once, which is known to be NP-hard.
Incorrect! Try again.
38The concept of polynomial-time reduction () is used to show that:
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Medium
A.Neither problem is in NP.
B.Both problems can be solved in polynomial time.
C.Problem is at least as hard as Problem .
D.Problem is at least as hard as Problem .
Correct Answer: Problem is at least as hard as Problem .
Explanation:
If , any instance of can be transformed into an instance of in polynomial time. Thus, if you can solve , you can solve , meaning is at least as hard as .
Incorrect! Try again.
39What is the value of , where is Euler's totient function?
Modular Arithmetic
Medium
A.12
B.20
C.14
D.10
Correct Answer: 12
Explanation:
Since and both 3 and 7 are prime, .
Incorrect! Try again.
40Which of the following is the first problem proven to be NP-complete by Cook's Theorem?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Medium
A.The Boolean Satisfiability Problem (SAT)
B.The Knapsack Problem
C.The Vertex Cover Problem
D.The Traveling Salesman Problem
Correct Answer: The Boolean Satisfiability Problem (SAT)
Explanation:
The Cook-Levin theorem proved that the Boolean Satisfiability Problem (SAT) is NP-complete, making it the first known NP-complete problem.
Incorrect! Try again.
41Suppose we want to compute using the repeated squaring method. If is a -bit integer, what is the exact number of multiplications required in the worst-case scenario (excluding modulo operations)?
Modular Arithmetic
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
In the worst case, every bit of except the most significant bit is 1. There are squarings and multiplications by , totaling multiplications.
Incorrect! Try again.
42Let be pairwise coprime integers and . According to the Chinese Remainder Theorem, the system of congruences for has a unique solution modulo . If , what is the exact formula for the solution ?
Chinese Remainder Theorem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The standard construction for the CRT solution forms a linear combination where each term contributes modulo and $0$ modulo (), requiring .
Incorrect! Try again.
43In the Extended Euclidean Algorithm for computing , we find integers and such that . If and (successive Fibonacci numbers with ), what is the magnitude of the coefficients and generated by the standard algorithm?
Greatest Common Divisor
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
For successive Fibonacci numbers, the quotients in the Euclidean algorithm are all 1. The coefficients and obtained from the extended Euclidean algorithm inherently follow the Fibonacci sequence, yielding magnitudes and respectively.
Incorrect! Try again.
44Which of the following conditions is both necessary and sufficient for the linear congruence to have exactly distinct solutions modulo ?
Modular Arithmetic
Hard
A. and
B. and
C. and
D. and
Correct Answer: and
Explanation:
A linear congruence has solutions if and only if divides . If this condition holds, there are exactly distinct solutions modulo .
Incorrect! Try again.
45Let be an NP-complete problem and be a problem in P. Which of the following is true about ?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Hard
A.It is always NP-complete.
B.It could be outside NP.
C.It is in NP, but not necessarily NP-complete.
D.It is always in P.
Correct Answer: It is in NP, but not necessarily NP-complete.
Explanation:
If (which is in P), then , which is in P and thus not NP-complete (under polynomial-time many-one reductions, as cannot be mapped to a non-trivial language). It is always in NP since NP is closed under union.
Incorrect! Try again.
46If P = NP, which of the following statements about cryptographic hash functions and one-way functions is strictly correct?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Hard
A.One-way functions cannot exist.
B.Cryptographic hash functions can still be collision-resistant.
C.Public-key cryptography can still be securely implemented based on worst-case hardness.
D.Symmetric key encryption like AES will run in exponential time.
Correct Answer: One-way functions cannot exist.
Explanation:
The existence of one-way functions implies P NP. Thus, if P = NP, no one-way functions can exist, completely breaking public-key cryptography and most modern cryptographic constructs.
Incorrect! Try again.
47Consider a decision problem that is NP-hard. We know that problem can be reduced to in polynomial time (). What can be definitively inferred about ?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Hard
A. is NP-hard.
B. is NP-complete.
C. belongs to NP.
D.None of the above.
Correct Answer: None of the above.
Explanation:
Since reduces to , is no harder than . Because is NP-hard (an upper bound in this context), this reduction places no specific lower bound or upper bound on , so could be in P, NP, or even NP-hard. No definitive classification is possible.
Incorrect! Try again.
48Ladner's Theorem states that if P NP, there exist problems in NP that are neither in P nor NP-complete (NP-intermediate). Which of the following problems is widely conjectured to be NP-intermediate?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Hard
A.Linear Programming
B.Graph Isomorphism
C.Boolean Satisfiability (SAT)
D.Vertex Cover
Correct Answer: Graph Isomorphism
Explanation:
Graph Isomorphism is one of the most famous problems conjectured to be NP-intermediate. SAT and Vertex Cover are NP-complete, and Linear Programming is in P.
Incorrect! Try again.
49In the context of polynomial-time approximation schemes (PTAS) for NP-hard optimization problems, an FPTAS (Fully Polynomial-Time Approximation Scheme) requires the algorithm's running time to be polynomial in:
Optimization Problems
Hard
A. only.
B.The input size only.
C.The input size and .
D.The input size and .
Correct Answer: The input size and .
Explanation:
An FPTAS guarantees an approximation ratio of (or ) and runs in time bounded by a polynomial in both the size of the input and the reciprocal of the error bound, .
Incorrect! Try again.
50If you are using the Chinese Remainder Theorem to compute the sum of two large numbers and by working modulo a set of primes , what is the necessary condition on to ensure the result is strictly correct for general integer addition?
Chinese Remainder Theorem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
To recover the exact sum of and using CRT, the product of the moduli must be strictly greater than the maximum possible value of the result, which is , to avoid modulo overflow.
Incorrect! Try again.
51Fermat's Little Theorem states that for prime and . Carmichael numbers are composite numbers that satisfy this congruence for all coprime to the number. What is Korselt's criterion for a composite integer to be a Carmichael number?
Modular Arithmetic
Hard
A.For all prime factors of , and .
B. is square-free and for all prime factors of , .
C. is square-free and for all prime factors of , .
D.For all prime factors of , .
Correct Answer: is square-free and for all prime factors of , .
Explanation:
Korselt's criterion states that a positive composite integer is a Carmichael number if and only if is square-free, and for all prime factors of , it is true that divides .
Incorrect! Try again.
52What is the worst-case time complexity of the Euclidean algorithm to compute where , expressed in terms of the number of decimal digits of the smaller number ?
Greatest Common Divisor
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Lamé's theorem proves that the number of division steps in the Euclidean algorithm is at most 5 times the number of decimal digits of the smaller number, leading to an step complexity.
Incorrect! Try again.
53Which of the following accurately describes a co-NP-complete problem?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Hard
A.It is a problem in co-NP to which every other problem in co-NP can be reduced in polynomial time.
B.It is a problem that is both in NP and co-NP.
C.It is an NP-complete problem whose complement is also NP-complete.
D.It is a problem that cannot be verified in polynomial time.
Correct Answer: It is a problem in co-NP to which every other problem in co-NP can be reduced in polynomial time.
Explanation:
A problem is co-NP-complete if it is in co-NP and every problem in co-NP is polynomial-time many-one reducible to it. Tautology is a classic example of a co-NP-complete problem.
Incorrect! Try again.
54The Minimum Vertex Cover problem is NP-hard. However, its optimization version can be approximated in polynomial time using a simple maximal matching algorithm. What is the tightest guaranteed approximation ratio for this specific algorithm?
Optimization Problems
Hard
A.
B.
C.2
D.1.5
Correct Answer: 2
Explanation:
Finding a maximal matching and including all endpoints of the edges in the matching guarantees a vertex cover that is at most twice the size of the optimal minimum vertex cover (approximation ratio 2).
Incorrect! Try again.
55Consider a boolean formula in 2-CNF. The problem of determining whether this formula is satisfiable (2-SAT) belongs to which of the following complexity classes?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Hard
A.NL-complete and P
B.NP-complete
C.NP-hard but not NP
D.EXPTIME
Correct Answer: NL-complete and P
Explanation:
2-SAT is solvable in polynomial time (hence in P) by reducing it to finding strongly connected components in an implication graph. It is also known to be complete for the class NL (Nondeterministic Logarithmic-space).
Incorrect! Try again.
56The Miller-Rabin primality test is a probabilistic algorithm. For a composite number , what is the maximum probability that the test declares as prime for a single randomly chosen base ?
Number Theory Problems
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The Miller-Rabin test guarantees that for any odd composite , at most of the bases are strong liars. Thus, the error probability for a single iteration is at most .
Incorrect! Try again.
57To compute the modular inverse of modulo (where is prime), we can use Fermat's Little Theorem. Which expression computes ?
Modular Arithmetic
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
By Fermat's Little Theorem, . Multiplying both sides by yields .
Incorrect! Try again.
58The Traveling Salesperson Problem (TSP) is a classic NP-hard optimization problem. Which of the following statements is true regarding approximating the general TSP?
Optimization Problems
Hard
A.Unless P = NP, general TSP cannot be approximated within any constant factor.
B.General TSP admits a Fully Polynomial Time Approximation Scheme (FPTAS).
C.General TSP is in P if edge weights are restricted to be positive integers.
D.General TSP has a 1.5-approximation algorithm known as Christofides algorithm.
Correct Answer: Unless P = NP, general TSP cannot be approximated within any constant factor.
Explanation:
Without the triangle inequality, approximating the general TSP within any constant factor is NP-hard. The Christofides algorithm applies only to Metric TSP (which satisfies the triangle inequality).
Incorrect! Try again.
59Which polynomial-time reduction demonstrates that the Subset Sum problem is NP-hard?
Basic Concepts of Complexity Classes- P, NP, NP-hard, NP-complete Problems
Hard
A.Reduction from Hamiltonian Cycle to Subset Sum.
B.Reduction from 3-SAT to Subset Sum.
C.Reduction from Vertex Cover to Subset Sum.
D.Reduction from Subset Sum to 3-SAT.
Correct Answer: Reduction from 3-SAT to Subset Sum.
Explanation:
A standard way to prove Subset Sum is NP-hard is by a polynomial-time reduction from 3-SAT (or exactly 3-dimensional matching), constructing integers in base-10 to represent clauses and variables.
Incorrect! Try again.
60Let and be two large integers represented by -bit arrays. What is the time complexity of the Binary GCD algorithm (Stein's algorithm) in terms of bit operations?
Greatest Common Divisor
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Stein's algorithm replaces division with arithmetic shifts, comparisons, and subtraction. In the worst case, it takes iterations, and each subtraction or shift takes bit operations, leading to an overall bit complexity of .