# Question
Title: What does it mean to be "independent of machine model"?
I have often heard people mention off-hand that the class $\mathsf{P}$ is "machine-independent", or "independent of machine model", or "invariant under change of machine model" - something to do with subroutines or composition or something. My question is: What precisely does that mean? or, what precisely does it mean to be independent of the choice of machine model?

It makes sense to me that invariance under change of machine model - whatever that means - would make $\mathsf{P}$ a theoretically natural class to study, sort of the same way that Euclidean geometry is interested in the notions which are invariant under similarity, or linear algebra is interested in the notions which do not depend on a particular choice of basis. (The analogy is not entirely accurate, as those fields are *only* interested in such invariant notions, while computer science is still interested in properties of particular machine models.) While I understand what it means to be independent of the choice of basis, I don't understand what it means to be independent of the choice of machine model. Is there even a unique such concept, or are there several different concepts used in different contexts?

I've talked about $\mathsf{P}$ as a specific example, but what other commonly-studied ideas (in complexity theory or otherwise) are machine-independent in the same sense that $\mathsf{P}$ is? Are there ones that are not?

Thanks for helping to clear this up for me.

# Answer
> 5 votes
The class $\mathsf{P}$ is usually defined as the class of decision problems solvable in polynomial time by (one-tape) Turing machines. However, you get the same class if you replace "one-tape Turing machines" by "multi-tape Turing machines", "RAM machines", "machines running C natively", and many other machines. That's what is meant by the class being independent of the machine model.

Other classes, such as $\mathsf{TIME}(n)$, are very much dependent on the machine model: there are (I think) languages which can be computed in linear time on a two-tape Turing machine but not on a one-tape Turing machine.

The reason we are happy that $\mathsf{P}$ is machine-independent is that it makes $\mathsf{P}$ a very natural class. You don't have to ask yourself whether the correct model is Turing machines with one tape, two tapes, or more: all definitions result in the same class. The same cannot be said about $\mathsf{TIME}(n)$, for example.

# Answer
> 2 votes
You might want to look at the so-called Strong (or Efficient) Church-Turing Thesis (SCTT) - an informal statement that whatever can efficiently be computed by some natural device can efficiently be computed by Turing machines. Church-Turing Thesis (CTT) drops the efficiency requirement and states that whatever can be computed by some natural device can be computed by Turing machines.

Note: you can never prove such statements, but you could in principle disprove them by giving a computational model that people would deem natural that computes something (add "efficiently" for SCTT) that Turing machines don't. A word of caution: CTT is much older and much more universally believed than SCTT, because in the past 80 years people have given lots of (often very weird-looking) computational models that always turned out to be equivalent to Turing machines in terms of what they can compute (without efficiency requirement). In contrast, there is a lot of evidence that quantum computing is a serious challenge to SCTT.

See this link for some interesting discussion about SCTT.

# Answer
> 1 votes
other answers are nice, however how about a different angle, a fairly simple empirical answer? imagine this as an applied measurement problem. take any algorithm of interest that has some complexity, say a sorting algorithm with O(n log n) time. now run that algorithm on *any* computer, for increasing inputs, for a range the computer can handle, and graph the results, and observe that function. now go to any *other* computer, and repeat this exercise. claim: the graphs will be essentially the same and roughly differ only by a constant factor. so this justifies the use of Big-oh notation which is invariant/ equivalent under constant factors and definition of complexity classes (which are tightly coupled with each other).

in other words most major complexity classes in theoretical computer science can be regarded as machine independent! hence their study! they are "natural" mathematical objects that serve as basic algorithmic building blocks somewhat akin to prime numbers in this way.

this also relates to the P vs NP question. the two are not "yet" provably separated so in a sense there is no theoretical way to discriminate sub-P algorithms from each other through mathematical proofs (nobody can prove that any "typical" P algorithms are faster than each other, although there is an abstract proof based on the Time Hierarchy Theorem). in other words we can empirically measure algorithms and get upper bounds on them but since tight lower bounds are so difficult and impossible so far, the "granularity" of theoretical TCS cannot be finer so far. there is some new theory related to "fine grained complexity theory" that attempts to get a better "resolution".

---
Tags: complexity-theory, terminology, computation-models
---


# Question
Title: Difficulty understanding pre-emptive vs non-preemptive CPU scheduling
I'm having difficulty understanding what my book is trying to say in regards to preemptive and non-preemptive CPU scheduling.

It says the following:

> CPU Scheduling decisions may take place under the following four circumstances:
>
> 1. When a process switches from the running state to the waiting state (for example, I/O request..)
> 2. When a process switches from the running state to the ready state (for example, when an interrupt occurs)
> 3. When a process switches from the waiting state to the ready state (for example, completion of I/O)
> 4. When a process terminates
>
> **In circumstances 1 and 4, there is no choice in terms of scheduling. A new process (if one exists in the ready queue) must be selected for execution. There is a choice, however, in circumstances 2 and 3.**
>
> When scheduling takes place only under circumstances 1 and 4, we say that the scheduling scheme is non-preemtive; otherwise, the scheduling scheme is preemptive. Under nonpreemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state.

It is mainly the bolded part that confuses me. What does it mean by there "being a choice"? The way it's worded almost sounds like it's saying that in circumstances 2 and 3, a new process DOESN'T have to be selected for execution. I'm not quite sure I follow at all what this section of my book is trying to tell me, especially the bolded part.

# Answer
> 7 votes
In circumstances 1 and 4, the current process can't continue running. Therefore, there's no choice: the OS scheduler *has* to step in and select a different process.

In circumstances 2 and 3, the OS scheduler has a choice: it can either allow the current process to continue running, or it could step in and put the current process to sleep and select a different process to run. The latter operation is called "preempting" the current process and scheduling a new one to run.

So, yes, your understanding sounds about right.

# Answer
> 4 votes
yes, this is rather abstractly defined in your reference. for illustrative purpose lets take an example of what this means in practice. early mac programs say early 1990s and windows also were "non preemptive". what this means is that every program that wants to run, if it is going to allow other programs to run, must call an OS "wait" subroutine in its inner loops of every major operation that will "allow" other programs to run. the programs in a sense have to periodically "defer" to other programs explicitly in the program code. the operating system does not have the ability to *interrupt* the running program in nonpreemptive code. this is also sometimes called *software multitasking* because the multitasking is accomplished via software.

in a *preemptive* OS, which all major OSes are today, the hardware supports interrupting running processes, and the OS works in conjunction with the hardware to interrupt other processes that do not explcitly call a "wait" subroutine that returns control to the OS. clearly, nowadays nonpreemptive multitasking is now regarded as rather feeble and fragile, because it relies on programmers to explictly implement it in their code based on "best efforts", and fails if they dont. so theres an analogy to dynamic memory management: it works great in theory but in practice there are typically memory leaks on complex programs because humans cant code it perfectly.

so *nonpreemptive* multitasking is more of a historical/ theoretical concept these days which a programmer could apply in their own code, but serious operating systems all implement preemptive multitasking.

---
Tags: operating-systems, process-scheduling, cpu
---


title: Cyber Security - recommended reading

text:
# Question
Title: Cyber Security - recommended reading
I'm applying for a doctoral training in Cyber Security, although I come from a maths background. I've been told that my background meets the entry criteria, although for my application I would like to be able to say that I've looked into Cyber Security it at least some detail.

Given that I will have very little time to do any reading before applying (about 2 weeks), what would you recommend I read? A few chapters from an academic text, or a popular book on the topic?

Specific book/paper recommendations would be appreciated.

# Answer
Take a peek at Anderson's classic "Security Engineering" (PDF legally available for free at the link). It won't help you with the details, but it gives an overview of the whole area, for (more or less) laypeople.
> 3 votes

---
Tags: reference-request
---


# Question
Title: Deterministic query complexity and polynomial degree
What is the current best upper bound known on deterministic decision tree complexity of a Boolean function in terms of its polynomial degree? Also, what is the current widest separation known between these two measures?

# Answer
> 1 votes
According to Table 2 in Aaronson, Ben-David and Kothari, the best separation between degree $\deg f$ and decision tree complexity $D(f)$ is $D(f) = \Omega(\deg f)^2)$, achieved by Göös, Pitassi and Watson, and the best upper bound is $D(f) = O((\deg f)^3)$ (perhaps already from the classic work of Nisan and Szegedy).

---
Tags: complexity-theory, polynomials
---


# Question
Title: Question about ε-moves at $\varepsilon NFA$
We learning know about ε-moves at $\varepsilon NFA$ and I'm little bit confuse...

If we have, for example, this $\varepsilon NFA$:

and we have the word "$a$" - can we end the run at $s$? Or the running will be finish at $q$?
In other words what I'm tring to ask is this:
**When we have an $\varepsilon$ - we first of all reading the letter from the input and then "jump"? or we can "jump" and then reading the input?** (or we can do both).

I look at the definition of: $\hat{\delta}(q,a)$ *(for a word)* and $\delta(q,a)$ *(for a letter)*, and I'm not sure if the answer to my question dependence at $\hat{\delta}(q,a)$ or $\delta(q,a)$, because:
$\hat{\delta}(q,a)=\\{q,s\\}$ and $\delta(q,a)=\\{q\\}$.

Thank you so much! I hope I was clear (because I'm little bit confuse...)

# Answer
In an $\varepsilon NFA$, when processing an $\varepsilon$ character, we can move on an $\varepsilon$-edge or we can stay on the state we are currently in. And for example since $a= \varepsilon a \varepsilon\varepsilon$, in your $NFA$ these two paths are both correct:

$$p \rightarrow^{\varepsilon} p \rightarrow^{a} q \rightarrow^{\varepsilon} s \rightarrow^{\varepsilon} s$$

and

$$p \rightarrow^{\varepsilon} p \rightarrow^{a} q \rightarrow^{\varepsilon} q \rightarrow^{\varepsilon} s$$

Therefore, with the character $a$ we have $\delta(p,a)=q$ and for the word $a$ we have $\hat{\delta}(p,a)=\\{q,s\\}.$
> 2 votes

# Answer
Well we have ε-NFA to help us strengthen the theoretical world of Automata ! It's applications are not much ! we could do all these things with a NFA !

Look at the example you have given ! as you said if we have a string like : 'a' Our state will go from 'p' to 'q' but then in 'q' we have no other character after 'a' so the state of the Automata will go from 'q' to 's' !so by other words with the string 'a' we go from 'p' to 's' ! so what was the point of having a middle state and then saying with empty-string it goes to the last state !?

Well look at this example : suppose Automata had a fourth state named 'g' and with the character 'b' and the state 'q' we could go to the state 'g' and the state 'g' was an accepting state ! what does that mean ? well it means that the string 'a' is not in the language of Automata but the string 'ab' is in the language of Automate ! Now look the string 'bba' , with the character 'b' the state will not change , but with the character 'a' we will go to the state 's' which is not an accepting state ! so the string 'bba' wont be in the language of Automata !

That means Automata will only accept the string that should start with an 'a' and should have at least one 'b'. By other words empty-string just made our distinction between the strings that should be accepted and the strings that should not be accepted much simpler :) I hope it helps !

Good Luck.
> 0 votes

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


