Final Exam Review Spring 2003: Questions on Complexity


	Welcome to CS1315. Click on the python to add comments. Looking for the book? They have it at the Engineer's Bookstore at 748 Marietta St NW. Here is there website: http://www.engrbookstore.com/ - Monica

Hotspots: Slides and Code • TA Corner • Comments? • Announcements • FAQ • Static Webspace

Final Exam Review Spring 2003: Questions on Complexity

Questions, answers, comments?

(Back to Sp2003 Final Exam Review)

1. Alan Turning came up with the mathematical definition of what a computer could accomplish. He invented the Turning Machine to determine what is computable by a function. He was basically the father of modern computers and CS.
2. Intractable problems have known solutions but are so hard and big that they can't be solved in a reasonable amount of time. Optimization is an example of an intractable program.
3. No, the traveling salesman problem is class NP, which seems intractable but maybe there is a solution that hasn't been found yet. Kelly Farrell

Very nice! Anything else important that Alan Turing did? Mark Guzdial

Can anyone clarify what the song problem is? Please?
Lauren Biddle

Song problem: You have some 30-60 bits of sound of various lengths. Write a program to create every combination of these sounds, trying to find a song (a) shorter than 2 mins 30 secs for optimal air play and (b) with a good amount of volume change to sound interesting. Mark Guzdial

Angela Liang found this great page on the Traveling Salesman Problem. http://www.math.princeton.edu/tsp/ Mark Guzdial

Turning actually proved that the Halting Problem has no solution.

1. Alan Turning came up with the mathematical definition of what a computer could accomplish. He invented the Turning Machine to determine what is computable by a function. Turning actually proved that the Halting Problem has no solution about 10 years before computers were even built. He was basically the father of modern computers and CS.

Halting Problem: Can we write a program that will input another program (say, from a file) and tell us if the program will ever stop or not?
• Think about while loops with some complex expression—will the expression ever be false?
• Now think about nested while loops, all complex…
 It’s been proven that such a program can never be written.

2. Intractable problems have known solutions but are so hard and big that they can't be solved in a reasonable amount of time given current computer power. Optimization is an example of an intractable program. One example:

 Song problem: Write a program to create a song given:
o You have some 30-60 bits of sound of various lengths.
o Create every combination of these sounds, trying to find a song
 shorter than 2 mins 30 secs for optimal air play
 with a good amount of volume change to sound interesting.
 Current Answer: For n things, every combination of in-or-out is 2^n. If we ignore the empty combination, it’s 2^(n-1), though this is still too large and slow to be computed yet.

3. No, the traveling salesman problem is class NP, which seems intractable but maybe there is a solution that hasn't been found yet.

• Traveling Salesman Problem:
o Imagine that you’re a sales person, and you’re responsible for a bunch of different clients.
 Let’s say 30—half the size of our optimization problem.
o To be efficient, you want to find the shortest path that will let you visit each client exactly once, and not more than once.
• Current answer: The best known algorithm that gives an optimal solution for the Traveling Salesman Problem is O(n!), way too large and slow to be computed yet.

Sorry about the format. Outline style is hard to make. Lauren Biddle

Nice! Mark Guzdial

I know this is irrevelent, but I really think it is funny how everyone is calling him Alan Turning, instead of Turing. Man this week is getting to me! Purposely blank

You're right, Katie! I hadn't even realized that people were saying/typing TurNing. It's Turing. Bell Communications Research made a joke of it years ago – they built a video computing system that let you "visit" from place-to-place with high-resolution video and audio. They called it a "Turing Machine". (Turing's definition of a computer was called a "turing machine".) "Computer humor" :-) Mark Guzdial

Silly computer people..... just like the "u" variable joke on one of the other Final Exam review questions.... =)

Okay, the Traveling Salesman doesn't have a known solution, so it's not intractable? The definitions given here say that an intractable program has a known solution, but it can't be solved in reasonable time. I thought that the Traveling Salesman had a solution but couldn't be solved in a reasonable amount of time. I'm really confused. Is the only difference between them whether or not they have "known solutions"?????? These answers sound contradictory to me.

Okay, I relooked at Lauren's further explanations. So, is the main difference the fact that Traveling Salesman only has an equation to give how long it would take to solve it while the other one has an equation that would just take the computer too long to compute it?

Traveling Salesman has a known solution. You can write a program to solve Traveling Salesman – you can actually do it using only as much Python as we've talked about in this class. (You'd use WHILE or Recursion alot, though, so it'd be hard.) But for any reasonably sized problem, it won't get done in a reasonable amount of time. Did you visit the page that Angela Liang found for us? Somebody solved a Traveling Salesman problem with something like 13,000 cities in Germany. He did it using 110 computers, and it took 26 years of processing time (which may actually mean more like 6 months continuous on the computers, with some cost in time to move partial results from one computer to another). That's a huge cost. The equation part is the equation for the number of steps that it'll take to solve the problem, the "big O". Traveling Salesman is basically O(n!). For just 10 cities, the computer would execute roughly 3,628,800 steps. Not terrible. For 30 cities, that's 265,252,859,812,191,058,636,308,480,000,000 steps. The problem grows insolvable in reasonable time very quickly. The Halting Problem, on the other hand, has no known solution. In fact, Alan Turing proved that you can't solve the Halting Problem in the general case. You can't write a program that can always tell if another program will halt. Mark Guzdial

So, if the Traveling Salesman has a known solution, why isn't it intractable? Why is it NP instead of intractable? By Lauren's definition above, it fits. I don't understand.

Intractable are problems that we know can't be made faster. We don't know that Traveling Salesman can't be made faster. Maybe it can. Maybe someone will figure out a really cool trick that makes it solvable in O(n^4) or something like that. But we don't know yet. We call those problems that seem intractable but we're not sure yet "NP". Halting Problem, by the way, is in none of these. It's just plain not solvable. Mark Guzdial

How do we know that the Optimization problem can't be made faster. Maybe someone will do something really cool with it too. Isn't that just as possible as in the Traveling Salesman?

It turns out that it's provable. I don't think I could explain the proof even if I really understood it, but the reality is that mathemagicians have proven that it can't be made faster. So far, no one has made such a proof of Traveling Salesman. Mark Guzdial

Oh, now it makes sense. I guess, for the purpose of the course, I'll understand Traveling Salesman to be NP and Optimization to be intractable. I'll just assume that these are the only examples given. Otherwise, we'll need your definition you've given above in order to determine if they're intractable or NP.

Link to this Page

Sp2003 Final Exam Review last edited on 30 April 2003 at 10:25 am by lect02.physics.gatech.edu