title: Tricky Turing Machine state diagram

text:
# Question
Title: Tricky Turing Machine state diagram
what would the Turing machine state diagram be for this language: $A=\\{ (0 \cup 1)^a(1 \cup 2)^b(2\cup 3)^c \mid a \geq b\\} $ ?

how would the turing machine design know the size of $(1 \cup 2)^b$ ? since this contains elements from the first and last parts, would it be impossible to determine?

# Answer
As a supplement to the excellent recommendation by Karolis Juodelé I present some informal 'pseudocode' for how to run a TM to accept $L=\\{ (0 \cup 1)^a(1 \cup 2)^b(2\cup 3)^c \mid a \geq b\\} $. The key observation is that we may let $b=0$ and ignore the condition $a\geq b$ in all cases but those words $w$ which contain the subword $21$. In the situation where $21\in w$ the borders for when the $b$ count starts and ends are at the first occurrence of $2$ and the last occurrence of $1$ respectively.

Initial tape reads $\underline\Delta w\Delta^\star$, step right and replace all $0,1$ with $A$. When a $2$ is read overwrite it with a $B$ and proceed right overwriting $2$s with $B$s until either a $1$ or $3$ is encountered. If a $3$ is encountered then we know either $b=0$ or $w\not\in L$ so we finish by accepting iff the remainder of the string contains only the symbols $2,3$

If we encounter a $1$ we are in the case where $b\neq0$ and we need to enforce the $a\geq b$ requirement (also replace it with a $C$). Continue right replacing the symbols $1$ with $C$ and $2$ with $B$ until a $3$ is encountered or the string terminates. If a $3$ is encountered read the rest of the string to make sure it is only the symbols $3,2$ until the end (and replace them with $\Delta$s). Once the end of the string is reached step backwards (left) replacing any $B$ encountered with a $\Delta$ until the tape head rests on a $C$. Then ensure that $\\#(A)\geq\\#(B)+\\#(C)$ and if this is satisfied accept, otherwise reject.
> 1 votes

# Answer
This is a context free language given by $$\begin{align} S &\to S2 | S3 | T \\ T &\to 0T | 1T | 0T1 | 0T2 | 1T1 | 1T2 | \varepsilon \end{align}$$

I'm not suggesting that you should write down a TM that parses CF languages, although you could. I'm suggesting that you should take into account the properties of a language, not the properties of one of its descriptions, when writing a TM for it.
> 1 votes

---
Tags: turing-machines, computation-models
---


# Question
Title: Solve the worst case of this recurrence equation
I am trying to find the worst case $Θ$ bound for the following recurrence equation: $$ T(n)=\sum\_{i=1}^kT(a\_i)+n+\lg k\sum\_{i=1}^ka\_i\quad where\quad n=1+\sum\_{i=0}^ka\_i\quad and\quad a\_0\ge a\_1, a\_2, \dots,a\_k\ge 1 $$ By master theorem, with $k=a\_0=a\_1=n/3$ and $a\_2=a\_3=\dots =a\_k=1$, $T(n)=Θ(n\lg n)$. Now my freind and I guessed that the worst case of $T(n)$ is also $Θ(n\lg n)$, but we are not able to prove it.

My question is, what is the worst case bound of $T(n)$ and how to prove it?

**Edit**: By worst case I mean that $T(n)$ to be the *maximum* of the expression I wrote over all $k\ge1$ and $a\_0\ge a\_1,a\_2,\dots,a\_k\ge1$ such that $n=1+a\_0+\dots+a\_k$.

# Answer
For starters, let's rewrite the recurrence as $$ T(n) \leq \max \sum\_{i\>0} T(a\_i) + O(n\log n). $$ Suppose now that we could show that $T(m+1) - T(m)$ is increasing in $m$. In this case, it follows that we can assume that $a\_2 = \cdots = a\_k = 1$, and so $$ T(n) \leq \max T(a\_1) + O(n\log n). $$ The largest that $a\_1$ can get is $n/2$ (well, $(n-1)/2$), and so $$ T(n) \leq T(n/2) + O(n\log n). $$ Expanding this, we get $T(n) = O(n\log n)$.

Showing that $T(m+1) - T(m)$ (if this is indeed true) looks a bit messy, but potentially could be done in the spirit of the following lemma.

**Lemma** For all $a,b \geq 1$, we have $T(a+b) \> T(a) + T(b)$.

**Proof.** Choose the $a\_i,b\_j$ for which $$ \begin{align\*} T(a) &= \sum\_{i=1}^k T(a\_i) + a + \log k \sum\_{i=1}^k a\_i, \\ T(b) &= \sum\_{j=1}^\ell T(b\_j) + b + \log l \sum\_{j=1}^\ell b\_j. \end{align\*} $$ Consider the sequence $c\_0 = a\_0+b\_0$, $c\_1,\ldots,c\_t = a\_1,\ldots,a\_k,b\_1,\ldots,b\_\ell,1$, where $t = k+\ell+1$. This sequence sums to $a+b-1$ and satisfies $c\_0 \geq c\_r \geq 1$ for all $r \> 0$, and so $$ \begin{align\*} T(a+b) &\geq \sum\_{i=1}^k T(a\_i) + \sum\_{j=1}^\ell T(b\_j) + T(1) + a+b + \log(k+\ell+1) \left(\sum\_{i=1}^k a\_i + \sum\_{j=1}^\ell b\_j + 1\right) \\ &\> T(a) + T(b). \end{align\*} $$
> 1 votes

# Answer
From the division-into-2 case, I'd guess that the worst case is the most unequal division possible, i.e., $a\_0 = n - k$ and $a\_1 = \ldots = a\_k = 1$. Let's check: $$ T(n) = T(n - k) + k T(1) + n + k \lg k $$ This gives $T(n) = O(n^2)$.
> 0 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Relation between logspace-uniform circuits and P-uniform circuits
In the book "Computational complexity" of Barak and Arora, on page 112, they state that:

> Theorem 6.15: A language has logspace-uniform circuits of polynomial size iff it is in P.

The proof of this one is left as an exercise to the reader. I think both directions are trivial:

=\> seems trivial, as a logspace TM that generates a circuit also runs in polynomial time, and hence is a P-uniform circuit, which is part of P.

\<= seems trivial, as a language that has a polynomial-time TM can be transformed into a circuit with Cook-Levin's theorem in logspace.

However, what I don't get is why the theorem 6.15 explicitly states that the circuits must be of *"polynomial size"*. How can there exist a logspace-uniform circuit that isn't polynomial in size? The logspace computable function itself cannot exceed a polynomial bound, how can it produce a circuit of superpolynomial size?

Also, this theorem would imply that logspace-uniform circuits comprise the same languages as P-uniform circuits, which seems very unintuitive to me. I can't find any information on the relation between logspace-uniform and P-space uniform circuits on the web, so my assumption that they are equal is probably false, but I fail to see see why.

# Answer
The *circuit value problem* (CVP) is, given a circuit and an input, to evaluate the circuit. This is a well-known problem which is P-complete with respect to AC$^0$ reductions. Thus one can define P as the class of problems AC$^0$-reducible to CVP. We get the same class if we consider the class of problems polytime-reducible to CVP, or in general $L$-reducible to CVP, where $L$ is any intermediate class between AC$^0$ and P. An $L$-reduction to CVP is very similar to an $L$-uniform circuit (the only difference is that the inputs to the circuit could be any $L$-functions). Specifically, an AC$^0$-reduction to CVP can be converted to a uniform circuit (the notion of uniformity depends on the exact format of circuits, but it can probably be taken all the way down to AC$^0$).

The same phenomenon occurs whenever we have a universal circuit (in the case of P, this is the circuit solving CVP). For a recent example, see this paper on comparator circuits.
> 1 votes

---
Tags: polynomial-time, circuits
---


# Question
Title: Custom binary counter supports only increment in $2^i$ values amortized analysis
I'm a having trouble analyzing this algorithm. This is a binary counter that supports only increments in $2^i$ values it's implemented in this way: starting from the $i$-th location change all the straight $1$'s to $0$'s and the first $0$ to $1$.

So I analyzed the W.C to be $O(\log n)$ because the worst case is we need to increment by $1$ a $2^i-1$ number. Now for the amortized I thought using the accounting method, charging for each change from $0$ to $1$ $2\\$$ amortized cost, since each time we increment we flip at most one $0$ to $1$. and put $1\\$$ on each $1$ bit to pay from flipping it back to $0$. so at most the amortized cost is $2\\$$ which means amortized $O(n)$. if it's correct than what's the difference from a regular binary counter? I don't think I understand...

# Answer
> 0 votes
The counter you describe is a completely ordinary counter with an extra "appendage" which consists of the $i$ least significant bits. Those are never accessed by the algorithm, and the rest of the bits operate like an ordinary counter.

---
Tags: algorithms, algorithm-analysis, amortized-analysis
---


# Question
Title: Is this a proper Max Heap Data Structure
I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the following array which it said was a Max-Heap.

```
BookArray [] = {45,10,11,3,2,7,9,1,0}

```

I then decided to shuffle the elements (so they are no longer in binary heap) and got this.

```
Shuffled[] = {11,1,0,7,9,3,2,10,45}

```

I then decided to write a program that would sort the elements in the array in Min-Heap so I got this array

```
Sorted[] = {45,11,3,10,7,0,2,1,9}

```

My question is if my sorted array is also a valid max-heap ? since my array does not match the bookArray

# Answer
The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree, the tree is completely filled on all levels except possibly the lowest.

Min Heap has the property:for every node i (except root node) Array\[parent(i)\]\<=Array\[i\]. So the smallest element in a min-heap is at the root.

Max Heap is organized in opposite way, i,e. it has the property: for every node i (except root node) Array\[parent(i)\]\>=Array\[i\]. So the largest element in a Max-heap is at the root.

You can check if the array is maintaining the heap property by the following algorithms.

Algorithm 1

```
Parent(i)
    return floor(i/2)

```

Algorithm 2

```
Left(i)
    return 2*i

```

Algorithm 3

```
Right(i)
   return 2*i+1

```

Now you can check on your own that if your array maintaining **Max heap** property or not.

It is not mandatory that two heaps with same elements have same arrangement.The thing you have to be conform that if all elements are maintaining the heap property or not.
> 2 votes

---
Tags: data-structures, binary-trees, heaps
---


# Question
Title: If I solve hard instance, therefore I prove NP=P?
If someone (off-topic) asks a question (on-topic) like this:

Suppose that he claims that $\mathcal{P=NP}$. Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that cannot be solved by any computer optimally, i.e., to get the optimal solution, one must run an algorithm for very long time (the age of the universe for example).

If this someone (off-topic) solves this instance very fast optimally. Because the problem is NP-complete, we know that it can be easily verified.