# Question
Title: Proving grammar only generate strings that is multiple of 3
Hello I have an exercise for homework and I was hopping to get some hints in order to solve it.

> num-\> 11 | 10 num' 01 | num 0 | num num
>
> num'-\> 00 num' | 1 num' | ε

I need to prove that my grammar produces only strings that is multiply of 3.

What i know is:

1. 11 is 3 so no problem there
2. adding 0 to the end of the num is irrelevant because it will be still dividable by 3.
3. same with num num
4. I know that is something about the 10 num' 01 pattern. (1001 is divided by 3)

I was thinking to try to prove it with sums (this is how i solve a previous exercise). However i am not sure that i can solve it that way.

# Answer
> 3 votes
Hint: num' generates (1) numbers of even length which are divisible by 3 and (2) numbers of odd length which equal 1 mod 3. For the rule num → 10 num' 01, consider the parity of the length of the number generated by num'.

---
Tags: formal-languages, regular-languages, formal-grammars, proof-techniques
---


# Question
Title: How to remember NFA's choice on a certain computation?
I'm working on solving the question answered at this page but with different values at the table, my alphabet is {a,b,c} Words that have the same right- and left-associative product

Currently I'm in the stage where I have drawn the DFA of the multiplication table, found its reverse which was an NFA.

Here is the NFA I got by reversing the multiplication table's DFA

I apology for the miss draw, but I hope its readable.

Now I have taken the input "abcb" and applied it on the above NFA, and I have gone through this tree

As you can see here that the input is all consumed at the branch "C" and I could reach the Final State. Would someone elaborate to me how can I backtrack from that branch which is "C" in this case and indicate that the "C" is the state which shall be marked as the Final State my NFA?

# Answer
> 1 votes
Hint: Let the input be $x\_1,\ldots,x\_n$. As you mention, it is easy to compute the left-associative product $L\_n$ "as you go": $L\_{m+1} = L\_m x\_{m+1}$. The right-associative product recurrence has the wrong direction: $R\_m = x\_{m+1} R\_{m+1}$. To cope with that, at each step you have to *guess* the value of $R\_{m+1}$; it needs to be a value which conforms to your earlier guess of $R\_m$ and to the value of $x\_{m+1}$. At the end, compare your initial guess of $R\_1$ to the value of $L\_n$. Arrange things so that you only need to keep track of finitely many values of products.

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


title: is Co-NP in PSPACE?

text:
# Question
Title: is Co-NP in PSPACE?
Is Co-NP in PSPACE? I think it should obviously be, but I just wanted to make sure. I can find that NP is in PSPACE in Internet, but not on Co-NP.

# Answer
By the same reasoning that **NP** is in **PSPACE**, **co-NP** is in **co-PSPACE**. But **co-PSPACE** = **PSPACE** (you can just flip the answer), so **co-NP** is in **PSPACE**, too.
> 10 votes

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


# Question
Title: How to prove that a polynomial of degree n is θ(x^n)
How can I prove that if $T(x)$ is a polynomial of degree $n$ then $T(x) = \Theta(x^n)$.

# Answer
> 3 votes
Say $T(x) = a\_n x^n + \dotsm + a\_0$, then by the triangle inequality for $x \ge 1$:

$\begin{align} \lvert T(x) \rvert &\le \lvert a\_n \rvert x^n + \lvert a\_{n - 1} \rvert x^{n - 1} \+ \dotsm + \lvert a\_0 \rvert \\ &\le \lvert a\_n \rvert x^n + \lvert a\_{n - 1} \rvert x^n \+ \dotsm + \lvert a\_0 \rvert x^n \\ &= (\lvert a\_n \rvert + \lvert a\_{n - 1} \rvert + \dotsm + \lvert a\_0 \rvert) x^n \end{align}$

I'm sure you can take it from here. You'll have to figure out an appropriate lower bound to match.

---
Tags: asymptotics
---


# Question
Title: Why arrival process of packets at a switch is not a Poisson Process?
"Packet arrivals are not Poisson
.... but some events are, such as web requests and new flow arrivals"
I know since the network traffic is very bursty, they are not Poisson.
But I am unable to understand what "new flow arrivals" mean here and how web requests and new flow arrivals can be considered as Poisson processes.

# Answer
> 5 votes
"new flow arrivals" means "arrivals of new flows". A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow". So, this is talking about new TCP connections, and the rate/time at which the server receives new TCP connections.

Contrarily to the statement you quoted, web requests won't necessarily be Poisson. There are many factors that can cause web requests to be other-than-Poisson-distributed. For instance, the Olympics web site receives a lot more traffic when the Olympics events are happening than when they aren't. Many web sites receive more traffic during the time of day when their primary user population is awake than when they're not. In addition, visiting one page on a site typically triggers many requests for other related resources (e.g., images that are loaded on that page).

However, during any sufficiently short time period, if their user base is sufficiently large, the arrival process for a particular type of web request might well be approximately Poisson.

See, e.g., https://en.wikipedia.org/wiki/Poisson\_distribution#Occurrence.

---
Tags: terminology, probability-theory, computer-networks, modelling
---


title: Which "ID" extraction is correct?

text:
# Question
Title: Which "ID" extraction is correct?
This question related to attack on the LMAP++ the result of extracting ID from the messages. In Passive Attack on RFID LMAP++ Authentication Protocolm, page 188

```
ID = C ⊕ IDS ⊕ A ⊕ B

```

While in this paper Security Analysis of LMAP++, an RFID Authentication Protocol

```
ID = C ⊕ IDS ⊕ A ⊕ B ⊕ IDs ⊕ IDs ⊕ IDs

```

where(IDs = PID)

**Which one is correct?**

# Answer
You didn't copy the second equation correctly from the second paper. The equation in the second paper is

In your notation, this is

```
ID =  A ⊕ B ⊕ C ⊕ IDs ⊕ IDs ⊕ IDs

```

Note: the paper has 3 occurrences of `IDs`, not 4 occurrences; your post has 4 occurrences. This makes all the difference in the world.

Of course, `IDs ⊕ IDs ⊕ IDs = IDs` (follows since `X ⊕ X = 0` holds for all `X`). Therefore, the second equation is equivalent to

```
ID =  A ⊕ B ⊕ C ⊕ IDs

```

which is equivalent to the first equation.

Thus, if you accurately copy down the equation from the equation from the second paper, you'll find that it is equivalent to the equation from the first paper.
> 1 votes

---
Tags: logic, security
---


# Question
Title: What is the minimum pumping length of the following languages?
How to determine the minimum pumping length of union of two languages? How do I proceed after determining the individual pumping lengths?

1. 0\*1+0+1\* U 10\*1 - Here the minimum pumping length of the first expression is 1 and of the second is 2. I am stuck here ! Now what do I do?
2. 001 U 0\*1\* : The min PL of first expression is 4 and of the second is 1 , now what's the overall minimum PL?

# Answer
> 2 votes
I understand that a pumping length for a language $K$ is a constant $c\_K$ such that each string that has at least that language can be pumped within the language. Here "pumped" can remain somewhat abstract: it may be regular or context-free "uvwxy" pumping for instance.

It is clear that we can take $c\_{K\cup L}\le \max\\{c\_K,c\_L\\}$. Any string in $K\cup L$ of at least this length can be pumped within either $K$ or $L$ depending or where it comes from.

It seems we cannot say more than that. The main reason is that we can pump one language into the other. Look at a variant of your last example. If $K$ is finite, say it contains all words shorther than $m$, then $c\_K = m$, as no word in $K$ can be pumped. Let $L$ be the complement of $K$ containing all words of length at least $m$. Then $c\_L = m+1$ (assuming that pumping incluses "pumping down" where we obtain shorter strings). However $c\_{K\cup L}=c\_{\Sigma^\*}=1$.

I am afraid that for concrete examples you have to do a separate analysis.

---
Tags: regular-languages, finite-automata, regular-expressions, pumping-lemma
---


# Question
Title: What NP decision problems are not self-reducible?
So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of problems that are not. I was wondering if there are any examples, or if it's just a situation where you can't prove a negative easily. Wikipedia only says `It is conjectured that the integer factorization problem is not self-reducible.`

Googling found one result, which seems to state that planar graph 4 coloring is not self-reducible because LF-k coloring for a planar graph reduces to that reduction, but I couldn't quite follow the proof right now.

Is this an actual example of a self-reducibility disproof, and are there others?

# Answer
> 3 votes
The paper indeed shows that planar graph four coloring is not self-reducible in the sense of Schnorr. There are several other senses, under some of which every problem in P is self-reducible. See the follow-up paper of Große, Rothe and Wechsung. I am not aware of any other result of this kind. Going over all papers citing the paper you mention (this can be done using Google Scholar, for example), none give any such problems.

---
Tags: complexity-theory, reductions, decision-problem, np
---


title: What does it mean to fool a function?

text:
# Question
Title: What does it mean to fool a function?
In computer science papers, I see about the term 'fooling' a function.

What does it mean to fool a function against a particular complexity class? Why is it important?

# Answer
> 5 votes
Let's start with some background. The context is derandomization:

> Given a randomized algorithm, is there an equivalent deterministic algorithm?

Let's consider a randomized algorithm for some decision problem. The algorithm makes use of some random bits $r\_1,\ldots,r\_n$. In practice, we run this algorithm by using an "informal" pseudorandom number generator, perhaps injecting some physical randomness. Perhaps we can do the same formally?

The best case scenario is that there exists some really complex sequence of random bits that "looks random" for every efficient algorithm; the complexity of the sequence should grow with the complexity of the algorithm, but we want the algorithm generating the sequence to be efficient (though perhaps less efficient than the algorithm itself). While one sequence is perhaps too much to ask for (how exactly would it work, anyway?), but we can hope that a simpler distribution causes the randomized algorithm to act in roughly the same way: $$ \Pr\[A(x,\mathbf{r})\] \approx \Pr\[A(x,\mathbf{g})\], $$ where $A$ is the randomized algorithm, $x$ is the input, $\mathbf{r}$ is a vector of random bits generated uniformly at random, and $\mathbf{g}$ is the same generated pseudorandomly. What we aim for is for $\mathbf{g}$ not only to be generated efficiently, but moreover we want the support of the distribution to have polynomial size. By enumerating all possible values of $\mathbf{g}$, we can derandomize $A$.

Now back to your question. A pseudorandom sequence $\mathbf{g}$ (or a collection of such sequences) is said to *fool* an algorithm $A$ if $\Pr\[A(x,\mathbf{r})\] \approx \Pr\[A(x,\mathbf{g})\]$. It fools a complexity class if it fools all algorithms in this class.

Another context in which similar concepts appear is cryptography. For example, in cryptography a pseudorandom number generator is defined (roughly) as an efficient algorithm producing a long random sequence which fools every polynomial time distinguisher (a distinguisher a machine trying to distinguish the YES case (truly random) from the NO case (pseudorandom)).

---
Tags: complexity-theory, terminology, pseudo-random-generators
---


# Question
Title: EPI question on multiplying two integers
The Elements of Programming Interviews book has a question on "computing x\*y without arithmetical operators" (question 5.5). The solution is here: https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/MultiplyShiftAdd.cc

