# ZŁO Homework 2

Wiktor Pilarczyk 451436

## Task 1

We have a formula Boolean formula $\phi$ followed by padding.

The word look like this: $\phi\#...\#$

The word belongs to the language if the formula $\phi$ is satisfiable and the padding length is exactly $2^n$, where n is the length of $\phi$ formula.

I claim that the problem is L-complete.

Firstly, I will show that it can be solved in deterministic logarithmic space.

I will describe a Touring Machine which recognizes if a word belongs to the language.

The process of how this machine works can be divided into two steps:
1. It checks if the padding is correct
2. Then it checks if the formula $\phi$ is satisfiable

In the first step, our machine moves the head to the right until it finds a # and starts counting them (using a binary counter) until it hits the end of the tape. It can be easily checked if the counter is a power of 2, there should be only one 1 in the binary number. To check if it is the correct power of 2 we check if our counter size is the same as $\phi$ size. We used only $O(log(k))$ tape where k is the length of # sequence.

In the second step, we return to the beginning of the input tape.
1. Create a binary counter which will represent if a variable occurrence is true or false. For example for (x v y) ^ x the counter will look like this (1v0)v1, we know that it fits into working tape cause the padding is exponential to the size of the formula. (we keep the symbols like (, ), v and ^ to make it easier to track variables and evaluate the sentence.)
2. Check if the counter is valid for example for (x v y) ^ x counter (1v1)^0 will not be valid. It can be done in a loop, we start from the beginning of the counter and check if a variable occurred previously (if not we continue) and if it has the same evaluation we continue if not we increase the counter. It can be done with two pointers, one going through the counter and the second looking back for previous variable occurrence. It is obvious that their size is less than $log(input \space size)$.
3. If the counter is correct we have to check if the formula is satisfiable. To check it we can copy the counter and we have a formula like (1v0)^1 and we simplify it with certain rules:
* $\lnot1 -> 0$
* $\lnot0 -> 1$
* (1) -> 1
* (0) -> 0
* 0v0 -> 0
* 0v1 -> 1
* 1v0 -> 1
* 1v1 -> 1
* 0^0 -> 0
* 1^0 -> 0
* 0^1 -> 0
* 1^1 -> 1
(also other rules, depends on the format)
Then if we got a 1 at the end the formula is satisfiable and we accept the word otherwise we continue by increasing the counter and repeating the process. The space needed for that is also logarithmic.
4. If the counter will have an overflow (it can be checked when we try to add the carry and it gets out of the counter) it means that the formula is not satisfiable and we reject the word.

We found a machine which solves it in deterministic logarithmic space and we also know from the lecture that "each non-trivial machine in deterministic logarithmic space is L-complete". So this shows that the problem is L-complete.

## Task 2

We have variables in a three-element field and a system of equations. We want to know if there is a variable assignment that makes all equations
true.

I claim that the problem is NP-complete.

The problem is in NP cause it can be solved like SAT problem by non-deterministically assigning the values from our three-elementfield to the variables and then checking if the equations are fullfilled. Calculating the equations is trivial just by going through them.

Now I will show that every problem in NP is reducible by showing that we can solve 3-SAT (the sentence is in CNF) problem using this problem.

We want to find an equivalent representation of the 3-SAT formula in our problem using logarithmic reduction.

We can convert simple formulas to equations like here:
x v y -> $x^2 + y^2 = w_i$
x ^ y -> $x^2 + y^2 + 1 = temp_k; \space\space\space\space\space temp_k^2 - 1 = w_j$

(if we want that on the right site we have only 0 we can just subtract the right side on both sides).
and w represent the evaluation of the formula, 1 and -1 represent true and 0 false.

We see that in the evaluation table such equations correctly represent our formula.

| x value | y value | logic x | logic y | x v y | $w_i$ | x ^ y | $w_j$ |
| ------- | ------- | ------- | ------- | ----- | ----- | ----- | ----- |
| -1 | -1 | 1 | 1 | 1 | -1 | 1 | -1 |
| -1 | 0 | 1 | 0 | 1 | -1 | 0 | 0 |
| -1 | 1 | 1 | 1 | 1 | -1 | 0 | 0 |
| 0 | -1 | 0 | 1 | 1 | -1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | -1 | 0 | 0 |
| 1 | -1 | 1 | 1 | 1 | -1 | 1 | -1 |
| 1 | 0 | 1 | 0 | 1 | -1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | -1 | 0 | 0 |

