title: Context-free Language - Pumping Lemma?

text:
# Question
Title: Context-free Language - Pumping Lemma?
im having some problems when it comes to Pumping Lemma of Context-free Language ... this is the Language :

$$L = \\{a^n b^n c^m | n\ge 0 , 0 \le m \le 2n \\}$$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $p,r\>0$ be the pumping length given by the lemma.

Let $z=a^p b^p c^r$, then $z∈L$

Than according to the lemma, z can be written as z=uvwxy where the following properties hold:

$$|vx|≥1$$ $$|vwx|≤n$$ for every $i≥0$, $uv^iwx^iy∈L$

for the cases $i$ always had some problems ... there is one ..

$vx = a^n b^n$ (no $c$'s )

i really have some problems understanding the PL for CF Language

# Answer
> 2 votes
The solution which I provide below is very similar to Example 2.37 in classical Sipser's book "Introduction to the theory of computation"

> Let $p,r\>0$ be the pumping length given by the lemma.

I think you have a little abuse of notation. Look carefully at definition. It states that if $L$ is $CFL$ then, there exists some constant $p$ (pumping length) that for every string $s \in L$ such that $|s| \ge p$, $s$ can be divided on five parts such that the following properites hold:

> $|vx|≥1$ $|vwx|≤n$ and for every $i≥0, uv^iwx^iy∈L$

So, let us take $s = a^nb^nc^{2n}$, where $n+n+2n \> p$. Then the conditions for lemma are hold, and it follows that $s = uvwxy$ with all those properties. From the first property we get that at least one of $v$ or $x$ is non-empty string. Now, we should consider several cases:

1) At least one of $v$ or $x$ contains diffent letters of the alphabet (for example, $v$ = $zabt$, $|z|, |t| \ge 0$). Then $uv^2wx^2y$ doesn't has the form $a^nb^nc^m$ (problems with order, in my example $v^2 = zabtzabt$), so we get a contradiction.

2) Either $v$ or $x$ contains only one letter from alphabet. Here we get such cases:

2.1) $v$ and $x$ don't contain the letter $c$. By lemma the string $s\_1 = uv^0wx^0y \in L$. But $s\_1$ has less than $n$ letters $a$ or $b$, while it contains $2n$ letters $c$. So, the property $m \le 2n$ doesn't hold in this case and we get a contradiction.

2.2) $v$ or $x$ contain the letter $c$, so either $a$ or $b$ doesn't belong to $v$ and $x$. Then string $s\_1 = uv^2wx^2y$ contains at least $2n + 1$ $c$'s, and only $n$ $a$'s or $b$'s. Again, we get a contradiction.

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


# Question
Title: Is SAT sparse? Is this an understood problem?
Intuition suggests that SAT is definitely not sparse. For any well-formed SAT problem $\phi$, we have $(\phi \in SAT) \vee (\neg\phi \in SAT)$, and $\exists \phi : (\phi \in SAT) \wedge (\neg\phi \in SAT)$ (perhaps "many" such $\phi$ satisfy this).

The set of well-formed queries is not sparse, consider $a\_1 \wedge \cdots \wedge a\_n$ with each $a\_n \in \\{x\_1, \neg x\_1\\}$.

But this proof is not complete since negation of a DNF and CNF and forcing canonical form changes length, and if canonical form is dropped then it is not obvious how problems relate to representations of their inverses.

* Is it known that SAT is not sparse?
* Is it possible for a dense language to reduce to a sparse language, as is supposed in Mahaney's theorem?

# Answer
> 5 votes
SAT is not sparse. For example, we have exponentially many monotone formulas per input length, and they are all satisfiable.

Regarding your second question, since most people conjecture that P≠NP, according to Mahaney's theorem those people don't expect NP-complete problems to be reducible to sparse languages.

# Answer
> 2 votes
* SAT is not sparse. For example $(x\_1 \vee \neg x\_1) \vee (anything)$ is in SAT.
* If SAT reduces to a sparse language (which is unexpected because it would imply P = NP by Mahaney), the reduction would necessarily include many collisions.
* If P = NP, SAT reduces to the sparse language $\\{1\\} \subset \\{0,1\\}^n$.
* In general, reductions can have collisions. For instance, any reduction from a canonical form such as CNF or DNF has collisions for any two representations of a formula with the same canonical form.
* P contains many dense languages, such as "strings with an even number of 1s" or, even just "all strings." These all reduce to $\\{1\\} \subset \\{0,1\\}^n$.
* NP problems that are not NP hard can reduce to sparse languages. For instance, every P $\subset$ NP problem does.
* If P = NP, then there are many sparse languages that are NP complete. In fact any sparse language in P would be NP complete in this case.

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


# Question
Title: Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?
I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\\{0, 1, ... n-1\\}$, so as to minimize the $L\_\infty$ norm, i.e. minimize $\text{max}\_{0 \leq i \< n}{\left| f(i) - p(i) \right|}$.

Now, I know that for $L\_2$, this can be solved using a system of linear equations (for getting a zero vector as the derivative of the error) - that is the "Least Squares" method. But - the $L\_\infty$ error is not a derivable function. I also know that for a continuous interval rather than a finite grid, there's an iterative approximation algorithm - the Remez Algorithm (although I'm not entirely clear about the specifics - I just noticed it.) And I also had a vague hunch which I didn't manage to act on that Chebychev polynomials, each of which being the optimal solution to the problem with $f = 0$ and a fixed leading coefficient 1, might be relevant here somehow.

Anyway, what I'd like to know is:

* Is this problem is essentially combinatorial or essentially numero-analytic?
* Can it be solved in PTIME (assuming operations on real values are O(1))?
* If so, what's the numerical stability features of such a solution (since my n is large-ish)?
* If not, does it admit an efficient (PTIME) approximation scheme?
* If not, how do people deal with it in practice?

# Answer
The problem can be solved in polynomial time using linear programming.

Write $p(x) = c\_k x^k + \dots + c\_1 x + c\_0$, and think of $c\_0,\dots,c\_k$ as unknowns. Also introduce an unknown $d$, which will represent the $L\_\infty$ norm. We will minimize $d$, subject to the following inequality:

$$-d \le f(i) - (c\_k i^k + \dots + c\_0) \le d.$$

Notice that, since $i$ and $f(i)$ are constants, this is a linear inequality in the unknowns. We obtain one inequality per value of $i$. Now the minimum achievable value of $d$ corresponds to the polynomial $p$ that minimize the $L\_\infty$ norm, so you can solve this using any algorithm for linear programming. Since linear programming is in P, your problem is in P, too.

I expect that this algorithm will be efficient in practice, as linear programming over $k+2$ unknowns and $n$ inequalities should be pretty efficient for reasonable values of $k,n$.

I don't know what the numerical stability issues might be.

---

Another solution in practice might be to find a solution that minimizes the $L\_p$ norm. You could start by minimizing the $L\_2$ norm, using any standard method (e.g., least squares). Then you could start from that solution and find a solution that minimizes the $L\_p$ norm, for some larger value of $p$, say using gradient descent. After increasing $p$ a few times I expect the resulting solution might often turn out to be a reasonable approximation, even if not optimal.
> 2 votes