I am confused about the Add() function in the solution. For example, if I want to add a=1110 and b=1, the while loop will execute only once (because temp\_b will decrease from 1 to 0). The iteration goes as follows:

```
ak = 1110 & 1 = 0, bk = 1 & 1 = 1,
carryout = (0 & 1) | 0 | 0 = 0,
sum = sum | (ak ^ bk ^ carryin) = 0 | 1 = 1,
carryin = carryout << 1 = 0,
k = 10,
temp_a = 111,
temp_b = 0

```

Then we return:

```
sum | carryin = 1

```

But the sum of 1110 and 1 should be 1111

EDIT: I realised that the while loop would not stop after the first iteration

# Answer
> 1 votes
Judging from your comment, it looks like you might see what the issue with your explanation was, but it might be fruitful for someone to see this example worked out, so I'll post this anyway.

We can see that this works by stepping through the execution of this function. Let's use your examples of values for `a` and `b`:

```
a = 0b1110;
b = 0b0001;

```

We can now step through the function. Here are the initial variable assignments:

```
sum     = 0;
carryin = 0;
k       = 1;
temp_a  = a; // = 0b1110
temp_b  = b; // = 0b0001

```

We can now look at the first while loop iteration:

```
// (temp_a || temp_b) == (0b1110 || 0b0001), so we loop
ak = a & k; // = (0b1110 & 0b0001) = 0
bk = b & k; // = (0b0001 & 0b0001) = 1
carryout =  (ak & bk);      // =      (0 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (1 & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0 | (0 ^ 1 ^ 0)) = (0 | 1) = 1
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 1      << 1 = 0b10
temp_a >>= 1; // = 0b1110 >> 1 = 0b111
temp_b >>= 1; // = 0b0001 >> 1 = 0b000

```

Thus, after this loop, we have the following variable assignments:

```
sum     = 1;
carryin = 0;
k       = 0b10;
temp_a  = 0b111;
temp_b  = 0b000;

```

We then check the condition (`(temp_a || temp_b) == (0b111 || 0b000)`), and see that it is true, so we loop again:

```
ak = a & k; // = (0b1110 & 0b010) = 0b10
bk = b & k; // = (0b0001 & 0b010) = 0
carryout =  (ak & bk);      // =      (0b10 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b10 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0    & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (1 | (0b10 ^ 0 ^ 0)) = (1 | 0b10) = 0b11
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b10  << 1 = 0b100
temp_a >>= 1; // = 0b111 >> 1 = 0b11
temp_b >>= 1; // = 0b000 >> 1 = 0b00

```

Thus, after this loop, we have the following variable assignments:

```
sum     = 0b11;
carryin = 0;
k       = 0b100;
temp_a  = 0b11;
temp_b  = 0b00;

```

Checking our condition again, we loop again (there are two loops left, so I will just go ahead and put both of them):

```
ak = a & k; // = (0b1110 & 0b100) = 0b100
bk = b & k; // = (0b0001 & 0b100) = 0
carryout =  (ak & bk);      // =      (0b100 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b100 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0     & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b11 | (0b100 ^ 0 ^ 0))
                            //   = (0b11 | 0b100) = 0b111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b100 << 1 = 0b1000
temp_a >>= 1; // = 0b11  >> 1 = 0b1
temp_b >>= 1; // = 0b00  >> 1 = 0b0
// Variable assignments:
/* sum     = 0b111;
   carryin = 0;
   k       = 0b1000;
   temp_a  = 0b1;
   temp_b  = 0b0; */
// Loop again ((1 || 0) is true)
ak = a & k; // = (0b1110 & 0b1000) = 0b1000
bk = b & k; // = (0b0001 & 0b1000) = 0
carryout =  (ak & bk);      // =      (0b1000 & 1)  = 0
carryout |= (ak & carryin); // = (0 | (0b1000 & 0)) = 0
carryout |= (bk & carryin); // = (0 | (0      & 0)) = 0
// In short, carryout == 0
sum |= (ak ^ bk ^ carryin); // = (0b111 | (0b1000 ^ 0 ^ 0))
                            //   = (0b111 | 0b1000) = 0b1111
carryin = carryout << 1; // = 0 << 1 = 0
k <<= 1;      // = 0b1000 << 1 = 0b10000
temp_a >>= 1; // = 0b1    >> 1 = 0b0
temp_b >>= 1; // = 0b0    >> 1 = 0b0
// (temp_a || temp_b) == false, so we are done.
// Final variable assignments:
/* sum     = 0b1111;
   carryin = 0;
   k       = 0b10000;
   temp_a  = 0b0;
   temp_b  = 0b0;*/

```

Lastly, we calculate `sum | carryin` and return:

```
return sum | carryin; // = 0b1111 | 0 = 0b1111

```

This returns the result `0b1110 + 0b0001 = 0b1111`, which we expect.

---
Tags: algorithms, arithmetic, multiplication
---


# Question
Title: How do I prove that a language is deletion closed?
For example, how could I prove that the following language is deletion closed:

{$a^k$$b^j$ : $j$, $k$ $\geqslant$ 0}

The reason seems obvious to me, I just can't see a way to prove it.

# Answer
You'd prove that a language $L$ is deletion-closed as follows.

Consider a word $w\in L$ and let $w = w\_1\dots w\_\ell$. Now, for any $r$ and $s$ with $1\leq r\leq s\leq \ell$, consider the word $w' = w\_1\dots w\_{r-1}w\_{s+1}\dots w\_\ell$, i.e., the word that results from deleting the substring $w\_r\dots w\_s$ from $w$. We have $w'\in L$ because \[some argument that will be specific to the language $L$ you're working with\].
> 4 votes

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


title: Getting the context free grammer

text:
# Question
Title: Getting the context free grammer
I am trying to get the a CFG for this. I got this:

L1={uv | u ∈Σ∗,v∈ Σ∗1Σ∗ and |v| ≤ |u|}

```
U -> A | B
A -> 0A | E
B -> 1B | E
V -> 1T | 0T | T
T -> G1
G -> I1 | I0 | E

```

Is this correct? **UAB** does the **u** section then **VTG** get the **v** part. Or am I completely doing it wrong?

# Answer
I did not check your solution, but it doesn't look convincing. The reason is that the $u$ part is independent of the $v$ part, and so the constraint $|v|\le |u|$ cannot be enforced.

How about the following: (hint)

> rewrite the language as $L=\\{ \alpha 1 \beta \mid |\alpha|\ge |\beta|+1\\}$
> 1 votes

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


# Question
Title: Is this an example of a type-0 grammar that is not context-sensitive?
A type-0 grammar generates a recursively enumerable (RE) language.

A RE language is also known as a semi-decidable language.

A semi-decidable language is a particular kind of undecidable language: If a language is semi-decidable, we can write a method that returns `true` for each string that is an element of the language; for strings that are not an element of the language, the method may return `false` or it may loop indefinitely.

Problem: Provide an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

Answer (I think): The following grammar generates this language:

```
(a+b+) union (infinite a's)

```

Here is the grammar:

```
S → aA | bE
A → aA | bB
B → bB | ε | aE
bE → aE
E → aE

```

A method for recognizing strings in the language generated by this grammar would return true for strings that are an element of a+b+ and would run indefinitely for strings that are not an element of a+b+

I think that this is an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

If I am incorrect, would you provide an example please?

# Answer
The language you state in the question, $L=\\{ a^+b^+\\} \cup \\{a^\* \\}$ is is regular (even though expressed via a context-sensitive grammar) and thus it is not undecidable.

To generate an undecidable language, you can think of a Turing machine for that language, and try to simulate the behaviour of the TM by the grammar. For instance, the nonterminals can be the TM's state (and their position in the sentinel clause will be the head's position). Now a move of the head can be described by grammar transitions of the form $aQb \to Qab$ or $aQb \to abQ$, etc.
> 2 votes

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: Finding regular expression for a language with more substring of one type than from another
Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110.

I tried to figure out what would be the finite automata but I'm not to sure. I also tried to proof it isn't regular using Myhill-Nerode theorem but the problem is the language "readjusts" itself:

110011 (1 110, 1 011)

011110 (1 110, 1 011)

011011 (2 011, 1 110)

110110 (1 011, 2 110)

Now I'm convinced it should be regular but don't know how to proof it.

**Edit:**

¿Should be something similar to: $(0^{+}11^{+}+11^{+}0^{+})^{\*}110(0^{+}11^{+}+11^{+}0^{+})^{\*} + \epsilon$?

# Answer
> 2 votes
Hint: Suppose that as you read a word, you keep a counter which increases by 1 whenever you encounter 011, and decreases by 1 whenever you encounter 110. Show that the counter only gets the values 0,1,-1. In other words, between two occurrences of 011 there is an occurrence of 110, and vice versa. Use this to design your regular expression (you could also start with a DFA).

---
Tags: regular-languages, finite-automata, regular-expressions
---


# Question
Title: Relationship between RAM size and 32-bit vs 64-bit word size
I know that x86 supports only 4GB of RAM, and that switching to x64 greatly increases the size of RAM you can use, but I don't understand why. Why is the maximum supported ram size related to whether the processor is 32-bit or 64-bit?

# Answer
x86 is a 32-bit processor. Memory addresses for x86 are 32 bits. Each byte has a different address, so a 32-bit address means that you can only address up to $2^{32}$ bytes of memory. $2^{32}$ bytes is 4GB. That's why 32-bit processors are limited to 4GB of memory (per application). In particular, each application can use only 4GB of memory. (Technically, due to the way paging works, you can have more than 4GB of physical memory, but each application will still be limited to 4GB of physical memory.)

In contrast, a 64-bit processor can use 64-bit memory addresses, which allows addressing a huge amount of memory. This has freed computers up to have more memory: they are no longer limited to 4GB of addressable memory. (Technically, x86\_64 has 48-bit addresses -- the high 16 bits of the 64-bit address basically can't be used -- but $2^{48}$ bytes of memory is still a humongous amount of memory, about 256 TB of memory. That's more than anyone is likely to want to buy for now.)
> 7 votes

---
Tags: computer-architecture, memory-hardware
---


title: Call-by-reference semantics for RPC

text:
# Question
Title: Call-by-reference semantics for RPC
Does call-by-reference semantics for remote procedure call (RPC) have a real use case? Why does call-by-reference RPC exist? Is it useful for anything? Is there a scenario where call-by-value can't do the job?

In a simple sentence: Do we need to have a (call by reference)-able RPC protocol? if yes, Why?

---

Background: Call-by-reference can be implemented for RPC. For instance, one implementation strategy is copy & restore: the value is copied from the client to the server when you make the call, and then copied back afterwards. There are other ways to implement it as well.

# Answer
> 2 votes
The *idea* is to be able to modify the argument. FORTRAN used call-by-reference always, Algol-60 used the (mathematically clean, but hard to implement and with surprising corner cases) call-by-name; Pascal distinguishes between call-by-value and call-by-reference ("gets the variable"). But call-by-reference has its surprises, introducing aliasing between variables. Thus Ada offers call-by-value-return too.

