Back to Subject

Unit 13: Intractable Problems - Practice Quiz

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

1 What is an intractable problem?

Basic concepts Easy
A. A problem with no valid inputs
B. A problem requiring no computation
C. A problem with no known efficient algorithm
D. A problem solvable only recursively

2 Which running time is polynomial?

Basic concepts Easy
A.
B.
C.
D.

3 Which running time is exponential?

Basic concepts Easy
A.
B.
C.
D.

4 What is a decision problem?

Basic concepts Easy
A. A problem generating every solution
B. A problem returning yes or no
C. A problem producing a sorted list
D. A problem calculating a real number

5 Why are polynomial-time algorithms generally considered efficient?

Basic concepts Easy
A. They examine only one input
B. Their running time is always constant
C. They use no additional memory
D. Their running time grows at a manageable rate

6 Which problem form asks for the best solution among all feasible solutions?

Basic concepts Easy
A. Decision problem
B. Verification problem
C. Search problem
D. Optimization problem

7 What does a non-deterministic algorithm conceptually do when several choices are available?

Non-deterministic algorithms Easy
A. It sorts the available choices
B. It explores only the first choice
C. It guesses a suitable choice
D. It rejects every possible choice

8 What are the two common conceptual phases of a non-deterministic algorithm?

Non-deterministic algorithms Easy
A. Compilation and execution
B. Encoding and compression
C. Sorting and searching
D. Guessing and verification

9 When does a non-deterministic algorithm accept an input?

Non-deterministic algorithms Easy
A. When no computation path terminates
B. When exactly two computation paths accept
C. When at least one computation path accepts
D. When every computation path rejects

10 In complexity theory, what is a certificate?

Non-deterministic algorithms Easy
A. A candidate solution used for verification
B. A program that generates random inputs
C. A table containing running times
D. A proof that every algorithm is fast

11 How is non-determinism mainly used in the definition of NP?

Non-deterministic algorithms Easy
A. As a programming language feature
B. As a data compression method
C. As a physical computer requirement
D. As a theoretical computation model

12 Which machine model can conceptually branch into multiple computation paths?

Non-deterministic algorithms Easy
A. Non-deterministic Turing machine
B. Sequential access machine
C. Fixed instruction processor
D. Deterministic finite automaton

13 What does the complexity class P contain?

NP-completeness Easy
A. Optimization problems with no solutions
B. Undecidable problems with finite inputs
C. Decision problems solvable in polynomial time
D. Decision problems requiring factorial time

14 What does the complexity class NP contain?

NP-completeness Easy
A. Problems whose solutions are never checkable
B. Problems that have exactly one solution
C. Problems whose certificates are polynomial-time verifiable
D. Problems solvable only with constant memory

15 Which relationship between P and NP is known to be true?

NP-completeness Easy
A.
B.
C.
D.

16 What two conditions must an NP-complete problem satisfy?

NP-completeness Easy
A. It must be in P and undecidable
B. It must be finite and deterministic
C. It must be recursive and exponential
D. It must be in NP and NP-hard

17 What is the purpose of a polynomial-time reduction?

NP-completeness Easy
A. To remove every input from a problem
B. To convert one problem into another efficiently
C. To prove that an algorithm uses no memory
D. To change a decision problem into code

18 Which problem was the first to be proven NP-complete?

NP-completeness Easy
A. Binary Search
B. Boolean Satisfiability
C. Matrix Multiplication
D. Minimum Spanning Tree

19 What would follow if one NP-complete problem were solved in polynomial time?

NP-completeness Easy
A. would be empty
B. would be undecidable
C.
D.

20 How does an NP-hard problem differ from an NP-complete problem?

NP-completeness Easy
A. It must be polynomial-time solvable
B. It need not belong to NP
C. It must have no valid solution
D. It must always belong to P

21 Which statement best describes a decision problem in the complexity class ?

Basic concepts Medium
A. It can be verified only by a nondeterministic algorithm
B. It can be solved only by using polynomial space
C. It requires exponential time for every possible input
D. It can be solved by a deterministic algorithm in polynomial time

22 An algorithm for a problem with input size runs in time, where is a fixed constant. How should its running time be classified with respect to ?

