Computer scientists arrange problems solved by computers into categori

Question

Computer scientists arrange problems solved by computers into categories based on the time it takes to solve them.

The time that it takes to solve a polynomial-time problem increases by a constant multiplier each time the size of the problem doubles. For instance, a polynomial time problem might take 5,000 calculations to optimize choices from a selection of 15 objects. Doubling the number of objects to 30 could increase the number of calculations by a factor of 5 to 25,000 calculations. This pattern would continue, with 60 objects requiring 125,000 calculations.

Problems that are solvable in the more complex exponential time increase in complexity by a constant multiplier with each additional item in the problem. If a computer could solve a 30-object exponential problem in 1 hour, adding a 31st object could increase the time required to 2 hours, and a 40-object version would then take that computer 1,024 hours—more than 6 weeks.NP-complete problems are a special class of mathematical puzzles. An NP-complete problem can be converted efficiently to any other NPcomplete problem. It is generally believed, but not proven, that NPcomplete problems require exponential time to solve. A polynomial-time solution for any (and thus every) NP-complete problem would revolutionize mathematics and computer science.A  Traveling Salesman Problem (TSP)  involves connecting multiple points with a single continuous path of the shortest possible distance, without backtracking. TSP's namesake is a common real-life scenario: a sales representative must visit every city on a list while minimizing the distance traveled. The TSP is NP-complete, but certain heuristics can quickly produce routes believed to be within 2–3 percent of the actual minimum.

A  Bounded Knapsack Problem (BKP)  involves selecting the most valuable set of items, constrained by a weight limit, from among a collection of items with different values and weights. The problem's name comes from campers, who must optimize the "value" of their camping equipment within the limits of their knapsacks' capacities. Finding an exact solution to the BKP is NP-complete.

The  Greatest Common Divisor (GCD)  of a set of numbers is the greatest integer that divides into each term of the set without remainder. Other problems involving factoring are notoriously difficult, but finding a common divisor is comparatively easy. The euclidean algorithm finds the GCD in polynomial time.

asanhu · Accepted Answer

On question 1: 
A) NO. First look at tab 3, it mentions "finding an exact solution to the BKP is NP-complete"; Then comes to tab 2 where it presents the characteristics of NP-complete "a polynomial-time solution for any NP-complete problem would be revolutionary", which indicates that NP-complete is not essentially a "polynomial-time" problem, and only "polynomial-time" problem has the features mentioned in question A.
B) YES. First look at tab 3, it mentions "finding an exact solution to the BKP is NP-complete"; Then comes to tab 2 where it presents the characteristics of NP-complete "a polynomial-time solution for any NP-complete problem would be revolutionary".
C) YES. First locate "heuristic" in tab 3's TSP, which is a NP-complete, but certain heuristics can quickly produce approximate solution, and since "finding an exact solution to the BKP is NP-complete", thus, heuristic methods can potentially find an approximate answer (but not exact) to BKP.

On question 2:
We need to determine what is the essence of this "microchip" problem, by looking at " in the minimum distance possible", we can infer that this problem is a derivative of the TSP. And the characteristics of TSP is "using certain heuristics can quickly produce approximate answers".

On question 3：
The question says "assuming the current beliefs about NP-complete problems are true", meaning we can use "polynomial-time solution" to solve the NP-complete problem. Now let's go to tab 1 to find out the method of time calculation. 
"The time that it takes to solve this problem increases by a constant multiplier each time the size of the problem doubles".
Now we need to find out the constant multiplier each time when we add one object into the BKP.
10 objects - 1 min, 11 object - 3 min, so the constant multiplier is 2 each time when we add one object in.
So 12 object = 3*3=9 min, 13 object = 9*3=27min

Sajjad1994 · Answer

Official Explanation

2. A microchip manufacturer wants a continuous electronic circuit to pass once through each semiconductor device on a chip in the minimum distance possible. According to the tabbed information, which of the following is true of the problem faced by the manufacturer?

Explanation

The problem appears to be similar to the TSP. We are told the TSP can be approximated closely by using efficient heuristics. Thus, we can infer that heuristics would also be able to give an efficient approximation for this problem, so  choice (C)  is correct. Answer  choice (A)  is too extreme. A polynomial solution would be revolutionary, but the information given does not suggest it is impossible. The other answer choices are all outside the scope of the information given; there is no way to know that any of them are true based on this information.