If caller and callee reside on different machines, the performance gain of not copying arguments in and out, just using a pointer, is lost. Even worse, doing call-by-reference is quite inefficient (need to copy back and forth each time something changes). If you are defining what to do, I'd just ditch call-by-reference, and fight users tooth and nail to keep it out.

---
Tags: programming-languages, distributed-systems
---


# Question
Title: How would a finite state transducer with no output function work?
Say I have a finite state transducer, 6 tuple FST with a set of states, input symbols, output symbols, transition function, a start state, and an output function. If I combine the output function into the transition function and create this mutated FST called iFST, where the output happens on the "edges" and just one symbol is outputted each step. Would this new FST still be able to compute the same functions as a normal FST?

# Answer
It seems your notion is called a Moore machine (output function in the nodes) whereas the other variant is called Mealy machine (output on edges). This is what wikipedia states:

> "Every Moore machine $M$ is equivalent to the Mealy machine with the same states and transitions and the output function $G(s, \sigma) \rightarrow G\_M(s)$, which takes each state-input pair $(s, \sigma)$ and yields $G\_M(s)$, where $G\_M$ is $M$'s output function.
>
> However, not every Mealy machine can be converted to an equivalent Moore machine. Some can be converted only to an almost equivalent Moore machine, with outputs shifted in time. "

In another terminology, the transitions of a FST are of the form $(p,a,b,q)\in Q\times \Sigma\times\Delta\times Q$, where, $\Sigma,\Delta$ are the input/output alphabet of the transducer: from state $p$, reading $a$ from input, move to state $q$, writing $b$ to output. Sometimes this is called a Generalized Sequential Machine, and the more general definition of a FST allows $Q\times \Sigma^\*\times\Delta^\*\times Q$ instead.

Now the transitions of a Moore machine, which in wikipedia formalization \[but with my symbols\] has a transition function $T : Q \times \Sigma \rightarrow Q$ and output function $G : S \rightarrow \Delta$, can be written in the above FST format like $(\\,p,a,G(a),T(p,a)\\,)$, for every $p\in Q$, every $a\in\Sigma$.

I do not know what a "normal" FST is. I prefer output on edges (like the input) to make input/output more symmetric.
> 1 votes

---
Tags: automata, finite-automata, simulation, transducers
---


# Question
Title: How is this algorithm average case derived?
For a simple linear search on an unsorted list my textbook says the following:

> To determine the average case, you add the number of iterations required to find the target at each possible position and divide the sum by n. Thus, the algorithm performs (n + n - 1 + n -2 + ... + 1)/n, or (n + 1)/2 iterations.

The code example he uses is this:

> ```
> def sequentialSearch(target, lyst):
>     """Returns the position of the target item if found, or -1 otherwise."""
>     position = 0
>     while position < len(lyst):
>         if target == lyst[position]:
>             return position
>         position += 1
>     return False
>
> ```

I'm having trouble understanding how he is deriving (n + 1)/2 from the above?

