# Question
Title: what is the general name of this problem?
what is the general name of a problems where learning agent observe new data as a learning goes on. For example when playing platformer games one must incrementally learn new level areas and states while remembering all previous states so as to successfully proceed through the level.

# Answer
The machine learning subfield you are asking about is called Data Stream Mining.

(However I'm not sure about its relationship to platform games)
> 2 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Seeking popular science book on bioinformatics or computational genomics
An intelligent 15-year-old I know is interested in both computer science and genetics. I told her that these fields make an excellent combination. I'd like to give her a book on bioinformatics or computational genomics. I'm looking for a fun book, not a textbook. Specifically, it should inspire people to want to study the field, not aim to provide in-depth knowledge itself. I am not interested in books on genetic algorithms. Any suggestions?

# Answer
> 2 votes
this is a very broad question so am going to answer it with decent lists found across the internet most of which are sorted by some criteria (eg bestsellers, top review counts, etc). also there are so many bioinformatics books now and one strategy might be to simply go with your favorite publisher. there are some that come up often in CS areas eg O'Reilly. also, even the "x for Dummies" book series has a bioinformatics title which might be of interest to those who like that publisher. another option is to narrow it down by your algorithmic angle eg there is one based on Python and there are others that emphasize other statistical packages, etc.;

as for your tricky criteria of "inspirational" it may make sense to look for biographies of scientists in the field or stories about successful startups, and if the student is into CS, then programming exercises might verge on "inspirational".

---
Tags: education, books, bioinformatics
---


# Question
Title: Particular techniques for NP-complete problems
Is it possible to show particular classes of techniques (for instance dynamic programming) cannot produce polynomial time algorithms to any NP-complete problem?

# Answer
For such a broad technique as dynamic programming, the answer is almost certainly no. Suppose somebody proves that **P = NP** (and we don't know that they can't) by giving a polynomial-time algorithm for 3SAT. Surely, that algorithm could be rewritten as some kind of trivial dynamic programming, since pretty much any `for` loop can be written as dynamic programming. For example,

```
total=0
for i=1 to n do
    total = total + data[i]
print total

```

can be rewritten as

```
total[n] = data[n]
for i=n-1 downto 1 do
    total[i] = total[i+1] + data[i]
print total[1]

```

However, one result that is in the spirit of a "yes" answer to the question is in Mihalis Yannakakis's paper "Expressing combinatorial optimization problems by Linear Programs" (*Journal of Computer and System Sciences*, 43(3):441-466, 1991; DOI, free PDF). This shows that any symmetric linear program for TSP must have exponential size – a linear program is symmetric if, whenever you permute the main variables, you can permute the auxiliary variables to get back the original program. Yannakakis's paper was, as I understand it, written because Ted Swart had been trying to use linear programming to solve Hamiltonian cycle in **P** and couldn't quite get the very large ($n^8$ to $n^{10}$ variables) linear programs to work.
> 1 votes

---
Tags: algorithms, np-complete
---


# Question
Title: Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$
Let $L\_4$ $\subseteq$ {0,1}$^\*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L\_4$.

I just wanted to check if my grammar is correct or not.

$$A \rightarrow 1B1$$ $$B \rightarrow 0B0\\;|\\;1B\\;|\\;0B\\;|\\;A\\;|\\;\epsilon$$

# Answer
Not exactly, as your $1B$ and $0B$ productions might cause problems. You will accept 1101 for example. I believe just simplyfing it a bit, like this:

$A → 1B1\ |\ 1\ |\ \epsilon$

$B → 0B0\ |\ 1B1\ |\ 1\ |\ 0\ |\ \epsilon$

is enough (if we say that an empty string is a palindrome).
> 0 votes

---
Tags: context-free, formal-grammars
---


title: Rotations in splay trees

text:
# Question
Title: Rotations in splay trees
I am having some difficulties splaying the element 4 to the root. Considering the following splay tree.

```
0
 \
  1
   \
    2
     \
      3
       \
        4

```

Could anyone show me the steps how to get the 4 to the root?

# Answer
Just follow the algorithm. First you have to do a *zag-zag-rotation*, which gives you

```
0
 \
  1
   \
    4
   /
  3
 /
2

```

Then you have to do another *zag-zag-rotation* and you obtain as the result of **splay(4)** the tree

```
    4
   /
  1
 / \
0   3
   /
  2

```
> 1 votes

---
Tags: data-structures, trees, splay-trees
---


# Question
Title: Genetic Algorithm, Neural Network, Deep Learning, Machine Learning Similarities and Applications?
I am a computer engineering student and trying to get the idea behind all these Artificial Intelligence Concepts and applications. I know little theoretically about machine learning and some high level brief introduction of artificial intelligence as a whole and neural network. What i am interested in is knowing the similarities or difference between the concepts: Deep Learning, Genetic Algorithm/Programming, Artificial Neural Networks and Machine Learning. How do they relate or how they help each other? What are their particular applications?

I google a bit but could not satisfy myself with the answers i got. As a beginner i would like to know what particular part they each play in Artificial Intelligence field. What type of problem they each solve and how?

**Update:**

If the question is too broad, i am also expecting a broad answer.Even, if the broad answer is too much then can you please tell me any particular book perhaps that might contain overview of these topics, so that i can relate by myself and go on learning.

# Answer
Here's a quick dictionary:

* **Machine learning** is a very broad subject encompassing mainly algorithms whose goal is classifying inputs to different categories. For example, an automated post system has to be able to read letters and digits. After the characters are segmented into individual characters using techniques from computational geometry, a computerized algorithm converts the images into digits and letters. Such an algorithm is *trained* using classified examples, that is, many examples of each digit and letter which are shown to the algorithm.
* **Neural networks** are a machine learning algorithm loosely based on the works of the nervous system, including the brain. They are examples of the paradigm of **deep learning**.
* **Genetic algorithms** are used to solve optimization problems (i.e. find the most stable structure supporting a bridge). They are loosely based on evolutionary biology.
> 3 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, genetic-algorithms
---


title: Conditional Probabilities as Tensors?

text:
# Question
Title: Conditional Probabilities as Tensors?
Is it proper to view conditional probabilities, such as the forms:

P(a|c)

P(a|c,d)

P(a, b|c, d)

...and so forth, as being tensors?

If so, does anyone know of a decent introductory text (online tutorial, workshop paper, book, etc) which develops tensors in that sense for computer scientists/machine learning practitioners?

I have found a number of papers, but those written at an introductory level are written for physicists, and those written for computer scientists are rather advanced.

# Answer
> 5 votes
This is definitely possible, although the tensor has of course certain additional structure (constraints).

If you consider the following conditional defined for a categorical response $Y$ on categorical predictors $X\_i$:

$P(Y|X\_1,\ldots,X\_n)$

this correspond to a conditional probability tensor of size $d\_0 \cdot d\_1 \cdot \ldots \cdot d\_n$. Here $Y$ (as a categorical response) takes $d\_0$ levels.

Foremost the elements of the tensor have each to be nonnegative.

You can find papers on this, e.g. "Bayesian Conditional Tensor Factorizations for High-Dimensional Classification" by Yang and Dunson (pdf, arxiv).

Of course, if the random variables concerned are not categorical variables, but either continuous random variables or taking an infinite number of values (or both), the mapping to finite tensors won't be so trivial. You'll need something like an infinite tensor (as an extension of an infinite matrix).

---
Tags: machine-learning, probability-theory, statistics
---


# Question
Title: Picking an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$
I've got the following problem:

Tommy has a toy consisting of wooden posts and in each move he can either hit one post (which decreases its height by 1) or pull out a post (which increases its height by one). Tommy wants to set all poles to the same height but he must do that using minimal ammount of moves. How many moves must be made?

An input is a list $\[x\_1,x\_2,...,x\_n\]$ where $x\_i$ is a starting height of pole number $i$.

Mathematically speaking we must find an $m$ which minimises the sum $\sum\_{i=1}^{i=n} |x\_i-m|$ where $x\_i$ is an element of the list $\[x\_1,x\_2,...,x\_n\]$ and then all we need to do is to calculate this sum. But how to find such an $m$? And if I have a candidate for $m$, how to prove that I am right?

# Answer
Rearrange the numbers in sorted order so that you have $x\_1\le x\_2\le \dotsm \le x\_n$. Now let $m$ be the median value, $x\_{\lceil (n/2)\rceil}$, i.e., the value for which half of the elements are greater than or equal to $m$. This will minimize $\sum\_{i=1}^n |x\_i-m|$. (If $n$ is even, any value $m$ in the range $x\_{\lceil (n/2)\rceil}\le m\le x\_{\lceil (n/2)\rceil+1}$ will do for $m$).

For example, if $x\_1=1, x\_2=2, x\_3=4, x\_4=8, x\_5=16$, the median value will be $m=x\_3= 4$ and you'll have $$\begin{array}{ccccccccc} & |x\_1-4| & + & |x\_2-4| & + & |x\_3-4| & + & |x\_4-4| & + & |x\_5-4|\\ =& |1-4| & + & |2-4| & + & |4-4| & + & |8-4| & + & |16-4|\\ =& 3 & + & 2 & + & 0 & + & 4 & + & 12\\ =& 21 &&&&&&&& \end{array}$$

so the minimum value of the sum will be 21.

It's not too difficult to show that this algorithm is correct: inductive proofs for $n$ even and $n$ odd will do it. To see what's going on, try graphing something like $y=|x-1|+|x-3|$ and looking for the $x$ value(s) that minimize this function.
> 5 votes

---
Tags: algorithms, proof-techniques
---


# Question
Title: Single-tape Turing Machines with write-protected input recognize only Regular Languages
Here is the problem:

*Prove that single-tape Turing Machines that cannot write on the portion of the tape containing the input string recognize only regular languages.*

My idea is to prove that this particular TM is equivalent to a DFA.

Using this TM to simulate DFA is very straightforward.

However, when I want to use this DFA to simulate TM, I encounter the problem. For the TM transition $\delta(q,a)=(q',a,R)$, DFA can simulate definitely by reading tape to the right and doing the same state transition.

For $\delta(q,a)=(q',a,L)$, I cannot figure out how to use this DFA or NFA to simulate the left move because the DFA only reads to left and has no stack or something to store.

Should I consider another way? Could anyone give me some hints? Thanks.

# Answer
## Introduction

I thought there might be an error in the original statement of the question, and the OP was no longer around to ask. So I assumed that the tape was read-only everywhere, and wrote a first proof based on that assumption, motivated by the fact that the TM has full Turing power outside the input part of the tape if it can write it, which induces the false belief that it can recognize any RE language.

However, that is not the case: the restriction on writing on the input part of the tape implies that only finite information can be extracted from the input, limited by the number of states on entry and exit of that part of the tape (combined with side of entry and exit). InstructedA is to be credited for remarking in a comment that there is a problem with recognizing any RE language, since it is not possible to make a copy of the input without EVER writing to the original input area,

Hence I wrote a second proof that assumes that only the input section of the tape is read-only, the rest being read-write allowed.

I am keeping both proofs here, as the first did help me find the solution, even though it is not necessary to understand the second proof, is more complex, and is subsumed by the second proof. It can be skipped. However, the weaker proof has the advantage of being constructive (to obtain a FSA equivalent to the Turing Machine), while the more general result is not constructive.

However I am giving first the last and more powerful result. I am a bit surprised that I was not able to find this result, even without proof, elsewhere on the net, or by asking some competent users, and any reference to published work would be welcome.

**Contents:**

* **Turing machines that do not overwrite input accept only regular languages.** *This proof is not constructive.*
* **Turing machines with read-only tapes accept only regular languages.** *It may be skipped as subsumed by previous proof, but it uses a different approach, which has the advantage of being constructive.*

## Turing machines that do not overwrite input accept only regular languages

We recall that, while the TM does not overwrite its input, and is thus read only on its input, **the TM can read and write on the rest of the tape**. The proof relies on the fact that the observational behavior of the TM over an unlnown input can produce only a finite number of different cases. Hence, though the TM has full Turing power just by relying on the rest of its tape, its information on the input, which can be any string in $\Sigma^\*$, is finite, so it can compute only on a finite number of different cases. This gives a different view of the finite character of regular languages, behavioral rather than structural.

We assume that the TM accepts when it enters an accept state.

**Proof.**

We define an **input restricted computations (IRC)** as a (read-only) computation of the TM such that the TM head stays on the input part of the tape, except possibly for the last transition that may move it to a cell immediately at the left or the right of the input area.

A **left input restricted computations** is an IRC that starts on the leftmost symbol of the input. A **right input restricted computations** is an IRC that starts on the rightmost symbol of the input.

We first prove that, for left input restricted computations that start in state $p$, the following languages are regular:

* the language $K\_{Lp\to Lq}$ of input strings such that there is a left input restricted computation, starting in state $p$, that ends on the first cell left of the leftmost input symbol in state $q$;
* the language $K\_{Lp\to Rq}$ of input strings such that there is a left input restricted computation, starting in state $p$, that ends on the first cell right of the rightmost input symbol in state $q$;
* the language $A\_{Lp}$ of input strings such that there is a left input restricted computation, starting in state $p$, that reaches an accept state.

And similarly, for right input restricted computations starting in state $p$, the following similarly defined languages are regular: $K\_{Rp\to Lq}$, $K\_{Rp\to Rq}$, and $A\_{Rp}$.

The 6 proofs rely on the fact that **two-ways non-deterministic finite state automata (2NFA)** recognize regular sets (see Hopcroft+Ullman 1979, pp 36-41, and execise 2.18 page 51). A 2NFA works like a read-only TM on a tape limited to its input, starting initially from the leftmost symbol, and accepting by moving beyond the right end in an accepting state.

In each of the 6 cases, the proof is done by building a 2NFA that mimics the input restricted computations, but with some extra transitions to make sure it can start from the leftmost cell and accept the language by exiting from the rightmost end in an accepting state. For the $K\_{??\to ??}$ languages, the original accepting state of the TM are changed into states leading to a halting non-accepting computation. In two cases, it may be necessary to add an extra cell with a new guard symbol on the left to detect TM computations that would terminate on the left end, so as to make them terminate on the right end.

These languages are defined for all combinations of states $p$ and $q$ of the original Turing machine. They represent all that can be observed (hence known and computed on) of the input by the TM.

If $k$ is the number of states, we thus define $4k^2$ languages $K\_{??\to ??}$ and $2k$ languages $A\_{??}$, hence a total of $4k^2+2k$ languages. Actually, some of these languages can be equal.

These are the only possible input restricted computations of the TM starting on one end of the input. Hence the computations induced by each input string (outside the input section of the tape) are characterised by the set of such languages the input belongs or does not belong to, hence by an intersection of each of these $4k^2+2k$ languages or its complement in $\Sigma^\*$. All these intersections are finite intersections of r$4k^2+2k$ regular languages, or their complement which are also regular, and are therefore regular.

As a consequence, the set of these intersections defines a partition $\mathcal P$ of $\Sigma^\*$ into at most $2^{4k^2+2k}$ regular languages (*at most* because some initial languages may be equal, and some intersections may be too). All strings belonging to the same equivalence class can produce exactly the same behavior, as seen from the ends of the input. This implies that they cannot be distinguished for computation of the Turing Machine, if you abstract away what happens in the read-only input area.

If we take two strings $u$ and $v$ in the same equivalence class of $\mathcal P$ , we can prove, by induction on the number of times the input area is entered, that for any accepting computation of the TM on $u$, there is an accepting TM computation on $v$ that is identical everywhere outside the input area. Hence, either all strings of an equivalence class are accepted, or none is. As a consequence, the language accepted by the TM is a union of equivalence classes of $\mathcal P$. Hence it is a finite union of regular languages, and thus it is a regular language.

To be very complete, we skipped the case of the empty input string. In this case, we just have a normal TM, that can read or write anywhere. If it reaches an accepting state, the empty string is in the language, else it is not. But that has little effect on the fact that the language recognized is regular.

Of course, it is not decidable whether an equivalence class is or is not in the language (the same holds for the empty string). This is a non constructive proof.

QED

## Turing machines with read-only tapes accept only regular languages

*This is subsumed by the previous result. It is kept as it uses a different approach, probably less elegant, and helped me in finding the previous proof by understanding what matters. But it can well be skipped by readers. However, one advantage of this proof is that it is a constructive proof producing a FSA accepting the language. A sketch of a similar proof is given by Hendrik Jan in his answer to a previous similar question, which assumes the whole tape was read-only.*

I assume that the blank symbol that is on the unused part of the tape is never part of the input. This symbol is noted here $\Box$. The TM is supposed to accept when it reaches an accepting state.

The first step of the proof is to show that the head need not ever leave the input area of the tape. We thus analyze what happen when the head moves off the rightmost input symbol. The analysis when moving off the leftmost one is identical.

If we consider that the head has moved on the first blank cell on the right of the input, the TM being in state $q$, we have to understand what can happen. There are actually three cases, that may be simultaneously possible when the TM is non-deterministic:

1. the TM keeps computing for ever, without the head ever coming coming back on the input part of the tape;
2. the TM reaches an (a) accepting or (b) stops in a non-accepting state;
3. the TM head ultimately comes back on the rightmost cell of the input, the finite control being in state $r$.

So we have to analyze the behavior of the TM finite control, when computing on a blank half-tape, starting in state $q$ on the leftmost cell of a blank half-tape, infinite towards the right.

Since the TM does not write, and reads only the blank symbol $\Box$, all the finite control can do is move left or right, and configurations are differentiated only by the position of the head, i.e. by an integer. The tape can be replaced by a counter, starting at $1$, that is incremented when the head moves right and decremented when it moves left, provided we consider only transitions that require the blank symbol on the tape. If the counter goes down to $0$, that correspond to a case of the head coming back on the rightmost input symbol.

A first remark is that we can ignore computations that do not terminate (case 1) or that terminate with rejection (case 2.b) since termination with acceptance is the only relevant case for accepting a string. So we only want to know whether the counter can go down to $0$, and in what state, or whether the computation can reach an accepting state.

We represent the relevant part of the finite state control by a directed graph where the vertices are the states of the TM, and where the edges are the blank transitions, with a weight +1 or -1 depending on whether the head is supposed to move right or left.

We define $A\_R$ the set of state $q$ from which an accepting state can be reached with a positive weighted path.

We also compute the set $E\_R$ of all pairs $(q,r)$ of states such that there is a path of weight $-1$ from $q$ to $r$, but no prefix of that path has a negative weight.

Then we modify the finite state control of the TM as follow (ignoring now all transitions on blank symbol $\Box$):

We create a new accepting state $q\_A$ with no transitions.

For every transition $p,a\mapsto R,q$ you add a transition $p,a\mapsto R,q\_A$ if $q\in A\_R$ (i.e. an acceptance is possible if you are on the rightmost symbol).

For every transition $p,a\mapsto R,q$, and every pair $(q,r)\in E\_R$ you add a dummy-transition $p,a\mapsto S,r$, where $S$ indicates that the head should not move. Since this is not an allowed move with most automata formalizations, these dummy states can be eliminated by transitive closure afterwards.

Once this is completed, we proceed to remove the dummy transitions. For every tape symbol $a$, we build the set $F\_a=\\{(p,r)\mid \text{ there is a dummy transition } p,a\mapsto S,r\\}$, and we consider the transitive closure $F\_a^\*$ of the relation defined by $F\_a$. Then, for every transition $r,a\mapsto L,s$ of the original TM, and every pair $(p,r)\in F\_a^\*$, we add a new transition $p,a\mapsto L,s$. Then all dummy transitions can be removed.

We proceed similarly for the moves of the head left of the input part of the tape, thus reversing left and right, and exchanging $+1$ and $-1$ in the graph weights.

Once this has been done, we remove completely all transitions on blank cells, since the corresponding computation are short-circuited by the new transitions. And we now have a new TM with a head that stays on the input all the time, except when accepting with state $q\_A$, and still recognizes the original language.

We now have to do a few cosmetic changes, so as to make this TM behave exactly like a two-ways NDA (acceptance is only by exiting the input on the right into an eccpting state). Then we can rely on the on the know equivalence between 2-NDA and FSA (see for example Hopcroft+Ullman 1979, page 40) to obtain the proof that the language is regular.

QED
> 13 votes

---
Tags: formal-languages, computability, regular-languages, turing-machines, automata
---


# Question
Title: How to find upper and lower bound without using formula
I'm studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything useful.

Prove the following sum is $\Theta (n^2)$ (we have to find $O(n^2)$ and $\Omega (n^2)$)

1. $P(n)= 1+2+3+4\cdots + n$
2. $P(n) = n+(n+1)+(n+2)+\cdots +2n$

Note you **cannot** use any formula you have to do it my **algebraic manipulation**. This might be simple but I am not getting any clue right now and I dont have solution of it.

# Answer
Another approach:

* $n^2/4=(n/2)^2= \underbrace{n/2 + n/2 +\cdots + n/2}\_{n/2 \text{ times}} \le 1+2+\cdots + n \le \underbrace{n + n +\cdots + n}\_{n \text{ times}} = n^2 $
* $n^2= \underbrace{n + n +\cdots + n}\_{n \text{ times}} \le n+(n+1)+\cdots + 2n \le \underbrace{2n + 2n +\cdots + 2n}\_{n \text{ times}} = 2n^2 $
> 5 votes

# Answer
Hint: For the first case of $P(n)$

1. Rewrite in reveresed order the right side of $P(n)$ to make another expression for $P(n)$.
2. Sum these expressions for $P(n)$
3. Solve the equation for $P(n)$. You should get it something like this. $$ 2 P(n) = n (n+1) \leq (n+1)^2 \in O(n^2) $$

$$ 2 P(n) = n (n+1) \geq n^2 \in \Omega(n^2) $$

Then, $P(n)\in \Theta(n^2)$.

For the second case, you could do the same thing that in the previous one, it just difference by $n$ so factorize it.
> 1 votes

# Answer
Clue: You only need to *prove* it, instead of *finding* it out. Mathematical induction is for this. IMO, this is what the problem wants you to do.
> 0 votes

---
Tags: runtime-analysis, discrete-mathematics
---


# Question
Title: What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$?
I'm still in the process of grokking computational complexity.

However, I came across a statement like the above in an old midterm paper I'm reviewing, and I'm not sure I completely follow its logic.

$NP$ is the class of solveable decision problems that can be verified in polynomial time.

So when we say that $A$ is a NP Complete problem, it is understandably *contained* within the $NP$ class.

However, if $\bar{A}$ is included in the class $NP$, wouldn't these two postulates essentially indicate that ALL problems are $NP$?

Any insight into how to look at this would be much appreciated!

# Answer
> 7 votes
If $A$ is ${\sf NP}$-complete and $\bar A$ is in $\sf NP$ then we can show that ${\sf NP = coNP}$. This would imply that the polynomial hierarchy collapses to the first level, which implies ${\sf NP = coNP = PH}$.

However, this implies **not** that all problems are in NP. Just an easy example. There are problems like the halting that are undecidable, and they will remain undecidable even if ${\sf NP = coNP}$, since the proof that the halting problem is undecidable does not use the concept of $\sf NP$ at all.

---
Tags: np-complete
---


# Question
Title: Can a language recognized by a NFA be recognized by a push down or Turing machine?
Every single NFA has an equivalent DFA representation so that every language recognized by NFA is recognized by the DFA, but is it also true that the language recognized by NFA is recognized by a push down automata and a Turing machine?

# Answer
> 5 votes
A language is recognized by an NFA iff it is regular. It is recognized by a push-down automaton iff it is context-free. It is recognized by a Turing machine iff it is computable. Every regular language is context-free. Every context-free language is computable.

Even without knowing these facts, it is not difficult to simulate an NFA by a push-down automaton and a DFA by a Turing machine.

---
Tags: formal-languages
---


# Question
Title: Language of binary strings divisible by 7
There was a question something like, "Consider the language of all integers converted to **binary form**. The language of all strings divisible by 7 is :

1) Recognizable by a finite-automaton.

2) Recognizable by a Non-deterministic finite-automaton.

3) Recognizable by a deterministic Pushdown Automaton.