# Answer
Here's my current idea. It's oriented towards a faster implementation - i.e., for me, $\Omega(n^2)$ is much too much. It also assumes a lower threshold value for distance (which is relevant for me, since the functions' domain in practice is values stored in O(1) space, e.g. 4-byte integers or floating point values).

Well, the idea is only a sketch, but in a nutshell:

* Look for feasible solutions instead of trying to optimize.
* Perform a binary search for the minimum feasible $L\_\infty$ value - bewteen an initial value of some simplistic solution and a threshold value under which you don't care (or under which you can assume optimality).
* The feasibility constraint for for $L\_\infty$-error $\epsilon$, at point i, is $$\left|\sum^k\_{j = 0} a\_j i^j - f(i)\right| \leq \epsilon$$ but this can easily be converted into two linear constraints: $$\sum^k\_{j = 0} a\_j i^j \leq f(i) + \epsilon \quad \text{ and } \quad \sum^k\_{j = 0} a\_j i^j \geq f(i) - \epsilon$$ <sub>(The variables here are the $a\_j$'s, so it's not a problem to use powers of $i$.)</sub>

... and this should be a reduction of the problem to checking the feasibility of a linear program, for a number of times which does not depend on $n$.

If that's the best I can do - although I have no reason to assume that is the case - then the answers to my questions would be:

* Combinatorial or numero-analytical? - Somewhere in the middle I guess you could say.
* Can it be solved in PTIME - ???
* Admits an efficient (PTIME) approximation scheme.
* How people deadl with it in practice - probably with this kind of approximation, perhaps with wiser guessing of initial solutions. For example, one might start with an $L\_2$-optimal solution on a fixed-size sample (perhaps using over-defined least squares with a larger-than-k+1 sample?) to get the initial solution, reducing the number of iterations if $f$ is well-behaved.
> 1 votes

---
Tags: optimization, approximation, polynomials, error-estimation
---


# Question
Title: What are the flaws in this encryption algorithm?
Let $A$ be a randomly generated matrix. Let $I$ be the identity matrix. $\times$ is the matrix multiplication operation, $/$ is matrix division (multiplying the first matrix by the inverse of the second). $$ I \times A \times A = B $$

Provide $B$ and $I$ to the recipient. To create encrypted message $E$ from unencrypted message $M$: $$ E = M \times A \times A $$

Send $E$ to the recipient. The recipient will solve for $M$ using: $$ M = E / ( B / I) $$ My question is:

1. Will the recipient be able to decode the message?
2. If an attacker knows $E$ and $I$, can they efficiently solve for $M$?
3. Is there a simple way to make it nonlinear?

I accepted an answer but am still waiting for #3.

# Answer
This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ciphertext E and knows the corresponding message M can recover the secret key and thus decrypt all other messages that were encrypted with the same key.

The recipient will be able to decrypt *if* A is invertible. If A is not invertible, then the recipient won't be able to decrypt.

See also the questions about the Hill cipher on Crypto.SE.
> 15 votes

# Answer
Cryptosystems which are algebraic in nature are amenable to algebraic cryptanalysis.

If you are trying to design a secure cryptosystem for actual use, there is one important maxim that you should keep in mind:

> Don't design your own cryptosystem!

It is easy to design weak cryptosystems. Off-the-shelf cryptosystems have withstood breaking attempts by the community, and are better than an obscure cryptosystem designed by an amateur.
> 10 votes

---
Tags: algorithms, algorithm-analysis, correctness-proof, cryptography, encryption
---


# Question
Title: Sorting using comparison is superlinear or sublinear?
My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem?

In more details: we know that sorting using comparison have the achievable lower bound of $O(n\ln n)$ where $n$ is the number of items to be sorted. Now the question of superlinear and sublinear is dependent on what is considered the size of the input, and I am not sure if $n$ is the size here. We have 2 cases:

(a) The input is a full acyclic graph describing the comparison relation. In this case the input size is actually $O(n^{2})$ and the problem is sublinear.

(b) The input is just the item to be sorted, plus the description of a Turing machine that will perform the comparison. Then the input size is $O(n)$ and the problem is superlinear.

Can anyone clarify what is the consensus on this? Some people tell me that sorting with comparison is an example of a problem with a nontrivial lower bound (ie. the lower bound stronger than just by looking at how much information do the algorithm need to know). However, it seemed to me that in fact this is one example where figure out how much information you need is the crux of the problem, and not any combinatorial nature of Turing machine. Thanks.

# Answer
In complexity theory, the input size is by convention (or definition, really) the *number of cells* the input takes up *on a Turing machine tape*.

The famous $\Omega(n \log n)$ bound does not adhere to this convention, though; $n$ is not input size but number of elements here. The input is (in general) longer than that since every element will have to be encoded on the tape in some way.

Generally, in sorting we consider the input to be the array (or list) of elements to be sorted. We don't pass the comparison matrix.

But you touch on an important point: *complexity statements depend on machine model and input encoding*. We usually default to TMs or RAMs depending on context and "reasonable" (i.e. not wasteful) encodings, but if there is any chance for ambiguity you need to state all the parameters.

For instance, the input size of sorting *is* $n$ is you consider RAMs with unit cost measure!
> 4 votes

---
Tags: complexity-theory, time-complexity, sorting, lower-bounds
---


# Question
Title: Given a set C of set P of sets R, find the smallest set S such that at least one subset R from each P is a subset of S
Given a universal set of elements $\mathbf{U} = \\{a\_1, a\_2, .., a\_n\\}$, a set $\mathbf{R} = \\{a\_i\\} \subset \mathbf{U}$ where $i ϵ \\{1, .., n\\}$, a set $\mathbf{P} = \\{R\_1, .., R\_m\\}$ and a set $\mathbf{C} = \\{P\_1, P\_2, .., P\_l\\}$, how do I go about finding a set $\mathbf{S} = \\{a\_1, .., a\_n\\} \subset \mathbf{U}$ such that at least one set $\mathbf{R}$ from each $\mathbf{P}$ is satisfied and such that the size of $\mathbf{S}$ minimal? I consider the set $\mathbf{R}$ to be *satisfied* by $\mathbf{S}$ if $\mathbf{R} \subseteq \mathbf{S}$.

This seems similar to set cover problem, but I am not sure how I can approach this.

# Answer
> 2 votes
Your problem is NP-hard, by reduction from Monotone SAT.

Recall that Monotone SAT is (the decision version of) the following problem: given a CNF formula $\varphi$, find a satisfying assignment with the fewest variables set to true.

Now, map each clause, say $x\_{i\_1} \lor x\_{i\_2} \lor \dots \lor x\_{i\_k}$, in $\varphi$ to a set $P=\\{R\_1,R\_2,\dots,R\_k\\}$ where $R\_1=\\{x\_{i\_1}\\}$, $R\_2=\\{x\_{i\_2}\\}$, etc. Finally, form $C$ to be the set of $P$'s obtained in this way from the clauses of $\varphi$. Then a set $S$ satisfies $C$ iff it corresponds to a satisfying assignment for $\varphi$ (including the element $x\_i \in S$ corresponds to setting $x\_i$ to true in the assignment), so the minimal-size set $S$ that satisfies C corresponds to the minimal-size satisfying assignment for $\varphi$.

Since Monotone SAT is NP-hard, your problem is NP-hard, too.

If you need to try to find an exact solution in practice, you could try formulating your problem as an instance of SAT and feed it to a SAT solver (using binary search over the size of $S$), or you could formulate it as an instance of integer linear programming and feed it to an ILP solver.

---
Tags: algorithms, set-cover
---


# Question
Title: Does a time quantum affect priority non preemptive scheduling?
I am given a list of processes with their arrival time, CPU, time and Priority. The time quantum is given as 2 seconds. A **lower** priority number translates to a **higher** priority.

(process #, arrival time, CPU time, Priority)

-P0: 0, 8, 5

-P1: 2, 2, 4

-P2: 4, 1, 6

-P3: 6, 3, 3

So the priority ranks P3,P1,P0, P4.

would my scheduling look like this using the **priority non preemptive** scheduling algorithm:

P0 P0 P0 P0 P0 P0 P0 P0 P3 P3 P3 P1 P1 P2

I wasn't able to figure this question out on my homework and I wasn't given the solution either. I wasn't sure if the time quantum would affect my scheduling or if I even am understanding the priority non-preemptive scheduling algorithm either.

# Answer
In non-preemptive scheduling the time quantum is not important for determining scheduling. The time quantum is only important when processes can preempt the CPU and 'cut' the line, such as in Round Robin scheduling. If you were given a time quantum for this problem I have a feeling it was stuck there to try to trip you up.

Your answer is correct though and it sounds like you understand the concept. Priority non-preemtptive scheduling can be visualized as a priority queue. If the queue is empty you can have the CPU, if not you get into line based on your priority and wait until whomever has the CPU releases it (on their own).
> 1 votes

---
Tags: process-scheduling
---


# Question
Title: Linear programming, Checking a constraint based on condition
I have a constraint $X \ge Y$ in a Linear programming formulation, where both $X$ and $Y$ are binary. I want to check this constraint on a condition like:

```
if (Y==1)
      then check the constraint
else
      Don't care about the constraint

```

How to do it.

# Answer
> 2 votes
If $X$ and $Y$ are zero-or-one (binary) integer variables, then this is encoded as

$$X \ge Y.$$

Why does this work? If $Y=1$, then this enforces the constraint $X \ge Y$, as you wanted. If $Y=0$, this enforces the constraint $X \ge 0$, i.e., it doesn't impose any rstrictions on $X$, which is also as you wanted.

In general, conditional constraints can be handled using the techniques found on page 7 of AIMMS Modeling Guide - Integer Programming Tricks, which is a helpful tutorial on how to encode constraints in integer programming. Thanks to @adrianN for pointing to that resource.

You can also take a look at https://cs.stackexchange.com/a/12118/755 and at Formulating Integer Linear Programs: A Rogues' Gallery for other techniques and practice problems.

---
Tags: linear-programming, integer-programming
---


# Question
Title: Are there algorithms for which we cannot determine if they ever halt?
My understanding of the halting problem in layman's terms is that there is no algorithm which will accept an arbitrary program as input and return true if it halts and false if it does not.

For a Turing machine does the question, "Does this Turing machine halt for all inputs?" always have an answer in the first place?

E.g. the algorithm "If this machine halts, then loop. Otherwise halt." seems to suggest that the answer is no. Is there something wrong with this example? Is there a canonical example?

# Answer
> 0 votes
As you point out, the general problem of deciding if a TM stops on any given initial tape content is undecidable. In this answer I'll assume you are talking about the concrete existence (to the point of being possible to indicate, not just demonstrate) of one such machine.

As it happens, the (hypothetical) problem of deciding if a *particular* TM always halts gets arbitrarily complex as the machines themselves get more complex. It is quite impressive how problems involving even very small machines exist that defy our current understanding. It is possible to conjecture that, for any given limited set of resources, there will be some relatively small machine that is "out of reach", whose behaviour is impossible for us to determine.

Your formula does not add significantly to this idealized scenario.

---
Tags: computability, halting-problem
---


# Question
Title: How these two Turing machine problems are different in terms of their decidability?
I was referring to slide 4 of this, which states following:

> It is decidable whether a given CFG accepts a non-empty language?

Then I was reading Intro to Automata theory book by Ullman et al. It states following:

> Let $L\_{ne}$ be the language of all codes for Turing machines that accept atleast one input string. $$L\_{ne}=\\{M | L(M)\neq \phi\\}$$ $L\_{ne}$ is not recursive.

Knowing that "not recursive" is same as "undecidable" and the functionality of Turing machine is expressed as a CFG, I feel that the problems in above two statements sound same and the statements contradicts each other in terms of their decidability claims. Thus, one of them must be wrong. However I also feel that I still miss something basic and both of them are non contradictory and equally true. But then what I miss?

# Answer
> 3 votes
The thing you missed is that Turing Machines are strictly more expressive than Context-Free Grammars. CFGs are as expressive as push-down automata (PDA, i.e. automata with one stack).

E.g. the language $L = \\{a^nb^nc^n | n \> 0\\}$ cannot be expressed by CFG (or decided by a PDA), but can be decided by a Turing Machine.

So, for CFG, the emptiness problem is decidable, but somewhere on the way to Turing completeness, this property is lost.

# Answer
> 1 votes
The solution is a bit subtle. Wikipedia says the following:

> A CFG can be constructed that generates all strings that are not accepting computation histories for a particular Turing machine on a particular input

That means you can reduce the halting problem to the problem, *"Does this CFG generate all strings?"*, but not necessarily to the problem *"Does this CFG generate the empty language?"*.

---
Tags: turing-machines, context-free, automata
---


title: How to count in binary? (basic problem)

text:
# Question
Title: How to count in binary? (basic problem)
I am trying to learn the binary number system but I keep coming up against a barrier to my comprehension. To people who are in the know this will no doubt seem an extremely elementary error so please be kind :). The problem concerns the eighth count. I’m going to explain my reasoning up to that point alongside the counting record in the hope that my error can be pinpointed. Apologies for being long-winded. Here goes…

1. First count to **1** (from 0)
2. We want to continue but have run out of digits. Therefore mark the first count with a digit on the left and begin counting from 0 again. Thus: **10** (This shows that the count is accumulative and not simply a repeat of (1) and is analogous to starting the tens column in decimal place value.)
3. Simply count forward in the right column, "carrying" the 1 from the previous count to indicate place value. Thus: **11**.
4. Repeat the procedure at (2), getting the original 1 to budge up and put a zero to the left to show place value. Thus: **100**.
5. Count forward, thus: **101**.
6. Repeat as per (2) and (4). We now have two left columns with 1s as their value and a fresh 0 in the right column, thus **110**.
7. Simply count forward in the right column as per (1), (3), (5), thus: **111**.

Right, the next stage \[(8)\] is what baffles me. I know that the next number is **1001** but I don’t understand why. Surely if we are following the pattern I have outlined above (and, assuming this is correct) the next number should be **1101**, i.e we start a new column as we did when faced with 1 on the right side at (2), (4) and (6). Instead it seems to be that when we max out on 1s (i.e. 111) we have to reset several columns at once. Why am I wrong? I know it will most likely have to do with 2 being the exponent for binary numbers but I can’t make the connection and all web explanations are overly complex. Any help gratefully received.

# Answer
> 1 votes
I don't really understand the algorithm you're trying to use to count. It seems rather complicated and, instead of trying to correct it, I'm just going to start from scratch.

Really, everything is just like decimal, only there are fewer choices for each digit. Just like decimal, leading zeroes don't alter the value of the number (0123 is the same number as 123 and 0000123) so we can always add leading zeroes if that helps us.

To add 1 in decimal, we just increase the last digit by 1, if it's not already the biggest possible value. If it is the biggest possible value, we replace it with 0 and "carry 1" to the second-to-last digit. What does that mean? Well, it just means that we increase that digit if we can and, if we can't, we reset it to 0 and carry the 1 to the previous digit. Eventually, if we started with something like 999, we'll have to say that 999 is the same thing as 0999 when we need to the 1 past the left-most 9

So, to add 1 in binary, we increase the last digit by 1, if it's not already the biggest possible value, which is 1. If the last digit is 1, we reset it to zero and "carry the 1", which we do just like we did before.

This means that it goes as follows:

* 0
* 1 (Increase the last digit)
* 10 (We can't increase the last digit, so we reset it to zero and carry the 1. We've run out of digits, so we put a new zero on the left. Then, to carry the 1, we add 1 to that new digit.)
* 11 (Increase the last digit)
* 100 (Reset the last digit to zero, carry the 1. Reset the second-to-last digit to zero, carry the 1. No digits remain, so put a new zero on the left and carry the 1 to it.)

Perhaps it was overly complicated to say that we put a zero on the left-end of the number and then increase it; I could have just said that we put a one on the left end and we're done. I used the slightly longer formulation because you can keep using that when you start adding numbers bigger than one.

# Answer
> 0 votes
Let's slow down. It seems like you're trying to do addition with binary? Let's understand how numbers are represented normally with base 10.

For instance, let's deconstruct a number like 812. 812 = 8(10^2) + 1(10^1) + 2(10^0)

Notice a pattern here?

Let's deconstruct a number like 7 in binary. 7 is written as 111. 7 = 1(2^2) + 1(2^1) + 1(2^0)

Just for emphasis, 6 is 110 or 1(2^2) + 1(2^1) + 0(2^0).

Now back to your example. If we wanted to add two numbers, say 7 and 6, we do the same as if it was base 10.

`111
 110
-equal sign-
 1101` Remember, binary cannot have a digit whose value is greater than 1, so we have to carry the 1.

---
Tags: arithmetic
---


# Question
Title: Equivalent DPDA that always halts for every DPDA with empty stack language
I want to show that for every deterministic pushdown automaton with the language of the empty stack there is a deterministic pushdown automaton that always halts. my transition function of $P$ is

$\delta: \Gamma \times Q \times \Sigma\_\lambda \to \Gamma^\* \times Q$

I tried to use look ahead pushdown method. I think I should create a $DFA$ for every $q \in Q$ that recognize if $P$ is in the lambda-cycle starting from $q$ with input string reversing of containing the stack of $P$. I define NFA with states of set $\Gamma \times Q$ and it has transition from $(\alpha,p)$ to $(\alpha',p')$ reading $\beta$ if there is $(\beta\alpha',p') \in \delta(\alpha,p,\lambda)$ and start state is $(Z\_0,q)$ and I think every state should be final state. then reverse $NFA$ and convert it to $DFA$. I don't know this works or not. I after that I can create $DPDA$ named $P'$ such that its stack simulate all $DFAs$ and also original stack of $P$ and after that I can decide if $P$ will be in the loop in future so in $P'$ it halts.

how can I edit creating $DFA$ that works well?

---

**Edit**

I changed the way using above automata, first of all, I design $DFA$ to check if in future there is a sequence of lambda-transitions that empties stack? if there is so I should let process continues because it will stop in future. $NFA$ is like above example with final states in $(\lambda,q)$ for each $q\in Q$ and simply we can convert $NFA$ to $DFA$, if there is not such sequence I ask another question, is it possible that we have some non-lambda transition? checking this is also simple we create exactly same $NFA$ as above $NFA$ and after that, if in a state we have non-lambda transition we go to a special final state. if there is no such transition it means we will stock on loop in future.

# Answer
The look-ahead property for pushdown automata is that a PDA $Z$ can answer certain questions of the form "how would PDA $X$ behave when given *my* stack", and then make moves based on that information. In particular, also deterministic PDA $Z$ can use this even when $X$ is nondeterministic.

You know, as I understand from the formulation of your question, this is possible because the property "when started on stack $\alpha$ PDA $X$ empties its stack" defines a regular set of stacks. The PDA look-ahead test can then be build in the original PDA.

So, to solve your problem, you have to formulate *which* PDA tests you would like to perform on the stack in order to avoid infinite computations.

I do not know whether it is necessary to actually construct the regular language of stacks that gives a positive answer.
> 3 votes

---
Tags: automata, pushdown-automata, simulation
---


# Question
Title: Selecting best crew combination that meets requirements of a variety of jobs
I am developing an application, which performs combinatorial function as described below. Could anyone point out a suitable algorithm (or direction)?

== Basic scheme: ==

There are fixed amount of *slots* (say air tickets), a few hundreds of workers, and a few dozens of jobs. Every time, a bunch of workers (the "crew") are sent to complete jobs. The number of workers sent are determined by the available slots. The crew must finish all appointed jobs by themselves.

Each job requires a combination of *skills* that were possessed by workers. Besides skills, some jobs may optionally require the worker to possess certain *ability*. Further, some of those jobs with *ability* requirements imposed as must-have.

Example:

1. A worker, possesses the *skill* "software engineering", but lacks "maths" *ability*;
2. There are 3 jobs that require "software engineering" skill;
3. *Job A* is a simple programming job;
4. *Job B* is a programming job involves basic "maths" processing, but since it's basic processing, "maths" *ability* is optional;
5. *Job C* is a programming job involves advance "maths" processing, so the "maths" *ability* is a must.

We say:

1. The worker fulfills *Job A*.
2. The worker fulfills *Job B*, but not the best candidate. Any worker possess "software engineering" *skill* and "maths" *ability* is better candidate to the job;
3. The worker cannot fulfill *Job C*, due to lack of "maths" *ability*.

On the server, calculation is done every night (or twice daily), to find out the best combination of workers to sent out:

1. Can finish all jobs;
2. No more than the available slots;
3. (Optional) With least head count.
4. (Optional) A crew list with highest rating;
5. (Optional) Best score to head count ratio;
6. (Optional) The algorithm should be portable to mobile platform.

== Update 2 ==

TL;DR;

The available slots is a constraint (relatively speaking, a constant), which confines the crew size we can sent out. After receiving a contract, the number of workers we'll be sending out is determined, hence the slot constraint. Theoretically, sending out less worker would be more profitable, and exceeding that may be an out-of-budget alarm.

The words "skill" and "ability" are similar in common concept. But they are two sets of factors to account for in this specific application, separately. These two words are actually come from the up-stream system, which generates the base data set. Maybe it's better put them as: "skill" could be accountants, programmers, etc. While "ability" could be "maths" as accountant & programmers both could possess maths ability; or "graphic" could be an ability of programmer who is making computer software like photo editors. These are well defined in the up-stream system.

While working on the program, before reaching this "combinatorial" portion, we have done some extra work on job & worker classifications. During job & worker classification, a few information is calculated and stored, and will be transferred to mobile device:

1. Lists of suitable worker to each job are generated, and attached to job records;
2. Each worker is given a "score", which is:
    * the total number of jobs he/she can finish;
    * plus the total number of jobs with optional ability requirements he/she can finish;
    * plus the total number of jobs with must-have ability requirements he/she can finish.

At the time of computation, no worker is actually occupied. The contract consists of various jobs, unique and/or repetitive. How to assign workers to jobs is left to the on-site manager's decision. So any worker could be assigned multiple jobs during the contract period, and is out of this application's scope. We just provide a team of workers that is capable of finishing all jobs.

== Update ==

I'm planning to do this the "brute force" way on the server, due to its limited probabilities. However, this process will be moved to mobile (phones, etc.) platforms eventually, since worker availability may change in reality. It seems performing such computation on mobile platform is not feasible.

It seems to me not a knack-sack problem, nor a linear problem. I can't find a way to place variable worker & job constraints to the formulas.

With this question, I'm hoping to have some better options that can come out with the result with as few iterations as possible.

---

So, as we enter this function, there will be a few constants & variables:

let $U$ to be all of our available workers;

let $Z$ to be the constant of the maximum crew size (*slot*);

let $V\_{w}$ to be the *score* of each worker, could be used as *weight*;

let $L\_{j}$ to be the *list* of suitable workers to a job, which in turn are subsets of our available workers, where $L\_{j} \in U$

# Answer
One strategy would be to formulate this as a mixed integer linear programming problem, and solve it with an off-the-shelf ILP solver.

You can create a zero-or-one variable $x\_{i,j}$ that indicates whether worker $i$ is assigned to job $j$. The requirement that job $j$ requires at least one worker with some skill can be expressed as the linear inequality $\sum\_{i \in S} x\_{i,j} \ge 1$ where $S$ is the set of workers with that skill. If the job requires multiple skills, then you can add multiple linear inequalities. Also, add the inequalities $\sum\_j x\_{i,j} \le 1$ (each worker is assigned to at most one job). You can minimize the head count by minimizing $h = \sum\_{i,j} x\_{i,j}$. You can take into account the "slots" constraint like this: if you want to send at most $m\_j$ people to job $j$, then add the inequality $\sum\_i x\_{i,j} \le m\_j$. Then, feed this entire linear program to an off-the-shelf ILP solver.

If you want to search for a solution with the best score to head count ratio, you can use the following technique. Let $s$ denote the total score; note that this is a linear function of the $x\_{i,j}$'s, namely $s = \sum\_{i,j} s\_i x\_{i,j}$ where $s\_i$ represent worker $i$'s score. Let $r$ denote the score to head count ratio you want to achieve; let's treat $r$ as a constant, and our goal is to see whether ratio $r$ is achievable. Then we can add the linear inequality $s \ge hr$ and see whether the resulting linear program is solvable, and then either increase or decrease $r$ accordingly. Finally, use binary search on $r$ to find the largest ratio $r$ such that the resulting linear program is feasible.

While ILP is intractable in general (in the worst case), for the size of problem you have, it's possible that existing ILP solvers might be able to find reasonably good solutions. At least, I expect this will be superior to brute force.

I don't really understand twhat is meant by the rating of a crew, so you'll have to figure out whether that can be represented them in an ILP -- I don't know how to help you there.

Your problem is related to the assignment problem, but with additional restrictions, so I don't expect the literature on that problem to necessarily be of any assistance to you.
> 1 votes

# Answer
**UPDATE**

I haven't figured out other options to this problem. So I've broken up the process to offline mobile computations.

First, I've done everything on the server. Calculating all fundamental statistics, and work out a basic solution to the allocation.

Then all those results are pushed to mobile devices. When the basic solution doesn't fit the final requirement, mobile devices use the stats data from server to work out a final solution.

\** Original \**

Please allow me to address the set cover problem approach in a new answer, so the question won't introduce more confusions. I would update this answer as I venture through this path.

And first, I have to explain myself a bit more. I've deserted maths for a decade more (not intentionally though). So my maths ability drops to every-day-maths capable. I'm picking stuffs up as I progress.

It seems I have made a wrong choice regarding $L\_{j}$. As my goal is to select crew that can fulfill all jobs, $L\_{j}$ won't help here. Instead list of doable jobs per worker should be the one to get.

$U \leftarrow$ all jobs

$W \leftarrow$ all workers

$L\_w \leftarrow$ jobs can be done by worker $w$ (where $w \in W$ and $L\_w \in U$)

Grep the set cover ILP from wiki: $$ \mathrm{minimize} \sum\_{j \in L\_w} x\_j $$

for all $e \in U$ $$ \sum\_{j\_{:e} \in L\_w} x\_j \ge 1 $$

for all $j \in L\_w$ $$ x\_j \in \\{0,1\\} $$

now we have the combination of workers (first part solved), correct?

---

Below stuffs were turned out unused.

$Z \leftarrow$ slots

$n\_u = |U|$

$u\_j \in U$ (where $1 \le j \le n\_u$)

$n\_w = |W|$

$w\_i \in W$ (where $1 \le i \le n\_w$)

$S \leftarrow$ all skills & abilities

$s\_j \leftarrow$ job $j$ skills, $s\_j \in S$ (where $1 \le j \le n\_u$)

$S' \in S$ (all skills used in jobs) where: $$ S' = \bigcup\_{j=1}^{n\_u} s\_j $$

$s\_i \leftarrow$ worker $i$ skills, $s\_i \in S' \in S$ (where $1 \le i \le n\_w$)

$L\_j \leftarrow$ suitable workers to job $j$ (where $j \in U$)

$v\_i \leftarrow$ worker $i$ score
> 0 votes

---
Tags: algorithms, optimization, assignment-problem
---


title: Is this simple problem NP-complete?

text:
# Question
Title: Is this simple problem NP-complete?
**Candy Allocation Problem:** Suppose there are $n$ candies, each with a weight $w\_i$ gram. There are $m$ kids, and each kid needs to eat at least $\omega$ grams of candies to be full. Candies cannot be cut into pieces. Is there a candy allocation algorithm such that at least $k$ kids can be full?

Is the above problem NP-complete? It has some similarity to knapsack, but not exactly the same. Can someone help me?

# Answer
> 1 votes
First, we prove that the decision version of the original problem is NP. Since an instance of an assignment can be verified within polynomial time, it's obviously NP.

Now, we try to prove the NP-hardness of the problem. Well, I believe this problem can be reduced from the **bin-packing problem**.

The bin-packing problem says the following: There are $n$ items each with a weight $w\_i$ and $m$ bins. We want to put the items to bins. Each bin has a maximum weight limit $\omega$. The problem is to find a item assignment scheme so as to minimize the number of bins needed. Mathematically: $$\textrm{minimize}~~~ z = \sum\_{j=1}^m y\_j$$ Subject to: $$\sum\_{i=1}^n w\_i x\_{i,j} \leq \omega y\_j, \forall j \in \\{1,2,\cdots,m\\}$$ $$\sum\_{j=1}^m x\_{i,j} = 1, \forall i \in \\{1,2,\cdots,n\\}$$ $$y\_j \in \\{0,1\\}, \forall j$$ $$x\_{i,j} \in \\{0,1\\}, \forall i, \forall j$$ The problem is NP-hard, and its NP-hardness has already been proved. The decision version of this problem is NP-complete.

Note that in the candy allocation problem, we tend to maximize the number of kids that are completely full. Since the number of kids are the same, the problem is equivalent to minimizing the number of kids that are not full, while ensuring every candy is allocated. The problem is formalized as follow: $$\textrm{minimize}~~~ \sum\_{j=1}^m y\_j$$ Subject to: $$\sum\_{i=1}^n x\_{i,j}w\_i \leq \omega y\_j, \forall j \in \\{1,\cdots,m\\}$$ $$\sum\_{j=1}^m x\_{i,j}=1 ,\forall i \in \\{1,\cdots,n\\}$$ $$x\_{i,j} \in \\{0,1\\}, \forall i, \forall j$$ $$y\_j \in \\{0,1\\}, \forall j$$ where $y\_j$ denotes if kid $j$ is hungry ("1" is hungry, "0" is full), and $x\_{i,j}$ denotes if candy $i$ is allocated to kid $j$.

One can easily see that the problem is equivalently to the bin packing problem. Thus, candy allocation is NP-hard.

Since candy allocation is NP and NP-hard, it's NPC.

The definition of bin packing problem can also be found in https://en.wikipedia.org/wiki/Bin\_packing\_problem.

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


# Question
Title: Pushdown automaton accepting $\{a,b\}^*$ with twice as many $a$s as $b$s
Design a pushdown automaton that can accept

> $$\\{w|w\in\\{a,b\\}^\*\text{ and $w$ has twice as many $a$s as $b$s}\\} \\, .$$

I have a solution as the following. The notation seems to follow "An Introduction to Formal Languages and Automaton" by Peter Linz, where $\delta$ is the transition function with three arguments: current state, input, current stack top; $\lambda$ as the second argument of $\delta$ means empty string $\epsilon$ in some other textbooks, and $\lambda$ as the third argument of $\delta$ means the transition ignores the current stack top. The $\lambda$ on the right hand side means "pop the top element of the stack".

I have several confusions,

1) I am **not sure what the right-hand side notation means**. For example, does the right hand side of $\delta(q\_1,a,A)=\\{\[q\_2，A\]\\}$ means pushing an $A$ into the stack? Or it means the stack top stays $A$ without a new $A$ pushed to it?

