Embedded Files
Level 3 CAT
Level 3 CAT
13COMP & 13DTEC
13COMP & 13DTEC
Date: Friday 23rd October
Date: Friday 23rd October
Time: 1pm to 4pm
Time: 1pm to 4pm
DURATION: 3hrs to complete 91908 (COMP) &/or 91909(DTEC)
DURATION: 3hrs to complete 91908 (COMP) &/or 91909(DTEC)
ROOM: Students will be allocated a room to go to sit the exam (not necessarily with their class).
ROOM: Students will be allocated a room to go to sit the exam (not necessarily with their class).
What exactly is 'complexity and tractability'?
What exactly is 'complexity and tractability'?
From Canterbury Uni's The Computer Science Field Guide (CSFG):
From Canterbury Uni's The Computer Science Field Guide (CSFG):
Are there problems that are too hard even for computers? It turns out that there are. In the chapter on Artificial Intelligence we'll see that just having a conversation – chatting – is something computers can't do well, not because they can't speak but rather because they can't understand or think of sensible things to say. However, that’s not the kind of hard problem we’re talking about here – it's not that computers couldn’t have conversations, more that we don't know just how we do it ourselves and so we can't tell the computer what to do.
Are there problems that are too hard even for computers? It turns out that there are. In the chapter on Artificial Intelligence we'll see that just having a conversation – chatting – is something computers can't do well, not because they can't speak but rather because they can't understand or think of sensible things to say. However, that’s not the kind of hard problem we’re talking about here – it's not that computers couldn’t have conversations, more that we don't know just how we do it ourselves and so we can't tell the computer what to do.
In this chapter we're going to look at problems where it's easy to tell the computer what to do – by writing a program – but the computer can’t do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer either: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem – one where it takes far longer than the lifetime of the fastest computer imaginable to come up with a solution!
In this chapter we're going to look at problems where it's easy to tell the computer what to do – by writing a program – but the computer can’t do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer either: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem – one where it takes far longer than the lifetime of the fastest computer imaginable to come up with a solution!
Page updated
Report abuse