4) Recognizable by a Non-deterministic Pushdown Automaton.

5) Not recognizable by any of the above.

I'm curious to know the answer and its reason.

# Answer
> 8 votes
The langauge is regular, so answers 1–4 are all correct.

The (deterministic) automaton has seven states, $0, \dots, 6$ corresponding to the remainder when the number is divided by 7. The initial state is $0$, which is also the only accepting state. We adopt the convention that the empty string represents zero (as does the string "$0$", obviously).

To describe the transition function, suppose you're reading in some binary string and the bits you've read so far correspond to the natural number $n$ and the state you're in is $r=n\\%7$ (the remainder when $n$ is divided by $7$). Let the next bit be $b\in\\{0,1\\}$. When you read that, you'll have seen the number $2n+b$, so you need to move to state

$$r' = (2n+b)\\%7 = (2r+b)\\%7\\,.$$

And, of course, there's nothing special about $7$.

---
Tags: formal-languages, context-free, regular-languages, pushdown-automata
---


# Question
Title: In general, does $f(g)$ and $f(h)$ have the same time complexity?
I thought about this question while looking at a textbook where it wanted me to compare the time complexity of $\lg^\*(n)$ and $\lg^\*(\lg(n))$

Now it is well known that $\lg^\*$ is a tremendously slow growing function, so what is inside of $\lg^\*$ shouldn't contribute to its complexity.