If this means "push", then what about $\delta(q\_1,a,C)=\\{\[q\_2，C\]\\}$? $C$ seems to mark the bottom of the stack. We push another $C$ to the stack when there is already a $C$ in it?

2) I think the solution might be wrong. **I don't see why it accepts $aab$**. Tracing this string, I think the transition is the following based on the design (if the big letter at the right-hand side means pushing a new symbol),

$q\_0,\lambda \to\_\lambda q\_1,C\to\_a q\_2,CC \to\_\lambda q\_1,ACC \to\_a q\_2,AACC \to\_\lambda q\_1,AAACC \to\_b q\_1,AACC$

It is very strange and I feel very confused. Hope someone can help! Thank you!

# Answer
When in doubt, one should always consult the definitions.

In this case, this is Definition 7.1 of the book by Peter Linz.

It states that $$\delta : Q \times (\Sigma \cup \\{ \lambda \\}) \times \Gamma \rightarrow \textrm{finite subsets of } Q \times \Gamma^\*$$ Thus, $\delta(q,a,A) = \\{\[q\_1,w\_1\], \ldots, \[q\_k,w\_k\\}$ means that when a pushdown automaton is in state $q$ and sees an $a$ on input (where $a$ may be an input or the empty string $\lambda$), then it can enter any one of the states $q\_1$ to $q\_k$ and *replace* $A$ by the corresponding string of stack symbols $w\_i$.

Therefore, a pushdown automaton can push a string $w$ to the stack by reading $\lambda$ and replacing it by $w$. Or it can pop the top symbol $b$ by seeing $b$ on the stack and replacing it by $\lambda$.
> 3 votes

---
Tags: formal-languages, automata
---


# Question
Title: Prove this langage isn't regular using the pumping lemma
How can I prove that this language isn't regular using the pumping lemma for regular language?

$$L = \\{a^nb^m| n,m \> 0, \gcd(n,m)=1\\}$$

I've already checked this answer: Proof that a language involving $gcd$ is not context-free but don't understand this part.

"Let s' be $a^{(n+ik)}b^m \ with \ k \geq 1$. Then s' e L if $gcd(n + ik, m) =$ , however the modular equation $n+ik = 0(m)$ have a solution $i = nk^{(-1)(m)}$ ..."

I don't understand how he proved, $gcd(n+ik, m) \gt 1$, could someone explain me more clearly the answer please.

Thank you.

# Answer
> 3 votes
As you know, the Pumping Lemma for regular languages states that if $L$ is a regular language, then there is an integer $p$ such that is $s$ is any string in $L$ with length $|s|\ge p$ then we can write $s=xyz$ with

1. $|y|\>0$,
2. $|xy|\le p$, and
3. $xy^iz\in L$ for all $i\ge 0$.

If we let $s=a^nb^m$ for distinct primes $n,m\ge p$ then certainly $s\in L$ since $\gcd(n,m)=1$. Now we know that in this case $y=a^k$ with $0\<k\le p$ and so if we pump $y$ we'll have $xy^{i+1}z=a^{n+ik}b^m$. Now we'll try to get a contradiction by showing that there is some $i$ for which $\gcd(n+ik,m)\ne 1$. We can get this if we can find an $i$ such that $m$ divides $n+ik$, since then we'll have $\gcd(n+ik,m)=m$.

In other words, we want an $i$ such that $n+ik\equiv 0\pmod m$. In modular arithmetic land we'll then have the following chain of equivalences:

$$\begin{align} n+ik &\equiv 0\pmod m\\ ik &\equiv -n\pmod m\\ i &\equiv -n(k^{-1})\pmod m \end{align}$$ The last step follows from the fact that when the modulus is prime, any nonzero value has a multiplicative inverse.

Here's an example: Suppose $p=6$, then we could pick $n=11,m=7$ and pump the string $a^{11}b^7\in L$. If it happened that $k=4$ then we could use $i=-11\cdot 2$, where the $2$ came from the fact that $4\cdot 2\equiv 1\pmod 7$. In other words, we'd have

$$ i=-11\cdot 2\equiv -22\equiv -1\equiv 6\pmod 7 $$ and then the pumped string would be $a^{11+6\cdot 4}b^7=a^{35}b^7$ and this is clearly not in $L$, since $\gcd(35,7)=7\ne 1$ $$ $$

# Answer
> 2 votes
An easy way to prove that this language isn't regular is using the Myhill–Nerode theorem. Let $p\_i$ be an enumeration of all primes. The words $a^{p\_i}$ are pairwise inequivalent, since $a^{p\_i} b^{p\_i} \notin L$ whereas $a^{p\_j} b^{p\_i} \in L$ when $i \neq j$. Since we found infinitely many pairwise inequivalent words, it follows that $L$ is not regular.

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


# Question
Title: Is a unary language regular iff its exponent is a linear function?
While doing the current assignment for my formal languages and automata course, I kind of got stuck on exercises involving unary languages (I hope that's the right term), i.e., languages which build upon a single letter. I don't want to ask about the specific exercises, though, but rather about a much more general conjecture I've come up with:

Let $\Sigma=\\{a\\}$ and $L=\\{a^{f(n)}\in\Sigma^\*:n\in\mathbb N\_0\\}$. My conjecture is:
$$L\text{ is regular}\Leftrightarrow \exists x,y\in\mathbb N\_0:f(n)=x\cdot n+y$$

**Has this question seen any scientific treatment before? Is it "obviously" true / false?**

To me, obviously the "$\Leftarrow$" direction is true because one can just construct a DFA with $x+y$ states that cycles through the $x$ states after having read through $y$ states and accepts iff it is at state number $y$.

# Answer
> 10 votes
Linear is close, but the technical term you're looking for is *semilinear:*, that is, a finite union of linear sets.

Half of the proof of this is a corollary of Parikh's Theorem, which says that any context-free language has a semi-linear Parikh map (that is, the set of vectors containing the occurrences of each letter in the alphabet).

For a unary language, the parikh map of the language is the language itself (i.e. each word is uniquely identified by how many letters it has), so every unary regular language is semi-linear.

The other half of the proof is showing that you can construct a regular language containing every unary semi-linear set. This takes a bit of work, but it's not too hard if you use regular expressions:

* $a^k$ recognizes the language $\\{ k \\}$
* $(a^k)^\*$ recognizes $\\{xk \mid x \in \mathbb{N}\_0 \\}$
* $R\_1 R\_2$ recognizes $S\_1 + S\_2$ if $R\_1$ recognizes $S\_1$ and $R\_2$ recognizes $S\_2$, where $+$ here is element-wise addition
* $R\_1 | R\_2$ recognizes $S\_1 \cup S\_2$ if $R\_1$ recognizes $S\_1$ and $R\_2$ recognizes $S\_2$, where $|$ here is regular-expression union.

# Answer
> 6 votes
You're almost correct. You need to consider the fact that you might have several linear functions, like $$ L=\\{a^k\mid k=3n+1\text{ or }k=7n+4\\} $$ or you might have finite languages, like $$ L=\\{a^k\mid k=4n+2\text{ or }k=13\\} $$ (In both cases, we're just taking the union of regular languages, so things work as they should.)

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


# Question
Title: How to compare an experimental study with amortized times
I have an implementation of a data structure I have to study for a group project (Fibonacci heaps if you're interested). I'm asked to compare the theoretical results of the operations in amortized time, with the running times of my implementation. Now my question: since amortized times are based on the fact that we look not just at a single operation, but at a series of operations, what can I do with my implementation to receive some experimental results that support (or not) my theoretical analysis?

# Answer
If you want to compare theory and experiment, you have to perform both analyses under the same assumptions.

Note that this includes what you measure. Since you did not analyse *time* in theory, there is little sense in measuring running times in the experiments. Use combinatoric measures you can count reliably and independently of the system and its load.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, heaps, amortized-analysis, experimental-analysis
---


title: What is a file?

text:
# Question
Title: What is a file?
I'm looking for a **formal** definition of file that does not only include storage but also abstractions like procfs or /dev/null (or any fuse-based file) that do not relate to storage.

So far I know that all files are abstractions that

* can be identified
* can have names (usually organized in hierarchical structures)
* can be accessed as a byte stream
* usually provide permissions and other (system specific) metadata

however I was unable to find any useful formal definition in any OS book I've read so far.

# Answer
According to Wikipedia, a computer file is simply a **resource** for storing information. The term appears to have originated in the punch card era, where a computer program was literally stored in a file (as in, a box used to store loose pages, see image below). As other forms of media were introduced, such as disks, the nomenclature followed.

From a \*nix point of view, everything is a file: sockets, devices, terminals, screens/monitors, data files, pipes, and so on. Microsoft Windows, in contrast, tends to call permanent storage data "files", and volatile resources as whatever they are, such as named pipes, sockets, raster devices, etc. Other systems may have similar definitions somewhere between these two extremes.

Unfortunately, as I've just stated, there's no single definition of what a file is, because it is different things to different people, except that everyone tends to agree on the base-line definition that a file is a *named resource that stores data on permanent media* (permanent does not imply that it can never be modified, simply that it persists through power cycles).

(Wikipedia)
> 6 votes

# Answer
I think of a file as a sequence of bytes. Even after it loses its name (usually caused by a call to rm, which unlinks it), it still exists on the disk until its chunks get overwritten by other stuff. File formats are contexts for reading files. It all goes back to the principle that information is bytes plus context.

The previous poster is right that devices, whilst being treated as files, are not really files. This is a very useful hack.

So my definition of a file: a sequence of bytes stored in memory.
> 2 votes

---
Tags: operating-systems, os-kernel, filesystems
---


title: When does a PDA halt?

text:
# Question
Title: When does a PDA halt?
In DFA/NFA the automaton halts when it finishes reading the string.

In a PDA there's the string and the stack. When the string is finished and there are symbols on the stack does it ignore them? Or does it have to pop them?

Or maybe does the behavior depend on whether the PDA is deterministic or not?

---

Here's an example to demonstrate where the ambiguity is.

It's a dumb example and it can be done with a DFA but just for demonstration.

This PDA should accept anything but the string `aa`.

It starts by inserting a `$` to mark the bottom of the stack. Then it inserts 2 `a`s. Then when it receives an a it pops one from a stack. It can do that twice.

Now at this point suppose that the input string was indeed `aa`, **and** that the machine reached state `x` and popped the two `a`s. Now the stack has only `$` in it.

* Does it have to go to the next state (`y`) because there's a `$` on top of the stack?
* Or by non-determinism can it be either in `x` or in `y`?

If the latter is true then this is a wrong PDA for this language. It would accept everything.

# Answer
> 4 votes
The setup places $aa\\$$ on the stack and puts the machine in state $x$. We then have this sequence of moves on input $aa$:

1. Consume the first $a$ and pop the stack. We're then still in state $x$ with stack contents $a\\$$. No other move is possible.
2. Consume the next $a$ and pop the stack. We're then still in state $x$ with stack contents $\\$$. No other move is possible.
3. Seeing a $\\$$ on the stack, the only possible move is to pop the $\\$$ and pass to state $y$.
4. In state $y$ with no further input, there are no possible moves, so the machine halts, in a non-accepting state.

Notice that there's no nondeterminism here: perhaps you were mistaken in your first bullet point: indeed there is a $\\$$ **in** the stack at move (1), but it's not on the **top** of the stack.

The deeper question is exactly what model of a PDA is being used here: some people allow multiple accept states and say that the PDA accepts a string if it is in an accept state when the input has been completely consumed, others require that the stack be empty when the input has been consumed; some require a single accept state, some don't. All these models are equivalent, but you need to look closely at the definition you are using.

# Answer
> 4 votes
Indeed, with $\epsilon$-moves there is some problem with acceptance for PDA even when they are deterministic.

The input of a PDA is accepted when the input is completely read and the chosen acceptance condition is met. This acceptance condition is either reaching a final state or reaching the empty stack. However, immediately after reading the last symbol of the input it might be possible to continue with $\epsilon$-moves on the input. Thus, we might reach a final state later, or move from a final state to a non-final state. This does not matter only the possibility to enter such a state matters.

To be precise, "halting" is not required, only the possibility of reaching the acceptance condition. Whatever is possible later does not count. In some 'theoretical' constructions this might be a problem: even for deterministic machines we cannot check the first state entered after reading the input. In fact the computation might accept when at the same time it is possible to run off in an infinite run of $\epsilon$-moves.

In classic definitions it is not possible to make moves on the empty stack, transitions are always required to make one pop. In your case you do allow transitions with empty stack. This *does* change the class of languages accepted by deterministic PDA, since in the classic definition those are 'prefix-free': after accepting one is in the empty stack, and no further symbols can be read.

---
Tags: automata, pushdown-automata
---


# Question
Title: Claimed problems with Lisp dynamic scoping
What would be the problem of running the following scala codes assuming we are working with dynamic scoping and a global stack to store environments as some variants of Lisp do?

```
def fact(n:Int,f:() => Int):Int =
 if(n == 0) f()
 else fact(n-1,() => n*f())
fact(7,() => 1)

def incrementer(x:Int)  = y => y+x
incrementer(2)(3)

```

# Answer
> 2 votes
With `fact`, the primary problem is with `f`. If `n` is `0`, then it works fine. However, for any other value of `n`, `fact` is called with an `f` of `() => n * f()`. So when the base case (`n = 0`) is finally encountered, `f` is `() => n * f()`. When `f` is invoked, `f` is still `() => n * f()`. So the call to `f` results in unbounded recursion with itself.

With `incrementer`, `x` will be not be defined when `y => x + y` is called in your example. This is because `y => x + y` does not close over `x` (because of dynamic, as opposed to lexical, binding), there is no call on the stack that binds `x` to a value when the closure is invoked, and there is no global / top-level binding for `x`.

---
Tags: stacks, variable-binding, lisp
---


# Question
Title: Extracting Boolean Function using Machine Learning
**How can machine learning help extract a Boolean relationship in a given binary input-output data set?**

Let us assume that the given data set is exhaustive - ie. it cover all possible input combinations, can we derive the boolean relationship between inputs and outputs? *(Say we assume x inputs and 1 output)*

Further, if the dataset is not exhaustive, can we predict the output for "(n+1)"th input vector if we know outputs for the previous "n" input vectors? *(in other words, can we "learn" how the function behaves?)*

**I'd greatly appreciate if you can share what approach should I devise to work on this problem, and if possible, about any on-going research on this topic?**

---

**UPDATE:** *As rightly pointed out by @D.W.* Several heuristics exist to tackle such NP-hard problems in logic synthesis and minimization.

The essence of my question is to find out if any Machine Learning algorithm can be adopted and developed, which *potentially* performs better than the currently known heuristics when deployed at scale.

And importantly, if any "recent" advances in ML can be of help in developing tools for Electronic Design Automation?

# Answer
> 1 votes
If you have an exhaustive list of all possible inputs, and the output for each, you already know the relationship between the input and output. You don't need fancy machine learning.

If you want to explicitly write a formula for this relationship, it is easy to write a DNF formula (each clause corresponds to a single input-output pair, i.e., a single row in the truth table). It's also easy to write a CNF formula, using a similar construction (each clause corresponds to a single input where the corresponding output is false).

If you want to find the *minimal-length* formula for this relationship, that is probably NP-hard (in fact it is "even harder" in some sense). However there are heuristics. Read about Karnaugh maps, Quine-McCluskey, the Espresso heuristic, and the fields of logic synthesis and circuit minimization.

---

I don't expect machine learning to perform better than existing methods. Existing methods have a lot of intelligence built in, based on this specific problem. ML methods wouldn't be able to benefit from any of that.

Ultimately, if you want to know whether some machine learning method performs better than standard methods, the only way to know for sure is to try it. But I don't expect it to yield useful results, without new insights.

---
Tags: machine-learning, artificial-intelligence, boolean-algebra, digital-circuits
---


# Question
Title: Extracting Randomness from Mouse Acceleration
I'm working on trying to make an "entropy pool" that will be fed as input into an RNG (as in, ex, Fortuna). In order to do so, I need to take various collected data and extract as much entropy as possible to turn it into unpredictable bits. I've read many papers about extracting randomness, but I haven't understood how to apply it to real-world data sources.

For example, as one entropy source, I'd like to use the position of the mouse cursor. After some simple experimentation, it seems like using the acceleration of the cursor (resulting in two streams of X acceleration and Y acceleration) is the best representation to use in that it reduces the sample range significantly. Running several min-entropy estimators on the acceleration data (separately for X and Y axis data), I get estimates of at worst 0.75 bits/sample of entropy (ignoring that the two streams are correlated). Beyond that, I'm not sure how to apply any published randomness extractor to this data.

Part of my problem stems from the fact that most entropy extractors talk about entropy rate, which I'm not sure how to calculate in this case. My samples are 8 bits each (signed byte), so that could make the entropy rate 0.75/8 ~= 0.09, which is far too low for most extractors. Another problem is that I have two correlated streams, and I can't remember any extractors that deal with that kind of input.

Any guidance or references on how to extract entropy from this data using any published randomness extractor would be greatly appreciated. I'm very interested in using a "real" randomness extractor and not the common "just hash it" approach.

---

I have a custom design that I can detail if desired. It essentially computes symbol statistics from the entire test capture (5 million samples) and uses range encoding to encode each symbol using those statistics. It results in about 1.5 bits/sample of output for each stream, and I'm not sure how well founded the idea is.

---

Edit: One of my end goals is to have a very large state RNG, suitable for being able to shuffle 200 card decks into every possible combination. 200! is ~1246 bits, so (for ex) using a typical PRNG-oriented implementation of AES-256-CTR would not suffice because it has too small a state to store that much entropy.

Also, as for using cryptographic hash functions, some of the early papers on extractors indicate that almost all functions are good extractors for high-entropy data, but I haven't seen any information about using them to reduce low-entropy data to shorter higher-entropy data (keep the entropy level, but reduce the total number of bits). If this is a mathematically valid use, I'd really like to see papers about it.

# Answer
Start by reading How to extract randomness from a file?.

At a broad level, it seems like you understand pretty well the techniques.

To extract randomness in practice, I recommend you use a cryptographic hash, and use techniques from the cryptographic literature for cryptographic building pseudorandom generators.

You mention "extractors". I know there's some cool theory surrounding them, but I don't recommend you use extractors. They are beautiful but not practical. Cryptographic hash functions are superior in practice.

You talked about estimating the amount of entropy in the data. Unfortunately entropy estimation is an inexact science. It's also easy to over-estimate the amount of entropy (e.g., if there are non-trivial correlations in the data that you didn't think to check for). So, a typical procedure that cryptographers often use is to make some estimate of the entropy rate (typically through a priori calculations), then divide by a factor of 4 or so to provide a safety margin -- and gather random values from many sources, and feed them all into the pool. The hope is that even if one source provides low-entropy data, or even if one of the entropy estimates is too optimistic, maybe some other source will have enough entropy in it to make up for the problem.

Overall, I recommend you spend some quality time in the cryptographic literature reading about the techniques that have been developed there. Cryptographers have spent a lot of time worrying and thinking about this, because cryptography relies upon high-quality random numbers. And, rather than re-inventing the wheel yourself, it's probably better to re-use some existing well-tested cryptographic method.

Here are a few pointers to get you started:

You can look around Crypto.SE and the resources mentioned there, and you'll probably be able to pick up a bunch about this topic. Have fun!
> 3 votes

---
Tags: reference-request, randomness, entropy
---


# Question
Title: Why is low-dimensional discrete representation of input space useful?
Self-organizing maps undergo unsupervised training to produce a low-dimensional, discrete representation of the input space. Why is this useful?

I think the results of the self-organizing map would have to be combined with some other machine learning algorithm or neural net in order to solve problems. Is this the case? If so, what algorithms or neural networks would benefit from being complemented with a self-organizing map? If not, what problems does the output of a self-organizing map solve?

# Answer
It may or may not be useful, depending upon the circumstances.

In some cases it can be useful as a visualization technique. The representation is low-dimensional, and often 2-dimensional -- which means it can be visualized. That said, there are many other methods of representing data in a low-dimensional space so it can be visualized, and it's not clear that self-organizing maps are the best way to do that.

Sometimes self-organizing maps are used as a general form of clustering, and can be useful anywhere that (unsupervised) clustering is useful.

That said, I agree with your general reaction. Often, self-organizing maps aren't very useful. I would not expect neural networks or other algorithms to benefit from being combined with self-organizing maps. Self-organizing maps don't really solve any clearly defined problem, and probably aren't of all that much use in many/most practical situations.

If you had never heard of self-organizing maps, you probably wouldn't be missing much (in my personal opinion).
> 1 votes

---
Tags: machine-learning, neural-networks
---


title: Memory needed for computational graph

text:
# Question
Title: Memory needed for computational graph
Suppose we have a set of equations like this

```
p7=f(p1+p6); p6=f(p2+p5); p5=f(p3+p4); p4=f(p3); p3=f(p2); p2=f(p1); p1=f()

```

It can be represented by computational graph below

If each intermediate value takes 1 unit of memory, you need at least 4 units to compute p7 without any duplicate computation.

Is there an algorithm for estimating memory needed in this setting for a general DAG?

I found a paper called "Adjoint Dataflow Analysis" for estimating this for restricted set of graphs, but it feels like this ought to be a problem that is covered more generally in graph theory.

# Answer
Your problem sounds similar to one-shot (black) pebbling. Wu, Austrin, Pitassi, and Liu, in their paper titled *Inapproximability of treewidth, one-shot pebbling, and related layout problems* (J. Artificial Intelligence Res. 49 (2014), 569–600), show that it is (probably) hard to compute the optimal cost (which corresponds to your memory).
> 4 votes

---
Tags: algorithm-analysis, space-analysis, data-flow-analysis, static-analysis
---


# Question
Title: Rice–Shapiro theorem in computation theory
I am trying to learn the Rice–Shapiro theorem on my own. Here is the theorem:

> Let $Γ$ be a set of computable functions such that the set $R\_Γ$ is recursively enumerable. We have $f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

I will appreciate if anybody helps me to make the theorem crystal clear. I just want to know what it really means and how I can use it to say that a set is not r.e., for example the set Empty or TOT.

# Answer
> 4 votes
Rice-Shapiro greatly helps in proving that a set is not RE, for some sets of the form $R\_\Gamma$.

E.g. take $A = \\{ n \ |\ {\sf dom}(\phi\_n) \mbox{ finite} \\}$. We have $A=R\_\Gamma$ with $\Gamma = \\{ \phi\_n | {\sf dom}(\phi\_n) \mbox{ finite} \\}$. If $A$ were RE, since e.g. the always undefined function belongs to $\Gamma$, then by Rice-Shapiro any recursive extension of that would be long to $\Gamma$ as well -- but this is false, since e.g. the identity function $\notin\Gamma$. Hence $A$ is not RE.

The above one is a typical use, where you reach a contradiction by extending a function inside $\Gamma$ to one recursive function outside.

We can also use it in the other direction: we reach a contradiction if we can take any function inside $\Gamma$ whose finite restrictions are all outside $\Gamma$. For instance, take $B = \\{n \ |\ \forall k\in\mathbb{N}.\ \phi\_n(2k)=5 \\}$. Clearly $B=R\_\Gamma$ with $\Gamma = \\{\phi\_n \ |\ \forall k\in\mathbb{N}.\ \phi\_n(2k)=5 \\}$. The function $f(x)=5$ is inside $\Gamma$, but any finite restriction of $f$ can not evaluate to $5$ on all even numbers, hence it must be found outside $\Gamma$. If $B$ were RE, by Rice-Shapiro one such restriction should instead be found inside $\Gamma$. We conclude that $B$ can not be RE.

I find Rice-Shapiro easier to use if I think about it as two separate results:

One is a *monotonicity* result, telling us that if $f \in \Gamma$ and $f \subseteq g$ with $g$ partial recursive, then $g \in \Gamma$. I.e. recursive extensions of functions in $\Gamma$ must belong to $\Gamma$ -- otherwise, $R\_\Gamma$ is not RE.

The other is a *compactness* result. For any function in $\Gamma$, there must be a finite restriction of it inside $\Gamma$ -- otherwise, $R\_\Gamma$ is not RE.

Many, many common examples of non-RE sets violate one of these two conditions, making it simple to prove they are not RE. For instance, consider $C = \\{n\ |\ \phi\_n(3)\neq 4 \land \phi\_n(5)=2 \\}$, where the notation $\phi\_n(3)\neq 4$ is meant to be true when $\phi\_n(3)$ is undefined. This immediately violates monotonicity, since I can always extend a (recursive) function which is undefined on $3$ so that it evaluates to $4$ on that point (and still get a recursive function). So $C$ is not RE.

# Answer
> 3 votes
The theorem says that any observation made about computable functions can be done by testing the values of the functions at finitely many arguments. In particular, acecss to the source code does not give you the ability to make more observations than what you get by trying out what the function does.

---
Tags: computability
---


title: Countably many oracle Turing machines?

text:
# Question
Title: Countably many oracle Turing machines?
In Sipser's text, when proving that there exists an oracle $A$ such that $P^A \ne NP^A$, he writes:

> Let $M\_1, M\_2, \ldots$ be a list of all polynomial time oracle TMs.

I understand that there are countably many Turing machines, but aren't there uncountably many oracles?

# Answer
There are $2^{\aleph\_0}$ possible oracles, but when fixing an oracle $A\subseteq \Sigma^\*$, there are only countably many Turing machines $M^A$ with access to the oracle $A$.

Remember that a Turing machine with access to some oracle is defined in the same manner as a normal Turing machine, but with an additional operation (they can query the oracle). They have a special tape on which they can write a query, and say, three additional special states $q\_{ask},q\_{yes},q\_{no}$. Upon entering $q\_{ask}$, if $s\in\Sigma^\*$ is the content of the query tape, the machine enters either $q\_{yes}/q\_{no}$, depending on whether or not $s\in A$.

Nothing stops us from encoding such machines as strings, in the same way we encode regular Turing machines, hence we only have countably many such machines.
> 3 votes

# Answer
There are uncountably many oracles.  However, those are sold separately:
The oracle Turing machine only comes with an interface for
interacting with whatever oracle one might choose to use it with.
> 0 votes

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


# Question
Title: Language Classification + AWS ML: what am I doing wrong?
I'm evaluating Amazon's machine learning platform, and thought that I would give it a "simple" classification problem first. As a disclaimer, I am quite new to machine learning (hence my interest in an ML platform).

The classification problem is language detection. Given a list of 20k words, and their language (`English, French, or Random`), train a model to classify new words.

My data is structured in CSV format, with 2 rows:

```
dàagzj, random
tunisia, english
craindre, french
voters, english
religions, english
condition, french
...

```

I imported the data successfully into the platform, and all seems fine.

When I attempt to run train a model (using both the default settings and tweaking them) I get the same result. English is selected as the language nearly 100% of the time.

I know this problem is possible to get reasonably accurate results with simple neural networks, however I'm not sure what is going wrong?

Do I need to perform any preprocessing operations on the text input, or is the plain string sufficient? What data can be collected about a single word that may be a more effective input to a machine learning model?

# Answer
> 3 votes
There are probably multiple things wrong here.

## Features

First, you don't tell us what features you have provided. If the only input you have provided is the word itself (e.g., the string `craindre`), then most likely the machine learning algorithm has no idea how to use that information: all it knows is that this string is different from all the others you've provided, so it has no ability to generalize.

So, you need to derive some suitable features, to enable this to generalize. For instance, maybe you'll have a feature vector of length $26^2=676$, one for each possible pair of letters, counting the number of times that pair of letters appears consecutively in the word. Then, instead of asking the machine learning algorithm to predict the language from the word itself, ask it to predict the language from the feature vector.

You can certainly come up with much more sophisticated and effective features; this is just an example. For instance, maybe you might have a feature that counts the fraction of letters that were vowels, or the fraction of letters that were consonants, or a feature that indicates what the last letter was, or a feature that indicates how many consecutive vowel-pairs the word had. Basically, you want to pick features values that you think might be helpful at predicting the language or might tend to take different values for different languages. If you want to build something that will be very accurate at predicting language, you'll probably need to get fairly sophisticated in designing features. There's lots of research literature on language detection; you could try reading it to get some ideas for better features. But if you just want to play around with this, my advice is to start with a small number of simple features.

Typically, machine learning algorithms are very smart about finding patterns in the feature vectors you provide -- but they don't do anything to automatically select features. So, the division of labor is: you come up with the features; the ML algorithm looks for patterns that enable it to use those features to predict the answer.

## Class imbalance

I suggest you read about "the class imbalance problem". You have 3 classes (English, French, and random). Your training set is imbalanced: you have twice as many examples with English as French/random. In other words, you don't have an equal number of examples for each class.

This is not *necessarily* a problem, but in some cases it can be. For instance, some machine learning algorithms behave poorly when the training set is imbalanced. And every machine learning algorithm will work sub-optimally when the frequency of the classes in the training set doesn't match what you expect to see in practice.

In your case, it's probably not any of those complicated explanations; it's probably a much simpler reason. Because you haven't given the ML algorithm any useful features, it basically has no information whatsoever that it can use to generalize or spot patterns. In other words, it's trying to guess the language of a given word *given no information about that word*. So what is the poor ML algorithm to do? All it can do is guess based on the relative frequency of different languages. In your case, your training set has told it that any given word is more likely to be English than to be French or random (about 2x as likely), so if you're forced to make a guess and pick one language, the smartest one to pick is 'English'.

In conclusion: it is no surprise that the ML algorithm is always outputting 'English', in your situation.

Once you add a suitable feature vector, if it still works poorly, you can read about the class imbalance problem and see whether it applies to you.

# Answer
> 0 votes
As a follow up, the suggestions made by @D.W. worked beatifully. Constructing a 26^2=676 long feature vector by counting pairs of letters, and training another model produced the following evaluation matrix:

It's not perfect by any means, but a significant improvement over my previous attempt.

---
Tags: machine-learning, neural-networks, classification
---


# Question
Title: Count combinations differing by fixed number of elements
I'll try to formulate my problem through an example. Lets suppose we have a collection of items of type a,b,c,d,e,f.

a1, a5, a7
b2, b3
c5, c6, c7, c8
d4, d5
e1, e2, e3
f3, f7, f8

If we take one element from each type there are 3\*2\*4\*2\*3\*3 abcdef lines (combinations).

We have another random line a1b5c7d1e5f7.

I want to count how many from the combinations lines differ by the current line in exactly 3 elements. I.e these lines differ only in one (the first) element

a5b5c7d1e5f7
a8b5c7d1e5f7

I want to do that if it's possible without generating and comparing each combination.

# Answer
> 2 votes
The trick to this count is to fix the elements that will be different, then calculate how many different choices we have for this set of elements. For each selected element we will have one less choice then we did originally, and for the elements which are to be the same we have one choice for that character. Let $V$ be the vector of the character set counts for the positions. In your example we would have $V=\[3,2,4,2,3,3\]$ and let $t$ be the number of differences. For each t-tuple $x$ (set of t positions) we have $\prod\_{i \in x} (V\[i\]-1)$ strings which differ in exactly those places. The final answer is the sum of this for every t-subset of the positions. Since you character set differs for each position you will need to go through all of the t-tuples to solve this. That is not overly bad since though since the number of t-tuples is polynomial instead of exponential as checking all combinations could have been.

---
Tags: algorithms, combinatorics
---


# Question
Title: Does a greedy strategy exist for this instance of the Bin Packing Problem?
I was wondering whether I can solve the following problem by using a greedy strategy: Let's say that I have a set of containers with 2 dimensions (width and height) and a set of items also with 2 dimensions. Can a solution be found where each item is assigned to a container so that it fits inside? I can have containers left over; however, all of the items must be assigned. Assuming a solution exist, is there a greedy choice I can make for assigning an item to a container?

# Answer
> 2 votes
No, a greedy approach would not guarantee a solution for this problem (regardless of whether this solution is optimal or not). To see why, proceed by reduction. Suppose that you could actually find a solution for your problem in polynomial time using a greedy approach. Then, you could use your algorithm to solve in polynomial time the decision version of the Bin packing problem, which is known to be **NP-complete** (and, therefore, unlikely to be solvable in polynomial time).

**How does this reduction work?**

The decision version of the Bin packing problem involves deciding whether a certain number of bins (for example, 9) is optimal. If your hypothetical polynomial-time greedy algorithm finded a solution for 9 bins and failed to find a solution for 8 bins, then the answer for the decision problem would definitely be *yes*, and *no* otherwise.

**Greedy is actually good.**

All that being said, to obtain an approximate solution, a greedy approach is, probably, the best heuristic: sort the items in decreasing order of size and insert them one by one into the first bin that has room for it. This heuristic is called *first-fit decreasing*. The main appeal of this heuristic is that we pack the big items first and **hope** that the little ones fill up the spaces.

---
Tags: greedy-algorithms, packing
---


# Question
Title: Determining if an integer appears more than $n/2$ times
> What is the minimum number of comparisons required to determine if an integer appears more than $n/2$ times in a sorted array of $n$ integers?

I am trying binary search on the array A.

Algorithm(A):

1. x = A\[mid\], where mid is the middle element of the array.
2. Compare x with A\[n/4\] and A\[3n/4\].
3. If x = A\[n/4\] and x ≠ A\[3n/4\] then search in A\[1\] to A\[3n/4 + 1\].
4. If x ≠ A\[n/4\] and x = A\[3n/4\] then search in A\[n/4 + 1\] to A\[n\].
5. If x ≠ A\[n/4\] and x ≠ A\[3n/4\] then it is a no instance.
6. If x = A\[n/4\] and x = A\[3n/4\] then it is a yes instance.

Running Time: $T(n) = T(3n/4) + O(1)$ which is $O(\log n)$ in asymptotic sense. At each step I am doing two comparisons so $2\log\_4n$ if $n = 4^k$. Is there any better (optimal) algorithm to solve the problem mentioned above?

Also, I don't know how to prove the lower bound.

# Answer
> 5 votes
You are asking two questions. I will only answer the second one. Consider the following set of possible inputs: the array is contains either $n/2$ or $n/2+1$ copies of $0$, all elements preceding it are $-1$, and all elements following it are $+1$.

I claim that any algorithm which works correctly for this set of inputs must query, in the YES instances, the first and the last position of the stretch of zeroes. Indeed, if it never queries the first position for example, then the input could have been the NO instance in which the value at that position is replaced by $-1$.

Since the first and last position of zero are at distance exactly $n/2$, and are the only two positions at that distance of equal value, we see that any correct algorithm for your problem can be modified (without any additional comparisons) to give an algorithm for the following problem:

> Given an array consisting of $n/2+1$ zeroes, preceded by $-1$ entries and followed by $1$ entries, find the location of the zeroes.

Since there are $n/2$ different answers to this problem, the usual decision tree argument shows that any comparison-based algorithm must make $\log\_3 n - O(1)$ three-way comparisons, or $\log\_2 n - O(1)$ two-way comparisons of the form "$x=y$ or $x \neq y$?". This shows that for two-way comparisons, your algorithm is nearly optimal. (Note that $2\log\_4 n = \log\_2 n $.)

---
Tags: algorithms, algorithm-analysis, lower-bounds
---


# Question
Title: Simple Recognition Algorithm, How Does It Work?
I am trying to understand how a simple image recognition of an image with dynamic size could work. What I have seen is that parts of the images are taken and evaluated. For example a simple finger recognition could be done turning the image grayscale, taking parts of the image and evaluating them. What I understand is how these parts are evaluated and how this could be done on an image with dynamic size ratio. Is a kernel function needed, or how do you proceed when you take the different parts of an image?

# Answer
> 1 votes
Normally we build a classifier that accepts images of a fixed size: say, 100x100 pixels. Given an image that is larger than that, we re-scale it to 100x100 pixels before feeding it into the classifier.

This is often combined with other techniques to locate where in a larger image the object is located. For instance, if you want to detect the presence of a bus in a picture, you build a classifier that recognizes a picture of a bus (where the bus fills the frame). Then, given a picture that might contain a bus and other stuff, you try cropping out different rectangles from within the image and feeding each one to the classifier. There are other more sophisticated techniques as well based on deep neural networks and regression.

To learn more, I suggest you read about object detection and object recognition. There's lots written about the subject in the research literature, and there are excellent tutorials available online. The state-of-the-art methods use deep neural networks.

---
Tags: machine-learning, image-processing, pattern-recognition
---


title: relation between ntime and dtime

text:
# Question
Title: relation between ntime and dtime
Given **DTIME**($n^2$) contains **NTIME**($n^{100}$) show that P=NP.

I think it's supposed to be straightforward but I just can't see it.

Take $L$, a language in NP. $L$ has a Turing machine which runs in **NTIME**$(f(n))$. If $f(n)$ is $\Omega(n^{100})$ it's obvious, but what about $O(n^{100})$?

# Answer
*Hint:* What is the time complexity of the fastest nondeterministic Turing machine that is a decider for $SAT$?
> 1 votes

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


# Question
Title: Best way to merge different trees to single data structure?
I trained an XGBoost model that classifies 50 different classes, therefore it generates a lot of boosters (trees). Also, I wrote a script that turns trained model to C++ code and it works really fast because every tree is simply nested if-else statement. What I noticed is that many trees are similar and I was wondering if there is a way to merge all of those trees into one tree or maybe to reduce number of trees by merging some of them? Maybe even convert everything to some different data structure?

This is what dump looks like:

```
booster[0]:
0:['::'] yes=2,no=1
    1:['=>'] yes=4,no=3
        3:['es'] yes=8,no=7
            7:['ef'] yes=10,no=9
                9:leaf=-0.0339584
                10:leaf=0.0612883
            8:leaf=-0.0484913
        4:leaf=0.0358804
    2:[';\s'] yes=6,no=5
        5:leaf=0.373993
        6:leaf=-0.0376609
booster[1]:
0:['</'] yes=2,no=1
    1:['h\n'] yes=4,no=3
        3:[':v'] yes=8,no=7
            7:leaf=-0.0487989
            8:leaf=0.0200258
        4:['_t'] yes=10,no=9
            9:leaf=-0.03375
            10:leaf=0.172536
    2:['*\s'] yes=6,no=5
        5:leaf=0.354577
        6:leaf=0.0165644

// etc.. boosters go on and on...

```

Let me explain how it works by going through booster\[0\]. First we check if sample we're classyfing contains '::'; if yes we jump to branch 2. There we check if sample contains ';\s' and if yes, we jump to branch 6. Branch 6 is leaf so we just take value -0.0376609 and we add it to probability that sample is class '0'.

We do the same for booster\[1\] and it gives us probability that sample is of class '1'. It goes on and on for all 50 classes and then the process is repeated for many iterations that gives us 50 * num\_iterations of trees. It comes up around 10k of trees.

Anyone has any idea if there is a better way of representing these trees so our classification works even faster?

# Answer
I don't think post-processing the trees to try to exploit similarity is likely to lead to much success. Instead, I would suggest trying the following approaches, which to my mind seem more likely to be effective.

**Tune the hyperparameters.** Try adjusting the number of trees (num\_iterations). If you can get close to the same accuracy with fewer trees, the classifier will be faster.

**Try a different classifier.** There are other classifiers that are faster for evaluating new samples, especially in the multi-class regime. For instance, you could try logistic regression and random forests.

**Hierarchical multi-class classification.** XGBoost is fundamentally a boolean classifier (where there are only two classes). It handles multi-class classification (with more than two classes) using the strategy *one-vs-rest* (or *one-vs-all*) strategy: if there are $K$ classes, then we construct $K$ boolean classifiers, where the $i$th either outputs "class $i$" or "not class $i$". This is what leads to the blowup in number of trees: the running time is proportional to $K$.

If your classes have any hierarchical structure, then an alternative is to use a hierarchical structure. You build a binary tree, where each leaf corresponds to a single class and each internal node corresponds to a set of classes (hopefully, ones that are semantically related). You construct a classifier for each internal node of the tree, which predicts whether to go left or right down the tree. You classify each new instance by walking down the tree, as directed by the classifiers that you visit. Thus, with $K$ classes, we end up with a binary tree with $K$ leaves and of depth (typically) about $\lg K$. Thus, you can classify a new instance by evaluating $\lg K$ classifiers. This offers a speedup over one-vs-rest, because the time to classify a new instance is proportional to $\lg K$ rather than $K$.

However, hierarchical classification has some caveats. It can potentially lead to reduced accuracy. The effect on accuracy depends on the structure of the class labels. If there is some hierarchical structure, then it might work well, but if not, it might work poorly. For instance, suppose you have classes "Poodle", "Chihuaha", "Siamese", and "American Shorthair", you might group the first two into the cluster "Dog" and the latter two into the cluster "Cat". Thus, you would first apply a Dog vs Cat classifier; then, depending on the result, you would either apply a Poodle vs Chihuaha classifier or a Siamese vs American Shorthair classifier. So, hierarchical classification might work quite well in this example. However, if your four classes are unrelated, hierarchical classification might cause a loss in accuracy.

**Try a cascaded classifier.** Rather than building a single classifier, try to build a cascade of classifiers. A cascade is a sequence of multiple fast classifiers, which are applied sequentially. A classifier can either output a confident answer or can output "not sure"; in the former case, we stop and use that as the answer, and in the latter case, we proceed to the next classifier in the cascade. The goal is that many instances will get answered quickly (you only have to apply the first few classifiers), and only the difficult ones will have to be evaluated by classifier in the sequence.
> 1 votes

---
Tags: algorithms, graphs, trees, performance
---


title: Insert-only Levenshtein distance

text:
# Question
Title: Insert-only Levenshtein distance
I am wondering if a constrained insert-only form of Levenshtein distance has been implemented before by someone? In my particular use case, all other operations should not count as they are not possible. Only parts of the strings can be stripped off. As an example, if our library has "Hello" and "complex".

These strings can be stripped and we might only see "Hel" or "llo" or "com" etc. I want to explore, if what we see is part of a sequence in our library.

Thanks for any suggestions.

# Answer
Your problem appears to be:

* Given strings $S,T$, determines whether $S$ appears as a subsequence of $T$.

There are several ways you could approach this.

One way is to use dynamic programming and apply a straightforward modification to computing the Levenshtein edit distance, where you set the cost of an insertion to be 1 and the cost of a deletion or replacement to be $\infty$.

Another solution to use a string-matching algorithm. Build the regexp $.\star S\_1 .\star S\_2 . \star \cdots . \star S\_n . \star$ and check whether $T$ matches this regexp, using any standard method (e.g., convert the regexp to a NFA or DFA). For instance, if $S$ is the string `HOT` and $T$ is the string `HELLO THERE`, then you will check whether `HELLO THERE` matches the regexp `.*H.*O.*T.*`. I suspect this might be faster, but the best way to find out is to try it and see.
> 1 votes

---
Tags: edit-distance
---


# Question
Title: Comparison using only bitwise operators (and return -1 or 0)
I have to use only bitwise operators to compare two numbers (represented in two's complement), and return $-1$ (represented by all $1$'s) if the numbers aren't equal or return $0$ (represented by all $0$'s) otherwise.

