# Question
Title: Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages
So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}\_a(L) = \\{\text{shrink}\_a(w)\mid w\in L\\}$ and where $\text{shrink}\_a(w)$ is the string formed from $w$ by replacing every maximal substring of two or more $a$'s by a single a. For example, $\text{shrink}\_a(baaab) = bab$.

So I was browsing around for other examples to study, and I came across the following proof for the **prefix** operation: Proving that recursively enumerable languages are closed against taking prefixes (the proof given by the user Wu Yin). I thought that this was a very cool way of proving something like this, instead of just directly building an alternate TM. I'm curious to know, can anyone come up with a proof that is of a similar style and flavor to the one pointed above? I would be very curious to see a similar bijective proof regarding countable/uncountable sets!!

This has reminded me that there can be many ways to prove something, so I wanted to see what kind of flavor other people's proofs might have to this sample problem. I find that too often, students (and myself included) get caught up in a single procedure for finding solutions to a particular type of problem and neglect to see other ways of showing the same result.

# Answer
> 3 votes
For any kind of a serious argument about computably enumerable sets, you need to free yourself of details concerning Turing machines. So you should look for general useful principles that allow you to prove properties of c.e. sets. Here is one:

> If $A$ is computably enumerable and $f$ is computable then $f(A)$ is computably enumerable.

Using this, we immediately get:

> The set $\mathrm{shrink}\_a(L)$ is computably enumerable because it is the image of the computably enumerable set $L$ by the computable function $\mathrm{shrink}\_a$.

Other such useful principles are (note that I am using the new terminology in which "recursive" is replaced by "computable"):

* computable sets are computably enumerable
* c.e. sets are closed under finite intersections
* c.e. sets are closed under inverse images by computable functions
* c.e. sets are closed under computably enumerable unions
* c.e. sets are closed under projection: if $E \subseteq \mathbb{N} \times \mathbb{N}$ is a c.e. set, then so is its projection $\lbrace n \in \mathbb{N} \mid \exists m \in \mathbb{N} . (n,m) \in E\rbrace$
* a set is c.e. if and only if, it is the domain of a computable (partial) function
* a set is c.e. if and only if, it is the image of a computable (partial) function

With these you can get pretty far.

# Answer
> 4 votes
The question actually is easy, provided you take the right definition. RE languages can be defined using a Turing Machine in two equvalent ways. As an acceptor which accepts words in the language and halts (and may halt or loop otherwise), or as an enumerator, which will write the elements of the language (probably in some weird order) onto the output tape (assuming there is a separate working tape).

Using the latter concept several closure operations of the type you mention are trivialities. If I want to shrink, I start my enumerator, and when it outputs a word of the language apply shrink.

---
Tags: formal-languages, computability, proof-techniques, closure-properties
---


# Question
Title: Strict polynomial hierarchy and reduction
The following exercise gives me headaches:

> Show: If the polynomial hierarchy is strict (i.e. $\forall k \in \mathbb{N}. \Sigma\_k \neq \Sigma\_{k+1}$), then there is no $\text{PH}$-complete problem for polynomial-time reductions (i.e. there is no problem $\text{P} \in \text{PH}$ such that each problem in $\text{PH}$ can be reduced to $\text{P}$ through a function $f \in \text{FP}$).

The exercise describes in detail what has to be shown, but my issue is that I don't know how to show this. Can somebody please help me?

# Answer
> 1 votes
$\newcommand{\PH}{\mathsf{PH}}$To expand the comments:

Suppose there did exist a $\PH$-Complete language $L \in \Sigma\_i$ for some $i$. By definition of completeness $L' \leq L$ for all $L' \in \PH$. Therefore there exists some language $L' \in \Sigma\_{i+1}$ that reduces to $L$. This is a contradiction with the strictness assumption. Indeed, we conclude that no such $\PH$-Complete language exists.

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


title: Perplexed by Rice's theorem

text:
# Question
Title: Perplexed by Rice's theorem
**Summary:** According to Rice's theorem, everything is impossible. And yet, I *do* this supposedly impossible stuff *all the time!*

---

Of course, Rice's theorem doesn't simply say "everything is impossible". It says something rather more specific: "Every property of a computer program is non-computable."

(If you want to split hairs, every "non-trivial" property. That is, properties which *all* programs posses or *no* programs posses are trivially computable. But any other property is non-computable.)

That's what the theorem says, or appears to say. And presumably a great number of very smart people have carefully verified the correctness of this theorem. But it seems to completely defy logic! There are *numerous* properties of programs which are *trivial* to compute!! For example:

* How many steps does a program execute before halting? To decide whether this number is finite or infinite is precisely the Halting Problem, which is non-computable. To decide whether this number is greater or less than some finite $n$ is *trivial!* Just run the program for up to $n$ steps and see if it halts or not. Easy!
* Similarly, does the program use more or less than $n$ units of memory in its first $m$ execution steps? Trivially computable.
* Does the program text mention a variable named $k$? A trivial textual analysis will reveal the answer.
* Does the program invoke command $\sigma$? Again, scan the program text looking for that command name.

I can see plenty of properties that *do* look non-computable as well; e.g., how many additions does a complete run of the program perform? Well, that's nearly the same as asking how many *steps* the program performs, which is virtually the Halting Problem. But it looks like there are boat-loads of program properties which a really, really *easy* to compute. And yet, Rice's theorem insists that none of them are computable.

What am I missing here?

# Answer
> 41 votes
For the purposes of this discussion, a "program" is a piece of code which always takes an integer as an input, and either runs forever or returns an integer. We say that two programs $f$ and $g$ are *extensionally equal* if they compute the same function, i.e., for every number $n$ either both $f(n)$ and $g(n)$ run forever, or they both terminate and output the same number.

An *extensional property* of programs is a property $P$ that respects extensional equality, i.e., if $f$ and $g$ are extensionally equal then they either both have the property $P$ or both do not have it.

Here are some examples of *non*-extensional properties:

1. The program halts within $n$ steps. (We can always modify a program to an extensionally equal one that runs longer.)
2. The program uses fewer than $n$ memory cells within the first $m$ steps of execution. (We can always modify a program to an extensionally equal one so that it uses up some memory for no good reason.)
3. The program text mentions a variable named `k`. (We can rename variables.)
4. Does the program invoke command $\sigma$. This may depend a bit on what $\sigma$ is, but if it is something that can be simulated in some way, then we can evade $\sigma$ and still have a program which is extensionally equal to the original one.

I am sure you have noticed that I listed precisely your alleged counter-examples to Rice's theorem, which says:

> **Theorem (Rice):** A computable *extensional* property of programs either holds of all programs or of none.

There is another way to explain this: you have to distinguish between a program and the function it computes. Many different programs compute the same function (they are all extensionally equal). Rice's theorem is about properties of functions, not about properties of programs that compute them.

# Answer
> 36 votes
Fundamental misunderstanding:

> Every property of a computer program is non-computable

That is not what Rice's theorem talks about. It talks about properties of *functions* and that the set of *programs computing this function* is not decidable. Formally, given $\emptyset \subset P \subset \mathsf{RE}$ the set

$\qquad \displaystyle \\{ \langle M \rangle \mid f\_M \in P \\}$

is not decidable. For the properties you mention, you won't find a suitable $P$ for which the set of programs has this form. Some programs for one function may have the property while others (for the same function) may not. See here for some examples.

Rice's theorem deals with *semantic* properties (properties of the *function* computed by a program, e.g. domain or value range). What you refer to are *syntactic* properties (properties of the *program*, such as runtime or how many variables are used).

Not much seems to be known for syntactic properties; see this question.

---
Tags: terminology, computability, undecidability, rice-theorem
---


# Question
Title: Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$
The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem

For instance, the Arora-Barak book explains the theorem using $g(n) = n$ and $G(n) = n^{1.5}$ - but, I can see that $n \in o(n^{1.5})$ as well! So, I'm trying to better understand what "extra" time is guaranteed by specifying that in order for $\text{NTIME}(g(n))$ to be a proper subset of $\text{NTIME}(G(n))$, $g(n + 1) = o(G(n))$, **not** $g(n) = o(G(n))$...

# Answer
> 12 votes
One example is $g(n) = 2^{2^{n-1}}$, $G(n) =2^{2^{n}}$.

We have $g(n) = \sqrt{G(n)}$, so $g(n) = o(G(n))$.

Meanwhile, of course, $g(n+1) = G(n)$ so $g(n+1) = \Theta(G(n))$, so $g(n+1)\neq o(G(n))$

Why double exponential? When we add one to $n$, we want the effect to be more than a multiplicative constant (because big $O$ notation hides multiplicative, and therefore additive constants). Let's make it simple and say that we want adding 1 to $n$ to have a polynomial effect on the value of $g(n)$. When you add a constant to $n$:

* a linear function is increased by an additive constant
* an exponential function is increased by a multiplicative constant
* a double exponential function is increased polynomially (by a power of two in our example, hence $g(n)^2 = G(n)$)

We can also have $g(n) = n^n$, $g(n) = n!$, etc., where $G(n) = g(n-1)$. In general we can let $g(n) = f(n)^n$, where $f(n) = \omega(1)$ and $f$ is nondecreasing. Then we have:

$$\lim\_{n\to\infty} \frac{g(n)}{G(n)} = \lim\_{n\to\infty} \frac{g(n)}{g(n+1)} = \lim\_{n\to\infty}\frac{f(n)^n}{f(n+1)^{n+1}} \leq \lim\_{n\to\infty}\frac{f(n)^n}{f(n)^{n+1}} = \lim\_{n\to\infty}\frac{1}{f(n)} = 0$$

So we've shown $g(n) = o(G(n))$ using the limit definition (the last step is because $f(n) = \omega(1)$). Therefore, functions like $(\log\log n)^n$ and even $\alpha(n)^n$ where $\alpha$ is the inverse Ackermann function, will do the trick for us as well.

# Answer
> 8 votes
Take $g(n)= n!$ and $G(n) = (n+1)!$.

---
Tags: complexity-theory, time-complexity, asymptotics, landau-notation
---


# Question
Title: Finite state automata, multiple completion states?
I'm currently studying for an exam for a course where some of the material covered included finite state automata, I've completed a question and I'm not sure about my answer.

**Exercise**

Explain what is meant by a Finite State Automaton (FSA) by drawing an FSA to recognise strings of the form $a^rb^s$, where $r\gt0$ and $s\ge0$ and with an alphabet of $\\{a,b\\}$, i.e., there must be at least one $a$, zero or more $b$'s and all occurrences of $a$ must precede any occurrence of $b$. Illustrate, how your FSA works given the following sample strings:
$\quad$(i) $abbb$
$\quad$(ii) $aaaa$
$\quad$(iii) $aba$

**My Answer**

Are multiple completion states allowed?

# Answer
> 5 votes
Your DFA is close, but not quite right. Note that the description requires the strings in the language to have at least one $a$, whereas your DFA will accept the empty string. The fix is simple of course:

And yes, having multiple accept states is fine (in fact, some languages require it).

---
Tags: automata, finite-automata
---


title: Showing the function=? is impossible

text:
# Question
Title: Showing the function=? is impossible
Here's a lab from a first-year computer science course, taught in Scheme: https://www.student.cs.uwaterloo.ca/~cs135/assns/a07/a07.pdf