But is it true in general that any $f(g)$ is $O$-equivalent to $f(h)$ where f is a non constant function?

# Answer
> 3 votes
No, $f \circ g$ and $f \circ h$ (to use the standard mathematical notation) do not in general have the same complexity. For example, take $g(x) = 1$ (constant function) and $h(x) = x$ (identity function). Then $(f \circ g)(x) = f(1)$ and $(f \circ h)(x) = f(x)$; these functions only have the same complexity if $f = \Theta(1)$ (i.e. $f$ is asymptotically constant). This shows that the only functions $f$ for which all functions of the form $f \circ g$ have the same complexity are the ones that are asymptotically constant.

With the example $f = \lg^\*$, growth is very slow, so a lot of functions “collapse” when you plug them into $\lg^\*$. Nonetheless it is easy to cancel this collapse: define the function $e(y) = \min\\{x \mid \lg^\*(x) \ge y\\}$. This is essentially an inverse function for $\lg^\*$ (growing by $1$ at increasingly long intervals). With this you can easily construct functions that grow at any rate you like: $f(e(x)) \approx x$, $f(e(x^2)) \approx x^2$, etc.

(N.B. In my mathematical statements, I assume functions from $\mathbb{N}$ to $(0,\infty)$.)

# Answer
> 2 votes
No. First of all, You got the function $f(x) = \lg(x)$. And we know that this function is monotonically increasing. So, In the domain of this function always is true with $\epsilon \in (0, +\infty\]$ $$ \lg(x) \< \lg(x+\epsilon)$$ Cause of that, if you apply in a inequality this function $f$ to each member. This inequality conserves the form. In your example, $x \in \[1, +\infty\]$ $$ \begin{align} \lg(x) &\leq x \\ \lg(\lg(x)) &\leq \lg(x) \end{align} $$ For that, and by definition of landau notation. $\lg(\lg(x)) \in O(\lg(x))$. Remember the definition, specifically the quantifiers (i.e $\exists,\ \forall $). Last but not least. If $g\in O(h)$ and $f$ is monotocally increasing like this case, $(f\circ g)(x)\in O(f\circ h)$.

Now, you are using the a iterative logarithm $\lg^\*$ that is a function define as next:

$$ \lg^\* n := \begin{cases} 0 & \mbox{if } n \le 1; \\ 1 + \lg^\*(\lg n) & \mbox{if } n \> 1 \end{cases} $$

So, this function counts likely the number of times that you need to apply the logarithm function to the argument to achieve an outcome less or equal to 1.

For that, considering a value greater than 1, you have to need more iterations of logarithm with $n$ parameter than a less value, $\lg(n)$. Actually,

$$ \lg^\*(\lg n) \leq 1+ \lg^\*(\lg n) \leq \lg^\* (n) $$

---
Tags: asymptotics
---


# Question
Title: Devise a backtracking algorithm to allocate $p$ projects to $s$ students
There are $p$ projects and $s$ students where $p \le s$. Multiple students can work on the same project but the same student cannot work on multiple projects. All projects must be allocated and all students must have a project. I need to compute and display all possible ways of allocating projects to students under these constraints. Here's an example:

Input:

3 students, 2 projects

Output:

```
   P1      P2
   {1}     {2, 3}
   {2}     {1, 3}
   {3}     {1, 2}
   {1, 2}  {3}
   {1, 3}  {2}
   {2, 3}  {1}

```

In my attempts, I've thought about this as being related to the problem of partitioning the set of students into non empty subsets and then ignoring those partitions which have unacceptable length. i.e. for my example generate:

```
{{1}, {2}, {3}}
{{1}, {2, 3}}
{{2}, {1, 3}}
{{3}, {1, 2}}
{{1, 2, 3}}

```

and ignore the first and last as well as double count the three in the middle as they can be arranged in a two ways (order matters for this problem). I'm not sure however how I would go about generating and filtering these subsets and even whether this is a decent solution for any p or s values.

# Answer
I didn't get what you're exatly asking for? Backtracking **is** the solution. Are you looking for an actual implementation or an explanation of backtracking? Or a better performing approach in terms of runtime.

Here my pseudo code how I would generate all matching solutions.

```
state = [];  //array representing the current state, assigns students to projects

S = [..];    //array containing the students
P = [..];    //array with students
func assign(level) {
  if(level == S.length) {
    if is_valid_state() //ensure each project has at least one student
      output(state);
  }
  for(i = 0; i < P.length; i++) {
    state[level] = i;
    assign(level+1);
  }
}

level(0)

```

Can of course be optimized by moving the final condition atop, but this would be my first thought of how to solving this the least efficient way (in terms of performance).
> 0 votes

---
Tags: algorithms, backtracking
---


# Question
Title: Hash values that are impossible to reach
I was just curious as to if there are (or could by) any hash values that are impossible to compute due to the implementation of the algorithm. For example, SHA-256 produces a value that is 256-bits long. Technically, there are $2^{256}$ possible hash values that can be computed. Is it possible that a specific sequence of 256-bits cannot be generated using the SHA-256 algorithm?

This question is not specific to SHA-256 itself, but any hashing algorithm that follows a uniform distirbution pattern.

# Answer
> 0 votes
Regarding common cryptographic hash functions such as the SHA-2 family, it is highly likely that they are surjective (i.e. all potential $2^{256}$ values of SHA2-256 have a preimage). However, given $y$, finding $x$ such that $\text{SHA2-256}(x) = y$ is believed to be a computationally infeasible problem — that's preimage resistance, one of the defining properties of cryptographic hash functions. It's possible that there's a non-constructive way to provide that SHA2-256, but no such way is known, and as far as I know cryptographers tend to think the only way these functions might be proven surjective is by providing a way to compute inverses, which would mean that the functions would be broken.

To summarize, given $y$, it is probably (in the we-believe-it-but-we-could-be-wrong sense) theoretically possible to find $x$ such that $\text{SHA2-256}(x) = y$, but probably (in the chance-for-a-random-$y$ sense) practically impossible.