Say $a$ and $b$ are $W$ bits long ($W$ is not necessarily $2^n$). I find it easy to find out if both numbers are equal using $\mathsf{XOR}$: just do it like $a\ \mathsf{XOR} \ b$ and I will obtain $0$ (all $0$'s) if the two are the same. However I stuck at trying to get $-1$ when the two numbers differ, since the result of $\mathsf{XOR}$ just says which position of the two numbers differ and I have no idea how I should turn a *non-zero* number into $-1$.

How can I convert a non-zero number into $-1$ in two's complement representation (all bits set to $1$), while keeping it $0$ when it's not non-zero, which is a step further for the simple $\mathsf{XOR}$ comparison?

*Edit: In the situation this question was originated from, subtraction was not a native operator which could be directly used. The 5-operation solution from @Evil and the answer from @D.W. should also be perfectly right when an extended collection of operators, like the subtraction, were implemented.*

# Answer
> 5 votes
The first step is to take $c = a \text{ XOR } b$, this will return $0$ if the numbers were equal or some bits set to $1$ otherwise. Now to calculate the result the $c$ variable should be ORed with its circular shifts, to propagate $1$ on the whole variable.

$c = c \text{ OR } (c \text{ ROL } 1)$
$c = c \text{ OR } (c \text{ ROL } 2)$
$c = c \text{ OR } (c \text{ ROL } 4)$
$\dots$
$c = c \text{ OR } (c \text{ ROL }(W / 2))$.

Using consecutive powers of two gives exactly $\log\_2 n$ ROLs needed (credit for Extrarius, it works when you store the partial results back to $c$).

# Answer
> 2 votes
Since -1 in two's complement is all bits set, you need to figure out how to 'copy' any 1 bit into every location in the value. You can use "or" to take all the 1 bits from two sources, and you can use shifting to change the position of the 1 bits in a variable. For example, if you have 2-bit variables:

```
C = A xor B
C = C or (C >> 1) or (C << 1)

```

If, for example, C starts out as 0b10, then two "or" lines would be

```
C = 0b10 or 0b01 or 0b00 = 0b11 = -1

```

If, instead, C begins as 0b01, then you get:

```
C = 0b01 or 0b00 or 0b10 = 0b11 = -1

```

For larger variables, duplicated the OR line and change the constants to successive powers of two up to half the bit-width of your variables. For ex, for 16-bit variables:

```
C = A xor B
C = C or (C >> 1) or (C << 1)
C = C or (C >> 2) or (C << 2)
C = C or (C >> 4) or (C << 4)
C = C or (C >> 8) or (C << 8)

```

You can also replace the two shifts on each line with circular shifts of the same amount.

# Answer
> 2 votes
Here is a trick that is faster than the previous schemes on some architectures (namely, processors that don't natively support a rotate-left instruction). I'll present a scheme that works for 32-bit words; you can easily adjust it to any word size.

```
C = A xor B
C = C or (C >> 16)
C = C or (C >> 8)
C = C or (C >> 4)
C = C or (C >> 2)
C = C or (C >> 1)
D = C & 1
M = -D

```

Notice that there is any bit set in `A xor B`, then `C` will certainly have its low bit set, and thus `D` will be 1. In this case `M` will get set to the twos-complement negation of 1, i.e., to -1, which has the all-ones bit pattern. (The clever part here is the use of negation to spread a single bit to all of the bit positions, in a single instruction.)

So, if A is different from B, then M will get set to all-ones. On the other hand, if A is equal to B, then M will get set to all-zeros. This achieves your desired functionality.

My solution needs 13 operations (1 xor, 5 or's, 5 right-shifts, 1 and, and 1 negation). In comparison, Extrarius's solution needs 21 operations, so it is likely to be slower. On an architecture that supports circular left shifts, Evil's solution is faster, as it needs only 11 operations. However, if you're implementing in C, you'll need to be careful to make sure to use the right coding idioms so the compiler will generate rotate-left instructions rather than doing something slower. If you're on another platform that doesn't have a native instruction for rotate-left, then my solution above will be faster than Evil's solution.

# Answer
> 2 votes
This answer, like the previous one is not meant for the efficiency, please read @D.W. answer for that, and always check the output produced by the compiler (to find out if it understood and optimized the code) and check yourself if there is an improvement.
The idea is to check whether two numbers are equal under the strict requirement to use only bitwise operations.
The simplest version is to propagate all bits, which works no matter which one was set simply by ORing the number with all its ROLs: $$c = c \text{ OR } (c \text{ ROL } 1) \text{ OR } (c \text{ ROL } 2) \dots \text{ OR } (c \text{ ROL }(W - 1))$$ This is one line solution, it takes more terms than the previous one, but no intermediate assignments are used. ROLs are used to simply ignore the position of bit set. It also enables parallelism...

Another idea, with subtraction using only 5 operations $$\color{red}{-}(\color{blue}{((a - b) \text{ OR } (b - a))}\color{purple}{ \>\> (W - 1)})$$ It works in the following way: $\color{blue}{\text{two differences}}$ are calculated, if $a = b$ then both are zero and the sign bit is zero, otherwise one of the differences is negative and the second is positive, which ORed gives the sign bit set to one. The $\color{purple}{\text{sign bit is shifted to the last place}}$ yielding 1 as the result. $\color{red}{\text{The minus}}$ converts $1$ to $-1$, which gives all bits set to one in two's complement encoding.

---
Tags: algorithms
---