# Answer
The sum $n+(n-1)+\dots + 3+2+1$ evaluates to $n(n+1)/2$ (it's the so-called Gauss sum). Now divide by $n$, you and get $(n+1)/2$.
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis, search-algorithms, average-case
---


# Question
Title: Deleting useless (dead) states from a finite automaton
A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the useful states is trivial: Let $G$ be the set of good (useful) states and let $\Omega$ be the set of all states. Initialize $G$ with all final states. Check all states $\Omega\setminus G$ for those that have a transition to a state in $G$ and add them to $G$. Repeat until nothing is added to $G$ any more.

A straightforward implementation mimicking the above, however, can be quite costly, looping over states and transitions over and over again. The number of loops checking $\Omega \setminus G$ is limited by the depth.

In a degenerate automaton containing transitions $a\_0\to a\_1 \to\dots\to a\_n\to f$ where $f$ is a single final state and an additional transition $a\_n\to u$ such that $u$ is useless, there would be around $n$ loops if you always loop over the $a\_i$ in the order of $i$. But if you loop in decreasing order of $i$ shuffling found good states immediately into $G$, a single loop would suffice.

But this may lead to other degenerate situations (I am guessing).

I am looking for an algorithm to mark useful states, or remove useless states, that is not recursive (to prevent stack overflow, since I am looking at FAs with millions of states) and as efficient as possible.

Extra question: are there theoretical limits known for this algorithm?

# Answer
> 4 votes
Reverse all edges in the graph, and add a new state pointing at all accepting states. Find the set of states reachable from the new state in linear time (using BFS/DFS). These are the useful states (according to your definition).

The running time of this algorithm is linear in the number of states plus number of transitions. This is about the best you can hope for (in terms of asymptotic worst-case running time).

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


title: How is (0|1|...|n) handled as a DFA?

text:
# Question
Title: How is (0|1|...|n) handled as a DFA?
How is n-times regex alternation operation, e.g. (0|1|...|n), handled in a DFA (MYT algorithm)?

Here are the rules for the MYT also (Converting Regular Expressions to NFAs ):
https://swtch.com/~rsc/regexp/regexp1.html

# Answer
The article shows how to get a FA for the regexp `0 + 1`: make a FA, $M\_0$, for `0`, make a FA, $M\_1$, for `1`, make a new start state state, $q\_0$, and link it to the original start states of $M\_0$ and $M\_1$ with $\epsilon$-moves.

Then recognize that the regexp `0 + 1 + 2` is `(0 + 1) + 2`, so do the construction again, using the FA for `0 + 1` and the FA for `2`. Rinse and repeat.
> 2 votes

---
Tags: finite-automata, regular-expressions
---


# Question
Title: How do balancers work in the context of counting and balancing networks?
I was learning what balancing networks are and at some point the art of multicore programming talks about balancers. The text book says:

> A balancer is a simple switch with two input wires and two output wires, called the top and bottom wires (or sometimes the north and south wires). Tokens arrive on the balancer’s input wires at arbitrary times, and emerge on their output wires, at some later time. *A balancer can be viewed as a toggle: given a stream of input tokens, it sends one token to the top output wire, and the next to the bottom, and so on, effectively balancing the number of tokens between the two wires*

from the discussion above it would seem that a balancer simple has a state up and down and it alternates between them and send tokens up and down (depending what state it is). Consider how the figure in the textbook defines a balancer:

It says that no matter the order and time, the tokens are split (balanced) as equal as possible between the above wire and the bottom wire. Therefore, no matter how the wires arrive, the balancer **should** maintain the invariant that the difference between top and bottom is at most 1.

The issue that I have is that it seems to describe the balancer as a state machine than alternates between up and down, but such a machine wouldn't actually be able to properly balance. It has to have some sort of state counting how many tokens it has sent up and how many it has sent down (so that it can balance). The code presented by the book seems to do the alternating up and down (unless I misunderstood it):

It doesn't quite have a counter than makes sure that it maintains, the balancing invariant. If not, then how does it actually do it?

# Answer
The book is correct, and the algorithm works as advertised. See if you can prove that it does. No explicit counting is necessary.

A very similar situation occurs for languages: $(ab)^\*(a + \epsilon)$ is regular even though $\\{ w : 0 \leq \\#\_a(w) - \\#\_b(w) \leq 1 \\}$ is not.
> 2 votes

---
Tags: algorithms, parallel-computing
---


# Question
Title: What does it mean to have tokens at a state in a balancing network?
I was assigned as homework:

> Suppose we have a width-w balancing network of depth $d$ in a quiescent state $s$ called $B$. Let $n = 2^d$. Prove that if n tokens enter the network on the same wire, pass through the network, and exit, then $B$ will have the same state after the tokens exit as it did before they entered.

However, I do not understand what the question is asking (please don't actually do the problem).

I have followed chapter 12 of the art of mutlicore programming, and its still unclear what the question is asking. Let me give you my thoughts (and confusions):

What does it mean by $s$ and $B$? According to the textbook, a balancing network is quiescent if every token that arrived on an input wire has emerged on an output wire (which makes sense because we only care when the tokens pass the network, not their order). Does a quiescent state refer to which cables the tokens have entered? Or since the order doesn't matter it just means that the same number of tokens that entered left the network?

What do they refer to as "a state"? Does it means were the tokens are located and which wires they left or if we only care about quiescent states, that the total number of tokens at the beginning and the end is the same?

# Answer
> 1 votes
It seems that there is a typo – $s$ and $B$ represent the same thing. It looks like the original $s$ was changed to $B$, but the author of the question forgot to delete $s$.

The state of the network is the state of all balancers – which way they point.

---
Tags: algorithms, parallel-computing
---


# Question
Title: Programming Thompson's algorithm: How to represent a NFA?
I'm trying to create a small program that interprets a NFA to the corresponding regex using Thompson's algorithm.

My question: What kind of notation can be used to express a NFA (e.g. in the form of a string?) that can be read and then interpreted by the program?

# Answer
If you look closely, Thompson's R.E. to NFA algorithm is carefully tuned to be able to use a simple linked structure: a state is a node, it has one leaving transition on a symbol, or two on $\epsilon$ (thus you can reuse the space for the symbol for the second pointer, and distinguish between both cases by a spare bit somewhere). Your partial automata have one start and one accept state, so you need two pointers for each one, and splicing them together is again simple link manipulation.
> 4 votes

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


# Question
Title: Proving that removing unreachable states from $M$ does not change $L(M)$
What is the idea behind proving that:

> Removing **unreachable states** from a DFA $M$ does not change $L(M)$.

I don't know what cases I need consider. Consider any $w\in \sum^\*$ and then check for the cases $w \in L(M)$ or $w \not \in L(M)$? Then I was thinking that there could some lemmas regarding DFA minimalization, sort of like "Assume DFA not minimal, i.e. contains unreachable states.", then "DFA can be minimalized", then "minimal DFA recognizes the same language".

In checking $w \in L(M)$ or $w \not \in L(M)$ one should find out (as the answer below points out) that, because of the definition for $L(M)$ and unreachable states, $w \in L(M)$ does not depend on unreachable states (since $w \in L(M)$ with reachable states). Therefore, for any $w \in L(M)$, it's recognised by both the DFA with and without unreachable states. Is this enough?

# Answer
> 2 votes
Whether or not a word $w$is in $L$ depends on the sequence of states the automaton passes through when it reads $w$ (specifically, it depends on whether that sequence ends in an accepting state or not). If you have a state $q$ that's never reached, for any input, then there is no word $w$ such that the decision of whether $w\in L$ or $w\notin L$ depends on any property of $q$, or even its existence.

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


# Question
Title: How is out-of-order instruction execution related to superscalar execution?
How is out-of-order instruction execution related to superscalar execution?

How is data hazard detection and handling affected by superscalar execution?

# Answer
> 1 votes
Superscalar execution means that some instructions execute simultaneously. Since the instructions under superscalar execution aren't executing in-order, supserscalar execution is one form of out-of-order execution.

---
Tags: operating-systems, parallel-computing
---


# Question
Title: Halting problem - one issue that's bothering me
To my knowledge, halting problem asks if there exists a program that decides whether a program being tested, given some input data (no matter what program it is, or what input data we give) will terminate or not. The answer to this problem is 'no'. In other words, there is no 'single' program that can verify it for all possible pairs (some algorithm, some input data).

But it doesn't mean we can't decide if **particular** program X will terminate or not.

I can't comment other answers yet, but one of them brought my attention:

> In practical terms, it is important because it allows you to tell your ignorant bosses "what you're asking is mathematically impossible".

Maybe you can tell me what that person meant? In my scenario, my ignorant boss can ask me to verify (actually, prove or disprove) if my program (that's a particular program) will terminate or not. And of course there are pairs (algorithm, input data) that can be proven to terminate (or never terminate).

The question is - can I prove it for every such pair (program, input data) separately? Even if the answer is yes, then there's a problem - there can be infinitely many 'input data'. So it's quite natural to ask - can I prove, for every algorithm, that this algorithm will terminate (or the opposite), no matter what input data I provide?

# Answer
No, you cant prove this for every algorithm (Turing machine). This becomes a question about the nature of proofs rather than a question about computation.

Consider the following Turing machine $M(x)$: check if there exists a proof for the statement $\forall x \hspace{1mm} M(x)$ halts, of length $\le |x|$ (for explanation on the self reference, see Klenee's recursion theorem). If such proof is found, get into an infinite loop (otherwise halt).

Clearly you cant prove $M(x)$ halts for all $x$, since if you can find a proof of length $p$, it wont halt for all inputs of size $\ge p$. In addition, you cant prove $M(x)$ doesn't halt for some $x$, since this would mean there exists a proof for the halting of $M$ on all inputs (contradiction). The situation here is, that if our axiom system is consistent, then $M(x)$ halts for all $x$, but you cant prove it (meaning you can prove in your theory $T$ that if $T$ is consistent then $\forall x \hspace{1mm} M(x)$ halts, but you cant prove it halts without this assumption, unless your system is inconsistent).
> 6 votes

# Answer
For one specific program, sure I can prove that the program will halt on all inputs: my program has "halt" as its first instruction.

Another example: I can have a specific program that is a Turing machine simulator (i.e. a universal Turing machine). It interprets its input as a description of a Turing machine, and the simulator simulates the machine running on a blank tape. So the simulator will stop if the machine being input stops, and will run for ever if the machine being input runs for ever. (If the input is not in the correct format to describe a Turing machine, the simulator stops.)

We know it is impossible to decide whether an arbitrary Turing machine halts when started on a blank tape. So for my specific simulator machine, there is no algorithm to decide what it does on arbitrary input.

I don't know if these two examples help.

Surely in many problem domains it is reasonable to be able to prove that specific programs terminate. If my program multiplies two matrices I would expect to be able to prove that there is no way it can go on for ever.
> 2 votes

# Answer
I can at least clarify the hypothetical question the imaginary boss is presumed to ask which lead to this answer:

> Can you design a program that takes this other program/template/database query/ etc. which *always* determines whether it terminates/raises an exception/runs out of memory?

The point of the impossibility proof is that such a task cannot be accomplished. Of course it's common knowledge today that such a task can be *approximated* quite well, i.e. it is possible to give an algorithm that determines whether a program is going to raise an exception, **but sometimes answers "might raise an exception" even though the program doesn't do it in practice**.

Some of these are harder to do in practice as well, e.g. termination is quite harder to prove than the absence of null pointer exception for "real world programs" (but equivalent in theory).
> 2 votes

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


# Question
Title: Consequences of factoring and discrete log in $P/Poly$
What is the consequence of factoring and discrete log being in $P/poly$?

# Answer
There appear to be pretty much no interesting consequences, from a complexity-theoretic perspective. See Consequences of Factoring being in P? on CSTheory. (Any consequence of factoring being in P/poly would also be a consequence of factoring being in P; but as the answers to that question state, there are basically no known complexity-theoretic consequences to factoring being in P.)

A Google search for "consequences of factoring in P/poly" also turns up Factoring Could be Easy.
> 1 votes

---
Tags: complexity-theory, factoring
---


# Question
Title: Finding vertices for which there either exists a path to all other vertices or other vertices have a path to them
Or in other words, find all $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ or $w \rightarrow v$. This is for a directed acyclic graph. I need to find an $O(|E| + |V|)$ algorithm for this.

I can see how to identify if a given vertex meets these traits (perform a BFS starting at that vertex, then do another BFS on the reverse of that graph and see if every vertex was visited in those BFSes). The obvious solution would be to run this on every vertex of the graph, but that will end up being $O(|E||V| + |V|^{2})$.

I've considered identifying strongly connected components, but that doesn't seem like the right approach, since a SCC requires that $v$ and $w$ are mutually reachable, whereas this homework question requires that $v$ and $w$ are only reachable one way.

Advice?

# Answer
We can assume that the DAG is connected, since otherwise the solution is trivial. Consider some topological ordering of the vertices. A vertex $v$ satisfies your condition if (1) $v$ can be reached from all vertices preceding $v$ in the ordering and (2) all vertices following $v$ in the ordering are reachable from $v$. We can check conditions (1) and (2) separately.

To check condition (2), traverse the topological ordering in order, and for each vertex encountered, remove the vertex. Since this is a topological ordering, when a vertex is removed, it is a source, that is, it has no incoming edges. Condition (2) is satisfied for the vertex iff it is the unique source at that point. Condition (1) can be checked similarly by traversing the topological ordering in reverse.
> 1 votes

# Answer
Just to make sure. If,a graph is strongly connected then it has a cycle. which in turn means you cannot have topological sort.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Can a deterministic language be accepted by a deterministic Push Down Automaton?
I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic language contains a PDA that is deterministic.

The language in question is: $L = \\{w \in \\{a,b\\}^\* : n\_a(w) = n\_b(w)\\}$

# Answer
Sure, a deterministic language can trivially be accepted by a nondeterministic PDA. Simplest way to see it is that a deterministic PDA is just a special case of the non-deterministic one. If that isn't enough, for some transition

$\begin{align} \delta(q, a, A) = \\{(p, \alpha)\\} \end{align}$

you can add the following, *without changing the language accepted* (the modified PDA isn't deterministic, it is enabled to do completely pointless $\epsilon$ moves):

$\begin{align} \delta(q, \epsilon, A) = \\{(q, A)\\} \end{align}$
> 1 votes

# Answer
The definition of a deterministic context-free language is that it is a language that is accepted by a deterministic pushdown automaton. Therefore, every deterministic context-free language can be recognized by a PDA that is deterministic. In other words, the answer to your question is "no" (assuming I am understand correctly what you mean by "contain"). See https://en.wikipedia.org/wiki/Deterministic\_context-free\_language.
> 0 votes

---
Tags: formal-languages, pushdown-automata, nondeterminism
---


# Question
Title: Can a Turing Machine have infinite accept states?
I'm still fairly new to Turing Machines, but I've been doing some research.

I know that a Turing Machine can have an infinite tape and that it requires a finite number of states, but does it necessarily follow that a Turing Machine can have an infinite number of accept states?

I keep seeing different layouts when formally defining Turing Machines, for example:

M = (Q, Σ, Γ, τ, s, F).

1) F ⊆ Q is the set of final or accepting states. (plural)

2) F ⊆ Q is the accept state. (singular)

So I'm just wondering which one is correct?

Any help would be greatly appreciated.

# Answer
> 6 votes
In the *standard* Turing machine, the set of states $Q$ is finite $|Q| \< \infty$. Therefore, it cannot have infinite final states. However, it may, or may not have multiple final states. This will not change the power of the machine (i.e., one final state is equivalent to $k$ final states).

# Answer
> 2 votes
Turing machines are defined to have only a finite number of states. Since every accepting state is a state, it's impossible to have infinitely many accepting states. Being allowed to have more than one of something is not the same as being allowed to have infinitely many.

# Answer
> 1 votes
As for the difference between one and many accepting states, if you have a TM with multiple accepting states, you can add a new single accepting state and make sure that from the accepting states you can get to your new state in one move. Thus one/many doesn't affect the power of the machine, but it might simplify proofs. Thus you'll see varied definitions, all equivalent.

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


# Question
Title: Bipartite Graph - How to determine largest subsets that are all connected
I have a bipartite graph $G = (U,V,E)$, where $U$ and $V$ are disjoint node sets and $U \cup V$ is the set of all vertices, and $E$ is the set of all edges. I'm looking for subsets $U' \subseteq U$ and $V' \subseteq V$ such that there exists an edge $\\{i,j\\} \in E$ for all $i \in U', j \in V'$ and $|U'| + |V'|$ is maximum.

Ideally, I'm looking for the absolute best solution (a single one is sufficient if there is more than one), but happy to find any solution so that $U'$ contains at least 50% of $U$ and $V'$ contains at least 50% of $V$ (and no solution if no such solution exists).

The naive algorithm (construct all subsets, calculate if they satisfy the requirements and pick the largest) does not seem very promising to find a quick solution.

I'm not that familiar with the terms in graph theory, so I'll be perfectly happy with references to "standard problems" if that's what I'm looking for.

# Answer
Rephrasing from On Bipartite and Multipartite Clique Problems:

You can formulate the problem as an Integer Linear Program. Let the vertices in each partition be $V\_1,V\_2$ respectively. Take a (binary) variable $x\_v$ for each $v\in V\_1\cup V\_2$. Then the problem is do determine

$$\textrm{maximize } \Sigma\_{v\in V\_1\cup V\_2} x\_v \textrm{ subject to}$$

$$x\_v+x\_u\leq 1 \textrm{ for all } u\in V\_1, v\in V\_2 \textrm{ so that } (u,v)\notin E$$

In general, solving ILP's is $NP$-complete. However, in this case, the corresponding constraint matrix is totally unimodular. Consider the relaxed problem: instead of requiring all $x\_v$ to be binary, we instead only require that $0\leq x\_v\leq 1$ (dropping the integrality constraint). Because the constraint matrix is totally unimodular, the optimal solution to the LP will be integral (and thus also a solution for the ILP). You can use the simplex method (or if you insist on wost-case polynomial time, the ellipsoid method) to obtain a solution for the LP, which is automatically a solution for the ILP.
> 6 votes

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


# Question
Title: What is a brief but complete explanation of a pure/dependent type system?
If something is simple, then it should be completely explainable with a few words. This can be done for the λ-calculus:

> The λ-calculus is a **syntactical grammar** (basically, a structure) with a **reduction rule** (which means a search/replace procedure is repeatedly applied to every occurrence of a specific pattern until no such pattern exists).
>
> Grammar:
>
> ```
> Term = (Term Term) | (λ Var . Term) | Var
>
> ```
>
> Reduction rule:
>
> ```
> ((λ var body) term) -> SUBS(body,var,term)
>     where `SUBS` replaces all occurrences of `var`
>     by `term` in `body`, avoiding name capture.
>
> ```
>
> Examples:
>
> ```
> (λ a . a)                             -> (λ a a)
> ((λ a . (λ b . (b a))) (λ x . x))     -> (λ b . (b (λ x x)))
> ((λ a . (a a)) (λ x . x))             -> (λ x . x)
> ((λ a . (λ b . ((b a) a))) (λ x . x)) -> (λ b . ((b (λ x . x)) (λ x . x)))
> ((λ x . (x x)) (λ x . (x x)))         -> never halts
>
> ```

While somewhat informal, one could argue this is informative enough for a normal human to understand the λ-calculus as a whole - and it takes **22 lines** of markdown. I'm trying to understand **pure/dependent type systems** as used by Idris/Agda and similar projects, but the briefer explanation I could find was Simply Easy \- a great paper, but that seems to assume a lot of previous knowledge (Haskell, inductive definitions) that I don't have. I think something briefer, less rich could eliminate some of those barriers. Thus,

**Is it possible to give a brief, complete explanation of pure/dependent type systems, in the same format I presented the λ-calculus above?**

# Answer
> 7 votes
# Disclaimer

This is very informal, as you requested.

# The grammar

In a dependently typed language we have a binder at the type level as well as at the value level:

```
Term = * | (∀ (Var : Term). Term) | (Term Term) | (λ Var. Term) | Var

```

Well-typed term is a term with attached type, we will write `t ∈ σ` or

```
σ
t

```

to indicate that term `t` has type `σ`.

# Typing rules

For the sake of simplicity we require that in `λ v. t ∈ ∀ (v : σ). τ` both `λ` and  bind the same variable (`v` in this case).

Rules:

```
t ∈ σ is well-formed if σ ∈ * and t is in normal form (0)

*            ∈ *                                                 (1)
∀ (v : σ). τ ∈ *             -: σ ∈ *, τ ∈ *                     (2)
λ v. t       ∈ ∀ (v : σ). τ  -: t ∈ τ                            (3)
f x          ∈ SUBS(τ, v, x) -: f ∈ ∀ (v : σ). τ, x ∈ σ          (4)
v            ∈ σ             -: v was introduced by ∀ (v : σ). τ (5)

```

Thus, `*` is "the type of all types" (1),  forms types from types (2), lambda abstractions have pi-types (3) and if `v` is introduced by `∀ (v : σ). τ`, then `v` has type `σ` (5).

"in normal form" means that we perform as many reductions as possible using the reduction rule:

# "The" reduction rule

```
(λ v. b ∈ ∀ (v : σ). τ) (t ∈ σ) ~> SUBS(b, v, t) ∈ SUBS(τ, v, t)
    where `SUBS` replaces all occurrences of `v`
    by `t` in `τ` and `b`, avoiding name capture.

```

Or in two-dimensional syntax where

```
σ
t

```

means `t ∈ σ`:

```
(∀ (v : σ). τ) σ    SUBS(τ, v, t)
                 ~>
(λ  v     . b) t    SUBS(b, v, t)

```

It's only possible to apply a lambda abstraction to a term when the term has the same type as the variable in the associated forall quantifier. Then we reduce both the lambda abstraction and the forall quantifier in the same way as in the pure lambda calculus before. After subtracting the value level part, we get the (4) typing rule.

# An example

Here is the function application operator:

```
∀ (A : *) (B : A -> *) (f : ∀ (y : A). B y) (x : A). B x
λ  A       B            f                    x     . f x

```

(we abbreviate `∀ (x : σ). τ` to `σ -> τ` if `τ` doesn't mention `x`)

`f` returns `B y` for any provided `y` of type `A`. We apply `f` to `x`, which is of the right type `A`, and substitute `y` for `x` in the  after `.`, thus `f x ∈ SUBS(B y, y, x)` ~\> `f x ∈ B x`.

Let's now abbreviate the function application operator as `app` and apply it to itself:

```
∀ (A : *) (B : A -> *). ?
λ  A       B          . app ? ? (app A B)

```

I place `?` for terms that we need to provide. First we explicitly introduce and instantiate `A` and `B`:

```
∀ (f : ∀ (y : A). B y) (x : A). B x
app A B

```

Now we need to unify what we have

```
∀ (f : ∀ (y : A). B y) (x : A). B x

```

which is the same as

```
(∀ (y : A). B y) -> ∀ (x : A). B x

```

and what `app ? ?` receives

```
∀ (x : A'). B' x

```

This results in

```
A' ~ ∀ (y : A). B y
B' ~ λ _. ∀ (x : A). B x -- B' ignores its argument

```

(see also What is predicativity?)

Our expression (after some renaming) becomes

```
∀ (A : *) (B : A -> *). ?
λ  A       B          . app (∀ (x : A). B x) (λ _. ∀ (x : A). B x) (app A B)

```

Since for any `A`, `B` and `f` (where `f ∈ ∀ (y : A). B y`)

```
∀ (y : A). B y
app A B f

```

we can instantiate `A` and `B` to get (for any `f` with the appropriate type)

```
∀ (y : ∀ (x : A). B x). ∀ (x : A). B x
app (∀ (x : A). B x) (λ _. ∀ (x : A). B x) f

```

and the type signature is equivalent to `(∀ (x : A). B x) -> ∀ (x : A). B x`.

The whole expression is

```
∀ (A : *) (B : A -> *). (∀ (x : A). B x) -> ∀ (x : A). B x
λ  A       B          . app (∀ (x : A). B x) (λ _. ∀ (x : A). B x) (app A B)

```

I.e.

```
∀ (A : *) (B : A -> *) (f : ∀ (x : A). B x) (x : A). B x
λ  A       B            f                    x     .
    app (∀ (x : A). B x) (λ _. ∀ (x : A). B x) (app A B) f x

```

which after all reductions at the value level gives the same `app` back.

So while it requires just a few steps in the pure lambda calculus to get `app` from `app app`, in a typed setting (and especially a dependently typed) we also need to care about unification and things become more complex even with some inconsitent convenience (`* ∈ *`).

# Type checking

* If `t` is `*` then `t ∈ *` by (1)
* If `t` is `∀ (x : σ) τ`, `σ ∈? *`, `τ ∈? *` (see the note about `∈?` below) then `t ∈ *` by (2)
* If `t` is `f x`, `f ∈ ∀ (v : σ) τ` for some `σ` and `τ`, `x ∈? σ` then `t ∈ SUBS(τ, v, x)` by (4)
* If `t` is a variable `v`, `v` was introduced by `∀ (v : σ). τ` then `t ∈ σ` by (5)

These all are inference rules, but we can't do the same for lambdas (type inference is undecidable for dependent types). So for lambdas we check (`t ∈? σ`) rather than infer:

* If `t` is `λ v. b` and checked against `∀ (v : σ) τ`, `b ∈? τ` then `t ∈ ∀ (v : σ) τ`
* If `t` is something else and checked against `σ` then infer the type of `t` using the function above and check whether it is `σ`

Equality checking for types requires them to be in normal forms, so to decide whether `t` has type `σ` we first check that `σ` has type `*`. If so, then `σ` is normalizable (modulo Girard's paradox) and it gets normalized (hence `σ` becomes well-formed by (0)). `SUBS` also normalizes expressions to preserve (0).

This is called bidirectional type-checking. With it we don't need to annotate every lambda with a type: if in `f x` the type of `f` is known, then `x` is checked against the type of the argument `f` receives instead of being inferred and compared for equality (which is also less efficient). But if `f` is a lambda, it does require an explicit type annotation (annotations are omitted in the grammar and everywhere, you can either add `Ann Term Term` or `λ' (σ : Term) (v : Var)` to the constructors).

Also, have a look at the Simpler, Easier! blogpost.

# Answer
> 25 votes
Let's have a go. I'll not bother about Girard's paradox, because it distracts from the central ideas. I will need to introduce some presentational machinery about judgments and derivations and such.

**Grammar**

> Term ::= (Elim) | * | (Var:Term)→Term | λVar↦Term
>
> Elim ::= Term:Term | Var | Elim Term

The grammar has two mutually defined forms, "terms" which are the general notion of thing (types are things, values are things), including * (the type of types), dependent function types, and lambda-abstractions, but also embedding "eliminations" (i.e. "usages" rather than "constructions"), which are nested applications where the thing ultimately in the function position is either a variable or a term annotated with its type.

**Reduction Rules**

> (λy↦t : (x:S)→T) s ↝ t\[s:S / y\] : T\[s:S / x\]
>
> (t : T) ↝ t

The substitution operation t\[e / x\] replaces every occurrence of the variable x with the elimination e, avoiding name capture. To form an application that can reduce, a lambda *term* must be annotated by its type to make an *elimination*. The type annotation gives the lambda-abstraction a kind of "reactivity", allowing application to proceed. Once we reach the point where no more application is happening and the active t : T is being embedded back into the term syntax, we can drop the type annotation.

Let's extend the ↝ reduction relation by structural closure: the rules apply anywhere inside terms and eliminations that you can find something matching the left-hand side. Write ↝\* for the reflexive-transitive (0-or-more-step) closure of ↝. The resulting reduction system is confluent in this sense:

> If s ↝\* p and s ↝\* q, then there exists some r such that p ↝\* r and q ↝\* r.

**Contexts**

> Context ::= | Context, Var : Term

Contexts are sequences which assign types to variables, growing on the right, which we think of as the "local" end, telling us about the most recently bound variables. An important property of contexts is that it's always possible to choose a variable not already used in the context. We maintain the invariant that the variables ascribed types in the context are distinct.

**Judgments**

> Judgment ::= Context ⊢ Term has Term | Context ⊢ Elim is Term

That's the grammar of judgments, but how to read them? For a start, ⊢ is the tradional "turnstile" symbol, separating assumptions from conclusions: you can read it informally as "says".

> G ⊢ T has t

means that given context G, type T admits term t;

> G ⊢ e is S

means that given context G, elimination e is given type S.

Judgments have interesting structure: zero or more *inputs*, one or more *subject*, zero or more *outputs*.

```
INPUTS                   SUBJECT        OUTPUTS
Context |- Term   has    Term
Context |-               Elim      is   Term

```

That is, we must propose the types of terms in advance and just *check* them, but we *synthesize* the types of eliminations.

**Typing Rules**

I present these in a vaguely Prolog style, writing J -: P1; ...; Pn to indicate that judgment J holds if premises P1 through Pn also hold. A premise will be another judgment, or a claim about reduction.

> **Terms**
>
> G ⊢ T has t -: T ↝ R; G ⊢ R has t
>
> G ⊢ * has *
>
> G ⊢ * has (x:S)→T -: G ⊢ * has S; G, z:S !- * has T\[z / x\]
>
> G ⊢ (x:S)→T has λy↦t -: G, z:S ⊢ T\[z/x\] has t\[z/y\]
>
> G ⊢ T has (e) -: G ⊢ e is T
>
> **Eliminations**
>
> G ⊢ e is R -: G ⊢ e is S; S ↝ R
>
> G, x:S, G' ⊢ x is S
>
> G ⊢ f s is T\[s:S / x\] -: G ⊢ f is (x:S)→T; G ⊢ S has s

And that's it!

Only two rules are *not* syntax-directed: the rule which says "you can reduce a type before you use it to check a term" and the rule which says "you can reduce a type after you've synthesized it from an elimination". One viable strategy is to reduce types until you've exposed the topmost constructor.

This system is not strongly normalizing (because of Girard's Paradox, which is a liar-style paradox of self-reference), but it can be made strongly normalizing by splitting * into "universe levels" where any values which involve types at lower levels themselves have types at higher levels, preventing self-reference.

This system does, however, have the property of type preservation, in this sense.

> If G ⊢ T has t and G ↝\* D and T ↝\* R and t ↝ r, then D ⊢ R has r.
>
> If G ⊢ e is S and G ↝\* D and e ↝ f, then there exists R such that S ↝\* R and D ⊢ f is R.

Contexts can compute by allowing the terms they contain to compute. That is, if a judgment is valid now, you can compute its inputs as much as you like and its subject one step, and then it will be possible to compute its outputs somehow to make sure the resulting judgment stays valid. The proof is a simple induction on typing derivations, given the confluence of --\>\*.

Of course, I've presented only the functional core here, but extensions can be quite modular. Here are pairs.

> Term ::= ... | (x:S)\*T | s,t
>
> Elim ::= ... | e.head | e.tail
>
> (s,t : (x:S)\*T).head ↝ s:S
>
> (s,t : (x:S)\*T).tail ↝ t:T\[s:S / x\]
>
> G ⊢ * has (x:S)\*T -: G ⊢ * has S; G, z:S ⊢ * has T\[z / x\]
>
> G ⊢ (x:S)\*T has s,t -: G ⊢ S has s; G ⊢ T\[s:S / x\] has t
>
> G ⊢ e.head is S -: G ⊢ e is (x:S)\*T
>
> G ⊢ e.tail is T\[e.head / x\] -: G ⊢ e is (x:S)\*T

# Answer
> 8 votes
The Curry-Howard correspondence says that there is a systematic correspondence between **type systems** and **proof systems** in logic. Taking a programmer-centric view of this, you could recast it this way:

* Logical proof systems are programming languages.
* These languages are statically typed.
* The type system's responsibility in such a language is to forbid programs that would construct unsound proofs.

Seen from this angle:

* The untyped lambda calculus that you summarize doesn't have a significant type system, so a proof system built on it would be unsound.
* The simply typed lambda calculus is a programming language that has all the types necessary to build sound proofs in sentential logic ("if/then", "and", "or", "not"). But its types aren't good enough to check proofs that involve quantifiers ("for all x, ..."; "there exists an x such that ...").
* Dependently typed lambda calculus has types and rules that support sentential logic *and* first-order quantifiers (quantification over values).

Here are the rules of natural deduction for first-order logic, using a diagram from the Wikipedia entry on natural deduction. These are basically the rules of a minimal dependently typed lambda calculus as well.

Note that the rules have lambda terms in them. These can be read as the programs that construct the proofs of the sentences represented by their types (or more succinctly, we just say *programs are proofs*). Similar reduction rules that you give can be applied to these lambda terms.

---

Why do we care about this? Well, first of all, because proofs may well turn out to be a useful tool in programming, and having a language that can work with proofs as first-class objects opens many avenues. E.g., if your function has a precondition, instead of writing it down as a comment you can actually demand a proof of it as an argument.

Second, because the type system machinery needed to handle quantifiers may have other uses in a programming context. In particular, dependently typed languages handle universal quantifiers ("for all x, ...") by using a concept called **dependent function types**—a function where the *static type* of the result can depend on the *runtime value* of the argument.

To give a very pedestrian application of this, I write code all the time that has to read Avro files that consist of records with uniform structure—all share the same set of field names and types. This requires me to either:

1. Hardcode the structure of the records in the program as a record type.
    * Advantages: The code is simpler and the compiler can catch errors in my code
    * Disadvantage: The program is hardcoded to read files that agree with the record type.
2. Read the schema of the data at runtime, represent it generically as a data structure, and use that to process records generically
    * Advantages: My program is not hardcoded to just one file type
    * Disadvantages: The compiler can't catch as many errors.

As you can see in the Avro Java tutorial page, they show you how to use the library according to both of these approaches.

With dependent function types you can have your cake and eat it, at the cost of a more complex type system. You could write a function that reads an Avro file, extracts the schema, and returns the file's contents as a stream of records *whose static type depends on the schema stored in the file*. The compiler would be able to catch errors where I, for example, tried to access a named field that might not exist in the records of the files that it'll process at runtime. Sweet, huh?

---
Tags: functional-programming, type-theory
---


# Question
Title: Number of special paths between two nodes
Consider a directed graph. Each node in this graph has an integer label. We want to count the number of special paths between `source` and `sink`. Let's define a variable named `value`. Every path starts with `value = label[source]`. When we move from node A to B value changes like this: `value = lcm( label[B], value )` where `lcm` is lowest common multiplier. A speical path has two condition:
1- During the move from `source` to `sink` value should always change. It means when moving from node A to B, if `value` before and after the move remains unchanged, that path is not special.

2- `value` should become some predetermined integer `k` at the end of the path.

How many ways we can go from `source` to `sink` while not contradicting above conditions.

---

I think we can remove every node that `lcm(label[node], k) != k` because this node could not be on any special path. Also condition one removes every loop from the graph.

Now the only algorithm I know about counting all the paths between two nodes is to use Dynamic Programming but I can't reduce this problem to that.

Also I can compute the result using backtrack but as there could be exponentially large number of such paths, it's not efficient enough.

original problem statement

# Answer
> 2 votes
To start, notice that a room is only useful if v\[i\] divides k, where v\[i\] is the value of the room i. One other important thing to see is that, is the worst case there are at most 7 different primes (2\*3\*5\*7\*11\*13) in the prime factorization of k and at most 19 primes total (2^19). This gives us a good hint that we can use a bitmask to represent the value of each node in such a way that lcm(v\[i\], v\[j\]) = v\[i\] | v\[j\] (bitwise or).

After having the graph pre-processed (with only the useful nodes and with the bitmask pre-computed for every node and for k), we can do DP on the graph that can be seen as a DAG because we will never go through the same node twice. Our state will then be (cur\_node, cur\_bitmask).

There's only one final detail for this to fit in memory. One should notice that for the second dimension of the DP is very sparse so we can use a map for each node to keep the DP results.

Hope my explanation was clear enough, if not, feel free to clarify your doubts :)

Sample implementation: http://pastebin.com/KLfyyvhv

# Answer
> 1 votes
I don't have a solution, but here's something that's probably needed for a solution.

Recall that every natural number can be written uniquely as a product of prime powers: $n = p\_1^{k\_1} p\_2^{k\_2} \dots p\_a^{k\_a}$ for a number $n$ with at most $a$ prime factors $p\_1, \dots, p\_a$ all unique.

The lcm of two numbers can be easily computed in terms of products of prime powers: You simply take the maximum exponent for every prime. If $n = p\_1^{k\_1} \dots p\_a^{k\_a}$ and $n' = p\_1^{m\_1} \dots p\_a^{m\_a}$, then $\mathit{lcm}(n, n') = p\_1^{\mathrm{max}(k\_1, m\_1)} \dots p\_a^{\mathrm{max}(k\_a, m\_a)}$.

It follows that if we go from node $u$ with value $b$ to node $v$ with key $b' = \mathit{lcm}(b, l\[v\])$ and $b' \ne b$, then $b' \ge 2 b$. Thus any special path from the source to the sink has length at most $\log\_2 k$ (which for the programming contest, where $k \le 10^6$, means at most $20$ edges followed).

---
Tags: algorithms, graphs, number-theory
---


# Question
Title: Help with proof involving weighted full binary tree
Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v\_1,v\_2,...,v\_n$, and weights associated with the leaf nodes: $w\_1,w\_2,...,w\_n$, the **cost of the tree**, denoted by $|T|$, is defined as: $$|T|=\sum\_{i=1}^{n}w\_il\_i$$ Where $l\_i$ is the depth of $v\_i$ in $T$.

Example:

The cost of the above tree is:
$0.25\times 4+ 0.18\times 4+0.5\times 3+0.4\times 2+0.31\times 3+0.2\times 4+0.1\times 4+0.65\times 3+0.2\times 3=8.7$

Now, I need to prove two things. I'll start with the first.
1. Let $T$ be a full binary tree with $n$ terminal (leaf) nodes, then $T$ has $n-1$ internal nodes.

The proof for this is not too difficult. Using induction on the number of terminal nodes, I can easily prove it. The second is not so trivial, and this is where I need help. Before I'll move on to what I'm trying to prove, I'll introduce another concept.
Let's associate now weights with **internal nodes**: the weight of an internal node is the **sum of the weights of its two children**.
Example:

Now for the shocker:

2. Given a full binary tree, the sum of the $n-1$ internal nodes is the cost of the tree.

This looks surprising at first, but when you rethink about it, it makes sense (the picture above demonstrates it). My problem is proving it.
I tried proving by induction, but I got stuck in the inductive step (the base case is obvious).

Any help would be greatly appreciated.

\**EDIT

Let me show exactly where I'm stuck:

Base case is easy.
The first way @Yuval Filmus suggested: For the general case, since the number of leaves $n$ is bigger than $1$, then the tree can be split to two trees; the left subtree of the root, call it $T\_l$ and the right subtree of the root, call it $T\_r$, each has $n\_l$ and $n\_r$ leaves ($n\_r,n\_l\geq 1$ and $n\_l+n\_r=n$).
Now, according to the induction hypothesis, the cost of $T\_l$ is the sum of the $n\_l-1$ internal nodes in $T\_l$, and the cost of $T\_r$ is the sum of the $n\_r-1$ internal nodes in $T\_r$.
I don't know what exactly does that imply with regards to the entire tree $T$...

The second way @Yuval Filmus suggested:
For the general case: $T$ (with its $n$ leaves) is obtained from a smaller tree, call it $T'$, in which two leaves was removed.
According to the induction hypothesis, the cost of $T'$ is the sum of its $(n-1)-1=n-2$ internal nodes.
Again, how should I proceed? I feel like something is missing...
So suppose I say the cost of $T'$ is: $|T'|=\sum\_{i=1}^{n-2}w'\_i$, where $w'\_i$ corresponds to an internal node. (it is denoted with apostrophe on purpose, to distinguish these weights from the $w\_i$s - the weights of the terminal nodes).
Am I on the right track?

# Answer
> 5 votes
There are two basic induction patterns for (non-empty) full binary trees:

1. A tree is either a leaf or consists of a root and two full binary subtrees.
2. A tree is either a leaf or can be obtained from a smaller full binary tree by adding two children to a leaf.

Your first question can be proved in both ways. In both cases, the base case is clear: if a tree is a leaf then it has $n=1$ leaves and $n-1=0$ internal nodes.

According to the **first way**, if the tree $T$ is not a leaf then it has a root and two subtree $T\_1,T\_2$. By induction we know that if $T\_1,T\_2$ have $n\_1,n\_2$ leaves (respectively) then they have $n\_1-1,n\_2-1$ internal nodes (respectively), and together with the root, this gives $n\_1+n\_2-1$ internal nodes for $T$, which is exactly one less than the total number of leaves.

According to the **second way**, the tree $T$ is obtained from a smaller tree $T'$ by adding two children to a leaf. If $T'$ has $n'$ leaves and $n'-1$ internal nodes, then $T$ has $n'-1+2 = n'+1$ leaves and $n'-1+1 = n'$ internal nodes, exactly one less than the number of leaves.

Your other statement can also be proved in both ways. I leave you the details.

# Answer
> 2 votes
Personally I would not prove the second statement ("the shocker") unless I was explicitly forced to do so by my professor.

The weight in a particular leaf is added to the weight of each of the nodes on the path from the leaf to the root. This is exactly the number of times the weight is counted in the cost of the tree, the depth of the leaf.

Done.

---
Tags: graphs, trees, binary-trees, induction
---


# Question
Title: The symbolic differentiation of univariate expressions
I was reading "Doug McIlroy: McCarthy Presents Lisp" and the phrase "symbolic differentiation of univariate expressions" triggered a faint memory of a demonstration of differentiation done in haskell using higher order functions. (I think my memory is of using the language to produce a function that is the differential of a function given.)

However I haven't been able to find any other reference to the above phrase in lisp or ML-based languages.

Does anyone have more information on this, and is "symbolic differentiation of univariate expressions" the same thing as the memory I described?

# Answer
You might be looking for automatic differentiation, which is an entire field of research; many techniques are known.
> 1 votes

---
Tags: terminology, functional-programming, mathematical-programming, computer-algebra
---


# Question
Title: set of Kolmogorov-random strings is co-re
given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings.

How can I show that RC is co-re

I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings? which just says that we know that by Kum96 we know that RC is Co-re

I was not able to find the proof of how that is proved

# Answer
We want to show $\overline{R\_c}\in RE$.

$\overline{R\_c}=\left\\{x|\exists M\hspace{1mm} s.t. \hspace{1mm} M(\epsilon)=x,|\langle M\rangle|\<|x| \right\\}$, i.e. $x$ is not a Kolmogorov-random string if there exists a Turing machine which outputs $x$ (say, when initialized with blank input), with description $\langle M\rangle$ shorter than $|x|$.

Given $x$, run all the Turing machines $M$ with description $|\langle M\rangle|\<|x|$ with empty input $\epsilon$, simultaneously (i.e. dont execute any machine for $i+1$ steps before executing all of them for $i$ steps). This is possible since the set of all Turing machines of length $\le |x|$ is finite. If one of the machines halts and outputs $x$, accept, otherwise keep running. If all the machines halted with output different then $x$, reject.

Clearly if $x\in \overline{R\_c}$ then our machine accepts, otherwise it either rejects or doesn't halt (which is the case if none of the machines outputs $x$ after some finite number of steps, and at least one of them doesn't halt).
> 7 votes

# Answer
Not only is the set of incompressible strings unrecognizable, *no* infinite set comprising of incompressible strings is Turing recognizable. Let's assume we could enumerate an infinite set of incompressible strings. Let the enumerator be $E$. Built a Turing machine $M$ ( $M$ disregards its input ) which first obtains its own description $\langle M \rangle $ by recursion theorem. Then it runs the enumerator $E$ and while enumerating the incompressible strings when it sees a string $s$ which is sufficiently longer than $\langle M \rangle $ ( sufficiently long depending on your method of encoding ), then $M$ prints $s$ and halts. This leads to a contradiction as $s$ turns out to be compressible, as it is outputted by $M$ where $\langle M \rangle \<\< |s|$.
I misread the question,sorry for that. Anyways as Ariel has proved the set of incompressible strings is co-recognizable. And I have shown that the set is not recognizable, which also tells us that the set is not decidable.
> 2 votes

---
Tags: computability, semi-decidability, kolmogorov-complexity
---


# Question
Title: Show that each of these languages is decidable for regular grammars
Show that each of these languages is decidable for regular grammars by presenting a clear algorithm for each. In each case, assume is the encoding of a regular grammar as a string and L(G) is the language generated by G.

a. ERegular = { | L(G) = ∅ }

b. InfiniteRegular = { | L(G) is infinite }

c. EQRegular = { | L(G) = L(H) }

Algorithms should use concepts such as reachability and product machine. You may assume that any regular grammar can be converted into a DFA without reproving this fact. You may assume that it can be determined whether one state can be reached (in one or more steps) from another within a DFA.

---

Hello, I'm having a bit of trouble on this problem. I know what a regular grammar, but what confuses me is the "show each language is decidable for regular grammars" part. What exactly does that mean? The TA told me my algorithm can be informal, but how should my algorithm be structured? I really need to see an example before I can fully understand this. Any help is appreciated!

# Answer
> 1 votes
Consider your first question. It asks, find an algorithm that, for each regular grammar $G$, answers "yes" or "no", depending on whether the grammar generates any strings of terminals or not. There are known ways to determine that, have you seen any? Suppose we rephrased it as, given a finite automaton, how can you tell whether it accepts any strings or not. There's a known algorithm for that, too. Do a little digging--they're both standard enough in intro theory that you shouldn't have any trouble finding them.

The other two can be answered in the same vein.

# Answer
> 1 votes
Probably something went wrong while copying your question. This is indirectly about the family of regular languages, but formally about deciding membership of a grammar $G$ in a family $\mathcal G$ of grammars with a certain property. Both $G$ and $\mathcal G$ are coded as strings, which is usual in the context of decidability problems. So, the language $\mathcal G$ you get is a string language consisting of grammars coded as strings. The particular coding is not very important. You may assume that the grammar can be decoded from the string.

For example, given a regular grammar $G$ (or actually the encoding $\langle G\rangle$), can you decide whether its language $L(G)$ is empty?

This is equivalent to the first question, the decidability of the language $\\{\langle G\rangle \mid L(G) = \varnothing \\}$.

Now you are asked to give a simple somewhat informal solution that answers the question $L(G)=\varnothing$.

---
Tags: computability, formal-grammars
---


# Question
Title: How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$
I am basically trying to solve the following question:

Given a set $P = \\{\\{1\\},\\{2\\},\dots,\\{n\\}\\}$ of $n$ sets of elements, our aim is to merge these elements into one set.

At each step, sets can be only merged pairwise.

How many different ways can this merge happen?

For instance, given $P = \\{\\{a\\},\\{b\\},\\{c\\},\\{d\\}\\}$:

After the first step we can end up with three different combinations: \begin{array}{c} P\_{11} = \\{\\{a,b\\}, \\{c,d\\}\\}\\ P\_{12} = \\{\\{a,c\\}, \\{b,d\\}\\}\\ P\_{13} = \\{\\{a,d\\}, \\{b,c\\}\\}\\ \end{array}

And all the sets will be merged after the second step: \begin{array}{c} P\_{2} = \\{\\{a,b,c,d\\}\\}\\ \end{array} All the examples I could find about recurrences is summation of two recurring functions such as

$T(n) = T(n) + T(n/2) + \Theta(n)$

However, I want to solve a recurrence relation where recurring function is multiplied by itself:

$T(n) = T(n^2-n)\*T(n/2)$

I am not sure that I write the recursion correct but this is what I want:

\begin{array}{l} n\\ \dfrac{n(n-1)}{2}\*\dfrac{n}{2}\\ \dfrac{n(n-1)}{2}\*\dfrac{n}{2}\*\dfrac{\frac{n}{2}\left(\frac{n}{2}-1\right)}{2}\*\dfrac{n}{4}\\ \end{array}

At first sight, the number of nodes in the recursion tree grows like $O(n) \rightarrow O(n^3) \rightarrow O(n^6) \dots$ at each level, which can be formulated as $n^{2k}$.

Since the size of the problem is reduced by a factor of 2, we have $\log n$ depth in the recursion tree. Therefore, $n^{2k} = \log n$ and $2k = \log\_{n}\log n$ which does not seem a reasonable size.

Where am I mistaken?

# Answer
If you have a recurrence involving *only* multiplication, take the logarithm: $$ \log T(n) = \log T(n^2-n) + \log T(n/2). $$ This converts it into an additive recursion. In your case this is not really a recursion since it defines $T(n^2-n)$ in terms of $T(m)$ for $m \< n^2-n$, but not every integer is of the form $n^2-n$.

Regarding your original question, try to relate it somehow to binary trees, which are known to be counted by the Catalan numbers.
> 4 votes

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


# Question
Title: How to show all possible implied parenthesis?
Can I use recursion to find out the possible parenthesis we can add to this expression: 2\*3-4\*5 ?

(2\*(3-(4\*5))) = -34

((2\*3)-(4\*5)) = -14

((2\*(3-4))\*5) = -10

(2\*((3-4)\*5)) = -10

(((2\*3)-4)\*5) = 10

I am not able to find out the right states for the recursion to proceed. As at any point we wouldn't know if it would have two open parenthesis or two closed parenthesis. I am just looking for ideas.

# Answer
I'm assuming the input expression does not contain parentheses.

The idea is that for each binary operator we pick it as the principle operator (which is at the root of the parse tree) and split the expression into two subexpressions. Then we solve the subproblems recursively. After that we combine those solutions prepending and appending parens and inserting the principle operator in the middle. Notice that there could be multiple solutions for both subproblems.

Also you need to figure out the base case for recursion.
> 3 votes

---
Tags: combinatorics, recursion
---


# Question
Title: Shortest path visiting all nodes in an unrooted tree
I have a tree. This tree has no particular root (free-tree). I want to find a **path that visit all nodes**. This path has to be the **shortest possible**.

All edges are considered to have a distance of 1.

My problem is not finding a Hamiltonian path, because I don't have any restriction on the number of times a node can be visited.

**We don't know the source node of the path**. The source has to be one allowing us to find the shortest path visiting all nodes.

# Answer
> 2 votes
Hint: Start from a source $s \in V$ to visit all vertices that $V$ is the set of vertices of the tree. All edges are visited twice except those which contribute to the longest path.

Then, the shortest possible path, visiting all nodes, is equal to $2 \times |E| - |P\_{L}|$, where $|E|$ denotes the number of edges, and $|P\_{L}|$ is the number of edges in the longest path. This can be achieved with time complexity $O (E)$.

# Answer
> 0 votes
In a DFS traversal of the tree (starting from an arbitrary node) every edge is traversed twice: once down and once up. Some of these edges need not be traversed down.

Say your DFS traverses the children from left to right. Then the edges drawn in red in the following figure need to be traversed once only (we don't need to traverse them on the way back from the deepest node).

Now we want to find a red path that is as long as possible. This is known as the diameter of the tree and it can be found in linear time. The diameter of the tree above is equal to 5 for example.

---
Tags: graphs, graph-traversal
---


# Question
Title: Don't understand the merge part of the mergesort
I understand how the divide part of the algorithm works and how it is meant to spread efforts.

What I don't understand is how would you merge blocks `[7][14]` and `[3][12]` or `[9][11]` and `[2][6]`. For the latter part it's easy enough as you just concatenate them ( although how do you know that? ) but for `[7][14]` and `[3][12]` you have to rearrange their indexes for the order to be increasing. How in software/pseudocode do you implement that step?

# Answer
> 5 votes
The merge subroutine takes two sorted arrays and creates one sorted array out of these two arrays. It does so in linear time.

Say the sorted arrays are `A = [1 2 3]` and `B = [2 3 4]`. Since these two are already sorted, the minimum is going to be either the first element in `A` or the first element in `B`. So take the minimum among these two values and append it to the output array `C`. We get `C = [1]` and the two arrays now look like `A = [2 3]` and `B = [2 3 4]` (you don't have to remove 1 from `A`, you can increment an index to implement this step).

Now iterate this process until both arrays are empty and the final sorted array is `C`.

---
Tags: algorithms, sorting
---