Okay, welcome to the last SMEI lecture.

If you think this was the last SMEI quiz, that's not actually true, probably.

I'm planning to have another quiz because the quizzes are for you for preparation and so on.

Otherwise we would not be covering the stuff we're going to do today in a quiz.

So we'll somehow do another quiz.

I'll announce it widely, so on the Matrix channel and on the announcement in Stodorn.

So it'll probably just be possibly next week or the week after or so at the usual time.

Unless there's something that tells me otherwise.

So there's a big exam or so that we're completely free.

The idea is that you can actually prepare with another quiz now.

Then it will actually give us more choice to get the best ten exams or later.

So that's at least the plan.

Then there might be an end of semester survey, which is online, clickety-clack, the usual thing.

And at the end you get a token.

If you submit that token to a special quiz that we're making just for that token, then that will be a 100% quiz.

So to give you something for your attention to that quiz.

So there might actually be two more quizzes, so bumping up the total number to 12,

which makes the kind of ten best quizzes idea somewhat reasonable.

Okay, good. So are there any questions about complexity and all of those kind of things?

We didn't really talk about complexities of problems.

There's not a lot of things you can kind of profitably say other than you should probably be aware of how complex certain problems are.

There are books about that and most of the classes will probably say something like,

First order logic satisfiability is undecidable and propositional satisfiable is NP complete,

which means you can do it in NP, non-polynomial, non-deterministic polynomial time.

But there are instances that will need exactly that worst case complexity.

And if you are wondering about certain problems, whether those are NP or not, or NP-hard or not,

then you have to trot out your proof system, up here typically, like we learned it,

and then reduce your problem to say, satisfiability testing.

Or any other problem where the complexity of the problem is now.

Reduce it to a problem in that class, meaning if I can solve this, I can also solve that, so they must be equally hard.

Encode your problem in a Turing machine, or encode your problem as a SAT problem.

And on the other hand, if you want to know whether it's actually, that gives you hardness,

and then for completeness you have to do the embedding in the other way around.

That's kind of how you deal with these things.

But outside of a theoretical computer science lecture, it doesn't really help that much if I'll show you one of these embeddings or not.

Okay, I'm assuming that you've either seen them or read up on this or can imagine what an embedding would look like.

Good. So, I'm going to conclude.

I know. There's also the matter of the exam.

We have an exam date, but we don't have an exam time yet.

That's better than most courses, or many courses, because there's a central person who gives out those, has been in the hospital for a month.

So, you can understand that he's, well actually, he's still until the end of the week, officially in hospital.

But you can imagine that makes things a bit late.

So, we will get a time at some point, and it will be in Campo, and that's all I can do. It's out of my hands.

Yes?

Ha ha. Every professor has been asking that question to the dean and the chancellor.

Why is there only, well, no, the dean, because it's a techfac thing.

Other faculties do, I don't know, may do it differently.

The techfac is actually better organized than most. It's also bigger than others.

Yes, that's a good question.

Because it worked for 20 years, I guess, is the answer.