For formulas in our 3-CNF we want to combine the formulas
x v y v z -> $x^2 + y^2 = temp_l \space\space\space\space\space temp_l^2 + z^2 = temp_{l+1}$

For the negation of a variable for example $\lnot x$ we create equation $x^2-1=temp_k$ and the variable $temp_k$ represents the negation of the variable.

So let's move to how we will convert the 3-SAT formula.

We will need two counters, one for the temporal values to convert the 3 variable alternatives to one variable and to convert the alternative to one variable, the counter will not be bigger than the number of variables so its size is in O(log(n)). We will also have a second counter which we will use to represent the index semi-result of the conjunctions ($w_i$) and it will not be bigger than the number of conjunctions so its size is in O(log(n)).

How the machine will work?
We go through the sentence [...]^(x v y v z) ^... and we know that the evaluation in the square brackets is represented by $w_i$ (i - the second counter) and we output the equations to have $temp_{l+1}$ which will represent the evaluation of formula (x v y v z) (the counter have to be increased two times (if there are negations we have also to increase it by number of negations), one before (initial value is l-1) and one before the first equation to get $temp_l$ and second time for the second equation). In the end we want to create equation $w_i^2 + temp_{l+1}^2 = w_{i+1}$ and continue to go through the formula until the formula ends. With formulas with less then 3 variable we have just simpler case to evaluate.

At the end, we want to add the equations for the last used $w_i$, $w^2_i = 1$ which represents that the whole formula is true.

The reduction is logspace and solves the 3-SAT problem.

We showed that the problem is NP and all problems in NP can be reduced to it by a logarithmic reduction so the problem is NP-complete.

## Task 3

We have an NFA and a CFG and we want to know if their intersection is non-empty.

I claim that the problem is P-complete.

First I will show that the problem is P-hard. We can solve Context Free Grammar Membership using this (it is P-complete), we ask if a word belongs to a CFG, so we want to convert the word to a NFA machine which only accepts the word and check emptiness of the intersection of NFA and CFG will give the answer.

Converting the word to an NFA can be done in logspace. If there is no rule it means that a word is not accpeted, I will need a counter which will be used to number the state and the machine will go through the word and for letter $l_i$ and value of the counter $i$ it will output $(Q_i, l_i, Q_{i+1})$, to get i+1 we will increase the counter and repet the proccess until we go through the whole word (on the last letter we will go to the accepting state or we can add en epsilon transit frome the last state to accepting state). Then we just copy the CFG on the output.
This shows that the problem is P-hard.

Know we want to show that the problem is in P.

I will follow the proof used in script from JAO (theorem 7, page 59). Without loss of generality, I will assume that the productions in our CFG is in Chomsky form if not it can be done in O($n^2$) (so if we do the process it will not change the class of problem, we will still be in P).

Let's construct a CFG, which will answer if the intersection is empty.

Nonterminals of that language will be in the form of (p, X, q), where X is a nonterminal and p and q are states of the automa. The CFG from nonterminal (p, X, q) will generate words w that can be generated from X in our original CFG and in our NFA it has a run from state p and q for word w.

So we will create productions for nonterminals in the original we had $X_i -> X_j X_k$, and for each pair of states p, int and q we will produce productions $(p,X_i,q) -> (p, X_j, r), (r, X_k, q)$ we have to create O(n^3) ($number\_of\_states^3$) such rules for every original rule and we know that the number original rules is also polynomial (cause the tranforming to Chomsky form take polynomial time). Additionally for productions with nonterminals like $X_i -> a$ we want to create productions in the form $(p,X,q)->a$ under the condition that there is a transition in our automa which for a nonterminal moves from state p to q. Creating the rules for nonterminals is also polynomial cause the number of states used is O($n^2$) and the number of rules is polynomial. The proof that such construction is correct can be found on page 59 of Szymon Toruńnczyk's JAO script. Checking that the CFG is nonempty (it is in P) will answer for our question.

We showed that the problem is in P and all problem in P can be reduced to that problem so it is P-complete.