Hash functions for applications such as hash tables are a different matter. The point of such functions is to spread the input as wide as possible onto a finite-size output, so it is beneficial to cover as much output range as possible. It's often easy to find preimages for these hash functions, but that isn't guaranteed. A given hash function may or may not cover its whole potential $2^N$ output set.

---
Tags: cryptography, hash
---


# Question
Title: How many comparisons do we need to find min and max of n numbers?
Suppose we have given a list of 100 numbers. Then How can we calculate the minimum number of comparisons required to find the minimum and the maximum of 100 numbers.

Recurrence for the above problem is

$$T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2$$ $$\approx 1.5 \times n - 2$$

hence

$$T(100)=1.5 \times 100 - 2 = 148$$

But by solving like as I've mentioned below, I'm coming up with the ans 162

We can divide list of 100 numbers in two list (50,50). Now upon combining the result of these two list 2 more comparisons will be required. Now recursively we break the lists like below, which will make a binary tree

$$100 \implies (50,50)$$ $$50 \implies (25,25)$$ $$25 \implies (12,13)$$ $$12 \implies (6,6), 13 \implies (6,7)$$ $$6 \implies (3,3), 7 \implies(3,4)$$ $$3 \implies (2,1), 4 \implies (2,2)$$

By combining the results upwards in the tree with 2 comparisons on merging each two lists I'm coming up with ans 162. What am I over counting.

# Answer
You're dividing badly. If you look at your execution tree, you'll notice that most of the leaves on the last level are 3's. This means you'll need 3 comparisons here. For the same cost you could also compare 4 elements. Your efficiency here is 75%.

Your partial trees have to be full to be the most efficient. So you'll need to divide into trees with numbers of elements that are powers of two.

In your case dividing into a left oriented tree it's

```
T(100) = T(64) + T(36) +2
       = T(64) + T(32) + T(4) + 4
       = 94 + 46 + 4 + 4
       = 148

```
> 1 votes

---
Tags: algorithm-analysis, recurrence-relation
---


# Question
Title: Can someone provide a trivial example to the "reduction" procedure used to prove hardness?
I cannot comprehend how you can prove hardness between two NP complete problems.

For example, let X be a NP hard problem, I want to prove Y is also NP hard.

I can do this by reducing X to Y, if Y is as difficult as X then it is NP hard, otherwise it is not.

But how is this done exactly? Do we restate the problem?

When I looked online it was something about reducing 3 SAT problem to Clique problem, but I don't even know what these problem are.

Is there a trivial example showing how this is done? Thanks!

# Answer
Let $\Sigma$ and $\Gamma$ be two finite alphabets and $L\_A$ and $L\_B$ be two languages over $\Sigma$ and $\Gamma$, respectively. A polynomial reduction is a function $f$ from $\Sigma^{\star}$ to $\Gamma^{\star}$, which is computable in polynomial time, such that for all words $x \in \Sigma^{\star}$ it is true that \begin{align} x \in L\_A \iff f(x) \in L\_B. \end{align}

The function $f$ maps words from one language to words from another language. When speaking of problems, we mean the associated decision problems. Decision problem $A$: Given an word $x \in \Sigma^{\star}$, is it true that $x \in L\_A$ (analogous for $B$). Such a word $x \in \Sigma^{\star}$ is also called an instance of the decision problem $A$.

One easy reduction would be the reduction $\mathrm{CLIQUE}$ to $\mathrm{IS}$ (independent set). The languages are defined as follows: \begin{align} CLIQUE = \\{ (G, k) \mid \text{the graph $G$ contains a complete subgraph with $k$ vertices} \\} \\ IS = \\{ (G, k) \mid \text{the graph $G$ contains $k$ vertices, that have no edges between each other} \\} \end{align} The complete subgraph in the first definition is called a *k-clique* and the set of vertices in the second definition is called an *independent set*.

As you already stated in your question, $\mathrm{3SAT}$ can be reduced to $\mathrm{CLIQUE}$, thus $\mathrm{CLIQUE}$ is NP-hard. For proving that $\mathrm{IS}$ is NP-hard, we reduce $\mathrm{CLIQUE}$ to $\mathrm{IS}$: We map each element $(G, k)$ to $(G', k)$, where $G'$ is the complement graph of $G$ (that means two vertices are connected in $G'$ if and only if they are not connected in $G$). We can compute $G'$ in $\mathcal{O}(|V(G)|^2)$ many steps. If we find a clique $H$ in $G$, all nodes of $H$ are connect with each other in $G$. Thus there is no edge between those nodes in the complement graph $G'$, and therefore the nodes of $H$ are an independent set in $G'$. If we find an independent set $U \subseteq V(G')$ with $k$ elements in $G'$, we know that there is no edge between any of the vertices in $U$ in $G'$. Thus there is an edge between any two vertices of $U$ in $G$, and therefore $G$ contains a k-clique.
> 0 votes

# Answer
First of all It may be a good idea to read about SAT and Clique problems. Quite a good point to start your research in NP problems. I'd suggest investigating SAT-3CNF, as it is a flagship example of an NP-Complete (both NP-Hard and in NP itself) problem.

Now, to show that an NP-Hard problem X can be reduced to Y would indeed prove that Y is NP-Hard too. To do that you need to provide a relation that maps X to Y (so for any example from X this function maps it to an example from Y.) What you basically want to show is that being able to solve Y efficiently, you'd be also able to solve X efficiently. Personally I believe you should start by reading about SAT-3CNF and Independent Set problems - there are some great examples explaining how they are equivalent, and the mapping is pretty intuitive. You may read about them, for example, here.

To answer your last question - I believe dealing with NP problems can be treated as non-trivial itself. Therefore I would recommend to spend just some time with them, get used to them and try to understand them, so that you are not just pointlessly trying to memorize problems and solutions.
> 0 votes

---
Tags: complexity-theory, reductions, np-hard
---


title: Is this $LL(1)$ grammar valid?

text:
# Question
Title: Is this $LL(1)$ grammar valid?
Is the following a valid $LL(1)$ grammar:

> $ \begin{align} S &\rightarrow L \\$ \\ L &\rightarrow M L\_2 \\ L\_2 &\rightarrow \underline{::} L \\ L\_2 &\rightarrow \epsilon \\ M &\rightarrow \underline{id} R \\ R &\rightarrow \underline{(} R\_2 \\ R\_2 &\rightarrow M \underline{)} \\ R\_2 &\rightarrow \underline{)} \end{align} $

I am not sure because of $R\_2$ since there are two rules I could apply to reach $\\$$ (*bottom of stack*) or do I understand something wrong here?

So in the parsing table for $R\_2$ under $\\$$ I have the options $R\_2 \rightarrow M \underline{)}$ and $R\_2 \rightarrow \underline{)}$

Could somebody clarify?

# Answer
I believe you have misunderstood what the parsing table does. The parsing table tells for each pair $(A,a)$, where $A$ is a non-terminal symbol and $a$ is a terminal symbol, which grammar rule you have to use so that the next non-terminal symbol produced to the string from the left will be $a$. For example, the symbol $R\_2$ produces either the symbol $id$ by the derivation $$R\_2 \rightarrow M) \rightarrow idR)$$ or the symbol $)$ by $$R\_2 \rightarrow )$$ Thus in the parsing table, $(R\_2, id)$ points to rule "$R\_2 \rightarrow M)$", and $(R\_2,\textrm{'})\textrm{'})$ points to rule "$R\_2 \rightarrow )$". The case $(R\_2, \\$)$ is a parsing error, since the dollar sign cannot be reached from $R\_2$ without first producing either $id$ or $)$. If fact, all other terminal symbols except for $id$ and $)$ are parsing errors.

A grammar is a valid $LL(1)$ grammar if for every pair $(A,a)$ there is only one choice for which grammar rule to use. In our grammar the possibly problematic rules are the ones for $L\_2$ and $R\_2$, because they have two choices. The rest of the non-terminals are clearly unambiguous, as there is only one choice.

I gave the unambiguous parsing table rules $R\_2$ above. For $L\_2$, the only symbols which do not produce a parsing error are $\epsilon$ and $::$. For $\epsilon$ we use the rule $L\_2 \rightarrow \epsilon$, and for $::$ we use the rule $L\_2 \rightarrow :: L$. Therefore the parsing rules for $L\_2$ is also unambiguous, and in conclusion the grammar is a valid $LL(1)$ grammar.
> 0 votes

---
Tags: formal-grammars, parsers
---


title: Definition of a size of type

text:
# Question
Title: Definition of a size of type
In B. Pierce's book "Types and Programming Languages", he talks about the size of types (see pictures below).

I searched the book for a definition but could not find one. I only found a definition for the size of terms, but not for the size of types.

Could someone please explain what Pierce means by the expression "$size(T\_1)$" (marked by yellow in the image below) ?

# Answer
> 5 votes
A *term* in logic and rewriting theory is anything defined by a tree structure that's supposed to represent the syntax of something. It can be a term of a programming language, a type, a kind, a module, etc.

The size of a term is the size of the tree: it's 1 for a leaf, and $\mathit{size}(t) = \mathit{size}(t\_1) + \dots + \mathit{size}(t\_n)$ for a tree $t = C(t\_1,\dots,t\_n)$. The exact definition is often not terribly important: what matters is that the size of a term is strictly larger than the size of any term that appears as a part of it.

In programming language literature, some authors use *term* in this sense, and some authors use *term* for a term of the programming language itself as opposed to types, kinds, modules, etc. The former authors use *expression* for the narrow sense of a term of the programming language itself. Pierce uses *term* in the narrow sense.

The definition of the size follows the same principle no matter what syntactic category the term (in the broader sense) represents. Thus the size of a type is defined as $\mathit{size}(\mathsf{Nat}) = \mathit{size}(\mathsf{Bool}) = 1$, $\mathit{size}(\mathsf{T}\_1 \mathord\rightarrow \mathsf{T}\_2) = 1 + \mathit{size}(\mathsf{T}\_1) + \mathit{size}(\mathsf{T}\_2)$, etc.

When there are multiple syntactic categories, whether terms of another category count depends on the definition chosen by the author. For example, the size of $\lambda x:T. M$ could be defined as $1 + \mathit{size}(M)$, or as $1 + \mathit{size}(T) + \mathit{size}(M)$, or even as $1 + \mathit{size}(x) + \mathit{size}(T) + \mathit{size}(M)$ depending on what is convenient for the matters at hand.

# Answer
> 1 votes
It seems to be a typo:

> p 506 solution to 9.3.2
>
> ".... But this means that size(T1) is strictly greater than size(T1 -\> T2), ..." should read "... size(T1) is equal to size(T1 -\> T2) ..."
>
> \[It is impossible because all types in this system have finite size.\]
>
> Also, there is no formal definition of the "size" of a type. This can be taken to be the number of nodes in its tree representation.