Basic concepts Medium
A. Factorial, because both and appear
B. Exponential, because the expression contains a power of
C. Logarithmic, because does not depend on
D. Polynomial, because is a constant factor

23 Why is the decision version of an optimization problem commonly used in complexity theory?

Basic concepts Medium
A. It guarantees that the resulting problem belongs to
B. It provides a yes-or-no form suitable for complexity-class definitions
C. It eliminates the need to represent candidate solutions
D. It always has a lower running time than the optimization version

24 A dynamic programming algorithm for SUBSET SUM runs in time, where is the target value encoded in binary. Why is this called pseudo-polynomial rather than polynomial?

Basic concepts Medium
A. Its time uses dynamic programming instead of direct enumeration
B. Its time is polynomial only when all input values are distinct
C. Its time depends on both the target value and the number of items
D. Its time is polynomial in but may be exponential in the bit length of

25 Suppose an algorithm examines all subsets of an -element set and spends time on each subset. What is its overall asymptotic running time?

Basic concepts Medium
A.
B.
C.
D.

26 If a decision problem is proved NP-complete, which practical conclusion is most appropriate under the assumption ?

Basic concepts Medium
A. Approximation algorithms cannot be designed for the problem
B. No algorithm can solve any instance of the problem
C. No polynomial-time exact algorithm exists for every instance
D. Every instance requires the same exponential running time

27 How does a nondeterministic algorithm accept an input?

Non-deterministic algorithms Medium
A. It accepts when a randomly selected branch reaches an accepting state
B. It accepts when at least one computation branch reaches an accepting state
C. It accepts when most computation branches reach an accepting state
D. It accepts when every computation branch reaches an accepting state

28 For the CLIQUE decision problem, which object is an appropriate polynomial-size certificate for a yes-instance asking whether a graph has a clique of size ?

Non-deterministic algorithms Medium
A. A list of all paths between every pair of vertices
B. A list of vertices claimed to form a clique
C. A table containing every clique in the entire graph
D. A sequence of all permutations of the graph's vertices

29 A nondeterministic machine guesses a certificate of polynomial length and verifies it in polynomial time. What does this establish about the corresponding decision problem?

Non-deterministic algorithms Medium
A. The problem is undecidable
B. The problem belongs to
C. The problem is NP-hard
D. The problem belongs to

30 A nondeterministic algorithm has polynomially many steps along each branch but exponentially many branches. Why can it still represent an computation?

Non-deterministic algorithms Medium
A. All branches can be merged into one constant-time branch
B. The rejecting branches are excluded from the running time
C. Only the length of each accepting branch must be polynomial
D. The total number of branches must also be polynomial

31 A nondeterministic algorithm for HAMILTONIAN CYCLE first guesses an ordering of all vertices. What should its deterministic verification stage check?

Non-deterministic algorithms Medium
A. Every vertex has the same degree and consecutive vertices have distinct labels
B. Every vertex is reachable from the first through some path in the graph
C. Every vertex appears once and consecutive vertices are joined, including the last and first
D. Every edge appears once and consecutive edges have different endpoint pairs

32 Which statement correctly distinguishes nondeterministic computation from randomized computation?

Non-deterministic algorithms Medium
A. Nondeterminism permits infinite certificates, while randomness permits only finite certificates
B. Nondeterminism solves only search problems, while randomness solves only decision problems
C. Nondeterminism accepts if an accepting choice exists, while randomness assigns probabilities to choices
D. Nondeterminism selects choices uniformly, while randomness always selects the best choice

33 If a nondeterministic polynomial-time algorithm is simulated deterministically by exploring every computation branch, what commonly happens to the running time?

Non-deterministic algorithms Medium
A. It becomes independent of the number of branches
B. It may become exponential in the input size
C. It always remains polynomial in the input size
D. It necessarily becomes logarithmic in the input size

34 Which two conditions are sufficient to prove that a decision problem is NP-complete?

NP-completeness Medium
A. is in , and a known NP-complete problem reduces to
B. is NP-hard, and reduces to every problem in
C. is decidable, and every instance has a unique solution
D. is in , and reduces to a known NP-complete problem