Can we verify easily that it is the optimal solution or we can only verify that it is just a solution?

In the other hand, if this someone (off-topic) solves every instance (hard instances) of an NP-hard problem very fast. Can we claim that he proved that $\mathcal{P=NP}$?

I want an answer, not a vote up/down or on/off-topic.

# Answer
$\mathrm{P}$ and $\mathrm{NP}$ are both sets of languages. A language $A \subseteq \Sigma^{\star}$ is in $\mathrm{P}$ ($\mathrm{NP}$), if and only if there exists a deterministic (nondeterministic) turing machine $M$, that can **decide** in polynomial time for all $x \in \Sigma^\star$, whether $x \in A$.

There is an alternative definition of $\mathrm{NP}$: $A \subseteq \Sigma^\star$ is in $NP$, if there is an language $L\_0 \in \mathrm{P}$ and an polynom $p(x)$, such that $A = \left\\{ x \mid \exists y \text{ with } |y| \leq p(|x|) \text{ and } x\\#y \in L\_0 \right\\}$ That $y$ is called *proof* (or *witness*) that $x$ is in $A$. For example, the satisfiability problem is to check whether a given boolean formula is satisfiable or not. $\mathrm{SAT}$ is the language of all satisfiable boolean formula. Given a boolean formula $\phi$ (a instance of the satisfiability problem), we want to check whether $\phi$ is satisfiable (if $\phi \in \mathrm{SAT}$). A witness for $\phi$ is an interpretation. We can determine in polynomial time, whether the interpretation of that formula is true or false.

> Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that cannot be solved by any computer optimally, i.e., to get the optimal solution, one must run an algorithm for very long time (the age of the universe for example)

For descition problems, there no such thing as an optimal solution. The answer is yes or no (since the question is whether a string over an alphabet is in the language or not). Also, just because an algorithm runs for a very long time **does not imply** that the problem is in $\mathrm{NP}$: Consider the worst case time complexity of something like $n^{100}$, which is even for small input sizes very high, but in $\mathrm{P}$.

But lets consider we give him an instance of an $\mathrm{NP}$-complete problem, for example of the satisfiability problem:

> If this someone (off-topic) solves this instance very fast optimally. Because the problem is NP-complete, we know that it can be easily verified.
>
> Can we verify easily that it is the optimal solution or we can only verify that it is just a solution?

Again, for descition problems there is no such thing as an optimal solution. Therefore, we can verify an solution in polynomial time.

> In the other hand, if this someone (off-topic) solves every instance (hard instances) of an NP-hard problem very fast. Can we claim that he proved that P=NP?

If he presents us an (correct) deterministic polynomial time algorithm, the answer is yes. Theoretically, he could just got lucky everytime and guess a correct solution, or own a non-deterministic turing machine. Since there is an infinite amount of $\mathrm{NP}$-complete problems and only limited time, there is no way of solving *all* instances. Also, for only a finite amount of instances, one could use an (huge) lookup table.

For futher information regarding the $\mathrm{P}$ vs $\mathrm{NP}$ problem, you could look at the official problem description of the Clay Mathematics Institute.
> 5 votes

---
Tags: complexity-theory, p-vs-np
---


title: Generalized Geography with repetitions

text:
# Question
Title: Generalized Geography with repetitions
Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move wins.

> GG = { : G is a directed graph, b is a node in G, and the next player to play has a winning strategy for generalized geography from start node b, i.e., there are moves for the next player to win no matter how opponent plays }

This problem is well-known to be in PSPACE and EXPTIME-hard. My question is: If we allow repetitions in GG, it still belongs to EXPTIME-hard?

# Answer
> 3 votes
If repetitions are allowed, the problem is in P, as the (immediate) losing nodes are the ones with no outgoing edges, first find these, then declare the nodes winning from which you can reach such a node, if you can reach only winning ones, its a losing node, and so on, rest are drawing.

---
Tags: graphs, time-complexity, space-complexity
---


# Question
Title: Generating all strings that a regular expressions describe
I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this:

```
[atom_0] atom_1 (atom_2 | atorm_3 | ... | atom_n-1) <var> [atom_n]

```

Or any other combination of the following:

```
[], means, that the atom inside of it can be omitted
(), one of the atoms (seperated by | (stands for OR)) inside the braces can be chosen
<>, variable.
atom, it can be thought as a constant, which is hard coded.

```

For example:

```
The [yellow] (dog | cat) named <animalName>

```

This expression describes the following set of strings:

```
The yellow dog named <animalName>;
The yellow cat named <animalName>;
The dog named <animalName>;
The cat named <animal Name>;

```

The strings can vary, depending on the variable `<animalName>`, but say, we have two names for `<variableName>` : `Petsy` and `Rony`, then w'll have:

```
The yellow dog named Petsy;
The yellow cat named Petsy;
The dog named Petsy;
The cat named Petsy;
The yellow dog named Rony;
The yellow cat named Rony;
The dog named Rony;
The cat named Rony;

```

Right now, I'm thinking that I could build a tree (or graph) from the expression and then a DFS or BFS can do the job.

Any comments or document/article references would be helpful to me.

# Answer
There is a standard construction for converting regular expressions into finite automata (check here or any textbook on formal languages). Once you have such an automaton in hand (either NFA or DFA) you can enumerate all accepted strings with a breadth-first search from the initial state looking for finite states (ordered by length).

Be careful, though: in general, regular expressions specify infinite languages. You can easily specify a length limit, though.
> 2 votes

# Answer
For regular expressions specified the way you describe, you can use a backtracking algorithm to enumerate all acceptable strings. Following is a Python implementation.

The input is a list of items. An item being one of the ones you describe.

`gen_candidates` generates candidates for the k'th position.

```
def gen_candidates(item):
    c = []
    if type(item) is list:
        for e in item: c.append(e)
        if(len(item) == 1):
            c.append('')
    elif type(item) is str:
        c.append(item)
    return c

```

The next function prints a solution when one is found.

```
def process_solution(solution):
    s = ''
    for e in solution:
        if len(e) > 0:
            s += e + ' '
    print(s)

```

`backtrack` tries all possibilities recursively.

```
def backtrack(regex, solution, k):
    if len(regex) > 0:
        candidates = gen_candidates(regex[0])
        for c in candidates:
            solution[k] = c
            backtrack(regex[1:], solution, k + 1)
    else:
        process_solution(solution)

```

You invoke the algorithm as follows:

```
input = ['The', ['yellow'], ['dog', 'cat'], 'named', '<animalName>']
solution = ['', '', '', '', '']
backtrack(input, solution, 0)

```
> 1 votes

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


# Question
Title: Is Wikipedia's formal definition of NP correct?
Wikipedia's formal definition of NP based on deterministic verifiers states:

> A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that
>
> * For all x and y, the machine M runs in time p(|x|) on input (x,y)
> * For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1
> * For all x not in L and all strings y of length q(|x|), M(x,y) = 0

I'm not an expert in the field but the first bullet point leads me to think that M must run in time p(|x|) regardless of the size of y, which doesn't seem to be true, at least if M gets to read y completely. What if |y| \> p(|x|)?

Is the first bullet point of the definition correct? Shouldn't it be

> For all x and y, the machine M runs in time p(|x|+|y|) on input (x,y)

Can you point me to an authoritative source with the original definition of NP based on deterministic verifiers?

# Answer
I am currently reading "Introduction to the Theory of Computation" by Sipser and think that it is a great introduction to complexity (as well as automata and computability). Here are his definitions of **Verifier** and **NP**:

> **Definition 7.18**: A **verifier** for a language $A$ is an algorithm $V$, where $A = \\{ w \mid V \text{ accepts } \langle w, c \rangle \text{ for some string } c \\}.$ We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier. (Sipser, 293)
>
> **Definition 7.19**: **NP** is the class of languages that have polynomial time verifiers. (Sipser, 294)

Translating the wiki definition into the above, $A = L$, $V = M$, $w = x$, and $c = y$. It seems that the first condition of the wiki definition is correct, and this may make more sense given the alternative definition of NP. A language $L$ is in NP if there exists a non-deterministic TM $N$ that decides $L$ in non-deterministic polynomial time $NTIME(n^k)$. Here, the running time of $N$ is measured in terms of its input size $n = |w| = |x|$.

However, I have not seen nor am I familiar with the second condition, but that seems to set some upper bound on the length of $y$ so that $|y|$ is a polynomial in $|x|$, which should answer your question about if $|y| \> p(|x|)$. I figure the second condition is to protect against padding arguments. At any rate, if $p(|x|) \< q(|x|)$, then $p(|x|) \< |y| \< q(|x|)$, so $|y|$ is still a polynomial in $|x|$.
> 2 votes

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


# Question
Title: Abstract Syntax Tree of Pure Lambda Calculus
I was wondering if anyone had any good references or book recommendations that cover abstract syntax trees (ASTs). Specifically, I am interested in the abstract syntax trees of different evaluation strategies (call by value vs. call by name) of the pure lambda calculus. I would like to be able to draw the AST of some pure lambda calculus expression such as $$and \\, true \\, false = (\lambda a. \lambda b. a \\, b \\, (\lambda t. \lambda f. f))(\lambda t. \lambda f. t)(\lambda t. \lambda f. f).$$

I would like to know if/how evaluation strategies affect the structure of ASTs, or how order of operation is reflected in the AST of an expression. This seems trivial for any pure lambda calculus interpreter; so perhaps there is some AST generator out there somewhere? I did some searching on Google but found nothing.

I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.

# Answer
> 3 votes
> I would like to know if/how evaluation strategies affect the structure of ASTs, how order of operation is reflected in the AST of an expression

They don't, and it isn't. Evaluation strategies are functions which take ASTs as arguments, and return ASTs (or possibly only normal forms), so you can have different evaluation strategies working on the same AST.

> I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.

See e.g. this Stack Overflow question:

> ```
> data Exp = Var String
>              | App Exp Exp
>              | Lam String Exp
>
> ```

In the case of pure lambda-calculus, there is no `Constant Int`, and `and` would look like

```
Lam "a"
  (Lam "b"
     (App
        (App
           (Var "a")
           (Var "b"))
        (Lam "t"
           (Lam "f"
              (Var "f")))))

```

---
Tags: lambda-calculus, syntax-trees
---


# Question
Title: Analyze Speed Up in A Dispatcher-Woker Model
In a Dispatcher-Worker model of parallel computation, we have $N$ worker machines simultaneously working on the task (for example, computing the checksum of network packets). There is no synchronization between these workers. A dispatcher distributes total amount of work $S$ to these workers.

Now consider the problem of analyzing the speed up of this model. To simplify the situation, assume the dispatcher evenly distributes work $\frac{S}{N}$ to each worker. And each worker finishes it within $X\_i \sim \mathcal{N}(\frac{S}{N}, \sigma^2)$ time, where $\mathcal(\mu, \sigma^2)$ is the Gaussian distribution. Then I think the mathematical formula for the total amount of time needed is \begin{equation} Y = \max(X\_1, X\_2, ..., X\_N) \end{equation}

The question is how to compute the distribution of $Y$, so that analytically we could understand the parallel time needed, in terms of the number of workers $N$.

# Answer
> 1 votes
Here is how you can compute its distribution. Let $F(t) = \Pr\[X\_i \le t\]$ (the cumulative distribution function of $X\_i$), and $G(t) = \Pr\[Y \le t\]$ (the cumulative distribution function of $Y$). Then

$$G(t) = \Pr\[Y \le t\] = \Pr\[X\_1 \le t, \dots, X\_N \le t\] = \Pr\[X\_1 \le t\] \times \dots \times \Pr\[X\_N \le t\] = F(t)^N.$$

Now the probability density function of $Y$, $g(t)$, is the derivative of the cumulative distribution function, so

$$g(t) = G'(t) = N F(t)^{N-1} f(t),$$

where $f(t)$ is the probability density function of $X\_i$. This directly gives you the distribution of $Y$: namely, $g(\cdot)$ is the distribution of $Y$.

This calculation also gives you a good way to compute tail bounds. For instance, if you want to compute the probability that the whole process needs more than $t$ time, i.e., that $Y \> t$, you can compute this as $1-G(t) = 1 - F(t)^N$.

See also https://math.stackexchange.com/q/89030/14578 for other useful facts about the distribution of $Y$.

---
Tags: parallel-computing
---


# Question
Title: Is there a way to create a "captcha"-like problem that computers can verify, but only humans can solve?
In a normal CAPTCHA scenario, a computer creates a challenge and a correct response to it. (The challenge is an image of distorted text, for instance, and the response is the characters depicted.) These are constructed so that hopefully a human can easily determine the response from the challenge, but a computer cannot. Ordinarily only the originating computer, which already knows the correct response, can determine whether a given response was correct.

My question: is it possible to create a CAPTCHA that computers can verify, but not solve? In other words, is it possible to create a scenario that looks like this:

Computer A generates a challenge, sends it to Human B and Computer C

Computer C cannot feasibly determine the correct response, other than by brute-force search (which can hopefully be made impractical by the size of the response.)

Human B can feasibly determine the correct response. ("Feasibly" is not easy to define. We need the response to be much bigger than normal CAPTCHAs in order to deter simple brute-force searching by computers, so "as easy as a normal CAPTCHA" is going to be impossible. But it's not out of the realm of possibility to make a human type in a large response. It'd just be really annoying. A few hundred printable characters can get to 2048 bits, for instance. So as a rough definition: it's allowed it to be annoying as hell, but it has to at least be feasible for a person. Assume the person's physical and mental abilities are roughly average for a literate computer user.)

If Human B sends Computer C the correct response, Computer C can feasibly verify that the response is correct, without contacting computer A or having any prior knowledge other than the challenge.

Would it be possible, under today's technology and knowledge, to create such a protocol?

Furthermore, would it be possible to design the protocol such that even Computer A can't determine the correct response to the challenge it just generated without human input--and Computer C can verify that Computer A could not have known the response without a human providing the solution? If this all this can be achieved, then the result is analogous to the "proof of work" seen in bitcoin and other protocols. Instead of a proof of computational work, we'd have a proof of *human* work--the combination of the challenge and correct response would constitute proof that a human spent some marginal amount of effort. This proof would then be verifiable by any computer. Is such a thing even remotely plausible?

Of course, at some point in the future computers will probably overtake humans altogether. Once that happens, there will not be any problems that are feasible for a human but not a computer, and therefore no CAPTCHAs or CAPTCHA-like protocols will be possible.

But what about under currently known human and computer abilities?

# Answer
> 2 votes
Yes. Computer A can generate a CAPTCHA encoding a 24-digit code, and also compute a cryptographic hash of the correct response. Computer A can give the CAPTCHA and the hash to B and C. Now if B claims to have solved the CAPTCHA, computer C can verify the claimed answer using the cryptographic hash. The cryptographic hash doesn't help computer C solve the challenge, because the hash is one-way and cannot be inverted (except by trying all possible codes, but that would take far too long).

In practice, this is not very effective, because no one knows how to build a CAPTCHA that humans can solve but that is expensive for computers to solve. For one thing, there are black-market services that will solve CAPTCHAs for you at the price of about $1-2 per thousand CAPTCHAs solved, i.e., about 0.1-0.2 cents per CAPTCHA. For another, there are algorithms that break most CAPTCHAs with probability higher than we'd like. So ultimately, CAPTCHAs kinda suck. But the reasons they suck have nothing to do with verifiability. If we could make a CAPTCHA that didn't suck, we could probably build one that was verifiable in the sense you mention.

Also, if you were implementing this in real life, you'd make sure to use a slow hash (like PBKDF2, scrypt, or bcrypt) when hashing the code. But again, because CAPTCHAs have so many limitations, I'm not sure you'd want to implement this scheme in real life anyway.

---
Tags: computer-vs-human, human-computing
---


# Question
Title: AI approach for exploring a static grid environment
I have a grid environment which contains in each cell a static agent. When my agent enters a cell, the static agent in this cell might take points away from me, give me points, or do nothing. My agent can not observe adjacent cells until it moves into one them, it can only move up, down, left or right.

This agent can not learn whilst it is exploring. It enters the grid from a particular corner, and may only leave from that corner. If the agent manages to successfully explore the environment and return back to the corner with positive health, then it can learn from its collected experience, which includes the (row, column) positions it visited, and the properties of the static agents located in those positions. If the agents' health drops to zero whilst exploring, game over. But I can restart the exploration as many times as I want.

Each static agent has one of three shapes, one of three colours, and one of two sizes. It also has an associated "reward", indicating how many points it adds/removes from me.

Each move in this environment costs me one point. I want to design an agent that correctly recognises the reward associated with each type of static agent in this grid.

Please may someone recommend a learning and/or evolutionary approach to solving this problem? I'm stuck at the moment because of the restriction that agent may not observe adjacent squares. I'm not sure how I can learn anything from this testing environment from the (row, column) and static agent properties encountered alone.

# Answer
> 0 votes
Obviously one of the best learning methods that matches this problem is the `Reinforcement Learning` and to be more specific `Q-Learning`.
You'll find a good starting point here.
Hints: Q-learning is quite well-known and I don't repeat others here, but I give you the key point here.

At each step keep track of what happens (reward/punishment - no need to agent types,... if the environment stays fixed and you want to learn this Env. not the agents) using for example an array (Fortunately you're not learning anything so far!). Keep doing this until the agent stops, that as you said can have two reasons :

1. Agent's health drops to zero : Do nothing! (discard the array)
2. Agent leaves from the other corner : Apply the following rule with the values in the array

---
Tags: artificial-intelligence
---


title: Spanning Tree - Equivalent Properties

text:
# Question
Title: Spanning Tree - Equivalent Properties
I am working on the following problem:

> Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the *cycle property* if for any edge $e' \not \in T, c(e') \geq c(e)$ for all $e$ in the cycle generated by adding $e'$ to $T$. Let $T$ have the *cut property* if for any edge $e \in T$, $c(e) \leq c(e')$ for all $e'$ in the cut defined by $e$.
>
> Show that the following three properties are equivalent
>
> 1. T has the cycle property,
> 2. T has the cut property, and
> 3. T is a minimum cost spanning tree.