---
Tags: terminology, type-theory, type-checking, types-and-programming-languages
---


# Question
Title: Decidable product with an undecidable projection
I got some problems with building a set, which should looks like this: $S = A\times B \subset N \times N $, where $S$ is decidable but $A$ is undecidable.

Could somebody give me a clue how to actually do this?

# Answer
Let $A$ be set of Turing machines that halt, which is clearly undecidable. Now $B$ needs to be something that helps you decide $A$ (a certificate if you will, in the sense of a certificate for a $NP$ problem). Hint: if a TM halts, it halts in a finite number of steps.
> 1 votes

# Answer
Let $B \subset N^{2}$. Also we know that exist a set, which is enumerable but undecidable (for example, a set of all $n$ so that $U(n, n)$ is defined). This way, we build a $X \times Y$, which is decidable. More precisely, $(x, y) \in X \times Y$ iff $U(x, x)$ stops in $y$ steps. So $X \times Y$ is decidable, but its first projection (a set of $x$ so that $U(x, x)$ is defined) not.
> 0 votes

---
Tags: computability
---


# Question
Title: LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations
Consider a data structure called LazyHeap that supports the following operations:

* INSERT(x): Given an element $x$, insert it into the data structure. It has no cost.
* DELETE(x): Delete $x$ from the data structure. It has no cost.
* RETURN: Return an element $x$ such that its order, if the elements are sorted, satisfies:

$$k/2 - k/100 \le \mathrm{order}(x) \le k/2 + k/100\\,,$$

where $k$ is the number of elements in the data structure (at the time RETURN is called). RETURN also has no cost.

Come up with a strategy for the comparisons so that the running time for any sequence of $n$ operations is less than $1000n$.

I know that sometimes you have to make comparisons between two elements so that you can perform RETURN operation correctly, where one comparison costs one unit. However, I'm not sure where to go from there. Any help would be appreciated!

# Answer
I can't actually see an approach that would provide constant time insert and return of the mid-element in $O(1)$ (and I understand "no cost" to be some constant cost.) I have, however, some ideas that may suggest some solution.

One approach that comes to my mind are two heaps, one MIN and one MAX. The MIN heap would keep al elements greater than the current mid element (satisfying $\frac{k}{2} - \frac{k}{100} ≤ midElement ≤\frac{k}{2} + \frac{k}{100}$) and the MAX heap would store all smaller or equal ones. On INSERT(x) we'd need to keep the heaps as balanced as possible, so we would compare x with the current mid element, add it to the proper heap (MIN if x \> midElement, else MAX) and if the difference between heaps' sizes would grow larger than 1, we'd take an element from the larger one and insert it to the smaller one. However, RETURN would work in $O(log(n))$, as after returning the top of one of the heaps we would need to repair that heap. INSERT would also take $O(log(n))$ and DELETE could be even linear (select the heap in $O(1)$, get to the proper level of it (elements on lower level are too too big/too small) and search the level in $O(n)$).

Another approach would be to keep a balanced tree (like RB-Tree or an AVL-Tree). The top element would always be the mid-element. However, here RETURN would also work in $O(log(n))$ because we'd need to reset the root after removing it. INSERT would also work in $O(log(n))$ for the insert itself + eventual balancing and so would DELETE.

Constant times required ("has no cost") brings Hash-tables to mind. Average INSERT would indeed take $O(1)$ and so would DELETE (if table size and hashing function would be properly designed). As for RETURN - one approach would be to track the inserted elements and keep the index of the current mid-element. If greater or smaller elements were inserted we'd consider selecting the "next mid-element", but this would probably require $O(n)$ time (or at least I can't see any other way doing it). So this would actually cause our RETURN to work in $O(1)$ (if we keep an index of the mid-element), but grow INSERT cost to $O(n)$ (and similarly for DELETE.)
> 1 votes

---
Tags: algorithms, data-structures, heaps
---


title: Understanding transactions

text:
# Question
Title: Understanding transactions
1. In operating systems, Is a transaction a process? Are they the same concept?
2. Does a transaction have the same meaning in database management systems, as in OS?

A database book says

> A transaction is defined as any one execution of a user program in a DBMS and differs from an execution of a program outside the DBMS (e.g., a C program executing on Unix) in important ways. "
>
> a transaction is an execution of a user program, seen by the DBMS as a series of read and write operations.

In OS, a running program = a process, isn't it?
3. Is there some theory about transactions, or is there math theory underlying transaction management?

Thanks!

# Answer
* A transaction in database management system is a collection of tasks to be done by the system with certain guarantees on results depending on the type of the transactions.
* A process in OS is an implementation for a container which runs programs/code. Different kinds of processes (often just two types) have different capabilities.

There is a clear similarity between the two. However, they are different in several ways.

* Transactions do not create new transactions. They have a beginning and an end.
* Processes can create new processes, they have the beginning but they might not have an end

I believe that with PL/SQL, one can manage to accomplish a lot with transaction and with this a transaction might have a close resemblance to a process. For example, with PL/SQL, one can declare variables and use them in the same way that a process stores values and states in its virtual memory address. So in this way, a transaction and a process are very similar. This is about Turing completeness of PL/SQL. Transaction performs task written in PL/SQL language, and process performs task in the OS's programming language (which is the binary code of that OS).

One difference between the two is the way they communicate with each other. Transactions can only communicate indirectly with each other via the results of tasks stored in the database. Process can directly communicate with each other as well as indirectly with each other via side effect on the file system (or similar objects).

So the answer to your question:

1. Transaction is not a process in OS. They are similar concepts, but not the same
2. A program is not a process. This is because a program might be run by multiple processes
3. Of course, there are mathematical models behind transaction. Graphs are often used together with many other things. They use a lot of things in database management system theory. If you want to know more, perhaps a new, specific question will be more appropriate.
> 2 votes

# Answer
I don´t know about transactions in operating systems

A transaction in a database, in layman terms, is a set of instructions that must be done all or none.

For instance, suppose that you want to transfer 200 dollars or euros from your bank account to another bank account. The system has substracted 200 dollars or euros from your account, and is going to add that quantity to the other person but then, there is a failure and the operation cannot be completed. You have lost 200 dollars or euros but the other person doesn´t have the money. To avoid that, they invented transactions.

In a database, a transaction is something similar to this:

```
START TRANSACTION;
UPDATE bank_accounts SET money = money - 200 WHERE user='you'; //You lose 200
UPDATE bank_accounts SET money = money + 200 WHERE user='other_person'; //He wins 200
COMMIT; //Don´t do anything until you get here

```

No instruction is done if is not possible to get to the commit instruction

In this way, if there is an error doing the transaction, nothing gets done, and the error is prevented
> 1 votes

---
Tags: operating-systems, database-theory
---


# Question
Title: PRNG bad seeding and von Neumann unbiasing
Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is useful in production). For example, Marsaglia talked about seeding methods in his May 2003 Communications of the ACM article \[1\]. It feels like a chicken/egg situation. You need a source of high-quality random bits in order to seed your generator, so you can create a source of high-quality random bits.

I was wondering:

Is von Neumann unbiasing a legitimate way to defend against poor seeding of large-period PRNGs? In other words, if I apply von Neumann unbiasing to the bitstream output of Mersenne Twister, does the quality of the stream still depend on how I seeded it?

\[1\] George Marsaglia, "Seeds for random number generators." *Communications of the ACM*, 46(5):90–93, 2003 (ACM page.)

# Answer
Von Neumann unbiasing only works if the random source consists of independent samples. Otherwise it is not guaranteed to produce random bits. More generally, in theoretical computer science there exist objects called *(randomness) extractors* whose job is to extract random bits out of imperfect random sources. Usually they need access to a small number of "high quality" random bits.

In practice, seeding a PRNG is not difficult. There are many legitimate sources of randomness, and using an extractor such as a hash function, you can take a decently sized sample and extract a decently random seed. Once you have a handful of high quality random bits, you can use a PRNG to quickly extract many more seemingly random bits.
> 2 votes

---
Tags: probability-theory, randomness, pseudo-random-generators
---


# Question
Title: What is it called when two problems are similar?
Suppose that there are two problems $P$ and $Q$.

How can I say that "solving $P$ is same thing with solving $Q$"?

For instance, if $P$ is NP-Hard, then we can say "$P$ can be solved in polynomial time iff there exists an algorithm $A$ that solves $Q$ in polynomial time".

There should be a shorter term for this, and I'm sure that is not *similar*.

Is *equivalent* the right word?

# Answer
> 8 votes
In complexity theory we prefer, when possible, to use formal definitions. Two problems $P,Q$ are *polynomially equivalent* if there are polytime functions $f,g$ such that $x \in P$ iff $f(x) \in Q$ and $y \in Q$ iff $g(x) \in P$. This is the usual notion of equivalence in complexity theory.

Sometimes we prefer a coarser notion of equivalence which allows using a problem as an oracle. Two problems $Q,R$ are *polynomially equivalent with respect to oracle reductions* if $Q \in \mathsf{P}^R$ and $R \in \mathsf{P}^Q$, or in other words, $Q$ can be solved in polynomial time with oracle access to $R$, and $R$ can be solved in polynomial time with oracle access to $Q$. Under this notion, 3SAT and co-3SAT (its complement) are equivalent.

Unless I have made a blunder, both these notions are equivalence relations. In both cases, if one problem can be solved in polynomial time, then so can the other. Since the second is more general, it seems to fit your description better, though in complexity theory we usually prefer the finer first notion, or even finer notions such as logspace reducibility and AC0 reducibility.

---
Tags: complexity-theory, terminology
---


# Question
Title: Give an example of a non-regular language $L$ such that $L^*$ is regular
I can't think of an example of a non-regular language $L$ such that $L^\*$ is regular. . Any help ?

# Answer
Define $L=\\{a^nb^n|n\in \mathbb N\\}\cup \\{a,b\\}$

It's not hard to see that while $L$ is not regular, $L^\*=\Sigma^\*$.
> 1 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: If A is polynomial time reducible to B such that B <= A, does it mean B must be a polynomial time algorithm?
I don't understand what it means for A to be polynomial time reducible to B. I'm guessing is that we can revised the algorithm some how such that it becomes B, where B is a polynomial time algorithm.

Can someone point out if I have this completely wrong?

# Answer
> 0 votes
A language $A$ is polynomial time reducible to a language $B$ if there is a polynomial time function $f$ such that $x \in A$ iff $f(x) \in B$. In particular, if $B$ can be solvable in polynomial time, then so can $A$.

