Last time I wrote some stuff on
P versus NP.
This time I want to describe a bit some important **decision problems** -
and .

## Important decision problems

Short reminder on what is **decision problem**:

**Decision problems** are these which have an *output*: **YES** or **NO**.

**Boolean satisfiability problem** () is about checking if given
**propositional logical
formula** is **satisfiable**.
So for example when having formula like this: we want to know
if we can assign to all variables values from to make this formula to **evaluate** to .
In this case to
satisfy this formula all variables can be set to .

It’s proven that is -complete (so every problem
which is in is at least *less hard* than ) and it’s not my point to prove
it here. If you want to find the prove - look for **Cook–Levin theorem**.

Of course there are some variants of problems with some *additional constraints*,
which are
in - for example (when the number of *literals* in *clause* is limited to
).

Because is -complete you can **reduce** any problem from *set*
to . This **reduction** can be used to get a **representation** of your
problem, which makes it easier to describe this problem
using *programming language* or *formal logic*. That’s why there are
plenty of -solvers.

**Quantified Boolean formula** problem () is a *generalization* of -
we just add
**quantifiers** (*for all* - or *exists* - ) to
given **formulas**, for example:
.
Then we want to know if there exists an **evaluation** of variables which **satisfies**
the **formula**.

is a -complete problem, so it seems to be **even harder**
than .
This problem is so important, because it’s all about **reasoning**. If we were able to
have an algorithm which solves in *reasonable time*,
then it would be possible
to **prove theorems automatically** (it is somehow possible, but in *limited* way, for
example using **CoQ**).
There exist some -solvers, which do some heuristics on solution.
They are used in AI, but also in automatic theorem provers.

### So why vs matters?

There are some consequences that we cannot solve and in **reasonable**
time. For example **Artificial Intelligence** still is based on **heuristic algorithms**,
so they can have not
*deterministic* output.

The other thing is that when doing software development it’s nice to know
problems which are in , or even higher **complexity classes**.
If you know it, you will search of some **good heuristics** instead of
writing **non-optimal solution**.

## Leave a Comment