So again, we're going to look at different variants.

The kind of end-discrete variable ones is what we're going to look at most, where we

basically have variables with infinite domains, we'll have everything exponential, of course.

In the worst case, this information doesn't help you at all, so you're back, you degenerate,

the algorithms actually degenerate to normal search algorithms, which gives you the worst

case here of exponential algorithms, which again gets you into NP-completeness.

Who still remembers NP-completeness?

Good, can you give me a one-line definition or one-line elevator speech?

Too hard to solve.

You can only do very small problems.

We know these are too hard to solve in the worst case.

In the average case, and especially in the cases we care for, often they're quite well

behaved as we will see.

If you start having infinite domains, then integers, strings, all of those kind of things,

that's where it really gets interesting, not like Bundesliga or so, but job scheduling

and all of those kind of things.

Then you kind of need a constraint language where you say that job two can only start

five seconds or five days or whatever five means here after job one.

There the kind of set of the art is that linear constraints are solvable.

That works quite well.

Linear constraints really depends on how non-linear they are.

In general, they're undecidable, but you often can do something about them in special

cases, especially in many special cases we are interested in.

Then if you have continuous variables, it gets arbitrarily nasty.

We're not going to cover it here.

Types of constraints.

We have unary constraints.

Things like, remember Australia?

There is a territory called southern Australia.

You might actually have the constraint that this cannot be green.

For instance, because there's Ayers Rock and you don't want to put it into the green or

whatever.

You have binary constraints.

Things like, since southern Australia is next, shares a border with western Australia, they

cannot have the same color.

You have higher order constraints.

You probably know the famous one where a student writes home.

Essentially, you can have for every letter, you can put in a digit so that this actually

works out.

The parents are supposed to send quite a bit of money.

You can figure it out.

It's a nice little exercise.

There you have constraints of the form D plus E is Y plus minus 10.

Because you can have Ainsim and so on.

Those are relatively interesting constraints.

They're not binary because they're between three digits, possibly four.

Those we can work with, but we're not going to do any of that because you can always decompose

those into binary constraints.

We're going to make our life easy and only do binary constraints.

Then there's what is called preferences, which are not quite constraints because you can