There are other notions of reducibility in complexity theory, some stronger than this and some weaker. A weaker notion is polynomial time *oracle* reducibility: $A$ is polynomial time oracle-reducible to $B$ if $A$ can be solved in polynomial time given oracle access to $B$ (this can be defined formally). Stronger notions put more constraints on $f$, such as being computable in logarithmic space.

Weaker notions of reducibility could seem more natural: if $A$ is polynomial time oracle-reducible to $B$ and $B$ can be solved in polynomial time, then so can $A$. Why would we want to put more constraints on our reduction? For example, assuming $\mathsf {NP} \neq \mathsf {coNP}$ (which is a common assumption), an NP-complete cannot be polynomially reduced to its complement. For example, SAT, the language consisting of all satisfiable CNFs, isn't reducible to coSAT, the language consisting of all unsatisfiable CNFs. Intuitively, this seems ludicrous, since if you could find out whether a CNF is unsatisfiable, surely you could find out whether a CNF is satisfiable!

Indeed, Cook first defined NP-hard problems using oracle reduciblity rather than the modern many-one reducibility (described in the first paragraph of this answer). The problem with oracle reducibility is that it is hard to reason about, whereas many-one reducibility leads to a richer complexity theory. Also, the *polynomial hieerarchy*, which mirrors the classical *arithmetical hierarchy* from recursion theory, only makes sense using many-one reducibility. Perhaps in the future you will be able to formulate your own opinion on this matter.

When studying the internal structure of $\mathsf P$, we must use stronger notions, since all non-trivial problems in $\mathsf P$ are polynomially reducible to each other (the only exceptions are $\emptyset$ and $\Sigma^\*$). The most common notions are logspace reducibility, in which $f$ has to be computable in logarithmic space, and the even stronger AC0 reducibility (also known as first-order reducibility), in which $f$ has to be computable by uniform polynomial size circuits having constant depth.

---
Tags: complexity-theory, polynomial-time
---


# Question
Title: Proving that the set of non-universal CFGs is not in NP
How do I prove that $\overline{\mathrm{ALL\_{CFG}}}$ does not fall in NP, where

$\qquad\mathrm{ALL\_{CFG}} = \\{\langle G \rangle \mid G \text{ is a CFG}, L(G) = \Sigma^\* \\}$

# Answer
Hint: Use the fact that universality of context-free grammars (that is, deciding whether $L(G) = \Sigma^\*$) is undecidable.
> 0 votes

---
Tags: complexity-theory, context-free, np
---


# Question
Title: How can this grammar parse such an input?
I've an example which I simply don't get at all.

> Implement an attributed grammar that checks that either
>
> * the word ends in $b$ or
> * each prefix of the word contains at least as many $b$s as $a$s
>
> E.g. the word $bbbbaabaabaa$ is allowed but $abbabaabba$ is not. (I know - what an example!)

However, the grammar looks like this:

> \begin{align} V &\rightarrow S \\ S\_0 &\rightarrow S\_1 a \\ S\_0 &\rightarrow S\_1 b \\ S &\rightarrow \epsilon \end{align}

and I am allowed to extend it to an attributed grammar. But I can't imagine how this can even be parsed from those rules since removing element by element from e.g. $abbab$ will never end up such that a rule can be applied.

What am I missing here?

# Answer
> 2 votes
In attribute grammars, you have variables attached to the symbols in the parse-tree which can take values. Equations attached to the rules specify how these values are propagated through the tree.

For that purpose, different occurences of a non-terminal in the same rule are distinguished by subscripts, so as to distinguish the variables attached to them.

For example the rule $S\_0 \to S\_1 b$ is used in the derivation of the topmost $S$ in the tree. In this occurrence: $S\_0$ stands for the topmost $S$, while $S\_1$ stands for the $S$ just below. So if the second $S$ has a $count$ variable equal to $-2$, then by applying the attribute equation $S\_0.count=S\_1.count+1$, the top $S$ get a count variable equal to $-1$.

Note that the equations are often interpreted as assignments, at least in attribute systems used in compilers. That is what was just done. But there are uses in which it can be seen as unification of logical variables (but you probably have not seen that).

Here the attribute rules are used as assignments, that are computed bottom-up (Synthesized attributes), this is why the variable of the topmost symbol (i.e. with the index 0, left-hand side of the grammar rule) are on the left side of the assignment, and get assigned a value depending on the variables of the symbols corresponding to the right-hand side of the grammar rule. But attribute values can also propagate top-down sometimes and are then called inherited attributes. Synthesized attributes are more frequent, as they are computationally more powerful (but it may come at a price).

The parse tree for aab is

```
      V
      |
      S
     / \
    S   b
   / \
  S   a
 / \
S  a
|
ϵ

```

We associate three attributes to non-terminals:

* *count*: contains the number of $b$ minus the number of $a$ for the terminal string that non-terminal occurrence derives in.
* *ok*: is a boolean variable that is true for an occurrence of a non-terminal $S$ iff the terminal string this non-terminal occurrence derives in has no prefix with more $a$ than $b$. It is true for the non-terminal $V$ iff the terminal string $V$ derives in is acceptable.
* *endb*: is a boolean variable that is true for an occurrence of a non-terminal $S$ iff the terminal string this non-terminal occurrence derives in terminates with a $b$.

Now you have attribute computation associated to rules as follow:

\begin{array}{llll} \text{Grammar}& \text{Attributes computation}\\ V \to S& V.ok=S.ok\vee S.endb \\ S\_0 \to S\_1 a\\;\\;& S\_0.count=S\_1.count-1& S\_0.ok=S\_1.ok\wedge S\_1.count\>0& S\_0.endb=false \\ S\_0 \to S\_1 b& S\_0.count=S\_1.count+1& S\_0.ok=S\_1.ok& S\_0.endb=true \\ S \to \epsilon& S.count=0& S.ok=true \end{array}

# Answer
> 2 votes
In an attribute grammar one assigns values to the nonterminals of the grammar. This is to help evaluating parts of a grammar that are not context-free. One of the simple types is inherited attributes, these are assigned bottom-up in the derivation tree.

The indexes $S\_0$ and $S\_1$ are used here to distingish different occurrences of the nonterminal $S$ in the grammar. A good choice for an attribute here would be the difference of the number of occurrences $b$ and $a$. This number should never be negative according to your specification. I do not know how you are supposed to denote this, but assume the attribute is called $N$. For the rule $S\_0 \to S\_1 a$, the value of $N$ for $S\_1$ determines the value of $N$ for $S\_0$: $S\_0.N = S\_1.N - 1$ (since $S\_0$ has one more $a$ than $S\_1$.

Similarly for the other rule that introduces a $b$.

Now we have to introduce another attribute. In the end we should test whether the last symbol derived is a $b$. So the attribute should remember that letter and test it in the last step $V\to S$ (this is the last step in a bottom-upevaluation).

Again: check your class notes on how to specify alle these details.

Your examples are not clear: $aa$ does not end in a $b$ and neither has it at least as many $b$'s (?!)

---
Tags: formal-grammars, compilers, parsers, attribute-grammars
---


# Question
Title: What will trigger a worst time search for a binary heap and what is the run time?
I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of $\mathcal{O}(n)$ because you will have to go through each and every single node to get to the value you want.

However, many sources state that heap has a worst case of $\mathcal{O}(n\log n)$ for (all?) transactions.

I don't see how you can do $n\log n$ for a monotonically increasing binary heap.

Can someone clarity?

# Answer
Heaps are maintained so that they are always balanced. A heap containing $n$ elements will have height $O(\log n)$. All operations on heaps take time linear in the height.
> 1 votes

---
Tags: data-structures, heaps, priority-queues
---


# Question
Title: How to choose the maximum number of nodes (with constraints) from a graph
Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$.

A positive integer $x$ is given and you want to choose at most $x$ nodes so that

* There is a path connecting all the nodes you choose that doesn't visit any node you haven't chosen. A path can backtrack. This is to say the set of vertices you choose induces a connected subgraph in $G$.
* Each node you choose has weight at least as great as all nodes you haven't chosen.

The goal is to maximize the number of nodes you choose.

Is there a fast algorithm for this problem?

# Answer
> 6 votes
Assume the set of nodes have weights $v\_1 \< v\_2 \< \dots \< v\_n$.

Two observations that follow immediately from your restrictions:

1. Your selection has to be a set of the form $v\_i, v\_{i+1}, \dots, v\_n$.
2. Every chosen node is neighbour of another chosen node.

That is, we want to find

$\qquad\displaystyle \min \\{ i \mid \forall j \geq i\ \exists j' \> j\\,.\ j \in N(j')\\} $

where $N(i)$ denotes the neighbourhood of nodes with (weight-)index $i$.

Therefore, the following algorithm solves the problem in time $O(n \log n)$ (assuming an adjacency matrix):

1. Sort the nodes by weight.
2. Choose nodes greedily from the back of the list as long as the new node is neighbour of one of its predecessors (and you have chosen less than $x$).
3. Output the result.

I'll leave the proofs of correctness and runtime to you.

---

Now, if weights can be equal we may be able to take some more nodes; if $v\_i$ is the first weight we don't pick according to the above algorithm, we have to check all $k$ nodes of weight $v\_i$ we have not checked yet, picking as many as we can. This adds a fix-point iteration with at most $k$ iterations running in time $O(k)$ each.

An alternative is to sort the weights in to buckets and pick reachable nodes from the next smallest buckets. Details again left to the reader.

# Answer
> 3 votes
For general graphs, determining if there exists a solution of exact $x$ nodes is NP-complete, and therefore the problem is also NP-complete for general graphs. The proof reduces the Set-Cover (SC) problem to this problem. An instance of SC includes a collection $C$ of subsets $S\_j$ of a universal set $U=\\{u\_i\mid 1\leq i\leq N\\}$, and we want to determine if there exist $k$ subsets in $C$ such that their union is $U$. For each $S\_j$ and each $u\_i$ we construct a node. The weight of each $S\_j$ is one and each $u\_i$ has weight two. Connect all $u\_i$ into a clique and all $S\_j$ form an independent set. An edge $(u\_i,S\_j)$ exists iff $u\_i\in S\_j$. Now we can easily show that there is a $k$-subset SC iff there is a solution of $x=N+k$ nodes for this problem since such a solution must include all $u\_j$, according to the weight constraint.

For your problem, the input is a tree (connected undirected acyclic graph), and we can solve it in polynomial time as follows. First we show how to determine a solution with smallest weight $w$. Find the subgraph $H(w)$ induced by nodes of weight at least $w$. If $H(w)$ is disconnected, then no solutions. If it is connected and the number of nodes is smaller than or equal to $x$, then return yes. If it has too many nodes, repeatedly delete a leaf of weight $w$. In the deletion process, if no leaves of weight $w$, then return no solutions. Using a binary search on $w$, the problem can be solved in $O(n\log n)$.