I believe that to show that 3. implies 1., we suppose otherwise, and then show that this would give a cycle with an edge that can replace another edge in T and that is cheaper, whence we have a contradiction. Similarly, I believe to show that 3. implies 2., we similarly suppose otherwise, and then show that this would give a cut with an edge that can replace another edge in T and that is cheaper, whence a contradiction.

However, I am not sure how to prove the other implications needed for this problem. My feeling is to somehow use a similar argument to what I listed, but "in reverse".

Any help with this problem would be greatly appreciated.

# Answer
Continuing where @ijkilchenko left off.

$2\to 3$: Let $T$ have the cut property and let $T'$ be any other spanning tree of $G$. For each $e\in T$, there is some edge $e'\in T'$ that crosses the cut defined by $e$. Define $f : E(T) \to E(T')$ by mapping each edge $e \in E(T)$ to the edge $e' \in E(T)'$ with smallest weight among those crossing the cut defined by $e$. According to the cut property $w(e)\le w(f(e))$, so we get $$ w(T) = \sum\_{e \in T} w(e) \le \sum\_{e\in T} w(f(e))\le \sum\_{e'\in T'} w(e') = w(T')$$ where the third inequality comes from the fact that if $f$ is not injective, it only decreases weights. Since $T'$ was arbitrary, we have shown that $w(T)$ is minimum among all spanning trees of $G$, and we are done.

$3\to 1$: If $T$ does not have the cycle property, the definition supplies us with an edge $e\in T$ and $e'\notin T$ such that $w(e') \< w(e)$, so $T - e + e'$ is a tree with weight less than $T$. Therefore $T$ does not have minimum weight.
> 2 votes