At the end of the lab, it basically presents the halting problem, and shows that it is impossible to solve by introducing the function `diagonal`, which is defined as:

```
(deﬁne (diagonal x)
  (cond
     [(halting? x x) (eternity 1)]
     [else true]))

```

Where `eternity` is a non-terminating program defined as `(define (eternity x) (eternity x))`. What happens when you feed `diagonal` its own definition as input ... ?

This is all fairly standard stuff. Then, the lab says:

> For a real challenge, deﬁnitively answer the question posed at the end of Exercise 20.1.3 of the text, with the interpretation that function=? consumes two lists representing the code for the two functions. This is the situation Church considered in his proof.

So the gist of it is that `function=?` takes two inputs. Each is a list, which represents the definition of a function, i.e. it is a list of the form `(define (id args ...) body ...)`. We can assume that both functions are syntactically valid and will terminate for all inputs (without runtime errors). `function=?` returns true if and only if the two functions will always return the same result when given the same inputs. For example,

```
(function=? '(define (foo x) (* 2 x))
            '(define (bar x) (+ x x))) ; should return #t

(function=? '(define (foo x) (+ x 1))
            '(define (bar x) (+ x 2))) ; should return #f

```

Now, `function=?` is obviously impossible to write - the challenge is to *prove* it is impossible. I thought about this for a while, and the best solution I could come up with is the following:

```
(define (disprove-function=? x)
  ((lambda (snip)
     (let ((self (list 'define '(disprove-function=? x)
                       (list snip (list 'quote snip)))))
       (if (function=? self '(define (id x) x))
           (list x)
           x)))
   '(lambda (snip)
      (let ((self (list 'define '(disprove-function=? x)
                        (list snip (list 'quote snip)))))
        (if (function=? self '(define (id x) x))
            (list x)
            x)))))

```

Basically, `disprove-function=?` uses standard quining techniques to generate its own source code (the variable `self`), and then asks `function=?` if it is equivalent to the identity function. If `function=?` says #f, then `disprove-function=?` will always behave like the identity function. Contradiction! If `function=?` says #t, then `disprove-function=?` will always behave differently from identity; in particular, it will behave like the `list` function. Contradiction! Thus, `function=?` can't exist. QED.

My question is: is there a more elegant way to approach this problem? My solution seems ... long and ugly. Not nearly as nice as the `diagonal` function for proving that the halting problem is unsolvable.

NB: Please give me answers and not hints! Even though this is a homework question, it is not *my* homework question: I don't go to this university! Further, as you can see from the lab, this question is under the `Enhancements` category and isn't worth marks, so even if you don't believe me, there is still no problem with just giving me an answer. Finally, I already *have* a solution, which I am pretty sure is right; I was just wondering if there was a *better* solution.

# Answer
Using the halting problem seems like the good solution. Suppose you have a function `red` that takes the code of a function (or λ-term) (or a untyped function), reduces one step (or β-redex) in it and returns the code of the resulting function. Suppose also that you have a function `normal` that says if the term is in normal form.

In Turing machines language, `red` would be the computation of one step and `normal` would return true when we are in a final state.

Let's simulate the computation of $n$ steps, returning $43$ instead of $1$ if we reach the end of the computation:

```
(define (run t n)
  (if (= n 0) 1
    (if (normal t) 43
      (run (red t) (n-1)))))

```

Then we can decide if the execution of a term will terminate or not:

```
(define (one x) 1)
(define (terminate t) (not (function=? (run t) one)))

```

From that we can use the usual diagonal argument:

```
(define (loop x) (loop x))
(define (f x) (if (terminate (code-of-application x (quote x))) (loop 0) 1)
(f code-of-f)

```

If `f` terminates on `code-of-f` then `(terminate (code-of-application code-of-f (quote code-of-f))` will return `true` and then `f` will loop on `code-of-f`. So it should loop. Then `(terminate ...)` should return `false` and `f` will terminate on `code-of-f`, contradiction.

Technicalities: one need to define a base language which is expressive enough to be able to write everything is written above. You then need `red` and `normal` which can be tougher than one can imagine. You need also the standard quine techniques: `quote` which, given the code of a term, returns a term representing the code of the term, `code-of-application a b` is easy and self-explanatory, and of course you need to write everything above internally to write `code-of-f`.

The lambda-calculus is surprisingly simple and expressive to both write all this down and to prove its correctness, which is why Church used it to solve Hilbert's tenth problem, but one can do it in a lot of languages, possibly in a simpler way, using language-specific quine tricks.
> 1 votes

---
Tags: undecidability, lambda-calculus, halting-problem
---


# Question
Title: How to draw a Turing Machine for Even-Even
A TM to accept EVEN-EVEN (a collection of all strings with an even number of a's and an even number of b's) can be based on the algorithm:

1. Move up the string, changing a’s to A’s
2. Move down the string, changing b’s to B’s

Modified algorithm: To avoid the problem of crashing on the way down the $Tape$, change the letter in the first cell to an $X$ (if it's an $a$) and to a $Y$ (if it's a $b$). This way we can recognize the left end of the tape.

So far I have this but am not sure how to implement the modified algorithm (note: the e's from start to halt mean empty):

Any help is appreciated!

# Answer
From what I understand, your first algorithm intends to process the $a$ and $b$ inputs separately, which doesn't seem necessary. Your difficulty seems to come from formalizing a TM, which you can do in a couple ways.

**Direct Conversion** (Courtesy of Raphael in the comments)

> You can view an NFA as TM that can not write and move only to the right. In other words, you don't have to do anything at all for the conversion, just add $R$ to transitions that consume a symbol and $N$ to $ε$-transitions, and then you basically have your equivalent TM.

**Multitape Approach** \- Suppose we know that a multitape TM is equivalent to a TM, so we can have two tapes:

* An input tape (with a string $x\in(a|b)^\*$), which we'll read through exactly once.
* A computation tape which will have one of four numbers $1$, $2$, $3$, or $4$, reflecting the state that the analogous finite automata (for which you have an image) might have. If we didn't want to expand the alphabet, we could instead have $\\{\epsilon\epsilon,a\epsilon,\epsilon b,ab\\}$ to indicate the parity of each letter.

As we proceed through the input, we update the computation tape accordingly: if we read an $a$, and we're in state $1$, we swtich to state $3$, etc. To reduce this back to one tape, we need another symbol $\\#$ to separate tapes, perhaps $\hat{a},\hat{b}$ to designate the location of the heads and pre/append our computation tape (for which we only need two characters of space).

**Formal Approach** \- we're going to define the set of states $Q$, the tape alphabet $\Gamma$, the blank symbol $\epsilon$, the input symbols $\Sigma$, the initial state $q\_0$, the accepting states $F$ and the transition function $\delta$.

$$\langle Q=\\{q\_{\epsilon\epsilon},q\_{a\epsilon},q\_{\epsilon b},q\_{ab}\\},\Gamma=\\{a,b\\},b=\epsilon,\Sigma=\\{a,b\\},q\_0=q\_{\epsilon\epsilon},F=\\{q\_\epsilon\\},\delta\rangle$$ $$\delta= \begin{vmatrix} & q\_{\epsilon\epsilon} & q\_{a\epsilon} & q\_{\epsilon b} & q\_{ab} \\ a & q\_{a\epsilon} & q\_{\epsilon\epsilon} & q\_{ab} & q\_{\epsilon b} \\ b & q\_{\epsilon b} & q\_{ab} & q\_{\epsilon\epsilon} & q\_{a\epsilon} \\ \end{vmatrix}$$
> 1 votes

# Answer
I ended up figuring it out, thanks all for the help.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Knapsack problem with multiple constraints
I am unsure if I have even identified the problem correctly, but reading up on knapsack problem seems the closest to what I am trying to solve:

> A cook has $k$ ingredients of $p$ quantities. Given a list of $n$ unique recipes, each consisting varying ingredients of varying quantities. Now, the cook would like to use all ingredients on ONE recipe with minimal leftovers.

What is his solution? And can it be determined in $O(\log n)$ time?

`Sample input`

500 pounds of flour 300 mg sugar 5 mg of vanilla pods 20 eggs

`Database of possible recipes`:

Thai Fried Noodles (doesn't contain vanilla or flour, but contains 1 tablespoon of sugar)

Tiramisu (doesn't contain flour and vanilla but contains 3 tablespoons of sugar and 8 eggs)

Anna's Special Tiramiu (doesn't contain flour and vanilla but contains 1 tablespoons of sugar and 8 eggs)

Truffle Tagliatelle (doesn't contain any input ingredients)

**EDIT** Cost/benefit decision:

Given the sample input, `Tiramisu` recipe is the most preferred because among the 4 recipes in the database, it contains the most number of input ingredient type (2 of 4 types), and the most number of input ingredient quantity.

Expected result where 1) is the top search result of relevance: 1) Tiramisu 2) Anna's Special Tiramisu 3) Thai Fried Noodles 4) Truffle Tagliatelle

**EDIT:** I believe my question is a variant of the integer knapsack problem

# Answer
I assume you can compare two recipes and say which would be preferable to the other. That is, you can define an order between them. Then:

1. You need to find appropriate recipe only **once** (or very few times). A simple scan through all the recipes is the only way possible. You *need* to look at *every* recipe at least *once* to be able to see if it is good enough or not. This will give linear complexity.
2. You have to find appropriate recipes **repeatedly for a lot of different baskets**. Then, it would make sense to order the recipes in a way that searching would be faster. You might want to sort the recipes first once, in $O(n\log n)$ time. Then, whenever you encounter a basket of ingredients for which you want to find the best recipe, you search the sorted list of ingredients using binary search in $O(\log n)$ time. Thus, the pre-processing phase (sorting) will be slow, but subsequent queries will be fast. This will be beneficial only when you have millions of recipes and want to search the best matched recipe for different baskets hundreds or thousands of times each second.

Admittedly, this is a little vague, but based on the given information, this is the best I can give.
> 1 votes

---
Tags: algorithms, knapsack-problems
---


# Question
Title: Why does a suffix tree have a linear number of nodes (relative to input string size)?
Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique *suffix substrings* is less than the number of unique *substrings* of a string.

# Answer
For a text of length $n$ we have up to $1+{ n+1 \choose 2}$ different substrings, however there are only $n+1$ suffixes (for every suffix you can pick the position where it starts).

I assume you consider the compressed suffix tree (edge labels are words). This is a tree with $n+1$ leaves and every internal node has at least two children. Thus we have less interior nodes than leaves an therefore the tree has size $O(n)$.

Notice that in the uncompressed version (edge labels a characters) with a large alphabet, you can have super-linear suffix trees. For example, consider the text `abcdefghijk...`.
> 9 votes

---
Tags: data-structures, trees, strings, suffix-trees
---


# Question
Title: Showing that Independent set of size $k$ can be decided using logarithmic space
An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of size $k$.

I'd really love your help with showing that $k-\text{IND} \in {\sf L}$, i.e., can be decided using deterministic logarithmic space.

# Answer
> 6 votes
You can use the following algorithm.

I assume that the vertices are labeled $1,\ldots,m$. You enumerate all $k$-tuples $\\{1,\ldots , m\\}^k$. This can be done by reserving $k$ counters on the TM tape. Since $k$ is not part of your input this needs only $O(\log m )\subseteq O(\log n)$ space. However for every $k$-tuple you can test if it is an independent set. Simpy test all pair of selected vertices if there are not connected by an edge. Again, since $k$ is fixed the edges you have to test (depending on the current tuple) are known. Thus this test can be hard-wired into the TM program, and therefore needs no extra-space.

---
Tags: complexity-theory, graphs, space-complexity
---


title: Reference Request for Synthesis

text:
# Question
Title: Reference Request for Synthesis
New to the world of software verification and synthesis. It was suggested to me that the book "Principles of Model Checking" is a good reference for verification, but I am clueless about synthesis. Could someone refer a good book?

# Answer
> 1 votes
Try these slides http://www.cs.bgu.ac.il/~frankel/HonoraryDay09/Slides/AmirPnueli.pdf or these ones http://www.cs.rice.edu/~vardi/papers/fmco06.ps.gz.

Also try googling "From Verification to Synthesis" and look at the work of Moshe Vardi and Orna Kupferman.

---
Tags: reference-request, formal-methods
---


title: Decidability of languages

text:
# Question
Title: Decidability of languages
> $L\_1$ is a recursively enumerable language over some alphabet $\Sigma$. An algorithm effectively enumerates its words as $w\_1, w\_2, ...$.
> $L\_2$ is another language over $\Sigma \cup \\{\\#\\}$ as $\\{w\_i\\#w\_j : w\_i, w\_j \in L\_1, i \< j\\}$
> Consider the following assertions.
>
> 1. $L\_1$ is recursive implies $L\_2$ is recursive
> 2. $L\_2$ is recursive implies $L\_1$ is recursive
>
> Which statements is/are true?

I reasoned both the statements to be true.

Statement 1 is true. $L\_1$ is recursive means it can lexicographically enumerate its strings. The membership question for $L\_2$ can be easily settled using the decider and lexicographic enumerator of $L\_1$.

Statement 2 is true. The algorithm which decides $L\_2$ can be modified to accept if the input string matches either $w\_i$ or $w\_j$. This settles the membership question for $L\_1$.

The given solution to this question however says that statement 2 is false. Could you let me know if my reasoning has gone wrong someplace?

# Answer
You seem to be right. But as Raphael says, be careful.

Statement 1. Note that the $L\_2$ is defined using the enumerating algorithm $\cal E$ for $L\_1$, not by $L\_1$ itself. To decide whether $u\\#v \in L\_2$, decide whether both $u,v$ in $L$, and if confirmed run the enumerator $\cal E$ and see whether $u$ is output before $v$. As we know both strings are in $L\_1$ this will terminate.

Statement 2. If $L\_1$ is finite, it is recursive, so we assume $L\_1$ is infinite. Run $\cal E$ and wait for first word $w\_1$. Now a decider for $L\_2$ can be turned into one for $L\_1$ as follows. To test $u\in L\_1$ first check whether $u=w\_1$, and then check $w\_1\\#u \in L\_2$. This is then equivalent to $u\in L\_1$ as we do not have to worry about the $i\<j$ requirement, which is now true by construction.

I am not even certain we need to know $w\_1$ by running $\cal E$: we only want to verify there *exists* a decider, not whether one can be effectively constructed. That seems impossible.

(**edit**) Just to note that Raphael has posted a more explicit "implementation" of these suggestions, which avoids possible ambiguities.
> 7 votes

# Answer
**Ad 1:** The statement is true, but your reasoning is not: you can not change the enumeration; the definition of $L\_2$ is intimately tied to the order of elements. Here is the simple algorithm that decides $L\_2$:

```
decide2(w) = {
  (u,v) = split (w,#) // w = u#v

  if ( decide1(u) && decide1(v) ) {
    i = 1
    while ( true ) {
      if ( enumerate1(i) == u ) {
        return true
      }
      else if ( enumerate1(i) == v ) {
        return false
      }
      i += 1
    }
  }

  return  false
}

```

Here, `decide1` is the decider for $L\_1$ and `enumerate1` is the enumerator for $L\_1$, which both exist by assumption. Note that the `while` loop always terminates; at that point, we know that $u,v \in L\_1$ so the loop will find them (in fact, the one occurring first) eventually.

**Ad 2:** This statement is indeed true, but again for different reasons than you state.

If $L\_2$ is recursive, the following program is computable and decides $L\_1$:

```
decide1(w) = {
  w1 = enumerate1(1)
  if ( w == w1 ) }
    return true
  }
  else {
    return decider2(w1#w)
  }
}

```

If $w = w\_1$, we clearly have $w \in L\_1$ and the program decides correctly. If $w \in L\_1 \setminus \\{w\_1\\}$, there is a $i \> 1$ such that $w\_i = w$, and therefore $w\_1\\#w \in L\_2$; conversely, if $w \not\in L\_1$, there is no such $i$ and thus $w\_1\\#w \not\in L\_2$. The program decides correctly in all cases.
> 2 votes

---
Tags: formal-languages, computability
---


# Question
Title: Randomized Rounding of Solutions to Linear Programs
Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global optimum. However, enforcing integral solutions has runtime that is exponential in the worst case. To cope with this barrier, several approximation methods related to ILPs can be used,

* Primal-Dual Schema
* Randomized Rounding

The Primal-Dual Schema is a versatile method that gives us a "packaged" way to come up with a greedy algorithm and prove its approximation bounds using the relaxed dual LP. Resulting combinatorial algorithms tend to be very fast and perform quite well in practice. However its relation to linear programming is closer tied to the analysis. Further because of this analysis, we can easily show that constraints are not violated.

Randomized rounding takes a different approach and solves the relaxed LP (using interior-point or ellipsoid methods) and rounds variables according to some probability distribution. If approximation bounds can be proven this method, like the Primal-Dual schema, is quite useful. However, one portion is not quite clear to me:

> How do randomized rounding schemes show that constraints are not violated?

It would appear that naively flipping a coin, while resulting in a 0-1 solution, could violate constraints! Any help illuminating this issue would be appreciated. Thank you.

# Answer
Of course, if you round, you have to verify that rounding preserves feasibility.

Let us for example consider the **relaxed** VERTEX-COVER LP formulation. $$ \begin{array}{lll} \text{min} & \sum\_{v\in V}c(v)x\_v & \\ \text{s.t.} &x\_u+x\_v\ge1, & \quad (u,v)\in E \\ &x\_v\ge 0. & \quad v\in V \end{array} $$

It is known that the solution to this problem is half-integral, i.e., each variable is either $0$, $1$, or $1/2$. The rounding scheme works as follows, whenever your solution contains $x\_v=1/2$ you **round up** and set $x\_v=1$. The constraints of the ILP were $$ \begin{array}{lll} &x\_u+x\_v\ge1, & \quad (u,v)\in E \\ &x\_v \in \\{0,1\\}. & \quad v\in V \end{array} $$ Both constraints are fulfilled after the rounding. And you have a nice 2-approximation.
> 7 votes

# Answer
Yes, this is confusing in the first sight.

I see it like this:

step1) generate a linear program solution \[all the linear program constraints are satisfied in here - except that it is not Integer solution\],

step2) randomize it (change the value to integers according to a probability distribution you select),

step3) make sure the randomized solution is correct (by making few changes on it).

For example, in the set-cover. After randomization, you may end up with a collection of sets that are not necessarily a set cover. In this case, you should add some sets that cover all the uncovered elements (and thus, you get the solution you want).

To avoid such big changes in the randomized linear program solution, follow a randomized rounding scheme that guarantees with high probability that a solution is found after rounding (i.e. you will not need to do many changes in the linear program solution in order to get what you want).

See this for a reference:
> 2 votes

---
Tags: optimization, randomized-algorithms, linear-programming, approximation
---


# Question
Title: Why use joint trees in Graphical Models?
I am wondering why some methods transform the underlying graphical model (Bayesian Network for example) to a junction tree¹? What are the advantages? Also what are the limitations?

I believe it's for computational purposes. If that's the case under what circumstances it is not recommended to transform the underlying DAG to joint-trees?

*Edit*: speaking about graphical models in general (whether they are probabilistic or not), is there some guidelines when to transform them i.e. decompose them?

---

1 Junction trees are also known as tree decomposition.

# Answer
> 2 votes
I view junction trees as basically an implementation/analysis tool for doing exact MAP and marginal inference in graphical models. They are needed so that you can safely localize the effects of of maxing or summing (in the case of MAP and marginal inference) out a variable.

When wouldn't you use a junction tee? Well, that's the same case as when you wouldn't do exact inference in your model. Why wouldn't you do exact inference? In general, because it can be expensive; it's exponential in the treewidth of your junction tree.

---
Tags: machine-learning
---


# Question
Title: Recursion problem involving head, tail and xor
Consider a set of functions:

* `head(l)` returns first bit from list `l`, e.g.

```
head([0,1,0]) = 0,
head([1]) = 1

```
* `tail(l)` returns a list by removing first element from `l`, e.g.

```
tail([0,1,0]) = [1,0],
tail([1]) = []

```
* `a:l` appends bit `a` to beginning of list `l`, e.g.

```
1:[0,1,0] = [1,0,1,0].

```
* `xor` takes takes as input two bits and returns a bit.

```
xor(a,b)
if (a == b)
  return(0)
else
  return(1)
endif

```
* `f1` takes as input a list and returns another list.

```
f1(s)
if (s == []) then
  return([1])
else if (head(s) == 0) then
  return(1:tail(s))
else if (head(s) == 1) then
  return(0:f1(tail(s)))
endif

```

+ `f2` takes as input a bit and a list and returns a bit.

    f2(b,s) if (s == \[\]) then return(b) else if (head(s) == 0) then return(f2(xor(b,1),tail(s))) else if (head(s) == 1) then return(xor(b,1)) endif
* `g1` takes as input a nonnegative number and returns a list.

```
g1(n)
if (n == 0) then
  return([0])
else
  return f1(g1(n-1))
endif

```
* `g2` takes as input a nonnegative number and returns a bit.

```
g2(n)
if (n == 0) then
  return(0)
else
  return f2(g2(n-1),g1(n))
endif

```

Can anyone explain what the function `g2()` returns?

I am able to find out g1() returns a list in binary for example

```
g1(1) = [1]
g1(2) = [01]
g1(3) = [11]
g1(4) = [001]

```

# Answer
> 4 votes
Hints:

* g1(0) = \[0\] so you can see that f1 for \[0\] returns \[1\] and for \[1\] returns \[0\]. From here g1 must be clear.
* f2 takes a bit and a list of one element and returns a bit so it is one of the boolean functions of 2 variables (they are only 16)
* after you know that g2(0) = 0 and the above hints it is easier to calculate g2

I can propose you to post your answer or I will update my answer after some time to be sure that it was not for homework.

---
Tags: recursion, functional-programming
---


# Question
Title: How to guess the value of $j$ at the end of the loop?
```
for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ;

```

All variables are integers.(i.e. if decimal values occur, consider their floor value)

Let $\text{val}(j)$ denote the value of $j$, after the termination of the loop. Which of the following is true?

(A)$\quad \text{val(j)} = \Theta(\log(n)) $
(B)$\quad \text{val(j)} = \Theta(\sqrt n) $
(C)$\quad \text{val(j)} = \Theta(n) $
(D)$\quad \text{val(j)} = \Theta(\log\log n) $

Please explain, is there any easy way to guess the value of $j$?

# Answer
> 0 votes
Lets break the loop as

```
j = 0;
for ( i = n ; i > 0 ; i = i/2 )
     j = j + i ;

```

Since the input size decreases by half, the total number of iterations would be $\log(n)+1 $

As $i$ becomes $n, n/2 , n/4 \ldots$ up to $\log(n)+1 $ terms, the corresponding $j$ value gets added.
So, $val(j) = n+n/2+n/4+n/8+\ldots n/2^{\log(n)} $

$val(j) = n ( 1 + 1/2+1/4+1/8+\ldots 1/2^{\log(n)})$

Performing sum of geometric series,

$S\_n = \frac{1 - (1/2)^{\log(n)}}{1 - (1/2)} $

We know that $a^{\log(b)} = b^{\log(a)}$
Thus $2^{\log(n)} = n^{\log(2)} = n$

$S\_n = \frac{2(n-1)}{n}$

$val(j) = n\frac{2(n-1)}{n}$

$val(j) = 2(n-1)$

Thus, $val(j) = \Theta(n)$

# Answer
> 3 votes
If you unfold the loop you get:

$$\text{val}( j)=n+n/2+n/4+ n/8 \ldots$$

In total you have $\log n$ terms. See this post, how to evaluate the sum.

# Answer
> 1 votes
In theoretical processor, this loops never ends. Dividing $i$ by 2 repetitively will always lead to i \> 0. \[This has been changed in the Q. description\] Therefore:

$ j = n + n/2 + n/4 ... $

$ j = \sum \_{i = 0} ^{\inf} n (1/2)^{i}= n \sum \_{i = 0} ^{\inf} (1/2)^{i}$

Given that $\sum \_{i = 1} ^{\inf} c^i = c / (1 - c) $ then the solution of this equation is $j = 2 n$

In your integer program, follow the link posted by @A.Schulz. -- If you compute the geometric series provided, it will end up to the same approximate result. so you guess your answer.

More details:

given that $\sum \_{i = 0} ^{\log n} (1/2)^i = \frac{(1/2)^{\log n + 1} - 1}{(1/2) - 1} = 2( 1 - 1/2n) = 2 - 1/n $

Then, the final result is $n (2 - 1/n) = 2n - 1$ . Therefore, it is C.

---
Tags: algorithm-analysis, asymptotics, integers
---


title: Recursive and regular languages

text:
# Question
Title: Recursive and regular languages
I'm trying to study for an exam and having difficulty with the following practice questions. Any help would be appreciated.

1. Give a language $L$ such that $L$ is not recursive but $\text{prefix}(L)$ is regular.
2. Give two languages $L\_1$ and $L\_2$, such that $L\_1$ and $L\_2$ are not recursive, but $L\_1\cap L\_2$ is recursive.
3. Give a language $L$ such that $L$ is regular but $\text{unary}(L)$ is not context-free.

# Answer
> 2 votes
Tips.

1. *Any* (infinite) unary language has regular prefix language.
2. $L\_1 = a \cdot K$ and similary $L\_2 = b \cdot K$ where $K$ is a well-chosen horrible language.

Question.

What is unary($L$)? If it is what I think, there is an easy example. Powers of two are not context-free: $\\{ a^{2^n} \mid n\ge 1\\}$.

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


title: Algorithm exercise

text:
# Question
Title: Algorithm exercise
making exercises to prepare a test I'm having problems to understand 2 questions, the questions are:

```
 how many are the leafs of a decisional tree associated to any algorithm for
  the search problem  in a ordered set?

```

for this question I have 2 set of answer where, for every set, 1 is right, looking at the solution I found this, but I'm not able to understand why the right answers are all C.

```
    1.                 a) Θ(n log n)    b) Θ(log n) *c) Ω(n!)   d) O(n!)

    2.                 a) Θ(n log n)    b) Θ(log n) *c) Ω(n)    d) Θ(n!)

```

The other question, referred to the first one is:

```
  and in a non-ordered one?

```

And here I can't see what does it change with the number of leafs in the ordered case.

I'm sorry if this question violates the rules, in the faqs, I read here https://meta.stackexchange.com/questions/10811/how-to-ask-and-answer-homework-questions and it seems to be possible to make these kind of question.

Thanks in advance.

# Answer
$\Omega(n!)$ is not a reasonable answer. The decision tree for the search problem on the ordered set is just a binary search tree. It has $\Theta(n)$ leaves. Unless they mean something non-standard by "search problem" and "decision tree". These arguments in terms of number of leaves in the decision tree are typically used in lower bound arguments. Wikipedia has an (incomplete) discussion of the decision tree model.

In the unordered case, the decision tree still has $\Theta(n)$ leaves, using linear search.
> 1 votes

---
Tags: algorithms
---


# Question
Title: I need to present a regular expression for the following languages:
1. L2 = E{0,1)

All the words in L2 with equal number of 0's and 1's and every prex of w has at most two more of either 0's or 1's.

2. All words that does not contain “bbb” as substring.

i think this is :( e + b + bb)(a + ab + abb)\*

Thanks in advance!

# Answer
Your point 2, is obviously correct.

As for the point 1, we construct the automaton: let's remember how much more 0's we've read than 1's. Then we have transitions:

```
S0  by 0 to S1
S0  by 1 to S-1
S1  by 0 to S2
S1  by 1 to S0
S-1 by 0 to S0
S-1 by 1 to S-2
S2  by 1 to S1
S-2 by 0 to S-1

```

`S0` is initial, only `S0` is final. This way we are sure, that in whatever state we are, the number of $0$'s and $1$'s that were read so far differs by at most $2$ and in the final state the number are the same.

Then the language is $$ \Bigl(0(01)^\*1+1(10)^\*0\Bigr)^\*$$

The large parenthesis corresponds to all paths from `S0` to `S0`, and we can repeat it as many times as needed.
> 2 votes

---
Tags: regular-expressions
---


# Question
Title: When does $1.00001^n$ exceed $n^{100001}$?
I have been told than $n^{1000001} = O(1.000001^n)$. If that's the case, there must be some value $n$ at which $1.000001^n$ exceeds $n^{1000001}$.

However, when I consult Wolfram Alpha, I get a negative value for when that occurs. http://www.wolframalpha.com/input/?i=1.000001%5Ex+%3D+x%5E1000001

Why is that? Shouldn't this value be really big instead of negative?

# Answer
$f(n)$ = $O(g(n))$ implies that for *all* $n \> N\_0$, $N\_0 \> 0$, the relation $f(n) \leq c \cdot g(n)$ holds for some $c \> 0$. Following this definition, we have:

$n^{1000001} \leq c \cdot (1.000001)^n$

$1000001 \cdot \log(n) \leq \log(c) + n \log(1.000001)$

Checking for $1000001 \cdot \log(n) = n \log(1.000001)$ on Wolfram, we find $N\_0 = 3.10672\*10^{13}$. For *any* $n \geq N\_0$, if we select $c$ such that $\log(c) \geq 0$, the above relation will hold. Thus, $c \geq 1$ will suffice. Therefore, $n^{1000001} = O(1.000001^n)$.

More intuitively, $n^{1000001}$ is *polynomial* in $n$, whereas $1.000001^n$ is *exponential* in $n$. Since the exponent of the first term (1000001) is very large, and the base of the second term (1.000001) is nearly 1, it takes a long time for the exponential (in $n$) function to overtake the polynomial (in $n$) function, but it *will* overtake it eventually as it is a faster growing function asymptotically than a polynomial function. Informally, any polynomial function (polynomial in $n$) will be $O(g(n))$ where $g(n)$ is an exponential function in $n$.
> 6 votes

# Answer
The $n$ where the two expressions are equal isn't all **that** huge. Here's how to calculate it.

We want $$ 1.000001^n \approx n^{1000001}.$$ This is the same as
$$e^{n \log 1.000001} \approx e^{1000001 \log n}.$$ Now, taking the $\log$ of both sides, and using Taylor's formula to approximate the left-hand side, we get $$ n\*10^{-6} \approx 10^6 \log n,$$ or $$\frac{n}{\log n} \approx 10^{12}.$$ Since this means $\log n \approx \log 10^{12},$ we get $$n \approx 10^{12} \log 10^{12} = 2.7 * 10^{13}. $$ More exactly, using Maple to solve the equation numerically (you have to give it the estimate above as a starting value or it gives up), we find that $n \approx 3.1\*10^{13}$.
> 7 votes

# Answer
What you have been told is true. However the number where both function meet is huge (see Paresh' answer). There is also a second intersection point that you got with Wolfram. You can play around with smaller numbers of this pattern to get a feeling how large this value gets.

To see that the statement is true, it is the easiest to evaluate $$\lim\_{n\to \infty} \frac{n^{10001}}{1.00001^n}.$$ Since can be done best with the rule of l'Hôspital. After taking 100001 derivatives of both enumerator and denominator you get $$\lim\_{n\to \infty} \frac{n^{10001}}{1.00001^n}=\lim\_{n\to \infty} \frac{0}{\ln 1.0001 \cdot 1.00001^n}=0.$$

Hence, $n^{10001}= O(1.0001^n)$.
> 6 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: What do these arrows in design pattern diagrams mean?
I am learning about software design patterns by reading Wikipedia pages about them. A lot of the patterns such as the bridge pattern have diagrams with boxes and different kinds of arrows:

Source: Wikipedia

Do these diagrams stem from a standard? Why do some arrows have different ending markings? Also, why are some of them dotted?

# Answer
> 3 votes
ConcreteImplementer inherits from Implementer, Same for RefinedAbstraction and Abstraction

The other arrow: these classes composes without belonging to each other.

See also here.

The paper-like box is a note (a comment).

# Answer
> 4 votes
The arrows mean distinct things. This is a UML (unified modeling language) diagram. Rules for reading and writing these diagrams are pretty well-established, and you should be able to look up some references.

In that diagram, the hollow arrow means generalization (i.e., inheritance, IS\_A), and the hollow diamond means aggregation (i.e., a kind of association, HAS\_A). The dotted line connects a comment/label and contains auxiliary/meta information (I believe, but double check this one).

---
Tags: terminology, software-engineering
---


# Question
Title: Question about a semi-decidable property of languages
Consider the following property of recursively enumberable (RE) languages

$$ L = \\{ J \in \text{RE} \mid J \cap L\_{uni} \ne \emptyset \\}$$

where $L\_{uni}$ is the language of the Universal Turing machine.

I am wondering if $L$ is semi-decidable. That is (by definition) if the set $$ S = \\{ \langle T \rangle \mid L(T) \in L\\}$$ is recursively enumerable.

If I am not mistaken then this should be true because one can always construct a Turing machine $M$ that accepts a code $\langle T \rangle$ and (using non-determinism) generates the "right" input for $T$ and $T\_{uni}$, verifies that both accept the generated word (simulating the machines) and if so accepts the supplied string.

Can someone verify this claim?

# Answer
> 2 votes
Let $M$ be any computably enumerable set and define the set $$J\_M = \lbrace n \in \mathbb{N} \mid W\_n \cap M \neq \emptyset\rbrace,$$ where $W\_n$ is the $n$-th computably enumerable set. Then $J\_M$ is a computably enumerable set because $$m \in J\_m \iff W\_n \cap M \neq \emptyset \iff \exists m . m \in W\_n \land m \in M$$ is obviously a semidecidable condition, as c.e. sets are closed under finite intersections and existential quantification over $\mathbb{N}$.

We may now get your result by taking $M = L\_{\mathrm{uni}}$.

If you are wondering about the "obviously semidecidable" condition, we can put in a bit more details: to semidecide whether $W\_n \cap M \neq \emptyset$ just keep enumerating the elements of $W\_n$ and $M$ in parallel, until an $m$ appears in both enumerations.

---
Tags: computability, turing-machines
---


title: Routing Algorithms and Hosts

text:
# Question
Title: Routing Algorithms and Hosts
I'm reading a book about computer network theory, and one topic is discusses is routing algorithms. It only mentions (probably not intentionally) how routers participate in forming the understood network topology stored in each routers memory - the routing tables.

So this brings me to my question, do Host acts like dedicated routers in this case and participate in and become part of that understood topology of the network in nearby routers?

For example, it says that routers communicate with each other to form their routing tables to find the best path. Do **hosts as end user machines** find themselves in this routing table (**as an entry in dedicated router, routing tables**) or routing topology? Do they participate in forming it?

Likewise do Computer Hosts, have entries for nearby dedicate routers in their routing tables? I'm trying to find the relation ship between a router and a host in the this process.

The issue I'm having, is if they don't participate in this process, how do the routers not where the end user machines are in the topology?

Thanks :-)

# Answer
> 1 votes
I believe you are talking about the Internet and the IP. Here are answers of your questions:

First note the internet is a network of networks. Networks communicate with each other through routers. These big networks are like the ISP, your university or a big organization. Your computer belong to a small network in your ISP subnetwork. This small network is probably your WiFi switch and your computer.

1. Do hosts find themselves in the routing tables ? NO, but from the IP address of the host and its subnetwork, a router can tell whether they belong to the same subnetwork or not. If they do belong, then there is no need to route the message to another router. The message is simple sent down the subnetwork. You have to study in this case the BGP protocol and the structure of IP.
2. Your host got nothing to do with routing. The ISP takes care of all that. or your cellular company if you are using your mobile phone .. or etc .. It would be hugely complicated to let these terminals take care of that. Again, you must have a look on the IP structure.
3. If you try to send a message to X, then your router will look at X (which has an address probably similar to 122.23.12.11 or whatever !) from the upper digits, the router (which is your ISP router in this case) will know which neighbor router to send it to. In general, Internet routing is greedy. How a router selects its neighbors ? \[that's another topic\]

One advice: dont look to the Internet from a pure theoretical point-of-view.

I guess I answered your question ?

---
Tags: computer-networks
---


# Question
Title: Condition in Shamir Secret Sharing Scheme
For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}\_p\[x\]$). The constant coefficient of this polynomial is defined to be the key. Then the scheme sends to player $i$ the value $q(i)$ (for $i \leq k$ for some fixed $k$). The interpolation theorem says that if $n$ players come together, then I can use interpolation to reconstruct the polynomial (there is a unique polynomial $p$ of degree at most $n-1$ such that $p(i)=q(i)$ .. in otherwords $p=q$. So that I can grab the constant coefficient of $p$ and it must be the same as the constant coefficient of $q$, and hence must be the key).

The question I have, is that what if the polynomial is degree less than $n-1$. There seems to be nothing in the construction as described by Shamir that prevents this. However, Shamir states that $n-1$ players cannot reconstruct the polynomial.

The problem I am having is that there seems to be a "most of the time" clause missing. If I happen to pick a degree one polynomial then any two players can reconstruct the polynomial. So is it that the players do not know the degree of the polynomial, or that the probability of picking a small degree polynomial is low enough that the probability of two participants guessing the key is still the same as random guessing, or am I missing something else.

# Answer
I am not sure if this will completely answer the question, but I have a couple observations that might help.

First, note that for the random polynomial $q$, $q(0) = a\_0$ is the key -- this is from the way that polynomial interpolation works. So it is important that the value $q(0)$ is never sent to a participant; $q(i)$ is sent for $0 \< i \< n$. This is also why it is important that the prime $p \> k$ (where $k$ is the number of participants) -- it is to ensure that I can obtain $k$ "shares" without revealing the key.

Second, the polynomial $q$ is not just random, but also secret. The fact that the degree of the polynomial $q$ is unknown matters. When $n-1$ participants come together, they can do anything they want -- they are super clever. They claim that the key is $w$. However, there is a unique polynomial $g$ of degree $n-1$ such that $$g(i) = q(i)$$ and $$g(0) = w$$ However, this would be true for any $w$. Since we know that the secret is given by a polynomial of degree less than $n$, and from the data that the pool of $n-1$ participants have, any value of key supposed is as likely ... no value of key can be ruled out. \**Note however, that this is not true if the participants know the degree of the polynomial.
> 4 votes

# Answer
There is no problem. True, if the polynomial you pick is of degree 1, then two parties can find the secret. However, they don't know that fact (without learning the other shares).

For instance, assume that the secret is 0, and you picked the polynomial $x$. Thus party 1 gets $q(1)=1$ and party 2 gets $q(2)=2$.

Had they known that the other shares are {3,4,5, ....}, they would've been able to realize that $q(x)=x$ and learn $q(0)$. *But they don't*. For each other selection of shares $\\{q(3),q(4),...\\}$ there exists a unique polynomial, and a different secret. Without knowing $\\{q(3),q(4),...\\}$, any value in $\mathbb{Z}\_p$ has the same probability of being $q(0)$, and thus the two users have no information about $q(0)$ prior to learning the other shares.
> 1 votes

---
Tags: probability-theory, cryptography
---


# Question
Title: Machine Learning: how to correctly calculate gradient descent for simple linear problem
So, I was trying to learn machine learning, and, after watching a couple of Andrew Ng's lectures decided to try and write a simple piece of code to determine what someone's salary would be based on the number of years they worked at a company by this simple linear function:

salary = w1 * numberOfYears + w0

I then used the least square method to calculate the error between the predicted results and the actual results and tried to minimize the error of the gradient of that function:

Error = (1/2) \[ sum of (predicted - actual)^2 for all samples (x, y) \]

The predicted value is the one calculated by the linear equation above, and actual = y. w1 and w0 are weights to the function that are set to some initial values (0 and 0 for example) and are changed to decrease the error throughout the process of gradient descent.

Steps to the algorithm:

1) Choose some (random) initial values for the model parameters (w).
2) Calculate the gradient G of the error function with respect to each model parameter.
3) Change the model parameters so that we move a short distance in the direction of the greatest rate of decrease of the error, i.e., in the direction of -G.
4) Repeat steps 2 and 3 until G gets close to zero.

In my implementation I have this code:

```
for(int i = 0; i < numSamples; i++) {
    double error = prediction(data.X[i]) - data.Y[i];
    while(nearsZero(error)) {
        for(int j = 0; j < w.length; j++) {
            w[j] -=  0.1 * error * data.X[i][j];
        }
        error = data.Y[i] - prediction(data.X[i]);
    }
}

```

If I run this with only one sample (meaning ignore the outermost loop), then the weights continuously subtract a value that is continuously nearing infinity (or -infinity). If I change the w\[j\] -= ... to a w\[j\] += ... then the function works for the first value and sets initial w that will solve it for one sample (but that isn't what I was supposed to do as far as I can tell). Also, when I add multiple samples the numbers just do the same thing on the second sample that they were doing on the first sample when I had -=.

I feel like gradient descent doesn't make sense here because it was demoed on graphs like z=y^2+x^2, which looks like a big bowl with one central min that it will find eventually.

On the graph in my problem the graph looks like a parabola that extends to infinity in both directions and has infinite min values along a line.

I'm not sure what it is that I am doing wrong, but I would assume that it's something to do with my understanding of the problem. If anyone knows how to get this working I would appreciate it.

**EDIT:** Updated data.X\[i\] in the while loop to data.X\[i\]\[j\]. Each data point i should have some value Y\[i\] and an array of X values at X\[i\].

# Answer
> 3 votes
First off, your gradient is `error*x1` with respect to w1, but not to w0. The gradient for w0 is just `error`.

Second, you're computing `error` with the wrong sign. It should be `predicted - actual`, not the other way around. What you're doing is essentially *adding* the gradient at every step.

---
Tags: machine-learning, linear-algebra
---


# Question
Title: What is OUTER UNION and why is it partially compatible
I am trying to understand how a `OUTER UNION` $∪^✳$ works, and why it is only partially compatible.

I am aware this operation was created to take union of tuples from two relations if the relation are not type compatible (which I understand).

Examples of this operation will be great!

# Answer
> 2 votes
There are two flavors of outer union: with and without `NULL`s. Google search readily exibits an example for `NULL`s version. The cleaner version of relational algebra desn't allow `NULL`s, and outer union is defined via De Morgan's law:

$ X \bigcup Y = \overline {\overline X \Join \overline Y} $

Date&Darwen call this operation $\blacktriangleleft OR \blacktriangleright$.

Given

```
R = [A B]
     1 2
     3 4

```

and

```
S = [B C]
     4 5
     6 7

```

both outer join variants agree that the result projected to common column `B` should be `{2,4,6}`. This is what is called *inner union* -- alternative way of generalizing standard relational algebra union operator. Now the problem is finding values of attributes `A` and `C`. Next, we match the values of the "middle column" with attributes `A` and `C` trying to leverage information in the relations R and S. In case of value `B=2` we don't have matching value of `C`. Likewise, for `B=6` we don't have matching value of `A`. Therefore, D&D $\blacktriangleleft OR \blacktriangleright$ operator fills the blanks in

```
[A B C]
 1 2
 3 4 5
   6 7

```

with all the values from corresponding domain, while the `NULL` version just blurts `NULL`s.

---
Tags: terminology, database-theory, relational-algebra
---


# Question
Title: Distributed algorithms - $\alpha, \beta$ synchronizers
I experience a difficulty in solving exercises in distributed algorithm. Below is the the exercise I try to solve, it looks like I miss basic idea.

**Exercise.** Consider a 15-processor asynchronous network with processors 0,…,14. The processors constantly run a synchronizer. Let $v$ and $v'$ be two processors in the network, and suppose that at a certain moment, the pulse counter at $v$ shows $p=27$. What is the range of possible pulse numbers at $v'$ in each of the following cases:

a) The network is a ring, $v$ is processor number 11, $v'$ is processor number 2 and the synchronizer used is $\alpha$.

**Idea**: if $v'$ hasn't sent any message up to pulse 27 of $v$, pulse of $v'$ is still 0, therefore lower bound of pulse of $v'$ is 0. The model of synchronizer is $\alpha$ it means every node informs all nodes about it's safe(v,p) state, hence I assume that $v'$ might be 11-2=9 pulses before $v$.

b) The network is a full balanced binary tree (4 levels), $v$ is the root, $v'$ is one of the leaves and the synchronizer used $\beta$.

**Idea**: $v'$ also might have pulse 27, in this case $v$ sends at speed of $v'$.

c) The same as in (b), except both $v$ and $v'$ are leaves.

Honestly, I am completely confused by this exercise, I wrote few ideas, but I don't have any understanding and any intuition behind the answers.

I will appreciate if someone show me the way how to solve such exercises.

# Answer
Please find solutions of all cases:

For case A ($\alpha$-synchronizer), the pulse at a node can either be more, equal, or less by one (therefore, $\\{26,27,28\\}$). This is because a node must inform its neighbors about its safeness and not all the other nodes (according to your question).