# Answer
> 0 votes
mentioned this following idea in chat w/you, expanding into answer. dont know why the following wont work. its $O(n^2)$. (other solutions may be faster but on the other hand not all the other answers calculate their complexity.) this does succeed in the criteria of "fast" in the sense of efficient/ PTime.

consider that greedy algorithms sometimes give the optimum with trees eg as with the minimum spanning tree algorithm where this problem has similarities.

imagine an MST-like algorithm but using node weights instead of edge weights. nodes have an analogous adjacency to a tree just as edges do. so start at each initial node, and generate sequentially an MST-like tree expanding outward, and stop only when condition (2) in your requirements kicks in. each of the $n$ nodes could lead to up to $n$ steps hence the quadratic complexity.

furthermore if you start in order of the largest weights 1st, the 1st solution found would be correct.

this solution seems to be similar to R's but is maybe not identical. (R made a comment in chat that might be interpreted as stating his algorithm is not correct based on new edits to your problem.)

---
Tags: algorithms, graphs, optimization, trees
---


# Question
Title: Can't see how this can be true: any connected undirected graph $G$ contains vertex v such that removing v results in another connected Graph $G'$
I am attempting to prove this result but I found a case where I can easily disprove this statement.

> Suppose $G$ is a graph with two nodes u, v and an edge (u,v) and respective self edges, then removing the edge u,v results in two nodes left, therefore leaving the resulting graph disconnected.

Can someone show me why I am approaching this question incorrectly?