# Answer
1 $\Rightarrow$ 2: Suppose that $T$ has the cycle property. Fix $e\in T$. The edge $e$ will define our cut because removing $e$ from $T$ will give us two disconnected components $T\_1$ and $T\_2$. Adding any edge $e'$ between $T\_1$ and $T\_2$ gives us a cycle in $T + e'$ that necessarily goes through $e$. By the cycle property, $c(e) \leq c(e')$.

To finish the problem, show that $2\Rightarrow 3$ and $3\Rightarrow 1$. Hope this helps.
> 1 votes

---
Tags: graphs, spanning-trees
---


title: Converting to Chomsky normal form

text:
# Question
Title: Converting to Chomsky normal form
Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form.

I have S -\> abC | babS | de C -\> aCa |b

I know what to do with the case of aCa and de and b but im not sure how to handle the abC case or the babS case. I believe that chomsky normal form is supposed to have outputs of only 2 characters. so with something like aCa you make and output aa and have A-\>a and create another nonterminal? X -\> SA but I dont know how im supposed to handle the abC case or the babS case.

# Answer
Let's work it out through the conversion algorithm given in Wikipedia.

**input:**
$S \to abC \mid babS \mid de$
$C\to aCa \mid b$

1. **Introduce** $S\_0$:
$S\_0 \to S$
$S \to abC \mid babS \mid de$
$C\to aCa \mid b$
2. **remove $\epsilon$ rules:** there are no $\epsilon$ rules, so nothing changes.
3. **eliminate unit rules**: Originally, there are none, but we added one, namely $S\_0\to S$. Since it's the only one, we'll deal with it later (after $S$ is already in CNF). This will be done by adding, for any rule $S\to V\_iV\_j$, the rule $S\_0 \to V\_iV\_j$. But let's first complete the conversion.
4. **replace all other rules into normal form**: we take each transition which is not in the correct form and replace it with $N\to V\_iV\_j$, introducing new non-terminals $V\_1, V\_2,...$ as needed:
* $S\to ab C$ $\Longrightarrow$ $S\to V\_1 C$ setting $V\_1 \to ab$. The new $V\_1$ is not in CNF, but can easily be converted to CNF by re-defining it as $V\_1\to AB$ with $A\to a$, $B\to b$.
    * $S\to babS$ $\Longrightarrow$ $S\to V\_2S$ adding $V\_2 \to bab$. Now $V\_2$ is not in CNF, so we change it to $V\_2 \to V\_3B$ adding $V\_3\to BA$. (skipping a trivial step here)
    * $S\to de$ is almost CNF. We change it to $S\to DE$ and add $E\to e$, and $D\to d$.
    * $C\to aCa$ $\Longrightarrow$ $C\to AV\_4$ where $V\_4 \to CA$.
    * $C \to b$ is already in CNF.

so we end up with:
$S\_0 \to S$
$S\to V\_1 C$
$S\to V\_2S$
$S\to DE$
$C\to AV\_4$
$C \to b$
$V\_1 \to AB$
$V\_2 \to V\_3B$
$V\_3 \to BA$
$V\_4 \to CA$
and $A\to a$, $B\to b$, $D\to d$, $E\to e$.

Finally, we need to deal with the unit rule $S\_0 \to S$. As said, we will replace the $S$ in the right-hand-side with the "content" of S. That is, we remove that unit rule and add instead:
$S\_0 \to V\_1C \mid V\_2S \mid DE$.
> 2 votes

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


# Question
Title: How many states when converting CFG to PDA
When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find out the "worst case scenario" of how many states there can potentially be? I don't mean for one particular CFG, but in general. I'm having difficulties trying to figure out how I can calculate this...

# Answer
> 0 votes
I do not know about Qstart, Qloop and Qaccept ... there are many ways to organize the construction of PDAs.

the minimal number of states required depends a bit on the formal model you use for defining PDAs. But essentially you need only one state (which means no finite control) if you allow pushing and popping several symbols in one transition.

Instead of having several states, you push a on the stack a symbol representing the state, and you pop it for the next transition. The top of the stack is as good a place as any to keep the state information.

If having to pop several symbols makes you unhappy, you can always use a pairs of symbols as a unique symbol. Cross-products are handy.

This of course implies that acceptance is by empty stack rather than final state, which can cause some problems related to the prefix property of some languages. If that becomes a problem, use a PDA with two states, one being used as accepting state.

PS This question is already answered in How to get 2-state PDA for CFG?

# Answer
> 2 votes
When converting CFG to NPDA ,then to simplify the process, first convert the CFG to Greibach Normal Form(GNF). Now using three states: Qstart, Qloop and Qaccept, you can generate all transition rules for the NPDA.

To start the process add the transition: $ δ(Qstart,λ,z)=\\{(Qloop,Sz)\\}$ where S start variable and z is stack start symbol.

And add the following transition to get the NPDA into a final state:$ δ(Qloop,λ,z)=\\{(Qaccept,z)\\}$.

Now using the production rules of the CFG you can easily generate all the other transitions which includes only $Qloop$. And here the number of transitions depend on the number of production rules.

---
Tags: context-free, automata, formal-grammars, pushdown-automata, simulation
---


# Question
Title: Undirected graph with 12 edges and 6 vertices
For school we have to make an assignment, and part of the assignment is this question:

> Describe an unidrected graph that has 12 edges and at least 6 vertices. 6 of the vertices have to have degree exactly 3, all other vertices have to have degree less than 2. Use as few vertices as possible.

The best solution I came up with is the following one. Here the number in the circles is the degree of that vertex, now I was wondering if there is a better solution, if so, can somebody explain this to me?

*I do not need a better answer, just a push in the right direction - if needed.*

# Answer
> 2 votes
You have 12 edges, so the sum of the vertex degree is 24. Then there are 6 degree-3 vertices taking away 18. Thus the best you can hope for are 3 vertices of degree 2. Thus you found the solution.

# Answer
> 1 votes
**How to find solutions:**

If you vary the number of vertices of degree 3, and the other constraint on the total number of edges or vertices, there is a simple way to find a minimal solution. You put your n compulsory edges of degree 3 in a circle, hence using two edges for each. Then, starting clockwise from some vertex, you connect the next vertex with degree 2 to the second neighbor clockwise if it also has degree 2, until you can no longer do it. This may leave you with one edge that will require adding a vertex of degree one, if n is odd. This is a solution with a minimal number of vertices and edges, but possibly not enough edges or vertices depending on required constraint. Then you start cutting edges in two with new vertices in between to reach the required number of vertices or edges. Each cut will add one edge and one vertex. You can also increase the number of vertices by two while increasing the number of edges by only one, if you cut an edge and use a different new vertex for the open end of each half.

Alternatively. If you already found a solution (possibly not minimal) to the problem as stated, you can always reduce the number of vertices if you have more than one vertex with degree one. You simply take two of them and merge them. If it cannot be done, that means that the solution is already minimal in the number of vertices.

---
Tags: graphs, discrete-mathematics
---


# Question
Title: Are algorithms for searching text vs searching numbers fundamentally different?
I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially.

I save a draft in gmail with the content `I am mango`. Then I search it, by entering just `mango` and it gets me to the draft.

But when I save a draft with some number such as `123987645` and try to search by entering `12398764` i.e just one character missing I fail to find it. Also I failed when I just typed `87645`.

Out of curiosity I am asking are the algorithms for finding numbers and text fundamentally different? Or I am missing something?

# Answer
> 2 votes
There is no reason to assume that numbers and words are treated differently: for their servers, both are just strings. Different behaviour would be *extra* work and I don't see why that would be useful here.

There is one possible explanation for the behaviour you see: maybe they don't search for parts of words!

It is easy to preprocess texts so that finding whole words is fast. Well, looking for *any* substring is not that much slower (cf suffix trees) but it generates more data to store. Given the amount of data Google deals with, they might have a numbered dictionary and save tuples like `(msg_id, position, word_id)` (or similar)¹. Storing (matches for) all substrings would cause this data set to explode! (And don't even think about approximate search!)

You can try and verify this by searching not for `mango` but for `ngo` -- does it still find your message?

---

1. I'm quite sure Google does something far more clever.

---
Tags: algorithms, search-algorithms, strings, matching
---


# Question
Title: Proving that collision is less likely if the table size is prime in case modulo arithmetic is used
If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets,

```
  where m = table_length/GreatestCommonFactor(table_length, x)

```

Can someone help me to prove the above equation.

```
 Example for the above question would be:
 x = 3, table_length = 24
 m = 24/gcd(3,24) = 24/3 = 8

So 3%24 = 3  ->1
   6%24 = 6  ->2
   9%24 = 9   ->3
   12%24 = 12 ->4
   15%24 = 15 ->5
   18%24 = 18 ->6
   21%24 = 21 ->7
   24%24 = 0  ->8
   27 %24 = 3 ->1

```

From the above equation inference can be drawn that when

```
   table_length/GreatestCommonFactor(table_length, x) is 1,

```

i.e when x and table\_length are co-prime, the distribution would be proper and will cover all the buckets.

Based on observation

```
exactly 8 distinct multiples of 3 modulo 8.
exactly 2 distinct multiples of 4 modulo 8
exactly 1 distinct multiple of 8 modulo 8
exactly 4 distinct multiples of 6 modulo 8
exactly 8 distinct multiples of 6 modulo 8

```

There are exactly LCM(n,c)/c = n/GCD(c,n)distinct multiples of c modulo n

Is a better way of proving possible?

# Answer
It requires Theorem 31.20 on Page 927 from the CLRS (for which there is a proof of the theorem on the same page) that "if $d = gcd(a, n)$ then $\langle a\rangle = \langle d \rangle = \\{0, d, 2d, \ldots, ((n/d) -1)d\\}$ in $\mathbb{Z}\_n$, and thus $|\langle a\rangle| = n/d$"

But it's Corollary will be more useful to the proof: "The equation $ax \equiv b \mod n$ is solvable for the unknown $x$ if and only if $d|b$, where $d = gcd(a, n)$"

These conclusions will be the core of the proof.
> 1 votes

---
Tags: hash, hash-tables, primes
---


# Question
Title: Role of Term Constants in Simply Typed Lambda Calculus
In the Wikipedia article on Simply Typed Lambda Calculus (among other places), there is a notion of a "term constant". This is particularly notable in the production grammar given:

In this production grammar, the `c` is the term constant. I am new to the simply typed variant of lambda calculus -- I do not understand what role this constant plays in the overall computations of STLC. Can anyone give some examples of how the term constant is used and explain its general purpose?

# Answer
As per Sam's request, I rephrase my comment as an answer.

Constants play an important role in λ-calculi (not just the simply typed variant).

* They are often convenient: even though we can usually represent our target data using $\lambda$-terms without constants this tends to be unwieldy. For example integers directly by some variant of an unary encoding, e.g. the Church encoding has $$\lambda g x. \underbrace{g ( g ( ... g ( g\ x ) .. ) ) }\_{n}$$ as representation of $n$. That leads to cumbersome, unreadable terms. With constants we can do arithmetic with 0,1,2,..., and +,−,∗,...
* In a typed calculus, we need constructors for types, and constants play this rule. E.g. 0,1,2,..., or +,−,∗,... for the type of integers, true,false... or ∨,∧ for booleans etc. Naturally we also need to add reductions for constants like $3+4 \rightarrow 7$ etc (those are called $\delta$-reductions).

Note that the STLC was born with constants : Church's original formulation contains constants $N\_{oo}$, $A\_{ooo}$, $\Pi\_{o(o\alpha)}$ as well as $\iota\_{\alpha(o\alpha)}$, representing negation, disjunction, universal quantification and the selection operator, respectively.
> 7 votes

# Answer
I also don't like the **explanation** of constants in the article, but there are reasons for them.

You can certainly consider constants also in untyped lambda-calculus, and the behavior of constants is not generally interesting — as long as you allow them to be there.

However, most constants are typically redundant in untyped lambda-calculus, because any datatype can be Church-encoded. A typed variant of Church-encoding (called Böhm-Berarducci encoding, often also called Church encoding) is also available in polymorphic lambda-calculus (System F) and calculi containing it (TAPL\*, Sec. 24.3).

However, Church encoding does not really work in STLC: if you try to write 2 as `λ zero succ . succ (succ zero)`, you'll find you need to fix in advance what type τ to use for the type annotations `λ zero : τ. succ : τ → τ . succ (succ zero)`. Once you fix τ (say to Bool, assuming you have that type), you can only compute booleans with it, not anything else (in particular, not even numbers).

There's also another problem: unlike in System F, pure STLC the set of types is empty, as one can see by examining the definition of types (TAPL, Figure 9-1):

T ::= T → T

Since there is no base case, one can construct no finite type.

This is a different problem, and to solve it it is enough to add a set of uninterpreted base types. However, to make the calculus useful, you need to allow at least for arbitrary uninterpreted constants. Theoretically speaking, this is not a small problem in theory — every interesting bit of proofs about STLC can be done without base types, but all the statements are also vacuously true since no typed terms exist (because there is no type to fill in the type annotations).

\*TAPL is the book Types and Programming Languages by Benjamin Pierce, a standard reference nowadays in its field.
> 4 votes

---
Tags: type-theory, lambda-calculus
---


title: Can we break the Shannon capacity?

text:
# Question
Title: Can we break the Shannon capacity?
I have a friend working in wireless communications research. He told me that we can transmit more than one symbol in a given slot using one frequency (of course we can decode them at the receiver).

The technique as he said uses a new modulation scheme. Therefore if one transmitting node transmits to one receiving node over a wireless channel and using one antenna at each node, the technique can transmit two symbols at one slot over one frequency.

I am not asking about this technique and I do not know whether it is correct or not but I want to know if one can do this or not? Is this even possible? Can the Shannon limit be broken? Can we prove the impossibility of such technique mathematically?

Other thing I want to know, if this technique is correct what are the consequences? For example what would such technique imply for the famous open problem of the interference channel?

Any suggestions please? Any reference is appreciated.

# Answer
> 3 votes
Shannon proved that the capacity of the channel is a limit on its capacity. This is actually the easy part of Shannon's theorem — it is much harder to show that capacity can always be achieved. A good source for this is Shannon's paper from 1948, A mathematical theory of communication, page 24, last paragraph before Section 14. As Shannon writes, the Shannon capacity is the limit more-or-less by definition.

While Shannon already found a formula for the capacity of a channel, namely the Shannon capacity, two directions are still open (though they have partial solutions):

1. Zero-error encoding, also known as *block codes*. The best capacity in this regime is a major open problem in coding theory.
2. Codes with efficient coding and decoding. Shannon's theorem is non-constructive (it uses a random code), and so the codes it implies cannot be used in practice. It is more difficult to construct codes having efficient encoding and decoding. There have been lots of developments in the recent years in constructing efficiently decodable capacity-achieving codes.

Another problem is the rate of convergence in Shannon's theorem - I'm not sure what the status of that is.

In your specific case, it seems that the improvement is not be breaking the Shannon barrier (which is impossible) but by effectively changing the channels, just as telephone lines can be used to carry high-speed network traffic.

---
Tags: reference-request, computer-networks
---


title: Explain BadNeighbors problem statement

text:
# Question
Title: Explain BadNeighbors problem statement
I was solving a problem on topcoder http://community.topcoder.com/stat?c=problem\_statement&pm=2402&rd=5009 .

There is one example : `{ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }`

`Returns: 16`

So my question how its answer is `16` ?

# Answer
> 2 votes
This is $3 + 5 + 3 + 5$. More generally, what the problem wants you to solve is *maximum weight independent set* over a cycle. You can solve this using dynamic programming in linear time.

---
Tags: dynamic-programming
---


# Question
Title: Assume that SAT ∈ PSIZE, does it imply that NP = coNP?
Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ?

I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ and $\mathrm{coNP}$ are contained in $\mathrm{PSIZE}$, but I can't see how does help me. Any ideas ?

# Answer
If $SAT \in PSIZE$ then the polynomial hierarchy collapses to the second level: $\Sigma\_2 = \Pi\_2$ (see Karp-Lipton theorem ); but $NP=coNP$ (i.e. $\Sigma\_1 = \Pi\_1$) is stronger (the PH collapses to the first level).
> 3 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, circuits
---


# Question
Title: Can all NP-complete cryptosystems be broken if one is broken?
I was just reading something about NP-hard problems and cryptosystems.

I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) optimisation problem. A successful attack on one such NP-hard cryptosystem $A$ would mean that every other NP-hard cryptosystem $B$ would be vulnerable to that same attack; just reduce $B$ to $A$ and use the available attack.

That would actually mean that we would be able to extend Information Set Decoding attack of Code-based systems to any NP-hard based cryptosystem.

Is this consideration correct?

# Answer
As Yuval points out, contemporary crypto systems are not based on NP-complete problems.

NP-hardness is a **worst-case** notion of hardness. A problem might be NP-hard but easy to solve in many cases, or on average, or even in most cases. A crypto systems that was easy to crack on average would not be useful. We want crypto systems that are hard to crack in **almost all cases** (we cannot ask for all cases because the adversary can -- in principle -- just guess the secret used).

This seemingly stronger notion of hardness is formalised by one-way functions.

Incidentally, the existence of one-way functions implies $P \neq NP$, so you can imagine that we don't know if they exist. The reverse implication (does $P \neq NP$ imply the existence of one-way functions) is also an open problem.

There is an interesting theory of physical unclonable function which can be seen as the physical analogue of a one-way function.
> 7 votes

# Answer
Cryptosystems are not based on NP-hard problems. There are several standard hardness assumptions in cryptography on which cryptographic primitives are based, and cryptosystems are constructed based on cryptographic primitives, whose existence is thus assumed.

An example of a hardness assumption is DDH (Decisional Diffie–Hellman): given a prime $p$ and a generator $g$ of $\mathbb{Z}\_p^\times$, it is hard to distinguish triples $(g,g^x,g^y,g^{xy})$ (for random $g$ generating $\mathbb{Z}\_p^\*$ and random $x,y \in \mathbb{Z}\_{p-1}$) from triples $(g,g^x,g^y,g^z)$ (for random $g$ generating $\mathbb{Z}\_p^\*$ and random $x,y,z \in \mathbb{Z}\_p$).

An example of a cryptographic primitive is a one-way function. While the various definitions of one-way functions are somewhat intricate, informally a one-way function is a function that is easy to compute but hard to invert. One such example is $x \mapsto g^x \pmod{p}$, and assuming DDH, you can construct a secure one-way function based on this idea.

Cryptosystems, in turn, are composed out of cryptographic primitives satisfying some security assumptions, such as the one just mentioned: a one-way function is hard to invert. The primitives, in turn, are based on their own security assumptions, like DDH. The latter are different from NP-hardness in an important way: what is needed is average-case hardness rather than worst-case hardness.

Real-world cryptosystems are not usually based on this theory, their security being based on their designers (and then other cryptologists) not being able to break them. This seems to work rather well in practice.
> 3 votes

# Answer
as other answers point out crypto systems are generally not built out of proven NP complete problems although modern crypto is basically built out of assumptions equivalent or similar to P≠NP. following is a rare crypto system proposal that is based on an NP complete problem & has some analysis wrt NP completeness on cryptographic security. it seems not to be used. havent heard of later/followup analysis of its security. note that crypto hardness depends a lot on *average case complexity* which has many open problems associated with it. another useful ref in this area is Impagliazzo's worlds that describes the possible worlds we may be living in wrt cryptographic security.
> 0 votes

# Answer
No, if you created two NP-complete cryptographic systems, the solution to one would not fundamentally provide a fast solution to the other. This is because NP-Hard is an *exceptionally* loose concept.

I think we'd all be pretty happy if it took someone $n^{10}$ milliseconds to crack an $n$-bit key. If $n=2048$, that's $10^{12}$ times *the age of the universe*. And yet, if there's an $n^{10}$ overhead in converting NP-Complete problem $A$ into an instance of NP-Complete problem $B$, that's totally "fast" by NP-Hard's standards. If that's the best reduction we know of, that's how much it's going to cost you to use your solution to $B$. Heck, make that $10$ a $4$, and it's still 500 years!

High level asymptotic analysis can really lose sight of reality sometimes.

I should emphasize that this of course assumes that you have found two NP-Complete problems for which you can generate *many* genuinely difficult instances. It could also be the case that there does in fact exist a genuinely fast reduction of $A$ into $B$. It's simply not guaranteed in any way by the definition of NP-hardness.
> 0 votes

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


# Question
Title: What progress has been made on persistent catenable deques in the last decade?
I'm interested in persistent catenable deques: deques that can be concatenated.

Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version in 1997 using lazy evaluation (see Okasaki for references). Then a couple years later, Kaplan, Okasaki, and Tarjan came up with a simpler implementation using more general mutation in a disciplined manner. Then in 2003, Mihaesau and Tarjan came up with a simpler, non-bootstrapped strictly functional version.

My questions:

1. The Mihaesau and Tarjan catenable deques *appear*, to my untrained eye, to offer $O(\log n)$, or possibly even $O(\log(\min(i, n-i)))$ random access (lookup and modify). Is this correct?
2. Has anyone come up with any simplifications since then?
3. Has anyone either found a way to combine $O(\log n)$ (or, better yet, $O(\log(\min(i,n-i)))$) splitting along with $O(1)$ concatenation, or proved that it can't be done? For that matter, what about $O(\log n)$ arbitrary insertion and/or deletion?

# Answer
I don't think the Tarjan and Mihaesau catenable deques have that lookup/modify performance. The non-catenable ones certainly do, though.

1. I don't think there are any published simplifications since then. As far as I can tell, the T&M version wasn't ever published in a peer-reviewed venue. Publication about purely functional data structures seems to have slowed down in the last few years.
2. As far as adding splitting while maintaining constant-time concat, you can look at Brodal et al's "Purely Functional Worst Case Constant Time Catenable Sorted Lists" for some references. I don't think this problem is solved yet. As far as I know, the best known result is O(lg lg n) concat and O(lg min(n - i,i)) split, from Kaplan & Tarjan's "Purely functional representations of catenable sorted lists". For the insertion and deletion case that involves lookup, see the lower bounds I mentioned in another question on ropes. For the insertion and deletion case without lookup, you can use an order-maintenance structure.
> 7 votes

---
Tags: data-structures, functional-programming, persistent-data-structure
---


# Question
Title: Is the minimum weight independent dominating set np-complete in chordal graphs?
I have a found a small article \[1\] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to contradict that exact statement.

Moreover, I have found another reference \[2\] saying that in chordal graphs, it is polynomial time solvable. So which one is it?

Note: I am just trying to reference this result in a project of mine. No need for a proof.

Edit: I am referring to this piece of the introduction: "Domination and most of its variations are NP-complete for chordal graphs (even for the subclass of split graphs) with the exception of independence domination (see \[3\]). On the other hand, an unpublished proof for the NP-completeness of the weighted independent domination in chordal graphs by the author 20 years ago..." Then in my reference \[2\], it also states that the weighted version is polynomial time solvable, yet here they say that there is an NP-completeness proof. Am I missing something fundamental?

---

1. The weighted independent domination problem is NP-complete for chordal graphs by G. J. Chang (2004)
2. Fundamentals of Domination in Graphs by T. W. Haynes, S. Hedetniemi and P. Slater (1998)

# Answer
> 2 votes
As the article clearly mentions, *unweighted* minimum independent dominating set can be solved efficiently (in fact, linear time) for chordal graphs. A glance at the paper shows that this works even if the vertices are given $\\{0,1\\}$ weights (rather than all having unit weight). On the other hand, *weighted* minimum independent dominating set is NP-complete.

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


title: FPT algorithm for edge dominating set

text:
# Question
Title: FPT algorithm for edge dominating set
I have been attempting to learn parameterized complexity on my own, and decided to go through all of the FPT race problems, and defining easy FPT algorithms for them, using concepts such as bounded search tree. I am stuck on figuring out an FPT algorithm for edge dominating set, defined as follows:

**EdgeDominatingSet**

Instance: A graph $G=(V,E)$; a positive integer $k$.

Question: Is there a subset $D\subseteq E$ with $|D|\leq k$ such that for each $e\in E$, either $e\in D$ or $e$ shares an endpoint with an $e'\in D$.

Parameter: $k$

I'm not looking to define anything fancy, just a simple FPT result. Any help would be great!

# Answer
I'm not sure there are any really simple solutions. One algorithm is due to Fernau, and uses an enumeration of all vertex covers of size $2k$; within each of these, a simple dynamic programming algorithm attempts to find a small edge dominating set. Another (earlier) approach, due to Prieto, uses kernelization.
> 3 votes

---
Tags: algorithms, complexity-theory, parameterized-complexity
---


title: Polynomial Reduction 3SAT to K-Clique

text:
# Question
Title: Polynomial Reduction 3SAT to K-Clique
I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is:

\begin{equation} 3SAT \leq\_p KCLIQUE \end{equation}

I am really trying to understand everything formally -- putting everything in a strict logical notation helps me learn Math. To clarify, the content of this proof, has not helped me give other reductions because I don't understand one direction of the $\iff$ in the logic of reductions.

In this reduction, $f$ must be s.t: \begin{equation} w\in 3SAT \iff f(w) \in KCLIQUE \end{equation} and $f$ computes within a polynomial number of steps of the input size. The polynomial part is easy for me to understand, so no problem here!

I see that the above logical statement is equivalent to: \begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land w\not\in 3SAT \implies f(w) \not\in KCLIQUE\end{equation} The above just says yes-instances map to yes-instances and no-instances map to no-instances.

It appears that Sipser shows us: \begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land f(w) \in KCLIQUE \implies w\in 3SAT\end{equation}

Which is also equivalent to the above by taking the contrapositive of the second implication.

Here is my understanding of the $\implies$ direction. Given a yes-instance of $3SAT$, show that the reduction $f$ gives us a yes-instance for $KCLIQUE$. This seems completely natural.

**I don't really understand the other direction** -- namely, given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of $3SAT$. However since the reduction goes from $3SAT$ to $KCLIQUE$ i.e. the domain is the language $3SAT$ and the Codomain is the language $KCLIQUE$, I don't understand **how** we show this.

It appears that the argument is; Our reduction has provided us this graph, from which we can create a satisfying assignment from?

Please help me understand the other direction, and thanks for your time.

# Answer
> 4 votes
Your problem may be a slight misunderstanding.

> Given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of 3SAT.

This is *almost* correct; check the claimed equivalence again:

$\qquad\displaystyle w \in \mathrm{3SAT} \iff f(w) \in \mathrm{KCLIQUE}\\;. \tag{1}$

For the "backwards" direction, you only need to assume a yes-instance from the intersection of the image of $f$ and KCLIQUE, i.e. show that

$\qquad\displaystyle \forall w \in \operatorname{img}(f) \cap \mathrm{KCLIQUE}.\ f^{-1}(w) \in \mathrm{3SAT}$.

That means that you can assume some structure about the instances you need to prove the reverse direction for, namely that introduced by your reduction.

Another misunderstanding:

> the domain is the language 3SAT and the Codomain is the language KCLIQUE

That's not true; note that (1) is (maybe implicitly) supposed to hold for *all* $w \in \Sigma^\*$, that is the domain of $f$ is $\Sigma^\*$. All $w \not\in \mathrm{3SAT}$ must therefore map to $f(w) \not\in \mathrm{KCLIQUE}$ in order to fulfill (1), so the codomain also needs at least one value that is not a yes-instance of KCLIQUE.

---
Tags: complexity-theory, np-complete, reductions, proof-techniques
---


title: Is this method really uniformly random?

text:
# Question
Title: Is this method really uniformly random?
I have a list and want to select a random item from the list.

An algorithm which is said to be random:

> When you see the first item in the list, you set it as the selected item.
>
> When you see the second item, you pick a random integer in the range \[1,2\]. If it's 1, then the new item becomes the selected item. Otherwise you skip that item.
>
> For each item you see, you increase the count, and with probability 1/count, you select it. So at the 101st item, you pick a random integer in the range \[1,101\]. If it's 100, that item is the new selected node.

Is it really uniformly random?

**My thoughts are:**

As the number of nodes increases, the probability for them being selected decreases, so the best chance of selection is for items 1, 2, 3, ..., not for 20, 21, ..., 101.

Each node will not have equal probability of being selected.

Please clarify, as I have trouble understanding this.

# Answer
> 11 votes
The algorithm works, but to understand why, you need to know basic probability theory. The idea is to prove by induction that at step $t$, the currently selected algorithm is uniform among the first $t$ elements. This is clearly the case when $t=1$. Assume now the induction hypothesis for time $t$, and consider what happens at time $t+1$. With probability $1/(t+1)$, the element at position $t+1$ is selected. With probability $t/(t+1)$, the previously selected element is retained. By assumption, this is a uniformly random element among the first $t$ ones, and so the probability that any given element out of the first $t$ is selected is $t/(t+1) \cdot 1/t = 1/(t+1)$. In total, we see that each of the first $t+1$ elements is selected with the uniform probability $1/(t+1)$.

If you don't like induction, you can also do it all at once. For item $i$ to be selected as the output of the algorithm, it needs to have been selected at time $i$, and to not have been dropped at any further time. If there's a total of $n$ elements then this happens with probability $$ \frac{1}{i} \cdot \frac{i}{i+1} \cdot \frac{i+1}{i+2} \cdots \frac{n-2}{n-1} \cdot \frac{n-1}{n} = \frac{1}{n}. $$

---
Tags: algorithms, probability-theory, randomized-algorithms, sampling
---


# Question
Title: Does exploiting a spatial Locality in Cache always leads to a lower miss rate?
I've read that, incorporating many words(spatial locality) per cache blocks leads to lower miss rate. Is it the case always? One possibility of such approach is to make a single cache block of size equal to the size of the cache, but that would be meaningless as far as benefits of memory hierarchy are concerned. Isn't it so?

# Answer
If you use larger blocks in the cache, it will mean having less blocks available (given fixed cache size). If the blocks are too large, part of them isn't used; if they are too small, there is much traffic loading them.

More than *very* general statements like the above, it is almost impossible to say anything unless considering some specific memory access traces. Real workloads access memory in definite patterns that moreover change in time. Look up the working set model.
> 2 votes

# Answer
Spatial (and temporal) locality are both heuristics. Many (in fact, most) algorithms run on data structures in some sequential manner, which many times means that the memory used is consecutive.

However, there are examples where spatial locality may actually be very bad. Perhaps the most common example is scanning a 2-dimensional array: consider an $n\times n$ array, then in the memory, it is represented as an $n^2$ length array, where the entry $i,j$ is in cell $i+n\*j$.

If you scan the array row by row, then spatial locality is excellent, your cache will always prepare the next row. However, if you scan by column, then not only will you always get a miss, but using spatial locality, you will actually retrieve the same rows over and over.
> 2 votes

# Answer
If you increase the size of the data imported into the cache, it obliterates an equal amount of data that is previously a part of the cache- your cache, at the end of the day, can accommodate only a given number of bytes. Considering the column based access of matrix elements example discussed previously by Shaull, if I make the size of data equal to number of columns that reduces the chance of a miss. However if the number of columns are so big that it can't fit in the cache you still have a miss despite increasing the cache-block size. So in a nutshell, not always but does the job most of the times as there are only a few applications with irregular data patterns and only data-intensive applications can fill up the cache so fastly that it needs to invalidate it's contents entirely for fetching new data. Hope that helps.
> 1 votes

---
Tags: computer-architecture, memory-management, cpu-cache
---


# Question
Title: Complexity of calculating independence number of a hypergraph
Let $G$ be a "hypergraph", a collection of vertices $V=\\{v\_1,v\_2,\ldots,v\_n\\}$ and a collection of "hyperedges" $E=\\{e\_1,e\_2,\ldots,e\_m\\}$, where $e\_i\subseteq V$ and unlike normal edges, an edge may contain more than two vertices.

An "independent set" (http://en.wikipedia.org/wiki/Independent\_set\_(graph\_theory)) is a collection of vertices, $U$, that does not fully contain any of the hyperedges: $e\_i\not\subseteq U$. The "independence number" or "maximum independent set size" is the size of the largest independent set in the graph $G$.

I know that finding if there is an independent set of size $k\in\mathbb{N}$ in some normal graph $G$ is NP-Complete. If I am not mistaken, this holds for hypergraphs as well. However calculating the independence number is not proven to be NP. Even approximating it is not proven in NP.

First, is there a more specific complexity class for calculating the independence number than NP-Hard?

Second, how much harder is it for a hypergraph? Again, is there a complexity class more specific?

For related questions, a recent dissertation has been helpful to me: https://escholarship.org/uc/item/79t9b162.

Thanks!

# Answer
> 2 votes
did not find a proof of complexity class harder than "NP hard" for this problem (ie the presumably more complex hypergraph version of the problem does not seem to have been proven harder than the graph version) however did find the following. Saket has recent research in the area. results in complexity theory in active areas of research tend to be highly specialized and in the form "for limited hypergraph types \[x\], the following improved complexity bound \[y\] is shown." (ie more as approximability results, & more specialized than what you request but it can be mined for nearest desirable results/refs.)

basically hypergraphs while an old mathematical concept are a more recent area of complexity theory research and there is a large active/ongoing research program of determining complexity of operations around them and how those complexities relate to corresponding graph operation complexities, and translating theorems and knowledge about graphs into their hypergraph analogs.

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


# Question
Title: Recurrence for total number of extraneous key insertions in a hash table
I have a practice exam question that I don't know how to set up a recurrence for. It is dealing with a hash table. The question is as follows:

> Suppose that a hashing strategy is designed so that it starts with an initial hash table size of $H= 8$. You may assume that only insertions are performed (no deletions).
>
> Any time the hash table is going to be more than 50% full (when an attempt is made to add item $\frac{H}{2} + 1$ to a table of size $H$), the hash table size is doubled to $2\times H$, and then the $\frac{H}{2}$ keys in the previous hash table are rehashed using $\frac{H}{2}$ extraneous key insertions into the new table of size $2 \times H$. The key insertions used to initially place each key into the hash table are called necessary key insertions (these are not extraneous).

The question is asking to derive a recurrence relation $E(H)$ for the number of extraneous key insertions that have occurred in total up until the point in time that the hash table size is $H$ and to explain where the terms in the recurrence relation derive from.

If someone could help me out with this, it would provide very helpful as I am practicing for an exam that I have in a week. Thanks everyone.

I got the result $E(H)=2\times E(\frac{H}{2})$ because after each rehash there are $\frac{H}{2}$ extraneous key insertions being put into the table of size $2\times H$. So if the size is twice the amount of $H$, I figured the recurrence would be $E(H)=2\times E(\frac{H}{2})$. I only posted here because I was hoping someone could assist me with this because this question has me a bit stumped.

# Answer
> 2 votes
Your justification is flawed. There is no reason to think that the number of extraneous key insertions will necessarily be twice as much if the hash table is twice as large; you're just guessing here. When you choose a recurrence relation, you need to be able to justify it. Don't just guess.

My recommendation is that you go back to my first comment and try to answer the questions I asked there:

> Have you tried to count the number of extraneous key insertions in total, as a function of the number that occur until the most recent doubling and the number that have occurred since then? Does this give you any ideas for a recurrence relation?

I don't see any evidence that you've tried to pursue that direction yet, so I suggest that you spend some quality time thinking about that avenue. If you let $n\_t = $ the number of extraneous key insertions in total, $n\_0 =$ the number that occur from the beginning of time until the most recent doubling, and $n\_1 = $ the number that have occurred since then, can you write a formula that writes $n\_t$, $n\_0$, and $n\_1$? Hint: When you see the answer to this question, you'll probably kick yourself. If you think about it, you'll probably find it's not as hard as you think.

Then, once you can answer that question, here is your next step. When you can come up with a formula that relates those three quantities, you might next try to think about how/whether they are related to values of the form $E(\text{something})$. Can you find any formulas for any of $n\_t$, $n\_0$, and $n\_1$ as a function of $E(\text{something})$?

# Answer
> 0 votes
If the current occupancy of the hash table is $H \geq 3$, then the hash table is of size $2^{\lceil \log\_2 H \rceil + 1}$. Assuming this size is larger than $8$, this means that $2^{\lceil \log\_2 H \rceil-1}+1$ entries had to be copied last time the table was enlarged, which happened upon insertion of element no. $2^{\lceil \log\_2 H \rceil-1}+1$. Therefore $$ E(H) = \begin{cases} 2^{\lceil \log\_2 H \rceil-1}+1 + E(2^{\lceil \log\_2 H \rceil-1}+1) & H \geq 5 \\ 0 & H \leq 4. \end{cases} $$ This can be solved to give $E(H) = \Theta(H)$ for $H \geq 5$.

---
Tags: data-structures, runtime-analysis, recurrence-relation, hash-tables
---


# Question
Title: Can somebody explain Horner's method of evaluating polynomials and how does it reduce the time complexity to 2n operations?
I have been trying to understand the difference between normal polynomial evaluation and horner's method. usually it takes 3n-1 operations while horner's method reduces it to 2n operations. I tried a couple of explanations but they were too theoritical. I would be glad if somebody comes up with a decent and simple explanation.

# Answer
> 5 votes
Let's compute the polynomial $2+3x+x^2+15x^3$ using Horner's method: $$ 2 + x(3 + x(1 + 15x)). $$ The complete set of steps is $$ \begin{align\*} &t\_1 \to 15 \times x \\ &t\_2 \to t\_1 + 1 \\ &t\_3 \to t\_2 \times x \\ &t\_4 \to t\_3 + 3 \\ &t\_5 \to t\_4 \times x \\ &t\_6 \to t\_5 + 2 \end{align\*} $$ Compare this to the "trivial" method: $$ \begin{align\*} &t\_1 \to x \times x \\ &t\_2 \to t\_1 \times x \\ &t\_3 \to 15 \times t\_2 \\ &t\_4 \to 3 \times x \\ &t\_5 \to 2 + t\_4 \\ &t\_6 \to t\_5 + t\_1 \\ &t\_7 \to t\_6 + t\_3 \end{align\*} $$ Here the idea is to compute the powers $1,x,x^2,x^3$ and then take the linear combination corresponding to the polynomial. Since one of the coefficients is $1$ (coefficient of $x^2$), we only need $7$ rather than $8$ operations.

# Answer
> 2 votes
By computing powers, $2+3x+6x^2+15x^3+8x^4$ is obtained using $2d-1 \color{red}{\times }$ and $d\color{red}{+}$, as:

$p:=2\space \space \rightarrow 2$

$z:=\space \space \space \space \space \space \space x, \space p:=p\color{red}{+}\space \space 3\color{red}{\times }z\space \space \rightarrow 2+3x$

$z:=z\color{red}{\times} x, \space p:=p\color{red}{+}\space \space 6\color{red}{\times}z\space \space \rightarrow 2+3x+6x^2$

$z:=z\color{red}{\times}x, \space p:=p\color{red}{+}15\color{red}{\times}z\space \space \rightarrow 2+3x+6x^2+15x^3$

$z:=z\color{red}{\times}x, \space p:=p\color{red}{+}\space \space 8\color{red}{\times}z\space \space \rightarrow 2+3x+6x^2+15x^3+8x^4$

By Horner's method, $8x^4+15x^3+6x^2+3x+2$ is computed using $d\color{red}{\times }$ and $d\color{red}{+}$, as:

$p:=8\space \space \rightarrow 8$

$p:= p\color{red}{\times}x\color{red}{+}15\space \space \rightarrow 8x\space \space +15$

$p:= p\color{red}{\times}x\color{red}{+}\space \space 6\space \space \rightarrow 8x^2+15x\space \space +6$

$p:= p\color{red}{\times}x\color{red}{+}\space \space 3\space \space \rightarrow 8x^3+15x^2+6x\space \space +3$

$p:= p\color{red}{\times}x\color{red}{+}\space \space 2\space \space \rightarrow 8x^4+15x^3+6x^2+3x+2$

The trick is that every time you multiply by $x$, the multiply applies to all terms and you needn't compute the powers of $x$ separately.

# Answer
> 1 votes
**What happens is that the product of the coefficient $a\_i$ with $x^i$ is combined with the computation of the powers of x.** This is based on different uses of distributivity of multiplication for addition, with repeated uses of the following transformation, which saves each time one multiplication: $$A\_ix+a\_ix \\;\Rightarrow\\;(A\_i+a\_i)x$$ Here $A\_i$ stands for the higher power terms (with index greater than $i$) already added together, up to a factor $x^{i-1}$ that is still to be computed in the Horner evaluation: $$A\_i=\sum\_{j=i+1}^{n}a\_jx^{j-i}$$ This transformation is applied $n-1$ times, thus saving as many multiplications.

## More details

The transformation of the polynomial uses the following basic step: $$\sum\_{i=0}^n a\_ix^i = \Big(\sum\_{i=0}^{n-1} a\_{i+1}x^{i}\Big)x + a\_0$$

which you can repeat recursively $n-1$ times to get the Horner formula:

$$\sum\_{i=0}^n a\_ix^i = ((...((a\_nx+a\_{n-1})x + a\_{n-2})x + ...)+a\_1)x+a\_0$$

The left-hand side is the traditional representation of polynomials, while the right-hand side is the Horner representation. A first **important comment** is that the Horner representation is an arithmetic formula that shows explicitly all operations that are performed (though the multiplication operator is not written here for better readability). They can be directly counted on a Horner formula like $$ ((( a\_3 \times x +a\_2)\times x+a\_1)\times x + a\_0)$$ However this is not true of the traditional formulation with powers of x: $$a\_3\times x\times x\times x +a\_2\times x\times x+a\_1\times x+a\_0$$ because, in actual practice, the computation of the powers of x is factored, so that each power is computed only once. Consequently, the only products of $x$ by itself that count are those of the higest power of $x$.
The actual computation cannot be represented by a tree structure, hence by a simple arithmetic formula, and in prectice requires one extra variable of storage to keep the successive powers of $x$.
This is what makes the analysis more complex, and it might be more illuminating to compare separately each the two modes of evaluation with the most naive mode that does not factor (share) anything when computing the various powers $x^i$.
\[*I can attempt to do that on request, but this answer is long enough as it is.*\]

## **Analysis**

At each recursive application of the first formula above to obtain the Horner form, we save one multiplication, which totals to a saving of $n-1$ multiplications for the whole transformation.

**What happens is that the product of the coefficient $a\_i$ with $x^i$ is combined with the computation of the powers of x.**

More precisely this uses distributivity of product wrt sum: $ax+bx=(a+b)x$
When you do the sum first, you have 2 operations, instead of 3, saving one multiplication.

It must be objected that when you have $n$ terms, you should save $n-1$ multiplication, for example 3 multiplications when you have 4 terms as in: $ax+bx+cx+dx=(a + b + c +d)x$
This formula gives a saving of $n-1$ multiplications, i.e., 3 in the example.

This would be true if we were comparing with the very naive evaluation of polynomials that does not factor the computation of powers of $x$.
However the situation is here even more subtle, and follow a more complex pattern, where all terms but one contain a product with the same factor $y$, for example $ayx+byx+cyx+dx = (ay + by + cy +d)x$.
This again corresponds to the very naive evaluation of the polynomial, where $y$ is actually equal to $x$.

However, there are other ways of computing this, such as $(a+b+c)yx+dx$. This is precisely the case in the traditional evaluation of the polynomial, when computing only once each power of $x$, thus factoring the computation of $x^i$ for the computation of all $x^j$ such that $j \ge i$. Note also that in the case of the polynomial, we have $y=x$, but it changes nothing.

So the transformation used at each step is better represented (still taking the same four terms example) by the formula: $(a+b+c)yx+dx=((a + b + c)y +d)x$
which replaces three multiplications by only two, thus saving one multiplication at each step of the recursive transformation, independently of the number of terms in the sum.

As the formula is applied $n-1$ times to get the Horner form, we save a total of $n-1$ multiplications.

---
Tags: algorithms, time-complexity
---


# Question
Title: Amortized Analysis for Addition of $n$ numbers
How can we add n positive integers with binary expansion $l\_1$, $l\_2$,...$l\_n$ bits so that the total complexity is $O (\sum l\_i)$ for $i = {1,...,n}$ ? More importantly, how can show this complexity using amortized analysis (the potential method)?

I know the elementary school addition of 2 numbers of length $s$ and $r$ is $O(r+s)$ and hence, the addition of n integers is $O(\sum l\_i)$. However, what potential function would you use to prove that bound? I don't seem to have any intuition on that... Maybe use a function similar to the standard binary counter example (number of 1's in the binary representation of the number)..?

# Answer
> 1 votes
You should be slightly more careful in your argument. Let the actual numbers you are adding be $x\_1,\ldots,x\_n \> 0$, where $\ell\_i = \lfloor \log\_2 x\_i \rfloor + 1$. The complexity of adding two numbers $x,y\>0$ is $O(\log(x+y))$. In our case, assuming we are doing the addition sequentially, the numbers we are adding are $x\_i$ and $x\_1 + \cdots + x\_{i-1}$, for $i=2,\ldots,n$. Therefore the entire complexity is $$ O\big(\sum\_{i=2}^n \log (x\_1 + \cdots + x\_i)\big). $$ Suppose now that we arrange the numbers in non-decreasing order $x\_1 \leq x\_2 \leq \cdots \leq x\_n$. Then $$ \sum\_{i=2}^n \log (x\_1 + \cdots + x\_i) \leq \sum\_{i=2}^n \log (ix\_i) \leq n\log n + \ell\_1 + \cdots + \ell\_n. $$ This is tight (up to constant factors) when all $\ell\_i$ are equal. In particular, when adding $1$ to itself in this fashion, the complexity is $O(n\log n)$ rather than $O(n)$.

Can you think of a better way?

# Answer
> 0 votes
If the $i$-th number has $1$'s in bits $j\_1, j\_2, \dotsc$ (counted from the right), you can implement adding that number to the sum as stepping a counter once with each stepwidth $2^{j\_1}, 2^{j\_2}, \dotsc$. For this implementation, adapting the analysis for the standard binary counter should be straightforward. (See also here.)

---
Tags: algorithms, algorithm-analysis, amortized-analysis
---


title: Intersection of two NPDAs

text:
# Question
Title: Intersection of two NPDAs
Is there a way to take the interection of two NPDAs?

I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.

# Answer
The intersection of two context-free languages can be non-context-free. The classical example is $$ \\{ a^n b^n c^m : n,m \geq 0 \\} \cap \\{ a^m b^n c^n : n,m \geq 0 \\} = \\{ a^n b^n c^n : n \geq 0 \\}. $$ So in general you cannot simulate the intersection of two NPDAs with an NPDA.
> 6 votes

# Answer
Intersection of two NPDA means intersection of their languages. Of course, Context-free languages are not closed under intersection, so that you will not generally get a NPDA for the intersection. If interested in the topic, you may look at Range Concatenation Grammars, which are closed under intersection and parsable in cubic time. And, of course, they include Context-Free grammars.
> 2 votes

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


# Question
Title: insert and delete in order statistic tree
I am having trouble in understanding order-statistics tree .

**Definition :**
Every node in tree stores the number of descendants of itself .
Can you please explain the Algorithm or pseudocode how to **Insert** and **Delete** a node in the tree **when tree is to be balanced** .

Basically i want to find the rank of an element in the tree in **O(log N)** time complexity and nodes can be inserted and deleted in between querries .

P.S. I am able to understand the **rank(x)** operation .

# Answer
The exact implementation of **Insert** and **Delete** depends on the underlying binary tree structure which is used, but the idea is that you maintain the *size* field throughout the operation. Consider for example the following **Insert** procedure, which always inserts its element as a new leaf:

**Insert(Tree, $x$)**

1. If Tree is empty, set Tree to be $x$, and return.
2. Let $r$ be the root of Tree, and Left, Right its children.
3. If $x \< r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

Here is the updated algorithm, which maintains the size information:

**Insert(Tree, $x$)**

1. If Tree is empty, set Tree to be $x$ and *size*(Tree)=1, and return.
2. Increase *size*(Tree) by 1.
3. Let $r$ be the root of Tree, and Left, Right its children.
4. If $x \< r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

This is the basic idea. You can take it from here.
> 2 votes

---
Tags: algorithms, data-structures, binary-trees
---


title: Which NPC problems are NP Hard

text:
# Question
Title: Which NPC problems are NP Hard
I have read that TSP and Subset Sum problems are NPC problems which are also NP Hard. There are also problems like Halting Problem which is NP Hard, but not NP Complete

And Wikipedia defines this as

> A problem $H$ is NP-hard if and only if there is an NP-complete problem $L$ that is polynomial time Turing-reducible to $H$.

Like NP Complete problem is there any problem considered to be the first NP Hard problem?

To show one problem to be NP Hard we need just to reduce one NPC problem to it?

Whether all NPC problems are NP Hard?

If no, why not?

# Answer
A problem is **NP**-hard if every problem in **NP** can be reduced to it by some appropriate kind of reductions (typically, polynomial-time many-one reductions). A problem is **NP**-complete if it is in **NP** and is **NP**-hard.

Therefore, by definition, every **NP**-complete problem is **NP**-hard.
> 6 votes

# Answer
A problem is NP-complete if (1) it belongs to NP, and (2) if every problem in NP can be reduced to it in polynomial time. If (2) holds, a problem is said to be NP-hard. In other words, we say a problem is NP-complete if it is both NP-hard and in NP.

Polynomial-time reducibility is a relation among languages, and it is also transitive. That is to say, yes, you can prove NP-hardness of a problem by reducing a problem of *known* hardness to a problem of *unknown* hardness. For example, you could reduce 3-SAT to your new problem X, and it would prove X is NP-hard. Additionally, if you show X is also in NP, you have that X is NP-complete.

You might want to take a look at the Cook-Levin Theorem. By the theorem, we know that SAT and 3-SAT are NP-complete. Some of the "first" NP-complete problems were given by Karp.
> 2 votes

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


# Question
Title: Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages
I want to show that for any language $L \subseteq \\{ a \\}^\* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages.

I know that every regular language is also a context free language so I tried to show that direction of the proof first but ran into some difficulties.

Is there a more logical approach to this? Would I have to show that the conditions for both the pumping lemma for regular languages and the pumping lemma for context free grammars are equivalent for this language?

# Answer
let $ z \in L$ such that $ |z| \geq n $ (where $n$ is the lemma's constant). By the pumping lemma for CFL, we know that we can write $z=uvwxy$ such that:

1. $|vwx| \leq n$
2. $|vx| \geq 1$
3. for all $i \geq 0$: $uv^iwx^iy \in L$

Because $L$ is over an unary alphabet, we can change the order of the sub-words and the word ($z$) will not change, meaning we can also write $z=wvxuy$.

So. for all $i \geq 0$, $uv^iwx^iy = wv^ix^iuy = w(vx)^iuy$. Let's write a little different: $u' = w, v' = vx, w' = uy$. and we have that $u'(v')^iw' \in L$.

It's easy to see that $|u'v'| \leq n$ and $|v'| \geq 1$, So we can conclude that for the same $n$, the conditions of pumping lemma for regular languages holds.

It might be worth mentioning that every CFL of unary alphabet is also regular (We know that even though a language satisfies the pumping lemma for regular/CF languages, it does't mean that the language is regular/CF).

It can be shown using Parikh's theorem, and showing that for every semi-linear set $S \subseteq \mathbb{N} $ there is a regular language $L$ such that $\Psi (L)=S$ (or $p(L)$ using wikipedia's notations)
> 4 votes

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


# Question
Title: In flow networks, may source/sink have incoming/outgoing edges?
I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?

Flow-networks are always pictures with no edges entering source, and no edges leaving sink.

I've tried to search the web for an answer, but did not come across an answer i fully understand. Also, I've yet to see a flow network pictured with these edges from source/sink.

Could I transform an undirected graph into a flow-network ? This network will have edges going into source and edges leaving sink ?? This hypothesis is the reason for my question.

# Answer
> 2 votes
Yes, it's possible.

My source is 'Graph Theory and its Applications', 2nd ed, by Gross & Yellen, page 540, question 13.1.8:

> Some authors define an s-t network such that the source s must have indegree 0 and t must have outdegree 0. Describe how a network whose source and sink do not satisfy these additional requirements can be transformed by graphical operations into one whose source and sink do meet such requirements.

However, it doesn't give the construction, I can only think that it would be by adding a supersource and a supersink, as you'd usually do with multiple (though standard) sources and sinks, to 'soak up the leakage'. I am not sure though.

# Answer
> 2 votes
Whether you consider edges in- and out- edges to and from the source and sink, resp. will not change the solution. One usually ignores them, because you do not need to consider those edges (in the Ford-Fulkerson algorithm, for example).

Consider one of several edges emergent from the source. If after choosing a path from source to sink it turns out that you would have an arc in the residual graph to the source, it means that you still have some capacity left. But you will never consider a path going into the source. The goal is to find how much flow can go through the graph from the source to the sink. You just subtract the flow going through the path just analysed, and move on to the next one until no more flow can go though the graph.

You may take a look at Jeff Erikson's notes. I find them great.

Is your question motivated by the GraphCut problem in machine vision?

In that case you do not need to transform the graph, just to decide where to start clamp your source and your sink (usually at opposing corners of the image).

# Answer
> 1 votes
1. Depends on the definition (so there are definitions which are compatible)
2. Do you really want to turn existing vertices of your undirected graph to sink and source?

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: How to find out memory size by hex ranges?
so I am a bit confused here. I read a memory-map ranging from certain hex values and I'm trying to find out how large RAM is by it. Here's the code:

```
const char *memorybottom = 0x00000000;
const char *memorytop = 0xAA55D0AB;

```

The bottom is 0, and the top is AA55D0AB. I tried to convert that to binary and increased each 2 byte by a power of 2, left to right, but the result is 0.25 kilobytes; 256 bytes, which is 1/4th of a kilobyte. However, someone told me that AA55D0AB is for MB sized RAM.

Can anyone help me translate between hex to determine maximum RAM capacity in MB, GB, KB, etc.?

PS: This is for emulation. I am trying to emulate memory for an Atari 2600 by providing a lowest mem. value pointer to memorybottom, and the opposite with memorytop. However, I am not too familiar with hex but better with binary.

# Answer
> 1 votes
First thing I did was convert the hexadecimal address to decimal. And since it appears to be byte-addressed memory; then we have about 2857750699 bytes. This is about $2.86$ x $10^9$ bytes, or in other words about 2.86 GB.

---
Tags: memory-hardware
---