Events & Promotions
|
|
GMAT Club Daily Prep
Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.
Customized
for You
Track
Your Progress
Practice
Pays
Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.
Jul 1206:30 AM PDT
-08:30 AM PDT
Join our webinar to master GMAT RC Main Point Questions! Learn effective strategies to decipher passage themes and purposes. Senior Verbal Expert- Sunita Singhvi will equip you with tools to navigate complexities and avoid common traps set by the GMAT.
Jul 0901:00 PM EDT
-02:00 PM EDT
More Target Test Prep students are earning 100th percentile GMAT scores. Don’t settle for less when the Target Test Prep course gives you everything you need to score high on the GMAT. Start your 5-day free trial today.
Jul 1311:00 AM EDT
-12:30 PM EDT
Looking for your GMAT motivation to break through the score plateau? Pragati improved her score by massive 160 points with strategic guidance and hard-work! Find out how personalized mentorship and a strong mindset can turn GMAT struggles into success.
Jul 1508:00 PM PDT
-09:00 PM PDT
Full-length FE mock with insightful analytics, weakness diagnosis, and video explanations!
Jul 1611:00 AM EDT
-12:00 PM EDT
Prefer video-based learning? The Target Test Prep OnDemand course is a one-of-a-kind video masterclass featuring 400 hours of lecture-style teaching by Scott Woodbury-Stewart, founder of Target Test Prep and one of the most accomplished GMAT instructors.
Updated on: 29 Oct 2023, 12:38
Originally posted by Sajjad1994 on 13 Apr 2021, 21:00.
Last edited by BottomJee on 29 Oct 2023, 12:38, edited 2 times in total.
Last edited by BottomJee on 29 Oct 2023, 12:38, edited 2 times in total.
Moved to new forum
Kudos
Bookmarks
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.
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.
Doubling the number of items in the problem increases the processing time to find the exact solution by a constant multiplier.: No
An exponential-time solution to this problem, if discovered, would be revolutionary.: No
A heuristic method could potentially produce an approximate solution to this problem.: Yes
Be sure to select an answer first to save it in the Error Log before revealing the correct answer (OA)!
Difficulty:
95%
(hard)
Question Stats:
21% (03:29) correct
79%
(03:31)
wrong
based on 476
sessions
History
Date
Time
Result
Not Attempted Yet
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.
| 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. |
ShowHide Answer
Official Answer
Doubling the number of items in the problem increases the processing time to find the exact solution by a constant multiplier.: No
An exponential-time solution to this problem, if discovered, would be revolutionary.: No
A heuristic method could potentially produce an approximate solution to this problem.: Yes
There are efficient ways to get close approximations to the actual minimum solution.
Be sure to select an answer first to save it in the Error Log before revealing the correct answer (OA)!
Difficulty:
15%
(low)
Question Stats:
80% (01:13) correct
20%
(01:37)
wrong
based on 355
sessions
History
Date
Time
Result
Not Attempted Yet
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?
| 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. |
ShowHide Answer
Official Answer
There are efficient ways to get close approximations to the actual minimum solution.
27 minutes
Be sure to select an answer first to save it in the Error Log before revealing the correct answer (OA)!
Difficulty:
15%
(low)
Question Stats:
78% (01:07) correct
22%
(01:21)
wrong
based on 349
sessions
History
Date
Time
Result
Not Attempted Yet
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?
| 7 minutes | |
| 9 minutes | |
| 27 minutes | |
| 54 minutes | |
| 81 minutes |
ShowHide Answer
Official Answer
27 minutes
29 Nov 2022, 19:59
Kudos
Bookmarks
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
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
General Discussion
14 Apr 2021, 01:01
Kudos
Bookmarks
1- No, No, Yes
2- C
3- C, 27 = 3^3
2- C
3- C, 27 = 3^3