35 To prove that a new problem is NP-hard using a known NP-complete problem , which reduction direction is required?

NP-completeness Medium
A.
B.
C.
D.

36 Suppose and has a polynomial-time algorithm. What follows?

NP-completeness Medium
A. cannot have a polynomial-time verifier
B. must be harder than every problem in
C. also has a polynomial-time algorithm
D. must be NP-complete

37 A polynomial-time algorithm is discovered for one NP-complete problem. Which consequence follows?

NP-completeness Medium
A. becomes undecidable
B.
C. becomes equal to
D.

38 In the standard reduction from 3-SAT to CLIQUE, a 3-SAT formula with clauses is transformed into a graph. What clique size is requested?

NP-completeness Medium
A. , excluding one clause from the selection
B. , selecting two literals from each clause
C. , selecting every literal from each clause
D. , selecting one compatible literal from each clause

39 Which statement about NP-hard problems is correct?

NP-completeness Medium
A. An NP-hard problem need not belong to
B. Every NP-hard problem is also an NP-complete problem
C. Every NP-hard problem has polynomially verifiable certificates
D. An NP-hard problem must be a decision problem in

40 A student proves that a restricted special case of an NP-complete problem can be solved in polynomial time. What can be concluded about the general problem?

NP-completeness Medium
A. Nothing definitive; the unrestricted instances may remain NP-complete
B. The general problem must now belong to
C. The general problem can no longer belong to
D. The restricted case must have been NP-hard as well

41 A numerical problem has input length and largest numeric value . An algorithm solves it in time. Which classification is most accurate when is encoded in binary?

Basic concepts Hard
A. It is exponential because every numerical algorithm requires unary encoding
B. It is strongly polynomial because is part of the input
C. It is pseudo-polynomial because may be exponential in its bit length
D. It is polynomial because the runtime has two factors

42 Suppose a polynomial-time oracle decides whether a Boolean formula is satisfiable. How can a satisfying assignment be recovered when one exists?

Basic concepts Hard
A. Fix variables successively and use at most satisfiability queries
B. Convert to DNF and select a term containing no contradiction
C. Query all assignments and retain the first satisfying assignment
D. Query once because a decision oracle also returns a witness

43 Let be NP-complete under polynomial-time many-one reductions. What follows if ?

Basic concepts Hard
A. becomes complete for PSPACE
B. necessarily follows
C. must have a constant-size certificate
D. necessarily follows

44 Suppose and has a polynomial-time algorithm. Which conclusion is guaranteed?

Basic concepts Hard
A. is NP-hard because it can solve transformed instances of
B. is in P because its instances can be transformed and solved
C. is NP-complete because it reduces to a tractable problem
D. is in coNP because polynomial reductions preserve complements

45 A strongly NP-complete numerical problem admits an algorithm polynomial in and the largest input value . What would this imply?

Basic concepts Hard
A. The equality follows from the bounded-value restriction
B. The problem is weakly NP-complete but remains outside P
C. The equality follows without resolving P versus NP
D. The algorithm is polynomial only when all values use binary encoding

46 For a nondeterministic decision algorithm, which condition correctly characterizes rejection of an input?

Non-deterministic algorithms Hard
A. Every computation branch reaches a rejecting state
B. At least one computation branch reaches a rejecting state
C. More rejecting branches exist than accepting branches
D. The lexicographically first branch reaches a rejecting state

47 Which verifier condition is sufficient to establish that a language belongs to NP?

Non-deterministic algorithms Hard
A. No-instances have polynomial certificates checked by a polynomial-time nondeterministic verifier
B. Yes-instances have arbitrary certificates checked using polynomially many oracle queries
C. Every input has a polynomial certificate accepted by an exponential-time verifier
D. Yes-instances have polynomial certificates checked by a polynomial-time deterministic verifier

48 A nondeterministic machine has at most successors per step and runs for at most steps on every branch, where is constant. What is the direct deterministic simulation bound?

Non-deterministic algorithms Hard
A. by encoding each transition
B. by selecting one canonical branch
C. by grouping branches by depth
D. by exploring the computation tree

