Correct Answer: A problem with no known efficient algorithm
Explanation:
An intractable problem has no known algorithm that solves all instances efficiently, typically in polynomial time.
Incorrect! Try again.
2Which running time is polynomial?
Basic concepts
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
is polynomial because the input size is raised to a constant power.
Incorrect! Try again.
3Which running time is exponential?
Basic concepts
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
grows exponentially as the input size increases.
Incorrect! Try again.
4What is a decision problem?
Basic concepts
Easy
A.A problem calculating a real number
B.A problem returning yes or no
C.A problem producing a sorted list
D.A problem generating every solution
Correct Answer: A problem returning yes or no
Explanation:
A decision problem asks a question whose answer is either yes or no.
Incorrect! Try again.
5Why 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
Correct Answer: Their running time grows at a manageable rate
Explanation:
Polynomial running times usually grow more manageably than exponential or factorial running times.
Incorrect! Try again.
6Which problem form asks for the best solution among all feasible solutions?
Basic concepts
Easy
A.Verification problem
B.Decision problem
C.Optimization problem
D.Search problem
Correct Answer: Optimization problem
Explanation:
An optimization problem seeks a feasible solution that minimizes or maximizes an objective.
Incorrect! Try again.
7What does a non-deterministic algorithm conceptually do when several choices are available?
Non-deterministic algorithms
Easy
A.It explores only the first choice
B.It rejects every possible choice
C.It sorts the available choices
D.It guesses a suitable choice
Correct Answer: It guesses a suitable choice
Explanation:
A non-deterministic algorithm is viewed as guessing a candidate choice and then checking it.
Incorrect! Try again.
8What are the two common conceptual phases of a non-deterministic algorithm?
Non-deterministic algorithms
Easy
A.Compilation and execution
B.Sorting and searching
C.Guessing and verification
D.Encoding and compression
Correct Answer: Guessing and verification
Explanation:
A non-deterministic algorithm conceptually guesses a solution and verifies whether it is valid.
Incorrect! Try again.
9When does a non-deterministic algorithm accept an input?
Non-deterministic algorithms
Easy
A.When at least one computation path accepts
B.When no computation path terminates
C.When exactly two computation paths accept
D.When every computation path rejects
Correct Answer: When at least one computation path accepts
Explanation:
A non-deterministic computation accepts if at least one of its possible computation paths accepts.
Incorrect! Try again.
10In 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
Correct Answer: A candidate solution used for verification
Explanation:
A certificate is information representing a proposed solution that a verifier can check.
Incorrect! Try again.
11How is non-determinism mainly used in the definition of NP?
Non-deterministic algorithms
Easy
A.As a physical computer requirement
B.As a programming language feature
C.As a data compression method
D.As a theoretical computation model
Correct Answer: As a theoretical computation model
Explanation:
Non-determinism is a theoretical model used to characterize problems in NP.
Incorrect! Try again.
12Which machine model can conceptually branch into multiple computation paths?
Non-deterministic algorithms
Easy
A.Deterministic finite automaton
B.Fixed instruction processor
C.Non-deterministic Turing machine
D.Sequential access machine
Correct Answer: Non-deterministic Turing machine
Explanation:
A non-deterministic Turing machine can conceptually follow multiple possible computation paths.
Incorrect! Try again.
13What does the complexity class P contain?
NP-completeness
Easy
A.Undecidable problems with finite inputs
B.Optimization problems with no solutions
C.Decision problems solvable in polynomial time
D.Decision problems requiring factorial time
Correct Answer: Decision problems solvable in polynomial time
Explanation:
P is the class of decision problems that deterministic algorithms can solve in polynomial time.
Incorrect! Try again.
14What does the complexity class NP contain?
NP-completeness
Easy
A.Problems that have exactly one solution
B.Problems solvable only with constant memory
C.Problems whose certificates are polynomial-time verifiable
D.Problems whose solutions are never checkable
Correct Answer: Problems whose certificates are polynomial-time verifiable
Explanation:
For problems in NP, a proposed yes-certificate can be verified in polynomial time.
Incorrect! Try again.
15Which relationship between P and NP is known to be true?
NP-completeness
Easy
A.
B.
C.
D.
Correct Answer:
Explanation:
Any problem solvable in polynomial time also has solutions verifiable in polynomial time.
Incorrect! Try again.
16What two conditions must an NP-complete problem satisfy?
NP-completeness
Easy
A.It must be recursive and exponential
B.It must be in NP and NP-hard
C.It must be finite and deterministic
D.It must be in P and undecidable
Correct Answer: It must be in NP and NP-hard
Explanation:
A problem is NP-complete when it belongs to NP and every problem in NP reduces to it in polynomial time.
Incorrect! Try again.
17What 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 change a decision problem into code
D.To prove that an algorithm uses no memory
Correct Answer: To convert one problem into another efficiently
Explanation:
A polynomial-time reduction efficiently transforms instances of one problem into instances of another.
Incorrect! Try again.
18Which problem was the first to be proven NP-complete?
NP-completeness
Easy
A.Binary Search
B.Matrix Multiplication
C.Boolean Satisfiability
D.Minimum Spanning Tree
Correct Answer: Boolean Satisfiability
Explanation:
The Cook–Levin theorem established Boolean Satisfiability, or SAT, as the first NP-complete problem.
Incorrect! Try again.
19What would follow if one NP-complete problem were solved in polynomial time?
NP-completeness
Easy
A. would be empty
B.
C. would be undecidable
D.
Correct Answer:
Explanation:
Every NP problem reduces to an NP-complete problem, so a polynomial-time solution would imply .
Incorrect! Try again.
20How does an NP-hard problem differ from an NP-complete problem?
NP-completeness
Easy
A.It must have no valid solution
B.It must always belong to P
C.It need not belong to NP
D.It must be polynomial-time solvable
Correct Answer: It need not belong to NP
Explanation:
An NP-hard problem is at least as hard as every NP problem, but it does not have to be in NP.
Incorrect! Try again.
21Which statement best describes a decision problem in the complexity class ?
Basic concepts
Medium
A.It can be solved only by using polynomial space
B.It can be solved by a deterministic algorithm in polynomial time
C.It requires exponential time for every possible input
D.It can be verified only by a nondeterministic algorithm
Correct Answer: It can be solved by a deterministic algorithm in polynomial time
Explanation:
contains decision problems solvable by deterministic algorithms in polynomial time with respect to the input size.
Incorrect! Try again.
22An 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.Exponential, because the expression contains a power of
B.Factorial, because both and appear
C.Logarithmic, because does not depend on
D.Polynomial, because is a constant factor
Correct Answer: Polynomial, because is a constant factor
Explanation:
Since is fixed, is constant. The running time therefore grows as with respect to .
Incorrect! Try again.
23Why is the decision version of an optimization problem commonly used in complexity theory?
Basic concepts
Medium
A.It provides a yes-or-no form suitable for complexity-class definitions
B.It guarantees that the resulting problem belongs to
C.It eliminates the need to represent candidate solutions
D.It always has a lower running time than the optimization version
Correct Answer: It provides a yes-or-no form suitable for complexity-class definitions
Explanation:
Classes such as and are formally defined using decision problems, which return either yes or no.
Incorrect! Try again.
24A 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 depends on both the target value and the number of items
B.Its time is polynomial only when all input values are distinct
C.Its time uses dynamic programming instead of direct enumeration
D.Its time is polynomial in but may be exponential in the bit length of
Correct Answer: Its time is polynomial in but may be exponential in the bit length of
Explanation:
A binary representation of uses bits, so a running time proportional to can be exponential in the actual input length.
Incorrect! Try again.
25Suppose 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.
Correct Answer:
Explanation:
An -element set has subsets. Processing each subset in time gives a total of .
Incorrect! Try again.
26If a decision problem is proved NP-complete, which practical conclusion is most appropriate under the assumption ?
Basic concepts
Medium
A.No polynomial-time exact algorithm exists for every instance
B.Approximation algorithms cannot be designed for the problem
C.No algorithm can solve any instance of the problem
D.Every instance requires the same exponential running time
Correct Answer: No polynomial-time exact algorithm exists for every instance
Explanation:
If , an NP-complete problem has no polynomial-time algorithm that correctly solves all instances. Some instances or restricted cases may still be easy.
Incorrect! Try again.
27How does a nondeterministic algorithm accept an input?
Non-deterministic algorithms
Medium
A.It accepts when most computation branches reach an accepting state
B.It accepts when every computation branch reaches an accepting state
C.It accepts when a randomly selected branch reaches an accepting state
D.It accepts when at least one computation branch reaches an accepting state
Correct Answer: It accepts when at least one computation branch reaches an accepting state
Explanation:
Nondeterministic acceptance is existential: an input is accepted if at least one possible computation branch accepts it.
Incorrect! Try again.
28For 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 sequence of all permutations of the graph's vertices
B.A list of vertices claimed to form a clique
C.A table containing every clique in the entire graph
D.A list of all paths between every pair of vertices
Correct Answer: A list of vertices claimed to form a clique
Explanation:
The verifier checks that the list has distinct vertices and that every pair in the list is connected by an edge.
Incorrect! Try again.
29A 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 belongs to
B.The problem belongs to
C.The problem is undecidable
D.The problem is NP-hard
Correct Answer: The problem belongs to
Explanation:
A decision problem is in when every yes-instance has a polynomial-size certificate that a deterministic verifier can check in polynomial time.
Incorrect! Try again.
30A 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.The rejecting branches are excluded from the running time
B.Only the length of each accepting branch must be polynomial
C.All branches can be merged into one constant-time branch
D.The total number of branches must also be polynomial
Correct Answer: Only the length of each accepting branch must be polynomial
Explanation:
Nondeterministic polynomial time limits the number of steps along a branch, not the total number of branches in the computation tree.
Incorrect! Try again.
31A 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 edge appears once and consecutive edges have different endpoint pairs
D.Every vertex appears once and consecutive vertices are joined, including the last and first
Correct Answer: Every vertex appears once and consecutive vertices are joined, including the last and first
Explanation:
The guessed ordering represents a Hamiltonian cycle exactly when it includes each vertex once and all consecutive pairs, including the wraparound pair, are edges.
Incorrect! Try again.
32Which statement correctly distinguishes nondeterministic computation from randomized computation?
Non-deterministic algorithms
Medium
A.Nondeterminism selects choices uniformly, while randomness always selects the best choice
B.Nondeterminism accepts if an accepting choice exists, while randomness assigns probabilities to choices
C.Nondeterminism permits infinite certificates, while randomness permits only finite certificates
D.Nondeterminism solves only search problems, while randomness solves only decision problems
Correct Answer: Nondeterminism accepts if an accepting choice exists, while randomness assigns probabilities to choices
Explanation:
Nondeterminism is a mathematical model based on the existence of an accepting branch; randomized algorithms execute choices according to probability distributions.
Incorrect! Try again.
33If 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 may become exponential in the input size
B.It becomes independent of the number of branches
C.It necessarily becomes logarithmic in the input size
D.It always remains polynomial in the input size
Correct Answer: It may become exponential in the input size
Explanation:
Polynomially many nondeterministic choices can create exponentially many branches, so exhaustive deterministic simulation may require exponential time.
Incorrect! Try again.
34Which two conditions are sufficient to prove that a decision problem is NP-complete?
NP-completeness
Medium
A. is NP-hard, and reduces to every problem in
B. is decidable, and every instance has a unique solution
C. is in , and reduces to a known NP-complete problem
D. is in , and a known NP-complete problem reduces to
Correct Answer: is in , and a known NP-complete problem reduces to
Explanation:
Membership in establishes efficient verification, while a reduction from a known NP-complete problem establishes NP-hardness.
Incorrect! Try again.
35To 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.
Correct Answer:
Explanation:
A polynomial-time reduction from to shows that an efficient algorithm for would also solve the known hard problem efficiently.
Incorrect! Try again.
36Suppose and has a polynomial-time algorithm. What follows?
NP-completeness
Medium
A. must be NP-complete
B. cannot have a polynomial-time verifier
C. also has a polynomial-time algorithm
D. must be harder than every problem in
Correct Answer: also has a polynomial-time algorithm
Explanation:
Transform an instance of into an instance of in polynomial time, then run the polynomial-time algorithm for .
Incorrect! Try again.
37A polynomial-time algorithm is discovered for one NP-complete problem. Which consequence follows?
NP-completeness
Medium
A. becomes equal to
B. becomes undecidable
C.
D.
Correct Answer:
Explanation:
Every problem in reduces in polynomial time to an NP-complete problem. Solving that problem in polynomial time would therefore place all of inside .
Incorrect! Try again.
38In 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
Correct Answer: , selecting one compatible literal from each clause
Explanation:
The construction seeks one mutually compatible literal from each of the clauses, so the target clique has size .
Incorrect! Try again.
39Which statement about NP-hard problems is correct?
NP-completeness
Medium
A.Every NP-hard problem is also an NP-complete problem
B.An NP-hard problem need not belong to
C.An NP-hard problem must be a decision problem in
D.Every NP-hard problem has polynomially verifiable certificates
Correct Answer: An NP-hard problem need not belong to
Explanation:
NP-hardness only means that every problem in reduces to the problem. The problem may be an optimization problem or may even be undecidable.
Incorrect! Try again.
40A 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 restricted case must have been NP-hard as well
C.The general problem can no longer belong to
D.The general problem must now belong to
Correct Answer: Nothing definitive; the unrestricted instances may remain NP-complete
Explanation:
Special cases can be tractable even when the unrestricted problem is NP-complete. A polynomial-time special-case algorithm does not automatically handle all instances.
Incorrect! Try again.
41A 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 strongly polynomial because is part of the input
B.It is exponential because every numerical algorithm requires unary encoding
C.It is pseudo-polynomial because may be exponential in its bit length
D.It is polynomial because the runtime has two factors
Correct Answer: It is pseudo-polynomial because may be exponential in its bit length
Explanation:
Binary encoding uses only bits, so dependence on can be exponential in the actual input length. Such a runtime is pseudo-polynomial.
Incorrect! Try again.
42Suppose 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.Query once because a decision oracle also returns a witness
B.Fix variables successively and use at most satisfiability queries
C.Convert to DNF and select a term containing no contradiction
D.Query all assignments and retain the first satisfying assignment
Correct Answer: Fix variables successively and use at most satisfiability queries
Explanation:
First test satisfiability, then fix each variable to a value that preserves satisfiability. SAT is self-reducible, so only polynomially many oracle calls are needed.
Incorrect! Try again.
43Let be NP-complete under polynomial-time many-one reductions. What follows if ?
Basic concepts
Hard
A. necessarily follows
B. becomes complete for PSPACE
C. necessarily follows
D. must have a constant-size certificate
Correct Answer: necessarily follows
Explanation:
Every language in NP reduces to . Since coNP is closed under inverse polynomial-time many-one reductions, this gives and hence equality.
Incorrect! Try again.
44Suppose and has a polynomial-time algorithm. Which conclusion is guaranteed?
Basic concepts
Hard
A. is in P because its instances can be transformed and solved
B. is NP-complete because it reduces to a tractable problem
C. is in coNP because polynomial reductions preserve complements
D. is NP-hard because it can solve transformed instances of
Correct Answer: is in P because its instances can be transformed and solved
Explanation:
Compute the reduction from to and run the polynomial-time algorithm for . The composition remains polynomial.
Incorrect! Try again.
45A 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 algorithm is polynomial only when all values use binary encoding
D.The equality follows without resolving P versus NP
Correct Answer: The equality follows from the bounded-value restriction
Explanation:
Strong NP-completeness persists when numeric values are polynomially bounded. A pseudo-polynomial algorithm would then run in polynomial time on an NP-hard restriction.
Incorrect! Try again.
46For a nondeterministic decision algorithm, which condition correctly characterizes rejection of an input?
Non-deterministic algorithms
Hard
A.More rejecting branches exist than accepting branches
B.At least one computation branch reaches a rejecting state
C.The lexicographically first branch reaches a rejecting state
D.Every computation branch reaches a rejecting state
Correct Answer: Every computation branch reaches a rejecting state
Explanation:
A nondeterministic machine accepts if at least one branch accepts. Therefore, it rejects exactly when no branch accepts.
Incorrect! Try again.
47Which verifier condition is sufficient to establish that a language belongs to NP?
Non-deterministic algorithms
Hard
A.Yes-instances have polynomial certificates checked by a polynomial-time deterministic verifier
B.No-instances have polynomial certificates checked by a polynomial-time nondeterministic verifier
C.Every input has a polynomial certificate accepted by an exponential-time verifier
D.Yes-instances have arbitrary certificates checked using polynomially many oracle queries
Correct Answer: Yes-instances have polynomial certificates checked by a polynomial-time deterministic verifier
Explanation:
NP consists precisely of languages whose yes-instances possess polynomial-length witnesses verifiable deterministically in polynomial time.
Incorrect! Try again.
48A 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 grouping branches by depth
B. by selecting one canonical branch
C. by encoding each transition
D. by exploring the computation tree
Correct Answer: by exploring the computation tree
Explanation:
The computation tree can contain branches. Exploring each branch adds only polynomial overhead, yielding time when is polynomial.
Incorrect! Try again.
49Which 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 vertices, then accept if every graph edge appears in the sequence
C.Guess a permutation of all vertices, then verify consecutive and closing edges
D.Guess a vertex subset, then accept if the induced subgraph is connected
Correct Answer: Guess a permutation of all vertices, then verify consecutive and closing edges
Explanation:
A Hamiltonian cycle corresponds to an ordering containing every vertex exactly once, with edges between consecutive vertices and from the last vertex back to the first.
Incorrect! Try again.
50Given 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.A pair of certificates accepted by their respective verifiers
C.A certificate for either verifier, selected nondeterministically
D.An exponentially padded certificate shared by both verifiers
Correct Answer: A pair of certificates accepted by their respective verifiers
Explanation:
Concatenate polynomial-length certificates for membership in and , then run both verifiers. The combined verification remains polynomial.
Incorrect! Try again.
51A 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.NP forbids guessing because witnesses must be computed deterministically
B.The verifier must reject at least half of all possible witnesses
C.The witness and branch runtime are exponential in the input length
D.The witness must be unique for every accepted input instance
Correct Answer: The witness and branch runtime are exponential in the input length
Explanation:
NP requires a polynomial-length witness and verification polynomial in the original input length. Polynomial time in an exponentially long witness is still exponential in .
Incorrect! Try again.
52A 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.Yes, provided no branch accepts any no-instance
D.No, because every branch must halt within a polynomial bound
Correct Answer: No, because every branch must halt within a polynomial bound
Explanation:
An NP decider must have a polynomial running-time bound applying to every computation branch. A machine with nonterminating branches does not satisfy that requirement.
Incorrect! Try again.
53Given 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 coNP
B.Prove and prove that belongs to P
C.Prove and prove that belongs to NP
D.Prove and prove that belongs to NP
Correct Answer: Prove and prove that belongs to NP
Explanation:
The reduction establishes NP-hardness of , while supplies the membership condition required for NP-completeness.
Incorrect! Try again.
54In the standard reduction from a 3-CNF formula with clauses to CLIQUE, how is the graph constructed?
NP-completeness
Hard
A.Create assignment vertices and join assignments differing in exactly one variable
B.Create literal-occurrence vertices and join compatible vertices from different clauses
C.Create one vertex per variable and seek a clique of size
D.Create one vertex per clause and seek a clique of size three
Correct Answer: Create literal-occurrence vertices and join compatible vertices from different clauses
Explanation:
Vertices represent literal occurrences. Edges connect noncontradictory literals from distinct clauses, and a clique of size selects one mutually compatible literal per clause.
Incorrect! Try again.
55For 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
Correct Answer: has a -clique iff has a vertex cover of size at most
Explanation:
A clique in is an independent set in . An independent set of size exists exactly when its complement is a vertex cover of size .
Incorrect! Try again.
56What key property makes the Cook–Levin reduction polynomial for a nondeterministic machine running in time ?
NP-completeness
Hard
A.Each nondeterministic branch can be encoded using one Boolean variable
B.Every computation has only a constant number of configurations
C.The entire computation tableau has polynomial dimensions and local constraints
D.The reduction evaluates all branches before constructing the Boolean formula
Correct Answer: The entire computation tableau has polynomial dimensions and local constraints
Explanation:
A -step computation uses a polynomial-size tableau. Boolean clauses enforce the initial configuration, legal local transitions, and an accepting configuration.
Incorrect! Try again.
57Suppose produces instances of size , and produces instances of size . What size bound follows for the composed reduction from to ?
NP-completeness
Hard
A. because the second bound receives an input
B. because reduction exponents are added
C. because composed reductions need not remain polynomial
D. because both reduction bounds must be squared
Correct Answer: because the second bound receives an input
Explanation:
Substituting into gives . Thus polynomial-time many-one reductions are transitive.
Incorrect! Try again.
58Assume a sparse language is NP-complete under polynomial-time many-one reductions. Which consequence follows from Mahaney's theorem?
NP-completeness
Hard
A. because no sparse language can be NP-complete otherwise
B. because sparse languages are closed under complement
C. is finite because every sparse NP language has constant density
D. because sparse languages have polynomial density
Correct Answer: because no sparse language can be NP-complete otherwise
Explanation:
Mahaney's theorem states that an NP-hard sparse language under polynomial-time many-one reductions can exist only if .
Incorrect! Try again.
59Let be NP-complete under many-one reductions, and suppose while . What is the strongest conclusion justified directly?
NP-completeness
Hard
A. belongs to P because adaptive queries preserve tractability
B. is NP-complete under many-one reductions
C. is NP-hard but cannot itself belong to NP
D. is NP-complete under polynomial-time Turing reductions
Correct Answer: is NP-complete under polynomial-time Turing reductions
Explanation:
The given reduction makes NP-hard under Turing reductions, and provides membership. It does not necessarily establish many-one NP-completeness.
Incorrect! Try again.
60In 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.The verifier needs to compare only the largest edge weight with
B.Binary weights can be replaced by unary weights without increasing input size
C.Its total weight can be computed using polynomial-time binary arithmetic
D.Every valid tour necessarily has total weight polynomial in the vertex count
Correct Answer: Its total weight can be computed using polynomial-time binary arithmetic
Explanation:
The verifier checks that the certificate is a permutation forming a tour, adds the binary weights, and compares the sum with , all in polynomial time.
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →