# Question
Title: Pac learnable when changing distribution
if H is Pac learnable according to

> Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable if there exist a function $m\_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and for every labeling function $f \colon X \mapsto \\{0,1\\}$, if the realizability assumption holds with respect to $H,D,f$, then when running the learning algorithm on $m \geq m\_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L\_{(D,f)}(h) \leq \varepsilon.$$

and the algorithm returns h\* (for specific S of size $m\_H(\varepsilon, \delta$) and distribution D) , I can define a distribution D' that gives 0 for each x s.t. h\*(x)=f(x) and that will give me $L\_{D'}(h\*)=1$. I am trying to understand why this is ok (not a contradiction for H being PAC), so I have 2 questions on this: $$$$ 1. my guess is that since the algorithm does not depend on the distribution but does on S (that depends on it), we will probably get with the new distribution D' a different S that will return a different h that keeps us with $L\_{(D',f)}(h) \leq \varepsilon.$ with probability $1 - \delta$. Is this the right explanation? $$$$ 2. After defining the new distribution D' is it right to say that (D',f,H) still hold the realizability assumption? I don't see why not but want to be sure.

> definition 2.1 (The Realizability Assumption) There exists $h\* \in H$ s.t. $L\_{(D,f)}(h\*) = 0.$. Note that this assumption implies that with probability 1 over random samples, S, where the instances of S are sampled according to D and are labeled by f, we have $L\_S(h\*) = 0$.

Thank you

# Answer
> 0 votes
I think the definitions in that book are unclear. If you note, the realisability assumption is not stated as an assumption *on anything*, nor as a standalone definition, so that already is a bit confusing. I have struggled to find one anywhere that is clear actually.

It appears to me that The Realisability Assumption is also dependent on the distribution $D$ and the labelling function $f$. That is the trio ($H, D, f$) can be realisable. $H$ in and of itself cannot be realisable.

It took me some sleuthing to come to this conclusion, and I hope it is the right one. I think you are nearly on the right lines of thinking. Here is my thinking:

As you say, if we choose a distribution that causes problems then perhaps we can prove that $L(h) = Err(h) \> 0$. If you assume $H$ is finite, and $f$ is not in $H$, then we can find problematic points $x$s and put positive probabilities on them. Then for every $h$ in $H$, $L(h) \> 0$; i.e. $H$ is not actually realisable with respect to any distribution.

We have made an assumption that $H$ is finite, but given that the book later on goes on demonstrate results with realisability, and finite $H$, I think we should assume that realisability and finite $H$ together are a valid consideration, and therefore, we cannot assume that realisability holds across any distribution over the domain set $X$. I think therefore we should assume that that is what they meant when defining realisability.

Similarly for the labelling function $f$. If $H$ and $D$ are realisable, independently of $f$, then in the case where $H$ is finite and contains only one hypothesis $h$, we can choose an $f$ that is different to h on the whole domain, which would result in $Err(h) = 1$.

So here's how I would state the Realisability Assumption:

> Definition (The Realisability Assumption) Given a learning problem with distribution $D$ over the domain set, and labelling function $f$, then a set of hypotheses, $H$, is Realisable if there exists $h\* \in H$ s.t. $L\_{(D,f)}(h\*) = 0$.

Note that you do not need to know what $D$ and $f$ are to assume that $H$ is realisable with respect to them. We can just assume that $H$ is realisable with respect to them, whatever they may be.

So, assuming realisability in PAC Learnability also restricts $D$ and $f$ to be those which are realisable w.r.t. $H$.

---
Tags: machine-learning
---


title: Prime Implicants in Boolean Function

text:
# Question
Title: Prime Implicants in Boolean Function
A Boolean function $F(X\_1, X\_2, X\_3, X\_4, X\_5, X\_6)$ of six variables is defined as $F = 1$, when three or more input variables are at logic 1. otherwise 0. How many essential prime implicants does F have?

---

How to visualize this problem. A Six Variable k-map is very difficult to manage. Any hints?

# Answer
### Hints

Here are two independent hints.

* Try an easier case such as exercise 1 or exercise 2 below.
* Can you find one implicant? Can you expand that implicant to a prime implicant? Can you find more?

### Answer

$X\_1X\_2X\_3$ is an implicant since $F$ becomes 1 when $X\_1, X\_2, X\_3$ are 1.

Since none of $X\_1X\_2$, $X\_1X\_3$ and $X\_2X\_3$ is an implicant, $X\_1X\_2X\_3$ is a prime implicant.

Similarly, all $X\_iX\_jX\_k$ are prime implicant where triple $i,j,k$ are different from each other. There are $\binom 63 = 20$ of them.

---

Can there be other prime implicant? No. Here is how to see it. Suppose $A\_1A\_2\cdots A\_m$ is a prime implicant, where each $A\_i$ is one of $X\_1, \cdots, X\_6, \overline X\_1, \cdots, \overline X\_6$.

1. None of $A\_i$s is $\overline X\_1, \cdots, \overline X\_6$. Otherwise, we can remove them to get a larger implicant.
2. The number of $A\_i$s that are one of $X\_1, \cdots, X\_6$ must be at least 3. Otherwise, $F$ can become 1 when only those $X\_i$s are 1, i.e., less than 3 of input variables are 1.
3. The number of $A\_i$s that are one of $X\_1, \cdots, X\_6$ must be at most 3. Otherwise, we can select $A\_{i\_1},A\_{i\_2},A\_{i\_3}$ that are $X\_1, \cdots, X\_6$. $F$ can be expanded to the implicant $A\_{i\_1}A\_{i\_2}A\_{i\_3}$

---

An essential prime implicant is an prime implicant that covers an output of the function that no combination of other prime implicants is able to cover. Based on symmetry, we should expect that every prime implicant is an essential prime implicant, which is indeed the case. Can you find the output that is covered only by $X\_1X\_2X\_3$?

In summary, there are 20 essential prime implicants of $F$, which are $X\_1X\_2X\_3,X\_1X\_2X\_4,X\_1X\_2X\_5,X\_1X\_2X\_6,X\_1X\_3X\_4,X\_1X\_3X\_5,X\_1X\_3X\_6,X\_1X\_4X\_5,X\_1X\_4X\_6,X\_1X\_5X\_6,$
$X\_2X\_3X\_4,X\_2X\_3X\_5,X\_2X\_3X\_6,X\_2X\_4X\_5,X\_2X\_4X\_6,X\_2X\_5X\_6,$
$X\_3X\_4X\_5,X\_3X\_4X\_6,X\_3X\_5X\_6,$
$X\_4X\_5X\_6$.
It is not necessary to draw or visualize the Karnaugh map.

### Exercises

**Exercise 1.** A Boolean function $B(X\_1, X\_2)$ of two variables is defined as $B = 1$, when one or more input variables are at logic 1. Otherwise 0. How many essential prime implicants does B have?

**Exercise 2.** A Boolean function $C(X\_1, X\_2, X\_3)$ of three variables is defined as $C = 1$, when two or more input variables are at logic 1. Otherwise 0. How many essential prime implicants does C have?

**Exercise 3.** A Boolean function $F\_2(X\_1, X\_2, X\_3, X\_4, X\_5, X\_6)$ of six variables is defined as $F\_2 = 1$, when two or more input variables are at logic 1. Otherwise 0. How many essential prime implicants does $F\_2$ have?

**Exercise 4.** A Boolean function $P(X\_1, X\_2, X\_3, X\_4, X\_5, X\_6)$ of six variables is defined as $P = 1$, when one or more input variables among $X\_1,X\_2,X\_3$ are at logic 1 and one or more input variables among $X\_4,X\_5,X\_6$ are at logic 1. Otherwise 0. How many essential prime implicants does $P$ have?
> 2 votes

# Answer
An implicant of $F$ is a partial assignment to the variables of $F$ which guarantees that $F$ is satisfied. A prime implicant is a minimal implicant, that is, an implicant that is no longer an implicant if we remove any single variable.

Let us start by finding all the implicants of $F$. Let $\alpha$ be any partial assignment to the variables of $F$, and suppose that $\alpha$ assigns $k$ variables to true. We can complete $\alpha$ to an assignment by assigning the rest of the variables to false, in which case we get an assignment containing $k$ true variables. Hence $\alpha$ can only be an implicant if $k \geq 3$. Conversely, it is not hard to check that if $\alpha$ assigns at least 3 variables to true then it is an implicant of $F$.

When is an implicant a prime implicant? It must be a partial assignment with at least 3 true variables, such that if we remove any single variable, there are at most 2 true variables. Can you figure out how all such implicants look like? Give it a try.

As an aside, your function is monotone, and so its prime implicants are also known as *minterms*. Minterms have a special structure – they cannot be arbitrary partial assignments. I'll let you figure out the special property that minterms have.
> 1 votes

---
Tags: boolean-algebra, digital-circuits
---


# Question
Title: A question about decidable and undecidable problems
Maybe this question is not very smart but I really wanna learn this thing. also, I need someone who is familiar with printing 42 problem and zero program problem.

This is the context:

> Consider the problem of determining whether a number belongs to a set. This problem is easy for the following sets:
>
> * The set of odd numbers
> * The set of even numbers
> * The set of prime numbers
> * The set of numbers that can be written as a sum of five square numbers
>
> For every one of these sets, a program can be written that accepts a whole number as input and—depending on whether the input is in that set—outputs a yes or no answer.
>
> However, there are other types of sets. This chapter has shown that there are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not. For example,
>
> * The set of numbers of programs that will output 42 for some input
> * The set of numbers of programs that always output a 0"
>
> The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us by Noson S. Yanofsky

First of all, I should say that I am a self-learning in this area, so I don't have very good knowledge about this stuff. so, in this context, I don't get two parts. If anyone could help me, I would very appreciate it.

the first part is: "there are other types of sets. This chapter has shown that there are certain sets of whole numbers for which no computer program can be written that can decide if **they** are in the set or not." what are they. is the writer talking about inputs/ arbitrary whole numbers or certain sets of whole numbers?

second, I don't get this part at all and somewhat, this part is making me confused about the former question:

> * The set of numbers of programs that will output 42 for some input
> * The set of numbers of programs that always output a 0"

if you rewrite this part in another form, I think I would comprehend it because I think this is a grammatical confusion. thank you in advance

# Answer
> 2 votes
When the author talks about "number of programs", they mean numbers that represent programs. Normally, we think about programs of being strings of characters (e.g., Java programs) but we can also represent programs as numbers. The easiest way to see this is to think how they're represented inside your computer. That string of characters is just a big list of zeros and ones inside the computer, and a "big list of zeros and ones" is just a number written out in binary. Formally speaking, "programs" here are probably Turing machines but it won't hurt you to think of computer programs in whatever language you're familiar with.

The technique of using natural numbers to represent arbitrary objects like this is sometimes called "Gödel numbering", as it was first used by Kurt Gödel to prove things about logic. He encoded logical formulas as numbers, which allowed him to write formulas about formulas, in much the same way as a compiler is a computer program that operates on computer programs, and a universal Turing machine is a Turing machine that operates on Turing machines.

> "... \[T\]here are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not." What are "they"? Is the writer talking about inputs/arbitrary whole numbers or certain sets of whole numbers?

That's not a very well-written sentence. The interpretation that makes most sense to me (the only one I can think of that makes the statement true) is, "There are certain sets of whole numbers for which no computer program can be written that decides whether its input is in that set."

---
Tags: undecidability, decision-problem
---


# Question
Title: All superlinear runtime algorithms are asymptotically equivalent to convex function?
Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?

All the examples that I could think of satisfy the above mentioned requirement. For example, all polynomials are convex on $\mathbb N\_+$. Additionally, $n\log(n)$ is convex from $n=2$ and on, so it's asymptotically equivalent to convex function.

# Answer
> 9 votes
> Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?

No. A simple example is $$T(n)=\begin{cases}n & \text{ when } n \text{ is odd,}\\ n^2 & \text{ when } n \text{ is even.} \end{cases}$$

---

What if we also require $T(n)$ be strictly increasing?

The answer is still no. A simple example is

$$T(n)=\begin{cases}2^{(n+1)^2} & \text{ when } n \text{ is odd,}\\ 2^{n^2}+1 & \text{ when } n\text{ is even.} \end{cases}$$

Since $\displaystyle\lim\_{k\to\infty}\frac{T(2k)}{T(2k-1)}=1$ and $\displaystyle\lim\_{k\to\infty}\frac{T(2k+1)}{T(2k)}=\infty,$ there is no convex function $f$ such that $T(n)=\Theta(f(n))$.

---

**Exercise 1.** What if we also require both $T(n)$ be strictly increasing and $T(n+1)/T(n)$ be bounded?

**Exercise 2.** Let $T\_1$ and $T\_2$ be two increasing functions such that $T\_2(n)\not=O(T\_1(n))$. Show that there is a function $T(n)$ that is bounded between $f\_1$ and $f\_2$ such that there is no convex function $f(n)$ such that $T(n)=\Theta(f(n))$.

# Answer
> 1 votes
No. Consider $T(n) = n$ if $n$ is even, $T(n) = 2^n$ if $n$ is odd.

---
Tags: complexity-theory, algorithm-analysis, time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Finding maximal and average number of time slots in an Adaptive tree walk protocol
Tried to research here and on other sites with no luck regarding finding the maximal and average number of time slots in an Adaptive tree walk protocol. i'll explain what i mean here:

In a simple(provided an image for illustration at the end of the post) Adaptive tree walk protocol, Divided by time slots where a station can only transmit at the beginning of each time slot.

If for instance stations C and A want to broadcast in time t=0 with probability p(for simplicity) (None of the other stations want to transmit at all), Is it possible to know the maximal or average number of time slots that will pass until(including) the slot in which there will be a successful broadcast?

Simple network diagram i am asking about:

Note: for simplicity, in this question, no other station except C and A want to broadcast at all

# Answer
> 0 votes
It is clear that you cannot know the maximum if $p \neq 1$, because there is always some chance, no matter how small, that neither station will transmit after any $n$ attempts.

However, if $p=1$ then the answer is always **3** (both average and maximum): first all stations under 1 transmit (both A and C), then under 2 (same), then under 4 (just A – success).

Regarding the average (excepted value), it's a combination of two things: the average tries you need until any station transmits, and the expected value of a successful transmission assuming at least one station transmitted. The first is a standard geometric distribution, where the expected value is $E=1/p$.

---
Tags: computer-networks, communication-protocols, protocols, network-analysis
---


# Question
Title: Is purely functional programming in some situations less efficient than imperative programming?
I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that some of the data types don't exist in functional languages. For example, it may be hard to implement hash data structures or mutable arrays.

With that in mind, is purely functional programming in some situations algorithmically more expensive than imperative programming? For example,

* If I want to implement timer heap with O(1) peeking of next timer to expire, O(log N) removal of next timer to expire, O(log N) addition of new timer, O(log N) removal of arbitrary timer and O(log N) adjustment of timer expiration time, can I implement the timer heap in a purely functional programming language?
* If I want to implement a timer wheel, can I do so in a purely functional programming language?
* If I want to implement O(1) lookup in a set or a map, meaning in practice hash structures are needed, can I do so in a purely functional programming language?
* If I want to implement a ring buffer for efficient communication between threads in a producer-consumer pattern, can I do so?
* If I want to maintain a a list of free TCP ports in a firewall, doubly linked list would be a suitable O(1) data structure for that, allowing O(1) removal of an arbitrary port, but can I do so in a purely functional language?
* If I want to have a fast and efficient O(1) bit set, can I have such a construct in a purely functional language?

Note I'm not interested in large vs small constant in the runtime. I'm interested in runtime becoming fundamentally different, e.g. O(log N) instead of O(1). Of course functional algorithms may be less efficient due to the extra overheads of added abstraction in terms of runtime constant.

# Answer
Yes. There are problems where we can prove there is a $\Omega(\lg \lg n)$ factor slowdown. We also know that the slowdown is at most $O(\lg n)$ in all cases. See What classes of data structures can be made persistent?.
> 4 votes

# Answer
Another answer is that imperative (updatable) data structures can be used in pure functional program via monads (such as Haskell ST monad) or unique types (in Clean).
> 1 votes

---
Tags: algorithms, runtime-analysis, functional-programming, imperative-programming
---


# Question
Title: Asymptotic analysis with factorial and exponential
I'm solving a complexity question where I have:

$$ n!/2^n $$

The goal is to find an upper bound for this.

My idea is using the fact that: $$ n! = O(n^n)$$ $$ n!/2^n = O((n/2)^n) = O(n^n)$$

But is a correct upper bound, and if so is it the tightest upper bound that can be found? I know that n! is asymptotically larger than 2^n, but I'm struggling to do a tighter analysis.

# Answer
Stirling's approximation states that $$ n! \sim \sqrt{2\pi n} (n/e)^n. $$ It follows that $$ n!/2^n \sim \sqrt{2\pi n}(n/2e)^n = \Theta(\sqrt{n}(n/2e)^n). $$
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Satisfiability Toward A Sequential Circuit
Define a sequential circuit model be a directed graph with each vertices being a boolean gate. The difference is that we allow cycles in the boolean circuit. Each cycle will determine a boolean equation.

For example, constructing a loop by connecting the input and output of a negation gate will yield the equation $x=\lnot x$, which is not satisfiable. Given such circuit, the "satisfiability" in the sense naturally occur. My question is:

> Is determining whether this circuit can be satisfied known to be hard or easy? Furthermore, is finding or enumerating these configuration known to be hard or easy?

# Answer
> 2 votes
OK so now I figured this out. The problem is $NP$-complete. We could simply verify an assignment by checking each gate as an equation. For solving SAT of boolean function A(x), simply construct a equation, $y=y\otimes\lnot A(x)$ would suffice.

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


# Question
Title: Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle
Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF\_p \times GF\_p \rightarrow GF\_p$ which has an unknown degree $d$ polynomial, with $1 \< d \< p / 4$.

Although $f$ is unkonwn to us, there is an erroneous oracle $O$ satisfy the following property: $\underset{(x,y)\in GF\_p \times GF\_p}{Pr}\[O(x,y) = f(x,y)\]\ge1 - \frac{1}{20d}$.

The question asks us to come up with a randomized algorithm which makes $O(d)$ queries to the oracle $O$ and returns the correct value of $f(0,0)$ with probability at least 0.9.

The following is my thinking process: the probability of $O(0, 0) = f(0, 0)$ is at least $1 - \frac{1}{20d}$ according to the condition before. If the probability is at least 0.9, then $d$ should be $d \ge \frac{1}{2}$. Then $p$ should be larger than $2$. We can assume the expression for $f$ is $a\_db\_dx^dy^d + a\_db\_{d-1}x^{d}y^{d-1} + a\_{d-1}b\_dx^{d-1}y^d + a\_{d-1}b\_{d-1}x^{d-1}y^{d-1} + ... + a\_0b\_0$. There are total $d^2$ number of items in the function. The randomized algorithm is that we could randomly select the value of $x$ and $y$ from $GF\_p$, and at the following $d^2$ steps, we decide the parameters of the polynomials.

```
for i from 1 to d steps:
    for j from 1 to d stpes:
         randomly assign the values of other parameters except a_ib_j;
         solve the value of a_ib_j using the randomly assigned x, y and
         the result queried from Oracle with x and y;

```

This is just my general idea. The problem is I do not know the degree $d$, so I cannot decide the exact number of steps $d^2$. And even if I know the degree $d$, how can I manage to decrease the time from $O(d^2)$ to $O(d)$?

Or maybe I am going in the wrong way. Can somebody help me with this? Any help would be appreciated. Thanks in advance.

# Answer
> 3 votes
Some hints:

Could you solve the problem if the function was of the form $f : GF\_p \to GF\_p$, i.e., a univariate polynomial? I suggest solving that special case first. The below are some hints on how to do that:

If the error was zero, would you know what to do? Could you devise a strategy that would always work in that situation? How many queries would your strategy need?

Now suppose you applied your strategy, in the situation where there could be errors (but with the error probability bounded as you've described). What's the probability that your strategy gives the wrong answer? What's the probability that your strategy gives the right answer?

You might find it useful to use a union bound.

Can you think of any way to check whether a possible solution is correct?

Finally, once you can solve the univariate case, can you think of any way to repeat that procedure multiple times to handle the situation of a polynomial in two variables?

---
Tags: complexity-theory, turing-machines, discrete-mathematics
---


# Question
Title: Functional dependencies , minimizing SUU->V
Can SUU-\>V or any functional dependency that contains two or more times each attribute be simplified to the same dependency with one attribute? So SUU-\>V becomes SU-\>V or STTT-\>Q becomes ST-\>Q ?

# Answer
> 0 votes
Yes, each side of a Functional Dependency is a set of attributes, not a multiset, so `SUU -> V` can be simplified to `SU -> V`.

If you think about the definition of Functional Dependency you will understand why this is true.

---
Tags: database-theory, functional-dependencies
---


# Question
Title: Time complexity of finding subsequences of a string segmented into parts
Let $S$ be a string of length $N$, consisting of digits 0 to 9. For convenience, we assume $N$ to be a multiple of 3.

Then, we split $S$ into $N/3$ equal parts, each of length 3.

For each equal part, we count/enumerate all subsequences of all lengths up to 3.

Finally, we total up how many such subsequences are there altogether.

What is the time complexity of the above algorithm? Thanks.

I give a more concrete example in case the above is not clear. Suppose $S=\`111211'$, of length 6.

We first split it into 2 parts $\`111'$ and $\`211'$. For the first part $\`111'$, we count that there are 3 subsequences of $\`11'$ (note that subsequences do not have to be consecutive unlike substrings), for the $\`211'$, there is 1 subsequence of $\`11'$, so in total there are 4 subsequences of $\`11'$. We do this for all possible subsequences up to length 3, even for subsequences that do not appear such as $'000'$, we count that it occurs zero times.

---

I am new to time complexity, but I did try to calculate it myself. For each part of length 3, the time complexity of enumerating the subsequences is $O(1)$? Hence, in total, we have to repeat it $N/3$ times, so the overall time complexity is $O(N)$? Is that correct? Thanks a lot.

# Answer
> 2 votes
Yes, your analysis is correct.

---
Tags: algorithms, algorithm-analysis, time-complexity, subsequences
---


# Question
Title: What mathmatical model shall be used for describing P2P processes interaction?
I am creating a distributed service system. It runs in the cloud on heterogeneous hardware. I am using C# .NET for business logic and C++ for different physics\chemical calculations. Having three logic applications and 2xN heavy calculation applications. There are external web clients, which connect to logic applications, but for now, we do not care for them. Therefore, server side connected applications:

* They interact via heavily extended proprietary ZeroMQ analog middleware - so there is a finite set of communication patterns between applications.
* There is a protocol (Protobuf based) via which applications encode messages. Different types of messages are sent on same communication channels (for example 10 types of requests with 10 types of responses for each Request-Reply channel)

I wonder if there is a mathematical model in terms of which I can describe my Peer to peer services system. Of course, I need a model that can be useful: one that after its creation I would be capable to gain some new knowledge about properties of my distributed application.

I looked at a few

* Petri networks and they can provide reachability, liveness
* Queueing theory, which generally seems to lead to Stochastic Petri Nets

After few days of research, my small brain collapsed because I need a Colored Hierarchical Stochastic Petri Net and all I would get from it would be reachability and liveness of components and connections may be also maximal/normal messages passing volumes.

To create such model timing, message type’s interaction and publishing stats would be required as well as directions of message streams. Computational logic can stay as a black box.

So I wonder - is there any other mathematical model which could provide more data on system behavior in terms of prediction/reasoning, what data it would require?

# Answer
If you're looking for a single model that describes all relevant aspects of your system, you'll have a hard time. And building the model will take as much effort as implementing the system itself, if not more. Therefore, break the system down into different aspects, and consider different modelling techniques for each. Examples for aspects might be:

* The protocol between two of the peers. This could detect deadlocks or pointless messages in the protocol. Repeat for every combination of two types of peers.
* Behavior of a single peer as it connects with different types of peers. Could there be problems if a message from peer type X comes in while processing another message from peer type Y?
* Behavior of the network as peers come and go. Will it stay connected? Here, you'd just model "peer connects" and "peer disconnects", rather than the sequence of messages for connecting and disconnecting.
* Performance depending on the number of peers of each type.
* ...
> 1 votes

---
Tags: distributed-systems, computation-models, message-passing, petri-nets, peer-to-peer
---


# Question
Title: Don't understand minimax algorithm in terms of chess
I'm new to minimax algorithm, but i understand it's entire concepts as it's easy, my biggest issue is understanding it's implementation to my chess game, no internet solution answers this question

black or white players comprises of several pieces, so what piece is the AI predicting moves for, as the player could move any of their 16 pieces?

all i keep seeing is that we need to write the code to look several moves ahead in which the player could potentially make, my issue is that there are multiple pieces the player could pick from so what moves exactly are we talking about and how would the AI determine which of its pieces to move based on that.

I just need a brief explanation, no source code or how to's. I've spent days trying to wrap my head around this concept.

# Answer
In minimax you fully explore the game tree. So the answer to "which piece" is *all of them*. All possible moves for all movable pieces. And then it selects the minimum or maximum (depending on the depth) out of those options.

Obviously this isn't feasible which is why we never apply raw minimax to chess. It is always with other optimizations such as alpha-beta, and stopping after a certain depth and using a heuristic evaluation of that position instead of continuing.
> 1 votes

# Answer
You write a function that looks at a position and gives it a value. The value should be higher for good positions and lower for bad positions.

Strategy 1: You try all your possible moves, evaluate the position after each move, and pick the move that produces the highest value.

Strategy 2: You try all your possible moves, then assume that the opponent will move according to Strategy 1. You pick the move that produces the highest value after the opponent moved according to Strategy 1.

Strategy 3: You try all your possible moves, then assume that the opponent will move according to Strategy 2. You pick the move that produces the highest value after the opponent moved according to Strategy 2.

Your guess is what strategies 4, 5, 6 and 7 are :-) Of course each strategy is more time consuming than the previous one, so you stop when you run out of time. And there are a few tricks to make the evaluation faster.
> 1 votes

---
Tags: algorithms, artificial-intelligence, minmax-algorithm
---


# Question
Title: DFA multiple accepting states to Regular expression
I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states.

If I understand this DFA correctly, it recognises:

empty strings or strings with any number of `b` =\> `b*`

or

`a` followed by any number of `b` =\> `ab*` or `aa` followed by any number of `b` =\> `aa(b*)`

So the closest I have got is `b*+(a+aa)+(a+aa)b*` but I know this is not correct, since it doesn't recognise strings such `aabaabab`.

I have been using http://ivanzuzak.info/noam/webapps/fsm\_simulator/ so I can see I don't know how to make the transition back to `Q0` from `Q1` or `Q2` when there is a `b`.

I took a look to How to convert finite automata to regular expressions? but the explanations are way above my current level of understanding.

Could anybody help me finding where I'm going wrong and how could I fix it?

Many thanks in advance.

# Answer
Your DFA accepts all words not containing $aaa$. Such words are built of the following "building blocks": $b,ab,aab$. Additionally, a word may end with $a,aa$. In total, we get the regular expression $$ (b+ab+aab)^\*(\epsilon+a+aa). $$
> 1 votes

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


# Question
Title: How precise to be when describing a Turing machine?
I'm kind of new to the theory of computation and I was working on this problem:

> We say that a Turing machine $M$ **uses** $k$ squares of tape for an input string $w$ if and only if there exists a configuration $(q, u\underline{a}v)$ of $M$, such that starting with input $w$, $M$ yields $(q, u\underline{a}v)$ and $|uav| \geq k$.
>
> Now show that the following problem is solveable: Given a Turing machine $M$, an input string $w$ and a number $k$ does $M$ **use** $k$ squares of tape with input $w$?

So the solution I came up with is this:

If it is solvable there has to be a Turing machine $M^\*$ that decides $$U = \\{\ll M\gg\ll w \gg \ll k\gg\ :M\ \text{uses}\ k\ \text{squares of tape with input}\ w\\}$$

And I describe such a machine:

$M^\*$ writes in it's tape $w$ and starts operating as $M$ would. After each step of $M$, $M^\*$ counts the number consecutive squares of tape from the start of the tape until it finds an empty square, and if that number is $\geq k$ it goes into an accept state and halts. If not, it continues its operation as M would. If $M$ halts without having used at least $k$ steps, $M^\*$ goes into a reject state. So $M^\*$ decides $U$, and thus the problem is solveable.

So my questions are these:

Is my solution correct?, and

Is my description of $M^\*$ precise, or say, good enough?

# Answer
> 2 votes
You are asking two different questions: whether your solution is correct, and whether the level of description of your Turing machine is appropriate. I will answer them separately.

**Correctness** Your Turing machine $M^\*$ is not guaranteed to halt. In other words, your solution is incorrect. The missing observation is that if a Turing machine uses only space $k$, then there is an upper bound on the number of steps that it can run without getting into an infinite loop.

**Level of description** Here you should be asking two questions:

1. What does it mean to describe a Turing machine?
2. How do I prove that a certain language is decidable?

The level of description of Turing machines is a touchy subject. Usually they are described quite informally. The level of description should be such that in principle you could convert the informal description into a formal Turing machine. In practice, I suggest looking at some examples to get the general feel.

As to how to prove that a language is decidable, there is no need to describe a Turing machine. Decidability can be proved using any model of computation. In particular, you can use the "English" model of computation, in which you describe how to decide the problem in the English language (or in any other language). For example, you could say "Simulate $M$ on $w$, and if it ever uses more than $k$ space, immediately reject; otherwise, once $M$ halts, accept". (This is just your incorrect solution.)

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


title: What would be the consequences if P=NL

text:
# Question
Title: What would be the consequences if P=NL
I haven't found anything in the literature that suggests what would happen if that is the case. Thank you, Akash

# Answer
> 3 votes
$NL=P$ is not considered likely by the experts.

I found a few SE questions on this topic: \[1\] \[2\]

The corollaries include:

> $P\subseteq L^2$ by Savitch's theorem
>
> $NC=P$ by the Squeeze theorem
>
> $EXP=PSPACE$ by $P\subseteq polyL$

I would like to include or exclude $P=L^k$, $k\in\[1,2\]$, but I have not collected sufficient evidence for or against that conclusion.

---
Tags: complexity-theory
---


# Question
Title: Add type checking/inference to my programming language
I am currently creating my own compiled programming language, and I have come to a point where I would like to start working on the type system and introduce some type checking. Ideally I would like to introduce type inference.

Right now I'm using the Visitor pattern to traverse the AST produced by the parser. I started implementing a pretty naive and ugly solution, but wasn't very happy with it. It seemed pretty hacky. Type checking that fits with this pattern would be great, but not critical.

I have looked into algorithms like the Hindley-Milner. I'm developing the programming language in Swift, so I found this GitHub gist that shows how it can be implemented, but opening the lid on this code immediately gets me to Lambda Calculus, which seems like a beast. I know Swift uses a variant of the Hindley-Milner type inference, so that would be incredibly sexy to implement, but it's way over my head at this point.

**Since this is my first programming language, what's a good first attempt at a type system with type checking, possibly with type inference?**

# Answer
> 0 votes
You could start with the simple cases of Swift. Literals have type “Literal”, for example, and known variables have their known types. When you evaluate an expression you may know what type you want and evaluate accordingly, or you don’t know and get the type from the expression.

(Anyone not knowing the language: let x: Int = 7/2 assigns 3. let x: Double = 7/2 assigns 3.5 because assignment to Double wants a Double expression, therefore / wants two Double operands, therefore the literals 7 and 2 are Double).

Keep in mind you can always report an error if you can’t handle a situation, as long as the code can be changed to work without complaints.

---
Tags: compilers, type-checking, type-inference
---


# Question
Title: Start learning about Theory of Distributed Systems?
What's the best way that anyone can do to have a good introduction to the theory of distributed system, any books or references, and topics should be covered first and requirements to start learning in this topic.

# Answer
Roger Wattenhofer's *Principles of Distributed Computing* lecture collection is also a good place to start.

It is freely available online, it assumes no prior knowledge on the area, and the material is very well up-to-date — it even covers some results that were presented at conferences a couple of months ago.
> 22 votes

# Answer
Both of the books mentioned in the other posts are good, however I like:

* Design and Analysis of Distributed Algorithms, Nicola Santoro.
* Introduction to Distributed Algorithms, Gerard Tel.

Lynch and Wattenhofer, two big names in Distributed systems theory, focus "a lot" on synchronous systems. On the other hand, Santoro and Tel focuses more on asynchronous systems (without forgetting synchronous systems). Their opinion is that synchronicity of a distributed system is an "additional assumption" ! (that is, by nature, a distributed system is asynchronous). Given this, you will find more focus on message complexity, while on the other books the focus is given to time complexity. It is a different school in distributed computing in my opinion.

N. Santoro book was the book I used for studying (N. Santoro is my teacher actually). Following the book, you would master the main fundamental ideas of distributed computing. It is based on course notes, and research the author was involved in. This is why it is not the most complete book. But it s very well written !

For G. Tel book, there is an interesting level of formalism. I like that he includes a chapter for self-stabilizing distributed algorithms. I think it contains more topics than N. Santoro book.

Another book widely available is Distributed Computing (Attiya and Welch - two well known scholars with great impact on the field). I used it as a reference for few times, but i cant give a judgment.
> 11 votes

# Answer
A good start would by Distributed Systems by Nancy Lynch. It is perhaps a little dated, but nothing is wrong with the book as such. An impossibility result does not change with time.
> 8 votes

# Answer
All of the mentioned books are awesome, but I recommend you the James Aspnes Notes on Theory of Distributed Systems. It is a very good and up-to-date book that explores theory aspects of distributed systems. It is also free!

I used this notes when I was TA and students were very happy about it. It has many questions with their solutions.
> 7 votes

# Answer
A Course on Deterministic Distributed Algorithms by Jukka Suomela.

Is about:

* distributed systems as a model of computation.
* distributed algorithms in the port-numbering model.
* optimisation problems about vertex covers and edge dominating sets.
* networks with unique identifiers.
* ramsey theory and application of the theory.
> 4 votes

# Answer
I would add **Introduction to Reliable and Secure Distributed Programming** by Christian Cachin, Rachid Guerraoui and Luís Rodrigues (amazon link).

This book is great as it builds from the fundamentals on the theory of distributed programming, with a large coverage on relevant topics like *consensus* and *Byzantine agreement*.
> 0 votes

# Answer
The book Distributed Systems: Concepts and Design by George Coulouris, Jean Dollimore, Tim Kindberg and Gordon Blair.
> -2 votes

---
Tags: reference-request, education, distributed-systems
---


# Question
Title: Why are both caller-save registers and callee save registers needed?
I am having a difficult time understanding callee and caller-save registers. I get that caller-save registers are those which are needed after function call and hence caller saves them in caller prologue and restored in caller epilogue. Callee-save are those who are used by callee and are saved in callee prologue and restored in callee epilogue. But why are both needed? If caller is saving the needed registers already, why should callee save them again on use? I am really confused.

# Answer
Let's see. CPU have, f.e., 16 registers. If subroutine modifies them, they should be saved before that and restored later. Now, who should do that?

All 16 registers can be saved by caller, or all 16 registers can be saved by callee, or mixed scheme may be used. In this schema, 8 registers is considered as transient - caller don't expect that their contents will be left intact after a call. Thus callers usually use these registers only for temporary data, i.e. computations between calls. But in a few cases when these registers contains non-transient data, caller has to save their contents.

Other registers are considered as permanent, so caller expects that they are left untouched by callee. But in the cases when callee really needs to use more registers, it needs to save/restore their contents.

Why hybrid scheme is advantageous - because usually each procedure needs a few registers for transient data, so by having convention that these registers can be modified by callee, you can reduce calling sequence and therefore make procedure calls a bit faster and more compact.

OTOH, if we consider some registers as "permanent", we can try to avoid using these registers in leaf procedures (i.e. those not calling other procedures) and avoid saving/restoring these registers in leaf procedures. Since cpu usually spends most of time in leaf procedures, this also means quite substantial speed improvement.

So, by splitting registers into two classes, we can make program faster and shorter - leaf subroutines try to not use "permanent" registers and as result don't need to save/restore any. OTOH, other procedures try to don't use "transient" registers to hold values through calls, thus avoiding need to save/restore them.

So, hybrid scheme makes program more efficient compared to any of two pure schemes.
> 2 votes

---
Tags: programming-languages, functional-programming
---


# Question
Title: How to check if a list of XY coordinate meet the safety distance to each others?
My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I draw a circle with radius R at every points, would any circle cross other circles on the plane.

I want to code this in Python, if that matters.

# Answer
The problem you are solving has many well-known efficient algorithms.

The problem is to find closest pair of points in the plane.
If the closest pair have distance less than the safety distance, you already have a pair.
If not, no other pair can have a less distance, and hence all pairs are safe.

One efficient way to solve this problem is using divide and conquer. The algorithm is practical and easy to implement. It has run-time $O(n \log n)$ (check the notes at the end).

It might be an over-kill, but as efficient from the theoretical point of view, to build Delaunay-Triangulation over the set of points and compare each point to its neighbors in the triangulation, which is also achievable in $O(n \log n)$.

There are many libraries that offer a ready-to-use Delaunay-Triangulation (you can check CGAL-Boost library for C++), which makes it an easier way to implement that the previous method.

**ps.** Another very well-known approach, used in many different problems is line-sweep. There is also a line-sweep $O(n \log n)$ algorithm for Closest pair of points problem. (please check the link).
> 3 votes

# Answer
If you have many points, say a million, you want to do something that is faster than comparing each point to each other point.

There is a simple method that is far from perfect but will give you a significant advantage:

You start by sorting all the points by their x-value. The way you describe it, you want the distance between any two points to be at least 2R. So you iterate through the points, and for each point with x-coordinate X, you only examine the following points in the sorted array as long as their x-coordinate is at most X + 2R.

You know you have checked previous points in the sorted array earlier, so they don't need to be checked again. As a result, instead of comparing a point with all other points, you only compare it with points in the stripe X to X+2R. That should reduce the number of points to compare a lot.
> 0 votes

# Answer
You can use a spatial index, such as quadtree, kd-tree, R-tree, ... . Most implementations of spatial indexes provide a search method that returns all indexed points in a circle or rectangle. Before inserting any point P, you can simply query/search the index whether there is already any point in the rectangle/circle around P, where the rectangle/circle encompasses the safety distance. Of course, if you use a rectangle, you have to manually check whether the returned points really violate the safety distance.

These searches are usually in the order of $O(log (n))$, so checking all points requires something like $O(n * log(n))$.
> 0 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Why does Feistel encryption algorithm encode half block every time?
Why does Feistel encryption algorithm encode half block every time? What would happen if the entire block is encrypted in each step?

# Answer
> 0 votes
You can't. Some of the block is used as the input to the F function, and the rest is modified. Those can't overlap. If you wanted to modify all of the block, there wouldn't be any input to the F function.

You might be interested in https://en.wikipedia.org/wiki/Feistel\_cipher#Unbalanced\_Feistel\_cipher

---
Tags: cryptography, encryption
---


title: 3-Coloring Graph problem

text:
# Question
Title: 3-Coloring Graph problem
Can we prove that the 3 coloring graph problem (where no two adjacent nodes have same color) is **NP** instead of **NP**-complete?

$$\mathrm{3COLOR} = \\{\langle G \rangle \mid G \text{ is colorable with 3 colors}\\}$$

# Answer
> 0 votes
Since **3-Colors** is NP-Complete, it is also in NP.

**Reminder**:

$\bullet$ To prove a problem $P$ is in NP, we have to show a polynomial time "yes" certificate

$\bullet$ To prove a problem $P$ is NP-Complete, we have to show: $P \in$ NP *and* there is another problem $X$ which is NP-Complete, and $X$ can be reduced to $P$.

It is clear then, that:

$P$ is NP-Complete $\Rightarrow P\in$ NP.

The first condition is trivial, and the reduction to 3-SAT is widely known and can be found easily.

---
Tags: np-complete, np, colorings
---


# Question
Title: What's the purpose of the non-deterministic Turing machine?
(\*) Acronyms

NTDM := non-deterministic Turing machine. TM := deterministic Turing machine.

(\*) Consider the following idea

The NTDM is able to follow, in parallel, all paths of the tree of the universe of solution. Suppose that in some point in time, for a certain problem, a new theorem is discovered that tells us that we need not worry about certain branches of the universe of solution because those branches yield no solution. Then in some future point in time, a new theorem appears telling us we need not worry about some other branches of the tree and so on. New theorems keep on being proved such that eventually there's only a single path to be followed in the tree of the universe of solution. The problem therefore affords a polynomial solution since at every branch, it tells us where to go.

So the concept of NDTM accounts for all future scientific development. Therefore, if a problem cannot be solved in polynomial time in the NDTM, then it's not in NP and therefore has no chance of being polynomial, no matter how science might advance.

This seems to be a good reason for the concept. Is there any flaw in this argument? In parallel, I'm interested in the question: why was the NDTM invented?

# Answer
I will try to address why the concepts of NDTM and NP are useful, and possibly what motivated their study.

NDTM is one of many variants of turing mahcine. For example, the classical (deterministic) Turing machine can be equipped with multiple heads and tapes, randomness or quantum states. It can also be constrained by a limited alphabet, limited tape or pre-determined head-movements (see here).

A TM is said to decide a language (a set of words using a pre-defined alphabet), if it can halt on any input written on the tape, and accept precisely inputs belonging to the language. A language is called decidable if any TM decides it. Similarly, a function $f$ on natural numbers is said to be computable if there exists a TM which, given an input $n$, halts with $f(n)$ written on the input tape.

It turns out that all of the mentioned variations of TMs (including NDTM) are equivalent in the set of functions they can compute (similarly, the languages they can decide). This holds for other, much more different models than TMs, and has led to the Church-Turing thesis, which informally hypothesizes that any "reasonable" model of computation is equivalent to the classical Turing machine. In this aspect, NDTMs are useful as an example of fantastical computational models that are nonetheless as strong as a classical TM, supporting the Church-Turing thesis.

As far as I understand (see here and here for history), Turing himself did not focus on complexity classes, and so the previous reason might have been his sole motivation. However, later on it was discovered that different TM variants are not equivalent in the set of problems (languages and functions) they can solve in a certain amount of computation steps (time), bound on working-tape size (memory) and success probability. With this finer resolution, it turns out that the different models are **very** different, resulting in a zoo of complexity classes for problems.

I hope this is helps show why NDTMs (and the NP complexity class) are not a definite model for the problems science could potentially solve efficiently, but just one of many variations of computational models (less realistic than random and quantum machines, for example). There are, however, some reasons for why the specific class of nondeterministic polynomial time ($NP$) is such a popular attraction of the zoo:

1. It is relatively easy to explain and reason about. While researchers are working on many other open problems in complexity theory, the question of whether $P\neq NP$ requires only basic knowledge in math to understand, and the concept seems so intuitive that it invites many solution attempts from amateur researchers.
2. Whether a problem is solvable in polynomial time in a computational model is seen as an approximate measure of practical tractability (this is Cobham's thesis).
3. Any complexity bound derived by NDTMs can be seen as a bound on verification time by classical TMs (see here for why). Since classical TMs are used as models of practical computation, this has practical implications.
4. Many real-world important problems just happen to be not just in $NP$, but $NP$-complete. This means that if $NP$ is indeed a different complexity class than $P$, all of these important problems are **not** solvable in polynomial time with classical TMs.

Note that the fourth reason is unrelated to how realistic NDTMs are as a computational models (compared to classical TMs or other variants), or to any initial motivation for the invention of the concept. NP-complete problems are just surprisingly common in real life, and the scientific interest in them mirrors that.
> -1 votes

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


# Question
Title: How to model equality in Integer Linear Programming
How to implement v=(a==b) using Linear Programming? $$ v= \begin{cases} True, a=b\\ False, a≠b\\ \end{cases} $$

Until now I tried the big M-Method.

To show a≤b: $$a-b+Mv≤M$$ $$-a+b-Mv≤-1$$

To show b≤a: $$-a+b+Mv≤M$$ $$a-b-Mv≤-1$$

When they are equal everything is okay, but when a≠b it doesn't work.

# Answer
> 2 votes
Use Cast to boolean, for integer linear programming, setting $x=a-b$ and $y=v$. This only works if you have a constant upper bound on $|a-b|$. Otherwise, I don't know how to express it in an ILP.

See also Express boolean logic operations in zero-one integer linear programming (ILP), Boolean variable true iff equation is satisfied in ILP, Boolean variable that captures whether an inequality holds.

---
Tags: linear-programming, integer-programming, mathematical-programming, constraint-programming
---


# Question
Title: Is it possible to compute how many iterations this algorithm will take?
I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always guaranteed to terminate.)

Let $x$, $y$, and $z$ be some positive integers. The values of $x$, $y$, and $z$ are chosen such that neither $y$ nor $z$ will become $\le 0$ before the loop terminates.

$\text{do}$

$\qquad \text{if } (x+y) \text{ mod } z = 0 \text{ then done}$

$\qquad x \leftarrow x + y$

$\qquad y \leftarrow y - 4$

$\qquad z \leftarrow z - 2$

$\text{loop}$

For example, if we let $x =184$, $y = 376$, and $z = 187$, this algorithm terminates in $19$ loops.

Here is a plot of $(x+y) \text{ mod } z$ for some real inputs. Here is another plot for larger inputs.

# Answer
There might be no clean formula for that.

The values of $x,y,z$ after the $n$th iteration of the loop are $x\_0 + (n+1) y\_0 - 2n(n+1)$, $y\_0 - 4n$, and $z\_0 - 2n$, respectively, as can be verified by induction, where $x\_0,y\_0,z\_0$ are their initial values (before the first iteration of the loop). The loop terminates for the smallest positive integer $n$ such that

$$x\_0 + (n+1) y\_0 - 2n(n+1) + y\_0 - 4n \equiv 0 \pmod{z\_0 - 2n}.$$

There might not be any nice expression for the smallest $n$ that satisfies that equation, in terms of $x\_0,y\_0,z\_0$. It's also not obvious to me whether such an $n$ always exists, i.e., whether your loop will always terminate.

---

I'm glossing over a serious issue that you haven't addressed in the question: what is the meaning of $(x+y) \bmod z$ when $z=0$ or when $z\<0$? It's not clear, and that will affect the answer.
> 0 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis
---


# Question
Title: Prove the probability of which a hash function is collision-free
Suppose $H = \\{h\_1, ..., h\_T\\}$ be a family of pairwise independent hash functions mapping $\\{0, 1\\}^n$ to $\\{0, 1\\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x\_1, ..., x\_M$ be any M distinct points in $\\{0, 1\\}^n$. If we choose $h$ randomly form $H$ and let $E$ be the event that $h(x\_1), ..., h(x\_M)$ are all distinct. We need to show that $Pr\[E\] \ge \frac{3}{4}$.

$\textbf{Markove's inequality:}$ If $X$ is a random variable which only takes non-negative values then, for any $t \ge 0$, $Pr\[X \ge t\] \leq E\[X\]/t$.

The idea is to compute $Pr\[h(x\_i) = h(x\_j)\]$, compute the expectation of the random variable $Z = |\\{(i,j) : h(x\_i) = h(x\_j)\\}|$ and use the Markove's inequality to prove the question.

For two independent points $x\_i$ and $x\_j$, the probability that $h(x\_i)$ and $h(x\_j)$ are equal is $1 - \\{\text{the probability two independent points has the different hash values}\\}$, which is $1 - \frac{2^{n/2}}{2^{n/2}}\cdot \frac{2^{n/2} - 1}{2^{n/2}}$. That shows $Pr\[h(x\_i) = h(x\_j)\] = \frac{1}{2^{n/2}}$.

As for the random variable $Z$, maybe we can let $Z\_{i,j} = 1 \text{ if }h(x\_i) = h(x\_j)$. Otherwise, $Z\_{i,j} = 0$. Then we can get $Pr(Z\_{(i,j)}) = \frac{1}{2^{n/2}}$. This is where I stuck. I know how to compute the expectation the single random variable, which is $\sum\_{i=1}^{n} x\_i P(X = x\_i)$. But I have no idea how to expand this formula to the pair random variable $(i,j)$. Also I am a little confused how Markove's Inequality could be used in this proof.

Could someone give me some hints? Any help would be appreciated. Thanks in advance.

# Answer
For every $i \< j$, the probability that $h(x\_i) = h(x\_j)$ is at most $2^{-n/2}$. The number of pairs of indices $1 \leq i \< j \leq M$ is $M(M-1)/2 \< M^2/2 = 2^{n/2}/200$, hence a union bound implies that the probability that $h(x\_i) = h(x\_j)$ for some pair $i \< j$ is at most $$ 2^{n/2}/200 \cdot 2^{-n/2} = 1/200. $$ It follows that the probability that $h(x\_1),\ldots,h(x\_M)$ are all distinct is at least $199/200$.
> 1 votes

---
Tags: turing-machines, probability-theory, discrete-mathematics, randomized-algorithms, hash
---


# Question
Title: In what sense are dataflow architectures non-deterministic?
The Wikipedia article mentions non-determinism in the context of dataflow architectures. Arthur Veen's paper mentions non-determinism when it elaborates on MERGE nodes as conditional constructs.

Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?

For any program which deterministically runs on a von Neumann architecture, can we guarantee that it runs deterministically on a data flow architecture?

# Answer
> 2 votes
> Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?

In principle one could create a non-deterministic dataflow architecture, but that would be a bit odd. There is nothing about dataflow that fundamentally requires determinism or non-determinism.

Normally I'd expect that a dataflow architecture would be deterministic in the sense that the result of the computation is a deterministic function of the inputs (in principle it doesn't have to be that way, but that's probably the common case for a dataflow architecture). Of course, the order in which intermediate values are computed might not be deterministic, even though the result is. See Why doesn't parallelism necessarily imply non-determinism? for a detailed explanation of that point.

Beware that there are multiple meanings of the word "non-determinism". One meaning is non-determinism in the sense of a non-deterministic Turing machine, i.e., there can be a choice of transitions and the machine magically makes the best choice at every step; this is not implementable directly in real-world machines, so is purely a theoretical nothing. Another meaning is that the system is not deterministic, e.g., there are aspects of its behavior that are not specified or random; those are resolved somehow but not necessarily by choosing the best choice. Occasionally I've seen people use the word "indeterminism" for the latter notion, but that seems to be pretty rare. See also Differences and relationships between randomized and nondeterministic algorithms?, https://cs.stackexchange.com/a/38158/755, https://en.wikipedia.org/wiki/Nondeterministic\_algorithm, https://en.wikipedia.org/wiki/Indeterminacy\_in\_computation.

# Answer
> 2 votes
Dataflow architectures are more nondeterministic than a nondeterministic Turing Machine.

With a nondeterministic Turing Machine, you still have a single machine that performs all the actions. All input is predetermined, it is already on the input tape. The only nondeterminism in the system is in the choice of the next transition, for which multiple options may exist. Time is not a factor at all.

With a dataflow architecture, we may have any number of different data processing components, operating concurrently. The input isn't predetermined, but it streams in on the input channels, with unpredictable values and possibly at unpredictable rates. The system's behavior may be strongly affected by the value of the data items flowing in, the relative order at which they flow in on different channels, and time-related factors (e.g. how fast they flow in). So the amount of nondeterminism is generally much higher.

---
Tags: computer-architecture, nondeterminism
---


# Question
Title: How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?
When modeling a scenario with Petri nets how should I determine the places, transitions and tokens?

**Example:**

There are two exam assistants in an exam hall observing the exam. They stand in front of the exam hall. When a student has a question one of the assistants goes to him and answers his question while the other stays in front of hall. When the question is answered, the assistant goes back to the front of the hall.

By modeling this scenario it must be distinguished which assistant stays in front of hall. Then the Petri net must be expanded so that the assistants take turns answering the questions.

Here is my solution:

p0 represents the front of the exam hall. The two tokens represent the assistants and p1 is where the student seats. I also limited the capacity of p1 to one.

The given solution is however totaly different:

How should I generally think and how can I determine which part of a given scenario is represented by which part of the Petri net (places, transitions and tokens)?

# Answer
If you find it challenging to apply Petri Nets in modeling an application then it may help to consider the following mapping between the types of words found in a text description of an application with the types of Petri Net elements found in a Petri Net diagram of the application:

1. Nouns are candidates for places.
2. Verbs are nominees for transitions (and/or inputs and outputs).
3. Values, amounts or counts are contenders for tokens in places.

## Example Application

\[Consider Figure 1 for the following example\]. For the “Exam Hall Problem”, think of (Infinity, 2017):

1. A place as a holder or container for “things”. a. There are two exam assistants in front of the hall and each assistant must be distinguished from the other. Thus there are two places: one place for each assistant in front of the hall (P4, P5). b. The exam assistants can answer questions at the same time. Thus there are two additional places: one place for an exam assistant answering a question (P2, P3).
2. A token in a place as the counter for the place, the number of “things”. a. If an exam assistant is not in front of the hall then the place is empty. If an exam assistant is in front of the hall then the place is not empty, the place has a token. b. If an exam assistant is answering a question then the place is not empty, the place has a token. If an exam assistant is not answering a question then the place is empty.
3. A transition as a start or end of “activities”. a. An exam assistant going to a student to answer a question is an activity (T1, T3). b. An exam assistant who answered a question is another activity (T2, T4).

The given solution for the “Exam Hall Problem” appears to be a solution for the second scenario: the exam assistants take turns answering questions (Infinity, 2017). Figure 1 is a modified version of the given solution. It was modified to satisfy the requirements of the first scenario. It includes text labels, chosen from or derived from the words in the example description.

Figure 1 Petri Net Model for Exam Assistants Answering Questions in an Exam Hall

For the “dynamic and interactive version” of this document, the visibility of labels in Figure 1 can be toggled by clicking on the diagram (Chionglo, 2017).

## Reference

Chionglo, J. F. (2017). A Reply to "How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?" at Computer Science Stack Exchange. Available at https://www.academia.edu/31997446/A\_Reply\_to\_How\_to\_with\_Petri\_Nets\_At\_Computer\_Science\_Stack\_Exchange.

Infinity. (2017). "How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?" at Computer Science Stack Exchange. Retrieved on Mar. 21, 2017 at How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?.
> 3 votes

# Answer
Generally, the idea of a (normal) petri-net is to efficiently represent a system to model an arbitrary amount of 'agents' that change their state depending on certain transitions. (This would quite quickly get out of hand in a state machine)

So, the basic strategy is to first determine what your 'agents' are and model them as your tokens. The state of an individual agent corresponds to the places and the state transitions correspond to transitions in the petri-net.

Depending on what you want to model, you need to do a bit more and also consider *different* (in your modeling interpretation, not as far as the petri-net is concerned) tokens that are created by some action of other tokens, but the general idea of what tokens, places and transitions are remains the same.

Your answer follows the basic strategy, but it fails to meet the requirement that the tokens are distinguishable and that at least one of them must remain in front of the hall. In a normal petri-net, we cannot distinguish tokens from another, so if a token moves to $p\_1$, we cannot know which.

A solution is to construct different transitions such that we know which assistant moves, based on the transition taken. The 'given solution' you provide does this and adds some restrictions to model the requirement that at least one of them must remain in front of the hall.
> 2 votes

# Answer
When I use Petri nets or explain them to others, my general policy is to always name places and transitions and places by propositions of the form *\<subject\> \<predicate\>*.

The subject is a noun phrase. It may be definite or indefinite. It must be definite for a safe place (one that will never contain more than 1 token at a time).

The predicate is a verb phrase. For places, the verb is stative (describing a state); for transitions, it is dynamic (describing a change of state, an action or event).

With this naming convention, interpretation is straightforward:

A place represents a condition the subject may be in. For instance:

* An item is in store.
* The order is being processed.
* The computer has been assembled and is ready to be tested.
* The sun is shining.
* It is raining.

A token in a place is a subject to which the given proposition applies. For safe places, there exists only one possible subject (e.g. in *The sun is shining*) or no real subject at all (e.g. in *It is raining*).

A transition describes a change of state to the subject. For instance:

* An item is retrieved from store.
* The order finishes being processed.
* The computer starts being tested.
* The sun goes down.
* It starts to rain.
* It ceases to rain.

I've found that, particularly for places, insisting on them being named in this way avoids conceptual errors and makes the model much easier to understand.
> 1 votes

---
Tags: modelling, petri-nets
---


# Question
Title: Given a family of hash functions in table form, how can I know whether it's universal?
I've been given the following two families of hash functions:

H

and

G

Each family has three functions $\\{0,1,2,3,4\\} \to \\{0,1,2\\}$ that can be seen in the tables above. For each family I need to decide whether it's universal. I know that a family of hash functions $F$ is called universal if for every $x \neq y$, $\text{Pr}(f(x) = f(y)) \le \frac{1}{m}$ ($f$ is a function in $F$). However, I don't understand how to calculate this probability. Should I calculate it for any one of the functions or for the whole family?

# Answer
> 2 votes
As you have stated, given a family $H$ of hash functions, the condition for universality is $\forall x,y, x \neq y: \text{P}\_{h \in H}(h(x) \neq h(y)) \le \frac{1}{m}$. The probability is taken over $h \in H$, which is picked following a uniform distribution.

If you think for a while about what that means, you'll realize you need simply check whether there is at most one collision (i.e., equal entries) for any two distinct columns (i.e., every pair of $x$ and $y$) in the respective family's table. Hence, $G$ is universal, but $H$ is not; I'll let you figure out why.

---
Tags: hash, hashing
---


# Question
Title: Complexity class for NP with access to a DP oracle
Consider the following decision problem:

> **Given**: Two (3CNF-)formulas $\varphi\_1$, $\varphi\_2$ on a shared set $X\cup Y$ of variables ($X$ and $Y$ disjoint).
>
> **Question**: $\exists$ assignment $\tau\_X$ on $X$ such that $\varphi\_1$ is satisfiable and $\varphi\_2$ is unsatisfiable?

(The "satisfiable" and "unsatisfiable" conditions are relative to the fixed assignment $\tau\_X$ from the outer quantifier and can only "choose" the assignment to variables in $Y$.)

This problem is a generalization of the well-known 3-SAT/3-UNSAT problem, which is DP-complete:

> **Given**: Two (3CNF-)formulas $\varphi\_1$, $\varphi\_2$ on a set $Y$ of variables.
>
> **Question**: Is $\varphi\_1$ satisfiable and $\varphi\_2$ unsatisfiable?

The generalization works in the same way in which the NP-complete problem 3-SAT is generalized for higher levels of the polynomial hierarchy. In fact, if the formula $\varphi\_1$ and the corresponding condition is removed, this problem coincides with the $\Sigma\_2^p$-complete variant of 3-SAT:

> **Given**: A (3CNF-)formula $\varphi\_2$ on a set $X\cup Y$ of variables ($X$ and $Y$ disjoint).
>
> **Question**: $\exists$ assignment $\tau\_X$ on $X$ such that $\varphi\_2$ is unsatisfiable?

Now I wonder how to call the complexity class that this problem is a member of (and probably complete for). It seems to be $\textit{NP}^{\textit{DP}}$, i.e., $\textit{NP}$ with access to a $\textit{DP}$ oracle, in the same way that $\Sigma\_2^p=\textit{NP}^{\textit{coNP}}$ is $\textit{NP}$ with access to a $\textit{coNP}$ oracle. However, I have not found such a class in the literature. Is the problem simply too unnatural to receive any attention? Or can it be simplified such that it falls into another, more common class?

# Answer
You have not found explicit mention of it because it is the same class as $\Sigma\_2 = \textbf{NP}^\textbf{NP}$. $\Sigma\_2 \subseteq \textbf{NP}^\text{DP}$ holds because any $\textbf{NP}$ query can be poly-time (many-one) reduced to a SAT query, which, in turn, can be cast as a DP query (by setting $\varphi\_2$ to a trivially unsatisfiable formula). Conversely, $\Sigma\_2 \supseteq \textbf{NP}^\text{DP}$ because any DP query can be answered by two (adaptive) SAT queries.
> 3 votes

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


# Question
Title: how can this function be computed in polynomial time in regards to its input?
i am struggling for quite a while with this. trying to understand why the following function can be calculated in polynomial time(in regards to the input length)

defining a function from assignments of truth values to a set of booleans to 3CNF propositions:

the function gets an assignment of truth values to a set of n boolean variables $x\_1,x\_2,...,x\_n$ (n ≥ 3) (meaning each boolean variables gets either 0 or 1).

the function returns a 3CNF proposition that upholds(maintains) the following:

1)each clause of the proposition contains exactly three literals

2)the proposition consists of only the variables $x\_1,x\_2,..,x\_n$

3)the three literals in each clause are of different variables(there are no double literals in the clause, and none of the clauses consists of complimentary literals)

4)the proposition is satisfiable and the only assignment that satisfies the proposition is the assignment the function obtained as an input.

prove that the given function can be calculated in a polynomial time in regards to the input size

i don't understand how can it be computed in a polynomial time in regards to the input size. tried to look everywhere, this site, online, sipser's book and nothing. similar problems are usually from the NP family.

could someone please explain to me how this one can be polynomially computed? i just can't understand that

EDIT: this is how the final 3CNF should look in my opinion: $(l\_1 \lor l\_2 \lor x\_1) \land (\lnot x\_1 \lor l\_3 \lor x\_2) \land (\lnot x\_2 \lor l4 \lor x\_3)\land ... \land(\lnot x\_{n-3} \lor l\_{n-1} \lor l\_n)$ (from $(l\_1 \lor l\_2\lor...\lor l\_n)$).

but what i don't understand is why is it polynomial, could someone please explain to me why can it be computed polynomially in regards to input size?

# Answer
Let's start with solving the problem for 1-CNFs. The proof will be by example. If the truth assignment is $x\_1=x\_2=1,x\_3=0$ then a 1-CNF for which this is the only satisfying assignment is $$ x\_1 \land x\_2 \land \overline{x\_3}. $$ Now let's solve the problem for 2-CNFs, again by example. Continuing with our previous example, here is one possible construction: $$ (x\_1 \lor x\_2) \land (x\_1 \lor \overline{x\_2}) \land (x\_2 \lor x\_3) \land (x\_2 \lor \overline{x\_3}) \land (\overline{x\_3} \lor x\_1) \land (\overline{x\_3} \lor \overline{x\_1}). $$ More generally, we replace $x\_i$ with $(x\_i \lor x\_j) \land (x\_i \lor \overline{x\_j})$ for an arbitrary $j \neq i$.

Your problem can be solved in a very similar way.
> 1 votes

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


# Question
Title: Why is the blank symbol not considered part of the input alphabet of a Turing machine?
Definitions of Turing machines are always explicit about the blank symbol not being part of the input alphabet.

I wonder what goes wrong when you *would* make it part of the input alphabet, because effectively the blank symbol already seems to be part of the input.

To explain that 'seems' in the last sentence, consider the following.

In the default setup, an infinite number of blank symbols appear on the right of the input. When the tape head moves over the first blank symbol, computation can just continue, as it doesn't need to be an accept or reject state.

Now suppose the computation would subsequently write symbols from the input alphabet to the right of that first blank symbol, then return to the leftmost position while also returning to the start state. It would then 'start over' with a different tape. Effectively, it now starts with a different input, where there are input symbols to the right of the blank that weren't there before. The input seems to effectively include the blank symbol. The further behavior of the machine could now also be different: after encountering the blank again, it will now encounter different symbols to the right.

Supposing this scenario is indeed possible, why wouldn't you consider the blank symbol part of the input alphabet and why wouldn't you allow including it as part of the 'initial' input?

Perhaps it is just a way to define the input such that it isn't always infinite?

# Answer
The main reason is that it allows the machine to detect the end of its input: it's (the character before) the first blank. If you allowed blanks in the input, the machine could never know whether it might find more input by scanning farther to the right. Of course, you could solve that by having a special "end of input" character but then you have to insist that *that* can't appear in the input, so you've just shifted the problem one level deeper.

It also makes the initial conditions much easier to specify: the input is the non-blank section of the initial tape, which must be finite and contiguous. And if you want a blank character to be a part of the input alphabet, you can always add an extra character (call it "space" or something) and have the machine behave however you want when it sees it.
> 25 votes

# Answer
You can define the blank symbol to be part of the alphabet. The problem with that is that if a Turing machine with input b010010b (where b stands for *blank*) never reads past the second b, then the machine will behave exactly the same way on all inputs starting with b010010b.

These Turing machines are called *prefix Turing machines*, and they are very useful for proving some theorems about Kolmogorov complexity.
> 6 votes

# Answer
Very short answer: the **tape alphabet** is the set of symbols that can appear on the tape, and it includes the blank symbol. The **input alphabet** is the set of symbols that can appear *in the initial input*, and it does not include the blank symbol. The main alphabet the machine cares about is the tape alphabet: it still needs rules for what to do when it sees a blank, for example.

This distinction is important, as others have said, so that the machine can tell where its input ends. It's the same reason you can't (usefully) put a zero-character in the middle of a string in C: the zero-character is reserved to mean "the last non-zero character before this is the end of the data, so when you see this, you're done". If you need to expect zero-characters in the middle of the string, writing `strlen` gets a whole lot harder.
> 6 votes

---
Tags: turing-machines
---


# Question
Title: Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints
Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below?

Fact 1: For monotone submodular functions, Nemhauser, Wolsey and Fisher proved \[1\] that simple greedy algorithm gives $1-1/e$ approximation guarantee.

Fact 2: For non-monotone non-negative submodular functions, Buchbinder et. all proved \[2\] that randomized greedy algorithm gives $1/e$ approximation for cardinality constraint.

# Answer
**Edit:** See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use.

There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes into the sum of a monotone submodular and an arbitrary modular function. The optimization problem is $$ \max\_{S \in \mathcal{I}} g(S) - c(S) \enspace,$$ where $g:2^V \rightarrow \mathbb{R}\_+$ is a non-negative and monotone submodular function, $c:2^V \rightarrow \mathbb{R}$ is a modular function, and $\mathcal{I} \subset 2^V$ is a matroid on the ground set $V$. Note that if $c$ takes positive values, then the entire submodular objective $f = g - c$ is non-monotone and may take negative values. The first approximation result was given by Sviridenko, Vondrák, and Ward in 2014 who showed that one can use a continuous extension & rounding approach to obtain a set $S$ such that $$ g(S) - c(S) \geq (1 - e^{-1}) g(OPT) - c(OPT) $$ They applied this result to obtain tight approximation guarantees for monotone submodular maximization and monotone supermodular minimization with bounded curvature. They also show that this approximation is tight in the sense that no algorithm making polynomially many queries to $g$ and $c$ can do better. Then in 2018, Feldman gave an algorithm that also goes through the continuous domain but is more efficient in that it by-passes a certain "guessing step" in the previous algorithm. Most recently, Harshaw, Feldman, Karbasi, and Ward in 2019 gave a series of much faster algorithms which do not go through the continuous extension, but are based on greedily optimizing a "distorted surrogate objective" which changes thoroughout the algorithm; however, their results apply only when the modular function is non-negative and the constraint is a cardinality constraint. They also extend the analysis to show that when $g$ is $\gamma$-weakly submodular, then one may obtain the analogous approximation $$ g(S) - c(S) \geq (1 - e^{-\gamma}) g(OPT) - c(OPT) $$ Moreover, this extended approximation guarantee is tight in the value oracle model.

There is the hardness result by Uriel Feige which shows that even verifying that $f(S) \geq 0$ for some $S$ is NP-Hard. So, the decomposition into a sum of submodular and monotone functions really is crucial in all these algorithms. I don't know how much further one can push the decomposition approach.
> 5 votes

# Answer
The notion of approximation isn't well-defined when outputs are signed. If the correct answer is $1$ and the algorithm returned $-1$, what is the corresponding approximation ratio? It's not clear. This is why we want our functions to be non-negative.

That said, if $f$ is submodular then $f+C$ is submodular for all $C$. This means that you can shift your function to be non-negative, run one of the algorithm you mentioned, then shift back. You'll have to work out what guarantees you get. In fact, for the algorithms you mention you don't even need the shift, since shifting everything by a constant doesn't change the way they work at all.
> 2 votes

---
Tags: algorithms, optimization, np-hard, greedy-algorithms
---


# Question
Title: Name for value which may only be -1, 0 or 1?
Is there a name for a value which may only be -1, 0 or 1?

Is there a name for a function which creates such a value from arbitrary numbers?

It would be implemented like this:

T Function( T value ) { return ( value \< 0 ) ? -1 : ( value \> 0 ) ? 1 :0; }

# Answer
> 2 votes
There is no standard name, but the value can be seen as value in the balanced ternary numeral system or as the sign (sgn) function. IMHO, the name Sign() is more appropriate when working with calculations or ordering, the 'balanced ternary' is more appropriate when working with logic. For my purposes, I created a Tri enum in the C# language and, besides others, a generic mapping function with this code:

```
    // https://en.wikipedia.org/wiki/Sign_function
    public static Tri Sgn<T>( this T value ) where T : IComparable<T> {
        var t = value.CompareTo( default( T ) );
        return t < 0 ? Tri.Negative : t > 0 ? Tri.Positive : Tri.Zero;
    }

```

And, last but not least, there is the three-valued logic: https://en.wikipedia.org/wiki/three-valued\_logic. Values of the 'Tri' type can be used to implement functions for three-valued logic.

---
Tags: terminology
---


# Question
Title: Compact Shared Reduced Binary Decision Diagrams with negated identifiers
Consider a BDD implementation in which each bdd in the system has a unique positive integer identifying it (thanks to canonicity and as common implementation designs follow, by utilizing a hashmap). I was thinking of assigning a negative integer to a bdd in order to represent its negation. So say bdd id -3 will be bdd id 3 with just flipping the terminal nodes when processing them. The building blocks for new bdds would be the terminal T,F nodes, and the "ith var" bdd, where if the ith var is false then we get an id being the negation of the id of the bdd representing the ith var being true.

My question is whether such design breaks canonicity, or I can still rely on bdds having same (positive or negative) identifier to be equal.

# Answer
> 0 votes
Found the answer in the paper Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean function Manipulation.

more accurate treatment can be found in section 2.3 in Proving circuit correctness using formal comparison between expected and extracted behaviour (pdf download available).

in short, canonicity is preserved if, quoting from tvandijk.nl/pdf/mscthesis.pdf page 15 "Complement edges" (The Parallelization of Binary Decision Diagram operations for model checking, thesis by Tom van Dijk):

"Minato \[35\] proposes the following constraints:

1) Only 0 is used as the value of a leaf.

Alternative rule 1 : only 1 is used as the value of a leaf.

Alternative rule 2 : do not allow complement edges on leaves.

2) No complement edges are allowed on 0-edges.

Alternative rule: no complement edges are allowed on 1-edges"

note that this is not a "true" restriction as if we decide that only hi edges are complemented, and we want to create a node with its lo edge being complemented, we just negate the whole node, like a?b:not(c) == not(a?not(b):c).

# Answer
> 0 votes
In general this breaks canonicity. Suppose you have a BDD for $x\_1$ labelled $1$ and a BDD for $\neg x\_1$ labelled $2$. Then assigning the negative integer $-1$ to the negation of the first BDD breaks canonicity, because you now have two BDDs with two different labels ($-1$ and $2$) that represent the same function. You'd need a pretty special hash function for it to not break canonicity.

---
Tags: bdd
---


# Question
Title: Multi-prompt delimited continuations in terms of single-prompt delimited continuations
Let's call the two languages in question (untyped lambda calculus with single or multiple prompt delimited continuations) L\_delim and L\_prompt.

> Is it possible to express multi-prompt delimited continuations in terms of single-prompt delimited continuations

By express I mean the macro-expressible sense (to provide some kind of translation that doesn't involve interpreter overhead), of course it's possible to write an interpreter for multi-prompt delimited continuations even in pure lambda calculus.

I expected a negative result for this, that it's not possible but I don't know how that would be shown. Thanks for any input on this.

# Answer
> 4 votes
So, it turns out, the paper describing the construction I mentioned in the comments answers in the affirmative:

> Our technique of removing a dynamic prompt is rather general and thus can be used for the design of many other delimited control operators, which permit capturing the continuation up to an arbitrary (not necessarily the closest one) enclosing delimiter. It becomes entirely up to the user which delimiters to skip and how the captured frames are to be composed or used separately.

If you look at their method, it seems like the idea would be to tag the `H` and `HV` values with tokens that specify the different prompts involved, and have the `h` and `h'` functions compare those tokens to decide what to do. This isn't terribly surprising, because the multi-prompt implementation I'm familiar with uses (representations of) stacks with frames tagged with the prompt, and their technique uses 'static' shift/reset (and macros) to hide explicit manipulation of the stack implementation of e.g. control/prompt, more or less.

---
Tags: lambda-calculus, continuations
---


# Question
Title: In which situation do we choose randomized binary search instead of the normal binary search?
Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same time complexity like that of the original binary search ?

# Answer
Randomized binary search makes sense if your randomness source has a good bias towards your search target. You can then use it to reduce the expected search time (even retaining the $O(\log n)$ asymptotic worst-case complexity) as described in this answer.

If your randomness source is simply a uniform distribution, then you won't get much out of it. If you use it naively (i.e., simply choosing the midpoint according to your randomness source), it will actually perform *worse* than standard binary search since the worst-case complexity will be $O(n)$, not $O(\log n)$ (consider the case where your interval is $\[1,n\]$, your target 1, and your randomness source outputs $n-1, n-2, n-3, \dots$).
> 2 votes

---
Tags: algorithms, search-algorithms, binary-search, searching
---


# Question
Title: Using Chebyshev to derive an upper bound for Coupon Collecter's Problem
I'm TA'ing a course and have trouble solving an exercise.

Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E\[X\] = nH\_n = n \ln(n) + O(n)$ and $\sigma^2\_X = n^2 \sum\_{i=1}^n \frac{1}{i^2} - nH\_n$ with $\lim\_{n \to \infty} \frac{\sigma^2\_X}{n^2} = \frac{\pi^2}{6}$. The exercise asks how Chebyshev's inequality can be used to upper bound the probability that $X \> \beta n \ln(n)$ for some $\beta \> 1$.

I tried this: \begin{align\*} Pr\[X\>\beta n \ln(n)\] &\leq Pr\[|X-\mu\_X| \geq (\beta - 1)n \ln n\] \\ &\leq Pr\left\[|X-\mu\_X| \geq (\beta - 1) \left( \frac{\sqrt 6}{\pi} \sigma\_X \right) \ln n\right\] (1) \\ &\leq \frac{\pi}{6(\beta -1)^2 \ln^2 n} = O\left(\frac{1}{\ln^2n}\right) \end{align\*}

where (1) follows because $n \> \frac{\sigma\_X \sqrt 6}{\pi}$. However I believe the first inequality is incorrect because I'm discarding the $- O(n)$ from $\mu\_X$ in deriving an upper bound.

I also tried something else: \begin{align\*} Pr\[X\>\beta n \ln(n)\] &\leq Pr\[|X-\mu\_X| \geq \beta n \ln n - nH\_n\] \\ &\leq Pr\[|X-\mu\_X| \geq (\beta -1)nH\_n\] \\ &= Pr\left\[|X-\mu\_X| \geq \frac{6(\beta - 1)H\_n}{\pi^2n} \left(n^2 \sum\_{i=1}^\infty \frac{1}{i^2} - n H\_n \right)\right\] \end{align\*}

but I'm not sure where to go from here. Thanks for any help!

# Answer
> 1 votes
As you should have suspected, there is only a thin line between what you have tried and what is rigorous.

Here it is the rigorous version of your attempt. Since $\beta n\ln n\gt \mu\_X$ when $n$ is large enough, the first inequality holds for $n$ large enough. \begin{align\*} Pr\[X\>\beta n \ln(n)\] &\leq Pr\[|X-\mu\_X| \geq \beta n \ln n - \mu\_X\] \\ &\le \frac{\sigma\_X^2}{(\beta n \ln n - \mu\_X)^2}.\\ \end{align\*} **Now**

$$\begin{aligned} \lim\_{n\to\infty}\frac{\frac{\sigma\_X^2}{(\beta n \ln n - \mu\_X)^2}}{\frac1{\ln^2 n}} &=\lim\_{n\to\infty}{\frac{\sigma\_X^2}{n^2}}\lim\_{n\to\infty}\frac{(n\ln n)^2}{(\beta n \ln n - \mu\_X)^2}\\ &=\frac{\pi^2}{6}\lim\_{n\to\infty}\frac{1}{(\beta - \frac{\mu\_X}{n\ln n})^2}\\ &=\frac{\pi^2}{6(\beta - 1)^2}, \end{aligned}$$ which implies $$\frac{\sigma\_X^2}{(\beta n \ln n - \mu\_X)^2} = O\left(\frac{1}{\ln^2n}\right).$$

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


# Question
Title: Formulating the master theorem with Little-O- and Little-Omega notation
In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this:

> Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \mathbb{R}$ where $T(n) = aT(\frac{n}{b}) + f(n)$, then $ \\ T\in\left\\{\begin{matrix} \Theta(n^{\log\_b{a}}), & \text{ if } f \in O(n^{log\_b{a}-\epsilon}) \text{ for some } \epsilon \> 0. \\ \Theta(n^{\log\_b{a}} \log{n}), & \text{ if } f \in \Theta(n^{\log\_b{a}}). \\ \Theta(f), & \text{ if } f \in \Omega(n^{\log\_b{a}+\epsilon}) \text{ for some } \epsilon \> 0 \\ & \text{ and if the regularity condition holds. } \end{matrix}\right.$

When I first had to study this theorem, I found that for me personally, the meaning of $\epsilon$ was somewhat difficult to understand and memorise. I believe to have found a simpler way to write this theorem, and I am wondering if it can be used equivalently, or if there is a flaw in my reasoning.

Let's look at the first case in particular, $f \in O(n^{log\_b{a}-\epsilon})$. For simplicitly, let's assume $\log\_b(a) = 2$. If we choose an infinitesimally small value for $\epsilon$, then this case basically expresses that $f$ must be asymptotically less than or equal to $n^{1.999 \ldots}$. In other words, $f$ must be asymptotically strictly less than $n^2$. I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log\_b{a}})$ (and following the same logic, $f \in \omega(n^{\log\_b{a}})$ for the third case), rather than the (IMO) more convoluted alternative?

# Answer
> I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log\_b{a}})$ (and following the same logic, $f \in \omega(n^{\log\_b{a}})$ for the third case), rather than the more convoluted alternative?

That is indeed a natural attempt to understand that "convoluted" condition in simple terms. Unfortunately, it is not correct.

Here is a simple counterexample. Let $a=1$ and $b=2$, and let $T : \mathbb{N} \rightarrow \mathbb{R}$ where $T(n) = T(\frac{n}{2}) + f(n)$ and $T(1)=0$, where $f(n)=\frac1{\ln n} \in o(1)=o(n^{\log\_21})$.

If the first case of master theorem still holds, we should have $T(n) \in \Theta(n^{\log\_21})=\Theta(1)$. However, $$T(2^m)=T(2^{m-1})+\frac1m=T(2^{m-2})+\frac1m+\frac1{m-1}=\cdots=\frac1m+\frac1{m-1}+\cdots+1.$$ Letting $m$ goes to infinity, we see that $T(n)$ is not bounded because the harmonic series diverges.

---

For the same or a variety of other reasons, the usage of an arbitrarily small positive constant, which is usually denoted by $\epsilon$ pops up constantly in different places, especially in asymptotic estimate and complexity analysis. You may want to get used to it or even get addicted to it.

---

**Exercise 1.** Verify that for any $\epsilon\>0$, it is not true that $\frac1{\ln n}\in o(n^{-\epsilon})$ although $\frac1{\ln n}\in o(n^0).$

**Exercise 2.** Construct a counterexample for the master theorem where $a=4$, $b=2$ for

* the first case where $f \in o(n^{\log\_b{a}})$ instead of $ f \in O(n^{log\_b{a}-\epsilon})$ for some $\epsilon \> 0$ and
* the third case where $f \in \omega(n^{\log\_b{a}})$ instead of $f \in \Omega(n^{\log\_b{a}+\epsilon})$ for some $\epsilon \> 0$

respectively.
> 4 votes

# Answer
**No, that would be incorrect.**

Perhaps it is the condition $\varepsilon \> 0$ which is the root of your confusion. It is supposed to mean that $\varepsilon$ is a real positive number and *constant* (with respect to $n$). If we allow $f \in \omega(n^{\log\_b a})$, for instance, then for $a = b = 2$ we would have $f(n) = n \log n \in \Theta(n)$ as a consequence of the theorem, which is false.

---

On a side note, you write "$f$ must be asymptotically less than or equal to $n^{1.999\ldots}$". This *does* mean that $f$ must be bounded by $n^2$, though I believe not for the reasons you think it does. Recall that $1.999\ldots = 2$, so that statement is rather trivial...
> 2 votes

---
Tags: algorithms, time-complexity, asymptotics, master-theorem
---


# Question
Title: Algorithm to assign producers to consumers with respect to connections
I am trying to analyze supply chains in a game and have come across this problem:

First, an informal description: I have producers and consumers. Each producer produces a certain amount of goods, each consumer requieres a certain amount of goods. Each producer is connected to some consumers (these connections have infinite capacity).

Is there a way to transport goods from producers to consumers so that each consumer has sufficiently many goods? Each producer can provide goods to multiple consumers and each consumer can accept goods from multiple producers. A producer also doesn't have to deliver the entire production, as the rest can be discarted.

The connections form a bipartite graph with producers $p \in P$ and consumers $c \in C$ as vertices (so $V = P \mathbin{\unicode{x228D}} C$) and edges $E \subseteq (P \times C)$. Each producer has a positive production rate and each consumer a positive consumption rate.

We model how much is transported over each connection with a weight function $w: E -\> \mathbb{R}$. For each producer $p$ , we get the required production by summing up the weights of all edges incident to $p$. This must not be higher than the production of $p$.

Similarly, for each consumer $c$, we get the total delivery by summing up the weights of all edges incident to $c$. This must not be lower than the consumption of $c$.

**Does such a $w$ exist for a given graph, production rate and consumption rate?**

The left example has such a function, the right one does not:

I am pretty sure that if we allow negative $w(e)$, the problem is very easy (for connected graphs, just compare total production to total consumption). Therefore, it probably makes sense to restrict $w(e) \geq 0$.

I have tried to find similar problems, but most flow problems have limited flow rates and sources with infinite capacity (whereas here, it's exactly the other way around). I also know about the Assignment problem, but I don't think it applies here.

Perhaps there is a way to slowly remove consumers and producers. In the first example, we know that the top producer can only supply the top consumer, so we could just remove the producer and reduce the consumption rate on the right. It might also be possible to merge multiple producers and consumers if they all supply each other. However, I don't think that these operations alone suffice to solve the problem in all instances.

Perhaps there is no efficient algorithm, so I've also tried proving that the problem is NP-complete, but my attempt to reduce SAT to this problem wasn't successful.

This probably isn't the most enjoyable way to play Anno, but at this point, it don't want to give up...

# Answer
I'm not sure I understand the problem statement, but it looks like this can be modelled as a network flow problem. Here's how. First, create a new source vertex $s\_0$. Then, for each producer $p$, if its capacity is $c\_p$, and add an edge $s\_0 \to p$ with capacity $c\_p$. Do that for every producer, then look for a max flow in the resulting flow graph.
> 2 votes

---
Tags: bipartite-matching, assignment-problem, bipartite-graph
---