49 Which nondeterministic procedure correctly decides whether an -vertex graph contains a Hamiltonian cycle?

Non-deterministic algorithms Hard
A. Guess an arbitrary walk, then accept if its length is at least
B. Guess a vertex subset, then accept if the induced subgraph is connected
C. Guess vertices, then accept if every graph edge appears in the sequence
D. Guess a permutation of all vertices, then verify consecutive and closing edges

50 Given polynomial-time verifiers for and , which certificate proves that is in NP?

Non-deterministic algorithms Hard
A. A certificate rejected by at least one of the two verifiers
B. An exponentially padded certificate shared by both verifiers
C. A certificate for either verifier, selected nondeterministically
D. A pair of certificates accepted by their respective verifiers

51 A proposed NP algorithm guesses a witness of length and verifies it in time polynomial in the witness length. Why does this not establish membership in NP?

Non-deterministic algorithms Hard
A. The witness and branch runtime are exponential in the input length
B. The verifier must reject at least half of all possible witnesses
C. NP forbids guessing because witnesses must be computed deterministically
D. The witness must be unique for every accepted input instance

52 A nondeterministic machine has a polynomial-length accepting branch for every yes-instance, but some other branches loop forever. Does this prove that its language is in NP?

Non-deterministic algorithms Hard
A. Yes, because one short accepting branch is sufficient
B. No, because all branches must execute identical transitions
C. No, because every branch must halt within a polynomial bound
D. Yes, provided no branch accepts any no-instance

53 Given a known NP-complete language , which pair of results is sufficient to prove that a language is NP-complete?

NP-completeness Hard
A. Prove and prove that belongs to NP
B. Prove and prove that belongs to NP
C. Prove and prove that belongs to P
D. Prove and prove that belongs to coNP

54 In the standard reduction from a 3-CNF formula with clauses to CLIQUE, how is the graph constructed?

NP-completeness Hard
A. Create literal-occurrence vertices and join compatible vertices from different clauses
B. Create assignment vertices and join assignments differing in exactly one variable
C. Create one vertex per clause and seek a clique of size three
D. Create one vertex per variable and seek a clique of size

55 For an -vertex graph , which statement correctly relates CLIQUE to VERTEX-COVER?

NP-completeness Hard
A. has a -clique iff has a vertex cover of size at most
B. has a -clique iff has a vertex cover of size at most
C. has a -clique iff has a vertex cover of size at most
D. has a -clique iff has a vertex cover of size at most

56 What key property makes the Cook–Levin reduction polynomial for a nondeterministic machine running in time ?

NP-completeness Hard
A. The entire computation tableau has polynomial dimensions and local constraints
B. The reduction evaluates all branches before constructing the Boolean formula
C. Each nondeterministic branch can be encoded using one Boolean variable
D. Every computation has only a constant number of configurations

57 Suppose produces instances of size , and produces instances of size . What size bound follows for the composed reduction from to ?

NP-completeness Hard
A. because both reduction bounds must be squared
B. because composed reductions need not remain polynomial
C. because reduction exponents are added
D. because the second bound receives an input

58 Assume a sparse language is NP-complete under polynomial-time many-one reductions. Which consequence follows from Mahaney's theorem?

NP-completeness Hard
A. because sparse languages are closed under complement
B. because no sparse language can be NP-complete otherwise
C. because sparse languages have polynomial density
D. is finite because every sparse NP language has constant density

59 Let be NP-complete under many-one reductions, and suppose while . What is the strongest conclusion justified directly?

NP-completeness Hard
A. is NP-complete under many-one reductions
B. belongs to P because adaptive queries preserve tractability
C. is NP-hard but cannot itself belong to NP
D. is NP-complete under polynomial-time Turing reductions

60 In the decision version of TSP with binary-encoded nonnegative edge weights and bound , why is a proposed tour a polynomially verifiable certificate?

NP-completeness Hard
A. Its total weight can be computed using polynomial-time binary arithmetic
B. Every valid tour necessarily has total weight polynomial in the vertex count
C. The verifier needs to compare only the largest edge weight with
D. Binary weights can be replaced by unary weights without increasing input size
Previous MCQ
Unit 12
Next MCQ
Unit 14