You can see the rules in the following (copy-pasted from the paper)

1. A new pulse may be generated at a node whenever it is guaranteed that no message sent at the previous pulses of the synchronous algorithm may arrive at that node in the future.
2. Using the acknowledgment mechanism described above, each node detects eventually that it is safe and then reports this fact directly to all its neighbors. Whenever a node learns that all its neighbors are safe, a new pulse is generated.

For case B: ($\beta$-synchrnoizer) - if $v$ is the root, then at $v'$ the pulse is either the same or less (therefore, $\\{26,27\\}$).

For case C: ($\beta$-synchrnoizer) - if both $v$ and $v'$ are leaves, then here we may assume that the broadcast of the root is not received at the same time - since the network is asynchronous (otherwise, why would we need a synchrnoizer). Here, if $v$ is 27 then $v'$ is either 28 if the update of $v'$ is received before $v$ ,, or 26 if the update of $v'$ is received after. Or they both have the same pulse (therefore, the range is $\\{26,27,28\\}$.
> 3 votes

---
Tags: algorithms, distributed-systems, synchronization
---


# Question
Title: How can one simulate a PDA with a FIFO queue PDA?
I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most element which can be popped. When we push something, it goes to the top of the stack.

In a queue, as I understand, elements get "pushed" to the top, but pop from the bottom. Thus, first in first out.

In a stack (LIFO) PDA, let's say we push 'a'. It's at the top of the stack, and when we pop, we pop 'a' since it is at the top.

In a queue (FIFO) PDA, when we push 'a', it is at the top, but when we pop, it will be from the bottom of the queue and thus it will not be 'a' (assuming the size is greater than 2).

So how can we simulate a regular PDA which uses a stack, with a FIFO (queue) PDA?

# Answer
The answer is: "rotate".

Consider the stack like (*bottom*) `ABCD` (*top*). stack-pop is from top, queue-pop is from bottom (this is directed to myself, I am easily confused). Pushes are from top.

Now, if we want to stack-pop, we push a marker `#` (to top) then repeatedly queue-pop and push, essentially moving everything from bottom to top. If we delay the pushes by one, we are able to stack-pop, just not pushing the last symbol before the `#`.

By the way, almost the same trick shows that we can even simulate the Turing machine by a single queue. Which was asked in our sister math department.
> 7 votes

---
Tags: automata, pushdown-automata, machine-models
---


title: Height of AVL after entries

text:
# Question
Title: Height of AVL after entries
> **Problem:** Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$ elements. After the insertion of $n^2$ elements, what would be its height?

**My idea:** the height of an AVL tree is originally $O(\log(n))$ where $n$ is the number of elements. After insertion of $n^2$ elements, its height will be:$$O(\log(n+n^2))=O(\log(n^2))=O(2\log(n))=O(\log(n))$$

My answer would be $O(\log(n))$ but I'm having doubts.

Why is the asymptotic complexity of the result the same despite the fact that there are more elements?

# Answer
> 1 votes
To show that this isn't always the case, imagine you added $e^n$ elements, then it would take

$$O(\log(n+e^n))=O(\log(e^n))=O(n)$$

But what does that really mean? It's not that your binary tree takes $O(n)$ time on $n$ elements to find something. Rather, it takes $O(\log(m))$ time for $m=n+e^n$ elements.

I can understand why you would be confused; if you had to search linearly through a list, and then you added $n^2$ elements, it would take $O(n^2$) time in terms of the original input, but not the new input, for which it would take $O(m)$ time on $m=n+n^2$ elements.

Chances are you didn't want to solve for the asymptotic solution; it generally doesn't make sense to. What you probably want is the approximation $\log(n+n^2)\approx\log(n^2)=2\log(n)$; that is,

> **For a self-balancing tree, squaring the input size doubles the search time**.

---
Tags: algorithms, asymptotics, binary-trees, search-trees
---


title: A puzzle related to nested loops

text:
# Question
Title: A puzzle related to nested loops
For a given input $N$, how many times does the enclosed statement executes?

> for $i$ in $1\ldots N$ loop
> $\quad$for $j$ in $1\ldots i$ loop
> $\quad$$\quad$for $k$ in $i\ldots j$ loop
> $\quad$$\quad$$\quad$$sum = sum + i$ ;
> $\quad$$\quad$end loop;
> $\quad$end loop;
> end loop;

Can anyone figure out an easy way or a formula to do this in general. Please explain.

# Answer
You need to solve simple formula

$\sum\_{i=1}^N\sum\_{j=1}^i\sum\_{k=i}^j1$

this will give you overall result of

$\frac{1}{6}N(N+1)(N+2)$

Math is easy to do here but I used Wolfram Alpha
> 4 votes

# Answer
What you really count in the variable $\text{sum}$ are triples of the form $$\\{ (a,b,c) \mid 1\le a\<b\<c\le N\\}.$$

Clearly there are $N(N-1)(N-2)$ triples of different elements. Since you only consider sorted triples, you only count one of the possible $6=3!$ permutations for every triple containing $a,b,c$. Therefore you overcount by a factor of $6$, and this gives you $\text{sum}=N(N-1)(N-2)/6$.
> 3 votes

---
Tags: algorithm-analysis, loops
---


# Question
Title: Proof for P-complete is not closed under intersection
Unfortunately I have no idea how to show this:

> Show that the set of ${\sf P}$-complete languages is not closed under intersection.

As far as I understand my lecture notes, ${\sf P}$-completeness is defined as follows:

* $A \subset \Sigma^{\*}$ is complete for ${\sf P}$ iff $A \in \text{P}$ and $\forall B \in {\sf P}, B \le\_L A$
* $\le\_L$ is ${\sf LOGSPACE}$-reduction: for $A,B \subset \Sigma^{\*}$, the relation $A \le\_{L} B$ is defined by $$A \le\_{L} B \quad\text{iff}\quad \exists f \in {\sf FLOGSPACE}, (x \in A \Leftrightarrow f(x) \in B)$$

# Answer
Let $A$ be any P-complete problem (say circuit evaluation). Here are two other P-complete problems: $A\_0 = \\{0x : x \in A \\}$ and $A\_1 = \\{1x : x \in A\\}$. The problem $A\_0 \cap A\_1 = \emptyset$, while definitely in P, isn't P-complete. The latter is true even if we allow Turing reductions, assuming $L \neq P$.
> 10 votes

# Answer
I think this questions exploits only a technicality. However, you can follow this path

1. The class of ${\sf P}$-complete languages does not contain $\Sigma^\*$ and $\emptyset$. This is true for all classes and not only ${\sf P}$, since in order to reduce a language $L\_1\neq\emptyset,\Sigma^\*$ to another language $L\_2$, there has to be at least one element in $L\_2$ and at least one element in $\bar L\_2$
2. Show that there are two disjoint ${\sf P}$-complete languages (use Yuval's answer).
> 5 votes

---
Tags: complexity-theory, time-complexity, reductions
---


# Question
Title: What is an instance of NP complete problem?
I don't understand this definition of an "instance" of a problem. Quoting from the CLRS book on page 1054 on abstract problems (Chapter 34.1):

> We define an abstract problem $Q$ to be a binary relation on a set $I$ of problem **instances** and set $S$ of problem **solutions**.

# Answer
> 9 votes
Other answers are good, I'll give only another trivial example:

* *problem*: "given two numbers $k,n$ with $1 \< k \< n$, does a number $m$ smaller or equal than $k$ exist such that $n$ is divisible by $m$ ?"
* the *instances* of the problem (or informally the *input* of the problem) are all the valid pairs $(k,n)$ such that $1 \< k \< n$; so $I = \\{ (2,3),(2,4),...,(3,4),(3,5),...\\}$
* the set of solutions is the set $S = \\{ YES, NO \\}$, indeed the problem is a *decision* problem (the answer to the question "does exist ...?" is simply YES or NO)
* the abstract problem $Q$ is a subset of $I \times S$ and is the relation that associates an instance of the problem to the correct answer

So:

```
Q = { ( (2,3), NO  ),
      ( (2,4), YES ),
      ( (2,5), NO  ),
      ....
      ( (6,13), NO ),
      ( (6,14), YES ),
      ...
      ( (7,13), NO ),
      ( (7,14), YES ),
      ...
    }

```

P.S. the problem $Q$ is known as INTEGER FACTORIZATION and probably you'll meet it again ... :)

# Answer
> 7 votes
An *abstract decision problem*, such as **clique**, is an assignment of a truth value (b\>true or **false**) for each *instance* of the problem. In the case of **clique**, each instance is a pair $(G,k)$, where $G$ is a graph and $k$ is a natural number, and the problem assigns **true** to a pair $(G,k)$ if $G$ contains a clique of size $k$; otherwise it assigns **false** to the pair.

An *algorithm* for an abstract decision problem is an algorithm which takes an instance and returns its correct truth value. So an algorithm $A$ for clique takes as input a graph $G$ and an integer $k$, and returns whether $G$ contains a clique of size $k$. An algorithm should work for all instances at once, and we are interested in the resources it consumes (time and memory) in terms of the length of the input.

For example, let us consider the following algorithm for **clique**: given $(G,k)$, go over all sets of vertices of $G$ of size $k$, and for each one, check whether it constitutes a clique. One can check that the running time of this algorithm isn't polynomial in the length of the input.

We are interested in algorithms that work for *all* instances. For any given instance $(G,k)$, we can construct an algorithm that works correctly on it (one of the following algorithms will do: the algorithm that always outputs **true**, and the one that always outputs **false**). So it's not meaningful to look at single instances. If we have a particular algorithm in mind, then this algorithm might work better on some instances, and in that sense we can say that an instance is easy for a particular algorithm.

NP-completeness theory deals with worst-case time complexity - we're interested only in algorithms that work for all instances. The area of average-case complexity deals with algorithms that only have to work on almost all instances (in some precise sense), the idea being that such an algorithm is very likely to work on every instance encountered in practice.

# Answer
> 3 votes
A problem instance is the actual case you're trying to solve.

For example, the problem "can this set of numbers be divided into two sets which have the same sum" is an NP-hard problem. An instance of this problem would be an actual set of numbers, for example 87, 58, 62, 104, 29, 78.

# Answer
> 3 votes
In short: an instance of a problem is the input for an algorithm solving the problem. Correspondingly, solutions are the outputs of such an algorithm.

---
Tags: complexity-theory, terminology, np-complete
---


# Question
Title: Grammar for a language: odd length, middle character not repeated
Consider the following language over the alphabet $\mathcal{A} = \\{a,b,c\\}$: $$L = \left\\{w \in \mathcal{A}^\* \mid \text{\\(|w|\\) is odd and the middle character in \\(w\\) occurs nowhere else in \\(w\\)} \right\\}$$

I am trying to come up with a grammar for $L$, but I'm getting nowhere. I came up with some sample strings from the language which would be accepted: `b`, `abcab`, `accbcaa` I understand the length of the string has to be odd, and the middle character cannot be repeated anywhere in the string.

Therefore, the above three strings are accepted. However, something like `aabbb` will not accepted, because even though the length is odd, the middle character is repeated.

Can someone help with a grammar for $L$?

# Answer
Assume the middle character is $a$. Then a grammar is $$A \rightarrow bAb | bAc | cAb | cAc | a$$ Similarly, we can define nonterminals $B$ and $C$ for the strings in our language where $b$ and $c$, respectively, are the middle symbols. Given those, you can get a grammar for your language by taking the union: $$S \rightarrow A | B | C$$
> 8 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Conflicting definitions of language accepted by Turing Machine?
I am reading Papadimitriou, Computational Complexity, page 24, where it is says

> We say that $M$ accepts $L$ whenever for any string $x \in (\Sigma - \\{\sqcup\\})^\*$, if $x \in L$, then $M(x) =$ \`\`yes''; however, if $x\notin L$, then $M(x) = \nearrow$.

The key issue is what happens for $x \notin L$. This definition insists that $M$ must not halt for $x \notin L$. Other sources I read, e.g., this says that if $x\notin L$ then either $M$ does not halt, or $M$ halts at \`\`no''.

Prima facie this seems to me to be a significant difference. Could someone clarify to me if these definitions are equivalent and if there is no loss of generality in talking of acceptance in the sense of Papadimitriou? Or is only one of these definitions the correct one?

# Answer
The two definitions are in fact equivalent. Both halt and accept when the word belongs to the language. One is more restricted for strings outside of the language: it is not allowed to halt. Every Turing machine in the "classic" definition (which allows halting with "no") can be changed into a non-halting one easily. Just when the old machine wnat to stop in a no-state, its restricted equivalent moves into a no-sate that actually does not stop but instead keeps walking to the right (or the left, what you want). Both versions of the machine will accept the same language.

Thus, both versions define the class of recursively enumerable languages. Or partially decidable or Turing-acceptable, but I prefer the old terminology.

In conclusion, Papademitriou has a slightly non-standard definition, which is nevertheless equivalent to the commonly used one.
> 7 votes

---
Tags: reference-request, turing-machines
---


# Question
Title: determine if a machine prints a certain string in less time than it takes to run the machine itself?
Does there exist a procedure that determines if a polytime machine prints a certain string, and does so in less time than the machine itself takes to run?

Define a machine $a$ that analyzes another machine $b$, input $i$, and string $r$:

$a(b,i,r) = b(i) \text{ prints } r$ $\[T\_b = O(n^k), k \>= 2\]$

Is there an $a$ with run-time $T\_a \in o(T\_b)$ on all $b,i,r$?

# Answer
Your question is somewhat unclear, but here is something you can prove using the time hierarchy theorem. We will use the convention that a Turing machine computing some function prints the result at the end, and prints nothing except that. Suppose $T$ is a machine that accepts the code of a machine $P$ running in time $O(n^\alpha)$ and an input $x$, and returns the output of $P(x)$ in time $O(n^\beta)$ for $1 \leq \beta \< \alpha$. Using $T$, we can evaluate the function computed by $P$ in time $O(n^\beta)$, so $\mathrm{Time}(n^\alpha) \subseteq \mathrm{Time}(n^\beta)$, which contradicts the time hierarchy theorem.
> 2 votes

---
Tags: complexity-theory, time-complexity, turing-machines
---


# Question
Title: Inapproximability result implies apx-hardness?
If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard?

# Answer
> 3 votes
If P$=$NP then there is a polytime algorithm for any NP optimization problem, and so *every* problem is APX-hard. So from now on, suppose that P$\neq$NP.

We can associate with any decision problem $L \in NP$ an optimization problem $o\_L$ by defining $o\_L(x) = 1$ if $x \in L$ and $o\_L(x) = 2$ otherwise. Suppose $o\_L$ reduces to $o\_M$ via a PTAS reduction $(f,g,\alpha)$ (notation as in the Wikipedia article). Let $C = 1+\alpha(1/2)$. Thus if $y$ is a $C$-approximation to $o\_M(f(x))$ then $g(x,y,1/2)$ is a $3/2$-approximation to $o\_L(x)$, from which we can determine whether $x \in L$ or not. Altogether, this gives a polytime reduction from $L$ to $M$. Now take any NP-complete language for $L$ and any NP-intermediate language for $M$ (such a language exists because of Ladner's theorem). On the one hand, since $M \notin P$, you cannot 2-approximate $o\_M$. On the other hand, $L$ doesn't reduce to $M$ (since that would apply that $M$ is NP-complete), and so $o\_L$ doesn't reduce to $o\_M$. We conclude that $o\_M$ is *not* APX-hard.

---
Tags: complexity-theory, approximation
---


# Question
Title: Simple proof that circuit satisfiability problem is NP-Hard
$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.

> $\cc = \\{\langle C \rangle : C \text{ is a satisfiable combinatorial boolean circuit} \\}$
>
> **Lemma:** The $\cc$ problem is $\mathsf{NP}$-hard.

Can anyone provide an easy-to-understand proof?

# Answer
> 7 votes
The (very) simplified version is that they convert any verification algorithm $A$ for a language $L \in \text{NP}$ into a circuit.

What they end up with is a circuit $C$ that, given a (binary) string $x$ is satisfiable (i.e. $C(x)=1$) if and only if $x \in L$ (i.e. there exists a certificate $y$ such that $A(x,y) = 1$).

They do this by encoding the working of the algorithm embodied by some Turing Machine (i.e. the transition function) as a circuit $M$. The total circuit $C$ is then a series of concatenations of $M$, where the input values to each iteration of $M$ is a binary encoding of the state of the TM embodying $A$.

As every bit of this (including the number of steps $A$ takes) is polynomially bounded by the size of $x$, the circuit can be constructed in polynomial time.

So what they give overall is a polynomial time way to construct a circuit simulating $A$ set by step that is satisfiable if and only if we can find some certificate that $x \in L$. Then if we could decide in polynomial time if $C$ is satisfiable we'd know that there's some certificate which proves $x \in L$, hence deciding $L$ in polynomial time.

---
Tags: complexity-theory, np-hard, satisfiability, circuits
---


# Question
Title: Cliques in an alternate graph representation
EDITS: corrected $r$ to add edges just like $f$ does in paragraph 8 per the first comment below. Also specified the Clique problem of interest in paragraph 2.

Having received no response to this question on math.SE, I'm asking it here. Thanks for your help.

In the Wikipedia article on the Clique problem, we are told that under the brute-force algorithm, there are potentially exponentially many subgraphs of a given graph that must be checked as possible cliques. The particular Clique problem I'm interested in is the problem of finding a clique larger than a given size.

Informally, the question here is whether an unknown representation of graphs will also have a possibly exponential number of subgraphs that must be checked as possible cliques under the brute-force algorithm.

I'll try to make this more precise by first giving a function to build up normal graphs, and then a new, different function to build up the unknown representation with properties that the new function must satisfy. The whole discussion here is about undirected graphs.

Let's start by defining an operation that will build up a normal undirected graph. Let $E$ denote the null graph: $0$ nodes, $0$ edges. Let $f$ be the following operation:

$f(n\_1, n\_2, G)$

$f$ takes a graph $G$ and returns a graph with the edge from $n\_1$ to $n\_2$ added to $G$. So while the null graph $E$ is definable without $f$, all other standard graphs in our discussion are built by $f$: $f(n\_1, n\_2, G)$ where $G$ could equal $E$.

As an example, the expression $f(n\_1, n\_2, E)$ returns the graph $(\\{n\_1, n\_2\\}, \\{(n\_1, n\_2)\\})$.

Now consider an alternate graph representation $H$, built by a function we'll call $r$ that adds edges like $f$ does. But $H$ is an unknown representation that must obey the properties below.

First let's describe a similarity relation ($\sim$) between $G$ and $H$:

Case 1. $G \sim H$ if $G = E$ and $H = E$.
Case 2. $G \sim H$ if $G = f(n\_1, n\_2, G\_1)$, $H = r(n\_1, n\_2, H\_1)$, and $G\_1 \sim H\_1$.

As before, the null graph $E$ is definable without $r$, but all others in the unknown representation are built by $r$: $r(n\_1, n\_2, H)$ where $H$ could equal $E$.

The representation $H$ must obey the following properties:

1. Just as $G$ is built by successive applications of $f$ to the null graph $E$, $H$ is built by successive applications of $r$ to the null graph $E$.
2. The order in which the edges of a graph are added doesn't matter: in ordinary graphs, $f(n\_1, n\_2, f(n\_3, n\_4, G)) = f(n\_3, n\_4, f(n\_1, n\_2, G))$; in the unknown representation, $r(n\_1, n\_2, r(n\_3, n\_4, H)) = r(n\_3, n\_4, r(n\_1, n\_2, H))$.
3. Since we're talking about undirected graphs, the order in which the nodes of an edge are specified doesn't matter: in ordinary graphs, $f(n\_1, n\_2, G) = f(n\_2, n\_1, G)$; in the alternate representation, $r(n\_1, n\_2, H) = r(n\_2, n\_1, H)$.
4. Just as for $G$, $H$ has an operation $hasClique(\\{n\_1,...,n\_k\\}, H)$ which is true exactly when there is a clique among the nodes $\\{n\_1,...,n\_k\\}$.
5. Consider a graph $G$ with nodes $\\{n\_1,...,n\_m\\}$ and a subset $\\{n\_i,...,n\_j\\}$ and $G \sim H$ for some $H$. Then we require that nodes $\\{n\_i,...,n\_j\\}$ form a clique in $G$ if and only if the nodes $\\{n\_i,...,n\_j\\}$ form a clique in $H$. What I'm trying to capture here is that $H$ has a clique wherever $G$ does and vice versa for $G \sim H$.

Question: Can we conclude that $H$ has potentially exponentially many subgraphs that must be checked as possible cliques under the brute-force algorithm, just as in normal graphs?

# Answer
Like Joe, I'm assuming that you want to find all maximal cliques.

Assuming your representation can represent all graphs (and there's no reason to suspect otherwise), then there's certainly still possibly exponentially many maximal cliques as subgraph - as Joe suggested, this is a property of the graph, independent of the representation. So with the actual reporting of the cliques, we still have to potentially "say" an exponential number of things, so regardless of how tightly we can encode a graph, there's still an exponential number to report.

The question I guess is then whether by some clever representation we can reduce the number of (sub)graphs that we have to *check* to enumerate all the maximal cliques. In principle I guess this is possible, there's no *a priori* reason we couldn't decorate a data structure with additional information that would help us to enumerate cliques - the problem is then that this data structure could grow exponentially compared to the size of the original input. So in a sense it would add nothing - we're just hiding computation time in the space the data takes up.
> 1 votes

# Answer
You haven't specified exactly what your output is, but if it is the standard "output all maximal cliques", then the size of your output is exponential in the worst case, and therefore regardless of what algorithm you use, or what your representation\* is, the algorithm may have to spend exponential time, just to output the answer.

\*This is assuming the number of cliques you can represent in a single machine word is at most polynomial (which it clearly is, for any reasonable model).
> 1 votes

---
Tags: complexity-theory, graphs
---


title: Generalized data structure

text:
# Question
Title: Generalized data structure
Data structures are seen as important, equal to algorithms. This view is especially encouraged in situations, where appropriate data structure is the main factor that allows an algorithm to exist and to perform at satisfying complexity.

However, despite the additional features of data structures (e.g. organization, like in trees storing entries according to less-like relation), all that data structures do is keeping information unchanged between algorithm's actions. Can this generic feature of data structures be izolated and defined in abstract way?

# Answer
> 4 votes
Notice that a data structure stores more than just it's accessible elements. This is probably what mean by *additional feature*, but I would consider it the *essential feature*. Take for example a binary search tree. This tree stores information on the order of its elements. In particular, by a traversal you can output the sorted sequence of elements stored in the tree in linear time. There are roughly $\Theta(4^n)$ different full binary trees with $n$ leaves. Thus the data structure stores **roughly** $2n$ additional bits in this case.

Maybe this view helps. Some algorithmic problems are one-shot problems. So you take the input, process it, and then (hopefully) output the solution. Other problems, however, are trying to solve several problems for which part of the input is mostly the same. Here it might pay off to preprocess the static input (the data), such that further requests are easier to answer. The result of the preprocessing is stored (often in form of a labeled graph). This is what you do, when you store data in a data structure.

The above paragraph explained how static data structure behave. Usually data structures are dynamic, allowing you to alter the represented data and its associated information.

# Answer
> 0 votes
I will add an answer for different aspect: *How is an ADT(Abstract Data Type) different from an abstract type?*

An ADT has:

1. Storage of elements of the same type
2. Limited interface - operations for storing and retrieving elements from the data structure
3. Inner processing - automatic operations that are executed upon the elements of the data structure
4. The structure is optimized in time/space complexity and/or "optimized" in usage complexity

The generic data feature of ADTs, besides the storing and interface operations of adding/getting elements, is the **(optimized) automatic inner processing of the elements**. In concrete implementations this feature results in additional memory/time. This feature is used to simplify algorithms that need such a processing and a storage of same type elements.

---
Tags: algorithms, data-structures, information-theory
---


# Question
Title: Deterministic context-free languages are closed under regular right-product
I am looking for a proof for the following problem:

> For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language.

Note: $RL$ may not satisfy this condition, e.g. if $L=\\{wcw^R\mid w\in (a|b)^\*\\}$, and $R=\\{a\\}^\*$.

# Answer
Here is an idea. You have to work out the details by your own.

Let $Q\_R$ be the states of a DEA accepting $R$, and let $Q\_L$ be the states of a deterministic PDA accepting $L$. You build now a new deterministic PDA $P$ that accepts $LR$ as follows:

The state space of $P$ is $Q'=Q\_L\times \mathcal{P}(Q\_R)$. If you have read $w$ and you are with $P$ in state $(s,T)$, this tells you the following: $L$ would be in state $s$ after reading $w$, and for every $t\in T$ there was a possibility that a prefix of $w$ was in $L$, and the remaining suffix of $w$ would have send the DEA for $R$ to state $t$. You accept if you are in a state $(s,T)$, that contains an accepting DEA-state in $T$. The transitions can be worked out straight-forward. Notice that it might be helpful to modify the PDA for $L$ first, such that it has a total transition function. You can achieve this easily by adding a non-accepting dummy states, that collects all missing transitions.
> 4 votes

---
Tags: formal-languages, context-free, closure-properties, pushdown-automata
---


title: Show that k-clique lies in L

text:
# Question
Title: Show that k-clique lies in L
The following exercise is difficult for me:

> Show that for each $k \in \mathbb{N}$ the question of existence of a $k$-clique within a graph lies in $\text{L}$.
>
> Hint: A $k$-clique denotes $k$ verteces within a graph that are all connected with each other.
>
> Annotation: if the question also considers $k$ as parameter, then the problem is $\text{NP}$-complete.

So $\text{L}$ is "the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space". Now I'm wondering if this exercise isn't a catchy question, since I've found this paper and it says "We give an algorithm for $k$-clique that runs in (...) $O(n^{\varepsilon})$ space, for all $\varepsilon \> 0$, on graphs with $n$ nodes"?

Furthermore, I also don't understand the annotation, because how should it be possible to not consider $k$ for the $k$-clique problem?

# Answer
If you consider $k$ a constant, then k-clique can be solved be enumerating all $O(n^k)$ sets of vertices and checking that there are edges present in polynomial time (since the exponent is constant).

Enumerating k-Tuples of numbers up to n can be done in $k\log n$ space, you only have to figure out how to check for the presence of an edge between two vertices without using much space. Depending on how much details you have to give this is either obvious or very tedious to write down.
> 5 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: How does an automaton actually "compute"?
In my studies in computability I have come across the notion of the "machine", an abstract representation of a device that essentially computes. I have read about Turing Machines and Wolfram's binary cellular automata and I understand them.ie. the rules, states, colours, etc. and how they work. They begin in some state and run forever(unless a terminating state is specified). The point I'm trying to make here is that they receive no external input and are essentially functions of themselves:their current state is some function of its starting state, unlike realistic computers.

For the above reasons I'd like to know why automata are used to represent computers. More generally how can a machine be used to represent a computation?

# Answer
Most generally, an automata is a model of computation that describes the process how to convert an input to a solution. *Converting* means that there is a certain set of finite, elementary, local transformation rules, that is applied to the input. The idea behind the automata might be motivated by mechanical designs, however the concept is purely mathematical. In other words an instance of an automaton is a simplistic form of an algorithm. The concept of an automaton describes the way how computations in this model are carried out. Different models have different computational powers.

A realistic computer can be also described as a mathematical model. However the setting here is slightly different, since you will not want to build a new computer for every algorithmic problem you encounter. Also a computer is an interactive system, whereas classical automata are not. The closest model for a computer is the DFA. A computer has a large but finite set of ressources, hence the status of the system can be determined by a fixed-size description (think of a huge core dump). Depending on the input (clock, user input, etc.) the computer jumps form one state to a new state in a certain well-defined and unique way.

You might be disappointed, when you hear that closest model to a realistic computer is a DFA. But you should think of an automaton more as a formalism how to write an algorithm. And from that perspective, the way you write software (algorithms) on you computer, is equivalent to writing Turing machine programs.

Maybe you are confused by the fact, that automata work on strings, and not on other problem instances. However, this is not a big deal, since we can encode an instance as a string.
> 4 votes

# Answer
The input is what's initially written on the tape of the Turing machine. For cellular automata, I suppose the input is the initial pattern of life and dead cells. Then the rules of the machine define what kind of function to compute on the input.

Since we assume that there are e.g. TM rules to compute any computable function, we can use a TM as a model of computation.
> 2 votes

---
Tags: computability, automata, cellular-automata
---


# Question
Title: Using Clique decision to solve Clique optimization
How can you perform the clique decision algorithm fewer than $ O(n) $ times to solve clique optimization?

I'm not sure if my approach is right but this is my thought process: you would pick vertices in a graph and see if they form a clique, then keep picking more vertices until you have the max possible clique.

I'm not sure how it can be done less than $ O(n) $ times.

I can imagine an undirected graph such as:

where $ \\{A, B, C\\} $ and $ \\{B, C, D\\} $ would be cliques. The number of vertices is 4, and the number of vertices in the cliques is 3, which is $ n - 1 $. Would this count as being done in less than $ O(n) $ times, or is this the wrong approach to this problem?

# Answer
You would use binary search. Start with the lower bound being 3 and the upper bound $n$, where $n$ is the number of vertices. Call your clique decision oracle with a $k$ value halfway between the two bounds. If it answers "yes", move your lower bound to $k + 1$. If it answers "no", move your upper bound down to $k - 1$. Repeat until you have found the largest $k$ value the oracle answers "yes" to. It should take $O(\log n)$ calls to the oracle.
> 5 votes

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


# Question
Title: How does this algorithm for verifying if a string is $0^n1^n$ work?
I have found an efficient algorithm for verifying if a string $\omega$ is of the form $0^n1^n$, where $n \in \mathbb{N}$.

1. Scan across $\omega$. If a 1 appears before a 0, then reject.
2. Repeat so long as some 0s and some 1s remain on the tape.

1. Scan across $\omega$. If the total number of 0s and 1s remaining is odd, reject.
    2. Scan across $\omega$. Cross out every other 0 starting with the first 0.
    3. Scan across $\omega$. Cross out every other 1 starting with the first 1.
3. If no 0s and 1s remain in $\omega$, accept. Otherwise, reject.

I generally see how this algorithm is efficient. It gets rid of half of all 1s and 0s every iteration. How does it work though? Why must we reject if the total number of 0s and 1s remaining in $\omega$ is odd?

# Answer
This is a very informal answer (other users will give you a more formal and concise answer :-)

Suppose you have two numbers written in binary notation (the smaller one left-padded with zeros); for example:

```
14 =  1110
 6 =  0110

```

A simple algorithm to check if they are equal is comparing the two binary representations bit by bit; this can be done comparing the lower bit and then dividing the number by two (i.e. dropping the lower bit):

```
111[0] = 011[0]   OK (14 mod 2 = 6 mod 2 )
 11[1] =  01[1]   OK ( 6 mod 2 = 3 mod 2 )
  1[1] =   0[1]   OK ( 3 mod 2 = 1 mod 2 )
   [1] =    [0]   NO => 14 and 6 are different

```

You can easily notice that the lower bits of two numbers are the same if the numbers are both even or both odd (i.e. if their sum is even).

The algorithm above does exactly the same thing but the numbers are represented in unary:

```
00000000000000 111111   even 0s, even 1s, sum even OK
-0-0-0-0-0-0-0 -1-1-1   odd 0s, odd 1s, sum even OK
---0---0---0-- ---1--   odd 0s, odd 1s, sum even OK
-------0------ ------   odd 0s, even 1s, sum odd REJECT!

```
> 4 votes

---
Tags: algorithms, formal-languages
---


# Question
Title: Why is it that every k-tape Turing machine has a 1-tape TM that runs in $O(t^2(n))$?
Apparently, for every k-tape Turing machine that runs in time $O(t(n))$, there exists a 1-tape Turing machine that runs in $O(t^2(n))$.

I can see how any multi-tape machine $M$ can be simulated by a 1-tape machine $S$. Just have the tape of $S$ contain all of $M$'s tapes separated by some symbol such as #.

However, why is the running time of $S$ $O(t^2(n))$ if the running time of $M$ is $O(t(n))$? I think it would be $O(t^k(n))$ since there exist $k$ tapes, and we have to traverse through all of them.

# Answer
In your suggestion you write the tapes next to one another. That has another disadvantage, if one of the tapes runs out of space one has to move the information to extend that space.

The solution is to write different tapes on "tracks", above each another, technically this is done by extending the alphabet to a cartesian product of alphabets. If the original tapes all have alphabet $\Sigma$ (for $i=1,\dots,k)$ and blank $B\in \Sigma$, the single tape simulator has alphabet $\Sigma^k\cup\\{B\\}$. Additionally one needs to mark the positions of the heads, leading to extra symbols on the tracks.

(edited to include answer to question in comment)
> 8 votes

---
Tags: turing-machines
---


# Question
Title: Why is the unary representation of a number exponentially larger than a base k representation of it?
According to a book I am reading, the unary representation of a number exponentially larger than a base k representation of it. I, however, feel that the unary representation should scale linearly with the input.

After all, 1 is 1, 2 is 11, 3 is 111, and so on, right? Wouldn't that be linear?

# Answer
The base $k$ representation of the number $n$ takes $\log\_{k}n$ bits, whereas the unary representation takes $n$, and of course $n = k^{\log\_{k}n}$

The gap is more apparent with larger numbers, if we take our normal base 10 system, then writing 1000 takes 4 decimal digits, but writing it in unary takes 1000 ones.
> 5 votes

---
Tags: algorithm-analysis
---