# Answer
> 3 votes
Suppose to the contrary that removing any vertex of a finite graph $G$ would disconnect it. Then $G$ could not contain any cycles (else we'd have an immediate contradiction) and so $G$ would have to be a tree. However, removing a leaf vertex of $G$ wouldn't disconnect it, contrary again to our assumption.

# Answer
> 1 votes
The question asks you to remove a *vertex* rather than an edge. Also, undirected graphs usually don't have self-loops, and in the context of undirected graphs, undirected edges are usually not thought of as consisting of two directed edges, but rather as being indivisible.

In your example, removing either A or B results in a connected graph.

---
Tags: graphs
---


title: Algorithms: Difference Constraints

text:
# Question
Title: Algorithms: Difference Constraints
I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem:

> Consider the following set of difference constraints:
>
> ```
> x1 - x4 <= 1
> x2 - x1 <= 2
> x2 - x4 <= 0
> x3 - x1 <= 1
> x4 - x1 <= -1
> x4 - x3 <= -2
>
> ```
>
> What is the solution that will be provided by the shortest path based algorithm for this set of constraints?

I know that you are supposed to create a graph using these constraints, so that there is one edge per constraint and one node per variable. So, for this problem, there would be four nodes: x1, x2, x3, and x4. There would also be six edges because there are six constraints. The first constraint should make an edge from x4 to x1 with a weight of 1. The second constraint should make an edge from x1 to x2 with a weight of 2. The rest of the constraints are made into edges following the same pattern.

So after you create the graph, you're supposed to run a shortest path algorithm on it, and it somehow gives you the values for each variable. This is the part that I am unsure about.

The answer that I got when I did this was that `x1 = 0, x2 = -1, x3 = 0`, and `x4 = -2`. Unfortunately, this doesn't work because of the first and third constraints.

Can someone walk me through how to get the right answer using the shortest path based algorithm for this question? Thanks!

# Answer
> 2 votes
I think what you ask for is the AOE (Activity on edge) network, which is a popular tool for project management. Each $x\_i$ is a check point, and an arc (directed edge) $(x\_i,x\_j)$ of weight $w\_{ij}$ means there is an activity which takes $w\_{ij}$ time and can only start after we reach $x\_j$. You can rewrite all the constraints in the form $x\_j\geq x\_i+w\_{ij}$.

Usually we add a dummy source with zero-weight arc to all $x\_i$ of in-degree zero and a dummy sink with zero-weight arc from all vertices of out-degree zero. The graph must be a dag (directed acyclic graph), or otherwise there is no solution. Then we can find for each vertex the longest path length from source, which is the so-called earliest starting time. All the earliest starting times form a feasible solution (values of $x\_i$). A critical path is a longest path from the source to the sink, and the path length is the minimum total time we can complete the project.

BTW, finding single-source all-destination longest paths can be easily done in linear time, using a standard dynamic programming. (I think the textbook of data structure by Horowitz and Sahni contains this topic)

# Answer
> 5 votes
You seem to already know the correct procedure but you have calculated the shortest paths incorrectly.

Procedure:

1. Create a source vertex ($s$) and add zero-weight edges from the source to all vertices.
2. Compute single-source shortest path from the source to each vertex. (If a negative-weight cycle exists, there is no solution to the set of constraints.)
3. The constraints are solved by assignments $x\_i = \delta(s, x\_i)$ where $\delta(s, x\_i)$ is the shortest path from $s$ to $x\_i$.

```
x1 = -1 (s -> x3 -> x4 -> x1)
x2 = -2 (s -> x3 -> x4 -> x2)
x3 =  0 (s -> x3)
x4 = -2 (s -> x3 -> x4)

```

Source: See slides 6-10 of http://courses.csail.mit.edu/6.006/spring11/lectures/lec17.pdf

---
Tags: algorithms, shortest-path
---


# Question
Title: Why do we believe that PSPACE ≠ EXPTIME?
I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, then how can there be a class of problems that experience greater exponential time blowup and do not make use of exponential space?

Yuval Filmus' answer is already extremely helpful. However, could anyone sketch my a loose argument why it *might* be the case that PSPACE ≠ EXPTIME (i.e. that PSPACE is not a proper subset of EXPTIME)? Won't we need exponential space in order to beat the upperbound for the total number of system configurations achievable with space that scales polynomially with input size? Just to say, I can understand why EXPTIME ≠ EXPSPACE is an open matter, but I lack understanding regarding the relationship between PSPACE and EXPTIME.

# Answer
Let's refresh the definitions.

* **PSPACE** is the class of problems that can be solved on a deterministic Turing machine with polynomial space bounds: that is, for each such problem, there is a machine that decides the problem using at most $p(n)$ tape cells when its input has length $n$, for some polynomial $p$.
* **EXP** is the class of problems that can be solved on a deterministic Turing machine with exponential time bounds: for each such problem, there is a machine that decides the problem using at most $2^{p(n)}$ steps when its input has length $n$, for some polynomial $p$.

First, we should say that these two classes might be equal. They seem more likely to be different but classes sometimes turn out to be the same: for example, in 2004, Reingold proved that symmetric logspace is the same as ordinary logspace; in 1987, Immerman and Szelepcsényi independently proved that **NL$\\;=\\;$co-NL** (and, in fact, that **NSPACE\[$f(n)$\]$\\;=\\;$co-NSPACE\[$f(n)$\]** for any $f(n)\geq \log n$).

But, at the moment, most people believe that **PSPACE** and **EXP** are different. Why? Let's look at what we can do in the two complexity classes. Consider a problem in **PSPACE**. We're allowed to use $p(n)$ tape cells to solve an input of length $n$ but it's hard to compare that against **EXP**, which is specified by a time bound.

How much time can we use for a **PSPACE** problem? If we only write to $p(n)$ tape cells, there are $2^{p(n)}$ different strings that could appear on the tape, assuming a binary alphabet. The tape head could be in any of $p(n)$ different places and the Turing machine could be in one of $k$ different states. So the total number of configurations is $T(n) = k\\,p(n)\\,2^{p(n)}\\!$. By the pigeonhole principle, if we run for $T(n)+1$ steps, we must visit a configuration twice but, since the machine is deterministic, that means it will loop around and visit that same configuration infinitely often, i.e., it won't halt. Since part of the definition of being in **PSPACE** is that you have to *decide* the problem, any machine that doesn't terminate doesn't solve a **PSPACE** problem. In other words, **PSPACE** is the class of problems that are decidable using at most $p(n)$ space and at most $k\\,p(n)\\,2^{p(n)}$ time, which is at most $2^{q(n)}$ for some polynomial $q$. So we've shown that **PSPACE$\\;\subseteq\\;$EXP**.

And how much space can we use for an **EXP** problem? Well, we're allowed $2^{p(n)}$ steps and the head of a Turing machine can only move one position at each step. Since the head can't move more than $2^{p(n)}$ positions, we can only use that many tape cells.

That's what the difference is: although both **PSPACE** and **EXP** are problems that can be solved in exponential time, **PSPACE** is restricted to polynomial space use, whereas **EXP** can use exponential space. That already suggests that **EXP** ought to be more powerful. For example, suppose you're trying to solve a problem about graphs. In **PSPACE**, you can look at every subset of the vertices (it only takes $n$ bits to write down a subset). You can use some working space to compute on each subset but, once you've finished working on a subset, you must erase that working space and re-use it for the next subset. In **EXP**, on the other hand, you can not only look at every subset but you don't need to reuse your working space, so you can remember what you learnt about each one individually. That seems like it should be more powerful.

Another intuition for why they should be different is that the time and space hierarchy theorems tell us that allowing even a tiny bit more space or time strictly increases what you can compute. The hierarchy theorems only let you compare like with like (e.g., they show that **PSPACE$\\;\subsetneq\\;$EXPSPACE** and **P$\\;\subsetneq\\;$EXP**) so they don't directly apply to **PSPACE** vs **EXP** but they do give us a strong intuition that more resource means that more problems become solvable.
> 54 votes

# Answer
A machine running in exponential time could use exponential space. So a priori it could be that machines restricted to polynomial space would be weaker. A similar situation occurs for P and L. A machine running in polynomial time could use polynomial space, so a priori it could be that machines restricted to logarithmic space would be weaker. It is even conjectured that P is different from NL, the non-deterministic analog of L. (For PSPACE the corresponding conjectures are equivalent, since PSPACE=NPSPACE due to Savitch's theorem.) Unfortunately, we don't know how to prove these conjectures currently. The conjecture EXPTIME$\neq$PSPACE is stronger since it implies P$\neq$NL via a padding argument.
> 12 votes

---
Tags: complexity-theory, complexity-classes, intuition
---


# Question
Title: How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?
I'm so bad at solving the problem of the type:

> "If $A$ is an **NP-complete** problem, $B$ is reducible to $A$, then $B$ is..."

That I have to come here and ask these silly questions each and every time I encounter them.

Is there a good way of using the Venn Diagram shown below to tackle these kind of problem?

For example, how can I prove that If $A$ is an **NP-complete** problem, $B$ is reducible to $A$, then $B$ can be **NP-hard** using the above diagram?

If not possible, what would be another way to drill this into my head?

# Answer
> 1 votes
As Raphael said the definitions are important, especially if you try to create proofs. These definitions are not always captured in the Venn diagram.

The definition of **NP**-complete is not made clear from the diagram and will not help you to reason about

> "If A is an **NP**-complete problem, $B$ is reducible to $A$, then $B$ is...".

You cannot see from the diagram that this must mean that $B$ is **NP**.

To answer your question if it is not possible how you will be able to drill it into your head is much more complicated. But again the first step needs to be the definitions.

If you know that **NP**-completeness implies two properties of $A$ by definition, then you can take the next step.

> What does $B$ reducible to $A$ means when regarding these two properties. Do the properties of $A$ tell anything about $B$?

The second property says that any problem in **NP** reduces to $A$ in polynomial time. So if $B$ reduce to $A$ in polynomial time then $B$ is in **NP**.

# Answer
> 1 votes
The Venn diagram doesn't help very much.

Let's take your example of "If A is an NP complete problem, B is reducible to A, then B is..." NP-completeness tells you that everything in NP is reducible to A but that's not the question you're trying to solve. The question you're trying to solve is the converse: whether everything reducible to A is in NP. (It happens that it is but that's a theorem, not something that you can see immediately from the definitions.)

To use an analogy, your Venn diagram tells you that every elephant has four legs but you're trying to determine whether everything that has four legs is an elephant.

---
Tags: complexity-theory, proof-techniques, complexity-classes, intuition
---


# Question
Title: Can someone clarify this unification algorithm?
I've been having trouble understanding a unification algorithm for first order logic, as I don't know what a compound expression is. I googled it, but found nothing relevant. I also don't know what a list means in this context. A list of what?

Edit: I think I've cleared up with compound expressions are and what lists contain in this context, from Yuval Filmus's answer. However, now I have other problems:

* In Unify-Var, it uses the variable(?) val, even though val was never declared. Could {var/val} E theta (with E meaning is a subset of) instead be a function that returns whether var is already in theta, regardless of what value it's mapped to?
* The algorithm seems to break when unifying compound expressions. To unify them, it breaks compound expressions into two lists: one for function symbols and one for arguments and then calls Unify on both individually. When trying to unify the list of function symbols, it breaks the list into individual function symbols and then calls Unify on each individual function symbol. But Unify has no case to deal with function symbols, so it just returns failure, even if the two function symbols to be unified are identical!

Thanks.

Pseudocode from Artificial Intelligence A Modern Approach (3rd Edition): Figure 9.1, page 328:

```
function UNIFY(x, y, theta) returns a substitution to make x and y identical
  inputs: x, a variable, constant, list, or compound expression
          y, a variable, constant, list, or compound expression
          theta, the substitution built up so far (optional, defaults to empty)

  if theta = failure then return failure
  else if x = y the return theta
  else if VARIABLE?(x) then return UNIFY-VAR(x, y, theta)
  else if VARIABLE?(y) then return UNIFY-VAR(y, x, theta)
  else if COMPOUND?(x) and COMPOUND?(y) then
      return UNIFY(x.ARGS, y.ARGS, UNIFY(x.OP, y.OP, theta))
  else if LIST?(x) and LIST?(y) then
      return UNIFY(x.REST, y.REST, UNIFY(x.FIRST, y.FIRST, theta))
  else return failure

---------------------------------------------------------------------------------------------------

function UNIFY-VAR(var, x, theta) returns a substitution

  if {var/val} E theta then return UNIFY(val, x, theta)
  else if {x/val} E theta then return UNIFY(var, val, theta)
  else if OCCUR-CHECK?(var, x) then return failure
  else return add {var/x} to theta

```

Figure 9.1 The unification algorithm. The algorithm works by comparing the structures of the inputs, elements by element. The substitution theta that is the argument to UNIFY is built up along the way and is used to make sure that later comparisons are consistent with bindings that were established earlier. In a compound expression, such as F(A, B), the OP field picks out the function symbol F and the ARGS field picks out the argument list (A, B).

# Answer
> 5 votes
First, unification algorithms are tricky. Studying other textbooks will help.

Second, things will probably get clearer if you look at actual code implementations. Have a look at the online code repository for your textbook. The code in Lisp, for example, is here.

A helpful note to remember when looking at first-order unification algorithms is that function symbols and predicates must match exactly in order to be correct.

On to your questions.

* (Where is val declared?) This is a notational trick in the pseudocode that creates more confusion than good. It hearkens back to the old days of Lisp association lists. Maybe giving an example of theta would help: ((x 1) (y 2) (z 3)). This means x is bound to 1, y is bound to 2, and z is bound to 3. So var/val refers to a pair in theta like (x 1). So the first clause in UNIFY-VAR means, "if the pair (var val) is a member of theta, then return the result of doing UNIFY on whatever val is in that pair, with x and theta".
* (How do function symbols get unified?) Remember that function symbols must match exactly as I pointed out above. So actually the clause `else if x = y then return theta` covers this. This is via a recursive call through an outer COMPOUND case.

# Answer
> 4 votes
# This algorithm presentation is indeed pedagogically unclear.

I will not repeat here the previous contributions. However, I believe some points need clarification. Sorry if some of it is a bit subtle: this program is far from being pedagogically written. I am thinking in particular of the presentation of the function `UNIFY-VAR` which is analyzed below.

First one should note that we have two languages here, both with variables and constants, which may lead to much confusion if one is not very careful in the terminology. Hence my somewhat verbose presentation:

* the *object language* defining the expressions being unified
* the *programming language* which is a *meta-language* for the object language, and in which the unification algorithm is expressed.

## Regarding the object language

Apparently the OP could not find in his book the definition of the object language, and hence did not know what a *compound expression* may be. I do not have the book to check and can only guess. But it is quite abnormal to give a unification algorithm without a reference to a precise definition and terminology of the object language in which unification is defined. There are many such object languages, and unification may depend on them and their properties.

In this case my guess is that *compound expression* stands for an expression composed of an operator and its operands. So if the metavariable `x` has a compound expression as value, then `x.OP` is the operator while `x.ARGS` is the list of its arguments.

But then we do not see anywhere what unifies operators. The explanation is probably, as indicated by Yval Filmus in a comment, that operators are treated as constant. Actually, as far as I know, the habit is more to say that constants are operators without arguments. But indeed, both can be treated in the same way. But again, being explicit about it would not hurt the pedagogy, since few students are used to treat the `+` symbols as a constant, for example.

To conclude, the object language is just a language composed of expressions, where an expression is either an *atomic expression*, i.e. a constant or a variable, or a *compound expression* that applies an operator (given by its name) to a list of arguments which are expressions.

The name *compound expression* is in this context opposed to *atomic expression*. The former has to be decomposed for unification, while the latter cannot be decomposed.

## About the function `function UNIFY-VAR(var, x, theta) returns a substitution`

First note that the value of the argument `var` is always an object variable, while the value of `x` is always an object expression (which could be reduced to a variable).

The use of `if {var/val} E theta` here is a strange thing to do when describing a unification algorithm for the object language, since it is implicitly using unification at the programming language level, and in a strange way.

In the pair `{var/val}`

* `var` stands for the value of the meta-variable (i.e. programming language variable) `var`, i.e. for the object variable passed as argument. This object variable is a constant from the meta point of view of the programming language.
* `val` stands for itself, as a meta-variable: it was not assigned any value, and thus can hardly be expected to stand for its value.
* the pair `{var/val}` is just a meta compound expression, a construction, involving the pair operator, a constant (the value of `var`), and the variable `val`, at the meta level of the programming language.

The use of `if {var/val} E theta then do X` is actually intended to say, but at the meta level:

> if the meta expression `{[var]/val}` unifies with an element of theta , then do X.

where I insist again with the notation `[var]` that the variable `var` is replaced by its value, while `val` is not (and acts somewhat as what Prolog calls a logical variable).

Furthermore it does have a side effect: when the unification succeeds, then the variable `val` takes the value of the second component of the substitution pair with whch it actually unified. And this value is to be used in whatever is to be done, in this case `return UNIFY(val, x, theta)`.

So this is not at all trivial. Furthermore, it is pedagogically unwise (to understate it), when teaching beginners, since it is using unification at the programming level to define unification at the object level.

Note that is no unification succeeds in the above test, the variable `val` remains undefined. Then the next test `if {x/val} E theta then ...` is again a unification, slightly more complex, since the meta variable `x` is not necessarily a variable, though it will unify only if it is one.

In the last line the construction `{var/x}` is used again, but in this case, both variables stand for their values.

So again, reading this piece of programming is a bit subtle, at least for a beginner. It do not mean it is nad programming, only that it mixes too many concepts and levels from a pedagogical point of view.

## Occur-check

Finally, I do hope you understand what the call to `OCCUR-CHECK?` is supposed to do, because it is an essential part of the algorithm.

Essentially it is suppose to verify that when you try to unify a variable with an expression that the variable does not appear in the expression (allowing it would correspond to looping structures that are not usually allowed in the language).

Note that in the call to `[OCCUR-CHECK][1]?(var, x)` in your program, the meta-variable `var` is supposed to have as value an object variable, and the meta-variable `x` is supposed to have as value an object expression, and the function will check that the object variable does not occur in the object expression.

# Answer
> 0 votes
Reading the code, a *compound expression* is a function call such as `UNIFY(x, y, theta)`. It has an `OP` part, in this case `UNIFY`, and an `ARGS` part, in this case the list `x, y, theta`. Compound expressions can be nested or appear within other structures (such as lists). They can also appear in infix notation: `1 + 2`.

A *list* is a primitive data structure, which decomposes into its head (first element) `FIRST` and the rest of the list `REST`. According to the code, the empty list isn't considered a list but rather a constant. If we want, we can represent lists using angular brackets: `[1,2,3]`. We have `[1,2,3].FIRST = 1`, `[1,2,3].REST = [2,3]`, `[2,3].FIRST = 2`, `[2,3].REST = [3]`, `[3].FIRST = 3`, `[3].REST = []`, where `[]` is apparently a constant. Lists can be nested: `[1,[2,3],4]`. They can also appear inside compound expressions, or appear as arguments to compound expressions.

The members of a list have arbitrary type, at least as far as this code is concerned. They could contain constants, variables, other lists, and compound expressions.

---
Tags: logic, artificial-intelligence, first-order-logic, unification
---