NEW HERE? LEARN MORE
closeclose
Last visit was: 25 Apr 2024, 04:20 It is currently 25 Apr 2024, 04:20
Decision Tracker
My Rewards
New posts
New comers' posts

Close
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

we will pick new questions that match your level based on your Timer History

Track
Your Progress

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History
Not interested in getting valuable practice questions and articles delivered to your email? No problem, unsubscribe here.
Go to My Error Log Learn more
Close
Request Expert Reply
Confirm Cancel

Computer scientists arrange problems solved by computers into categori

Tags:
Find Similar Topics 
Show Tags
Hide Tags
User avatar
L
Sajjad1994
GRE Forum Moderator
Joined: 02 Nov 2016
Posts: 13958
Own Kudos [?]: 32899 [6]
Given Kudos: 5776
GPA: 3.62
Send PM
CAT Tests Forum Quiz Mode
Computer scientists arrange problems solved by computers into categori [#permalink] New post   Updated on: 29 Oct 2023, 12:38
6
Bookmarks
Expert Reply
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.
00:00

Difficulty:

85% (hard)

Question Stats:

24% (03:24) correct 76% (03:42) wrong based on 108 sessions
Hide Show timer Statistics
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.
Submit
Click Submit to add this question to your Error log
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

00:00

Difficulty:

45% (medium)

Question Stats:

72% (01:16) correct 28% (01:55) wrong based on 86 sessions
Hide Show timer Statistics
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.
Submit
Click Submit to add this question to your Error log
ShowHide Answer
Official Answer
There are efficient ways to get close approximations to the actual minimum solution.

00:00

Difficulty:

55% (hard)

Question Stats:

76% (01:13) correct 24% (01:20) wrong based on 79 sessions
Hide Show timer Statistics
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
Submit
Click Submit to add this question to your Error log


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.
Moved to new forum
User avatar
G
andreagonzalez2k
Manager
Manager
Joined: 15 Feb 2021
Posts: 187
Own Kudos [?]: 220 [0]
Given Kudos: 13
Send PM
Re: Computer scientists arrange problems solved by computers into categori [#permalink] New post   14 Apr 2021, 01:01
1- No, No, Yes
2- C
3- C, 27 = 3^3
User avatar
L
Sajjad1994
GRE Forum Moderator
Joined: 02 Nov 2016
Posts: 13958
Own Kudos [?]: 32899 [0]
Given Kudos: 5776
GPA: 3.62
Send PM
CAT Tests Forum Quiz Mode
Re: Computer scientists arrange problems solved by computers into categori [#permalink] New post   15 Apr 2021, 08:27
Expert Reply
OA of this question has been updated, It is:

Q.1

No, No and Yes

Q.2

C

Q.3

C
User avatar
B
asanhu
PM Intern
Joined: 24 Nov 2022
Posts: 1
Own Kudos [?]: 2 [2]
Given Kudos: 0
Location: China
Concentration: Technology, Entrepreneurship
GPA: 4.1
WE:Marketing (Tech)
Send PM
Re: Computer scientists arrange problems solved by computers into categori [#permalink] New post   29 Nov 2022, 19:59
2
Kudos
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
User avatar
B
mjsgmat
Intern
Intern
Joined: 06 Feb 2024
Posts: 1
Own Kudos [?]: 0 [0]
Given Kudos: 3
Send PM
Re: Computer scientists arrange problems solved by computers into categori [#permalink] New post   21 Mar 2024, 20:38
In Problem 2, since we can say the scenario is similar to TSP. Can't we say that the problem can be reduced to GCD as well? Since one NP can be converted to other?

Why isn't (ii) option correct?
User avatar
L
Sajjad1994
GRE Forum Moderator
Joined: 02 Nov 2016
Posts: 13958
Own Kudos [?]: 32899 [0]
Given Kudos: 5776
GPA: 3.62
Send PM
CAT Tests Forum Quiz Mode
Re: Computer scientists arrange problems solved by computers into categori [#permalink] New post   23 Mar 2024, 12:28
Expert Reply
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
GMAT Club Bot
gmatclubot
Re: Computer scientists arrange problems solved by computers into categori [#permalink]
23 Mar 2024, 12:28
Moderators:
Bunuel
Math Expert
92912 posts
BottomJee
DI Forum Moderator
1031 posts
chetan2u
RC & DI Moderator
11172 posts

Powered by phpBB © phpBB Group | Emoji artwork provided by EmojiOne
Main navigation
GMAT Resources
Partners
MBA Resources
www.gmac.com|www.mba.com | | GMAT Club Rules | Terms and Conditions