Answer: C

SamMenon · Answer

For Question 1 - How can we be sure that heuristics can potentially produce solution to BKP ? It can be true for TSP. Can some one help out?

DmitryFarberMPrep · Answer

The key is in the 2nd tab: " An NP-complete problem can be converted efficiently to any other NP-complete problem." Since the BKP and the TSP are both NP-complete, one can be converted to the other. So any solution for the TSP would also work for the BKP.

GulfTube · Answer

Can someone explain  Q3  to me. Are we supposed to use polynomial or exponential in it and why? and then show me how to do the calculation.

Bunuel

Bunuel · Answer

3. If a computer solves a 10-object BKP in 1 minute and an 11-object BKP in 3 minutes, how long will the computer take to solve a 13-object BKP, assuming that current beliefs about NP-complete problems are true?

BKP is NP complete.

The passage says NP complete problems are believed to require exponential time.

Exponential time means each additional object multiplies the time by the same factor.

10 objects: 1 minute

11 objects: 3 minutes

So the multiplier is 3.

12 objects: 3 * 3 = 9 minutes

13 objects: 9 * 3 = 27 minutes

Answer: 27 minutes.

DishaAgarwal12 · Answer

Can you post official solution of Q1 all parts  bb

Bunuel · Answer

1. Consider the following statements about the BKP. On the basis of the tabbed information, determine whether the statements can be reasonably inferred about the BKP. Indicate yes if a statement can be properly inferred; otherwise indicate no.

• Doubling the number of items in the problem increases the processing time to find the exact solution by a constant multiplier.

Doubling the number of items and increasing the time by a constant multiplier describes polynomial time, not exponential time. BKP is NP-complete, and exact solutions to NP-complete problems are generally believed to require exponential time.

Answer:  no

• An exponential-time solution to this problem, if discovered, would be revolutionary.

The tab says a polynomial-time solution to any NP-complete problem would be revolutionary, not an exponential-time solution.

Answer:  no

• A heuristic method could potentially produce an approximate solution to this problem.

The TSP example shows that an NP-complete problem can have heuristic methods that quickly produce approximate solutions. Since BKP is also NP-complete, it is reasonable to infer that a heuristic method could potentially produce an approximate solution.

Answer:  yes

DishaAgarwal12 · Answer

In statement C, the passage explicitly discusses heuristic approximations only in the context of the Travelling Salesman Problem (TSP), where near-optimal routes can be found efficiently. However, BKP is introduced separately, and the passage does not explicitly state that heuristic methods apply to BKP as well.

Given that TSP is a distance-minimization problem while BKP is a weight/value optimization problem, could you please clarify the basis on which statement C (“A heuristic method could potentially produce an approximate solution to this problem”) is considered a valid inference for BKP specifically?

Bunuel · Answer

C is valid because it says “could potentially,” not “definitely does.”

The passage shows that an NP-complete problem  can  have heuristic approximate solutions. Since BKP is also NP-complete, this possibility can reasonably be inferred.

DishaAgarwal12 · Answer

Can C also be said to be valid from tab 2 "one NP can be converted to another nP"?

Bunuel · Answer

Not really.

That conversion point does not guarantee that a heuristic approximation transfers from TSP to BKP.

C is better supported by “ could potentially ” and by the fact that BKP, like TSP, is an NP-complete optimization problem.

	It is mathematically impossible to find a solution in polynomial time.
	The problem can be mathematically reduced to finding a GCD.
	There are efficient ways to get close approximations to the actual minimum solution.
	The manufacturer cannot solve the problem without the help of expert mathematicians or computer theoreticians.
	Adding 10 more semiconducting devices to the chip would make the problem impossible to solve in a timely manner.

Computer scientists arrange problems solved by computers into categori

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

Yes	No
		Doubling the number of items in the problem increases the processing time to find the exact solution by a constant multiplier.
		An exponential-time solution to this problem, if discovered, would be revolutionary.
		A heuristic method could potentially produce an approximate solution to this problem.

GMAT Multi-Source Reasoning (MSR) Questions

Computer scientists arrange problems solved by computers into categori

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards