# Question
Title: Is Differential Evolution a genetic algorithm?
I am trying to classify the Differential Evolution algorithm according to the framework in the book:

> Introduction to Evolutionary Computing

The authors classify the field of evolutionary computation into 4 paradigms:

1. Evolutionary programming
2. Genetic programming
3. Evolutionary strategies
4. Genetic algorithms

I have ruled out 1. and 2., since they deal with programs as opposed to abstract optimization problems. I also ruled out 3. since evolutionary strategies maintain an explicit random distribution during the optimization process. That leaves only **genetic algorithms**. But when you say "genetic algorithm", the firs thing that comes to most peoples' minds is the traditional flipping of 0s and 1s. I have personally never heard anybody refer to differential evolution as a genetic algorithm.

# Answer
If you're asking for a homework assignment, then I can't really help you, because the answer really depends on how your professor interprets the taxonomy. But if you're asking for your own edification, I can give you my view.

First, the distinctions between the four classes you list (particularly between 1, 3, and 4) are largely historic. There are still some very real differences of course, but we don't view the lines between them as sharply as we once did. This means, for example, that GAs can be real-valued instead of binary and might rely on mutation more than crossover. You can have an evolution strategy for the traveling salesman problem. Really the description in the book isn't terribly well suited for use as a taxonomy for this reason. I teach from this book, and I like it a lot, so that's not really a criticism. I don't think the authors intended for you to try and use it as a well-defined taxonomy either.

If we go with this idea as a rough taxonomy though, then in principle, we have an umbrella term: "Evolutionary Computation" or "Evolutionary Algorithms" that covers all four of the cases you list. In practice though, while if someone says "evolution strategy" or "genetic programming", it's because they intentionally want to highlight that that's what they're doing, people sometimes say "genetic algorithms" when they really mean "evolutionary algorithms". So that term is especially hard to interpret.

So we might be able to call DE a GA with that understanding and be OK, but it really depends on who's asking the question as to whether that's what they had in mind or not.

Looking at the problem another way though, it gets even fuzzier. Right now, you're reading someone else's taxonomy and trying to fit the pieces together. What if you take a step back and try to formally define what a genetic algorithm or evolutionary algorithm is yourself? You might come up with something like "an algorithm that maintains a population of one or more candidate solutions, usually generated randomly, and continually selects the better individuals from the population, produces new individuals from the old ones via some type of variation operators, and favors the better of these new individuals for insertion into the population".

It's hard to get much narrower than that without excluding some things we think are "obviously" evolutionary algorithms, but this definition is really very broad. Certainly things like differential evolution and particle swarm optimization meet this definition, but so does, for example, simulated annealing. You can even take a simple next-descent hill-climber and call it a (1+1)-ES.

Personally then, my answer to your question is "sort of". If I write a paper that proposes a novel DE variant that looks super-awesome, I'd absolutely submit it to a journal like Evolutionary Computation. I know that my algorithm would be viewed as being appropriate for a venue that focused on genetic and evolutionary algorithms. But I probably wouldn't tell people that I used a "genetic algorithm" either, because that term doesn't feel precise enough to capture what it is that I want to express.

I'm not sure this is a particularly helpful answer, but I think it's probably a pretty common view among people in the field.
> 6 votes

# Answer
The wording of the original paper that introduced Differential Evolution is such that the authors consider DE a different thing from Genetic Algorithms or Evolution Strategies. Example:

> Choosing a subgroup of parameters for mutation is similiar to a process known as crossover in GAs or ESs.

Another one:

> A further disadvantage of GAs is the amount of expertise that is required to operate them, the same holds true for ESs.

Yet the differences remain unclear to me (I am not an expert in the field). Taking Eiben & Smith taxonomy strictly I would say DE is just another class of Evolutionary Algorithms.
> 4 votes

---
Tags: optimization, genetic-algorithms, evolutionary-computing
---


# Question
Title: Can every program be parallelized infinitely and automatically?
In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible.

And as I have read before, every program written in all programming languages is convertible to a Turing Machine. And of course, since there are no side effects and no order in calculating a lambda expression, parallelization is infinitely possible, and it can break down to computing one lambda function on a separate machine.

So with having these three facts in mind, An interesting question comes to mind. Since every program written in every programming language has an equivalent Turing machine, Turing machines are convertible to Lambda Calculus expression through an algorithm, and Lambda expressions are infinitely parallelizable, can every program be parallelized automatically and infinitely?

**EDIT** : I think I have to clear out one thing. By infinitely parallelizing, I mean to parallelize till the point where it benefits us, so the arguments about the size of parallelizations are not valid. For example, by having five cores of cpu, one can utilize all of his\her cores by these approach.

# Answer
If you're working in the strict lambda calculus, everything can be automatically parallelized. In particular, when evaluating a function application, the function and the argument can always be evaluated in parallel.

However, it cannot be infinitely parallelized. There are inherent data dependencies: the result of a function application can't be determined until both the argument and the function have been evaluated, meaning that you need to wait for your threads to both finish, then synchronize.

This is still relevant with your clarified definition of infinitely. For example, if you have 5 processors, it's possible that a particular program can only ever use 4 processors, because of the data dependencies.

Moreover, while this is automatic, it is not "performance for free." In practice, there is non-trivial overhead to creating and synchronizing threads. Moreover, it's difficult to do this in a way that scales only to the current number of processors: if you have 5 cores, the automatic parallelization might generate 6 threads, and in general, it's not possible to know at compile-time how many threads will be active at a given time.

So, you can automatically make a program that runs massively parallel, but with the current state of affairs, it will likely be slower than your original.

It's also worth mentioning that, in practice, this becomes difficult with shared access to resources and IO. For example, a real world program might write to a disk, which can cause problems if done in parallel without control. This is something that can't be modeled by the standard lambda calculus.
> 6 votes

# Answer
No, lambda expressions are not "infinitely parallelizable" (whatever that means).

For instance, consider the lambda expression $\lambda x . x$. This is the identity function. It takes $1$ step of computation to compute it. It cannot be parallelized; you can't somehow speed up the computation by using a parallel computer, and you certainly can't speed it up "infinitely".

So no, it's not true that every lambda expression can be "infinitely parallelized", and it's not true that every program can be "infinitely parallelized".
> 3 votes

# Answer
"Infinite parallelization" is not studied too much in CS because processors like other computational resources eg "time/ space" are almost always regarded as finite but here are at least two contexts where it shows up.

> In the case of parallelization, Amdahl's law states that if P is the proportion of a program that can be made parallel (i.e., benefit from parallelization), and $1 − P$ is the proportion that cannot be parallelized (remains serial), then the maximum speedup that can be achieved by using $N$ processors is $S(N) = ...$ . *In the limit, as $N$ tends to infinity,* the maximum speedup tends to $\frac{1}{1 − P}$.

So it is more of a theoretical concept or abstraction possibly sometimes used in mathematical theorems that does not really have direct applications and may break down somewhat where continuous math is used to represent discrete math problems.

In parallel computing there is an informal concept of "granularity". fine grained problems are somewhat analogous to many sand grains and can be split among many processors. roughly, these are also known as embarassingly parallel problems. But as an analogy, one cannot split a grain of sand in computation. There are still atomic-level operations that cannot be split further. Less fine grained problems have bigger "grains" that cannot be split as easily.
> 1 votes

---
Tags: turing-machines, parallel-computing, lambda-calculus, church-turing-thesis
---


# Question
Title: Is there an algorithm for converting Turing machines into equivalent Lambda expressions?
We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure.

But is there an algorithm, a systematic way for us to convert a Turing machine into a Lambda Calculus expression? Is it impossible to have such algorithm? (meaning does it go down to undecidability or NP-Completeness?) if not, are there any papers or algorithms for doing so?

# Answer
> 10 votes
Sure there is. I'm going to assume you can figure out how to convert Haskell into the lambda calculus; for a reference, look at the GHC implementation.

Now just to be clear: a Turing Machine is a (finite) map from `(State, Token)` pairs to `(State, Token, Direction)` triples. We'll represent the states as integers (this is okay by the finiteness of the map) and represent the tokens by the values `True` and `False`. The directions will be `L` and `R`.

The state of the machine is represented by a four-tuple `(State, LeftTape, Head, RightTape)`, where `LeftTape` and `RightTape` are lists of tokens and `Head` is a token.

The initial state for input `n` is `(1, [], True, replicate (n-1) True)`. The machine halts if it enters state 0. The result is the number of symbols on the tape.

Now it is easy to see that the following defines an interpreter:

```
data Direction = L | R
type Configuration = (Integer, [Bool], Bool, [Bool])
type TM = Map (Integer, Bool) (Integer, Bool, Direction)

tail' :: [Bool] -> [Bool]
tail' (_:xs) = xs
tail' [] = []

head' :: [Bool] -> Bool
head' (x:_) = x
head' [] = False

step :: TM -> Configuration -> Configuration
step tm (s, lt, h, rt) = (s', lt', h', rt')
     where (s', t, d) = tm ! (s, h)
           (lt', h', rt') = case d of
               L -> (tail' lt, head' lt, t:rt)
               R -> (t:lt, head' rt, tail' rt)

run :: TM -> Int -> Int
run tm n = go (1, [], True, replicate (n-1) True)
    where go (0, lt, h, rt) = length . filter id $ lt ++ [h] ++ rt
          go c = go (step tm c)

```

(This implementation may have bugs, but a correct implementation is not far.)

Now simply take your favourite Turing Machine, partially apply the run function to it, and convert the resulting `Int -> Int` term into the lambda calculus.

# Answer
> 12 votes
All proofs of the equivalence of these two models of computation are *constructive*, that is they describe an algorithm for converting a program from one model of computation to the other. However, I caution you that these proofs are probably rather informal, and may not satisfy you. You may get luckier if you consult original work by computing pioneers (Turing, Church, Post, Kleene and their ilk).

# Answer
> 10 votes
Since you did not like Yuval's answer, you deserve this one:

The equivalence of Church's $\lambda$-calculus and Turing machines is proved in the Appendix of Alan Turing's 1937 paper On computable numbers, with an application to the Entscheidungsproblem.

---
Tags: turing-machines, lambda-calculus, turing-completeness, church-turing-thesis
---


# Question
Title: Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays
Is there a mutual exclusion or semaphore or locking algorithm that only relies on atomic reads and atomic writes of shared memory and can tolerate a delay in propagation of the written data between processes? I.e. if process A writes to shared memory, process B might not see the change for a while (but process A will see the change immediately).

It seems to me that this might be theoretically impossible if I don't have an upper bound on the delay, but if I do have such an upper bound, is there an algorithm that's a little more clever than just sticking busy-waits for the worst-case delay between the reads and writes of any other non-delay-tolerant algorithm?

(I'm trying to solve this problem: Cross-window synchronization (critical sections) in the browser)

# Answer
If you don't have access to atomic primitives like CAS, you're going to have to depend on voluntary synchronization between the two halves. This means side A cannot proceed until side B has acknowledged that side A took the mutex.

Since we know nothing about the shared memory, we cannot assume that write to two seperate regions will be seen in order (some caches will change the order that writes present). We will have to assume that there is some atomic thing, like an int32. We're also going to have to assume that when you say atomic read and write, you never see tearing on the integer, and it's monotonic (if I numbered A's writes, and I've observed #13, I will never again see the #12 value that had been written).

If you do this, then just take one bit (say, the MSB) and use that as an ownership token over the communication used to handle locks. If it's a 1, it means A gets to write. If it's a 0, B gets to write. Whenever A sets it to a new value, the MSB is always 0, and when B sets it to a new value, the MSB is always 1. Now, with nothing but normal reads and writes, we can tell who has the "rights" to the communication channel.

Now the communication channel consists of the lower 31 bits. You can send anything you please across this, including requests to acquire or release a "mutex." If you want to acquire it, you simply have to wait for it to be your turn to read, send a "request mutex" message, and wait for the reply to say "mutex OK"

EDIT: From our chat discussion, it appears what is really needed is a lottery process to select a master thread, who then takes over the job of being the "kernel" that manages the mutual exclusions. All it needs is a way to detect when the master thread died, and elect a new master. This lets us split the problem up into a slow part, which is very robust, and a fast part that works as long as a master is present.
> 2 votes

---
Tags: algorithms, mutual-exclusion
---


title: One way recurrence O(N)->O(1)

text:
# Question
Title: One way recurrence O(N)->O(1)
Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence).
I'm trying to find a system where it's fast to find many steps in the future immediately, whereas it's **hard or impossible to work out a previous state**.
for example, if I know state = X at time t, I would like to calculate state at t+n steps in the future, done in order O(1) rather than having to iterate n times.
I'm assuming state has an implicit modulo of around some power of 2 so it must be restrainted to a given number of bits at each time.
Does anyone know of a system that could provide this?
Many thanks.

# Answer
There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated numbers is to mask the true state. Here's how it works. You take your $b$-bit number $x\_t$ to be the true state at time $t$, but the number your RNG generates is $x\_t \text{ mod } m$, where $m$ is much less than $2^b$. Then you can specify $g$ to be $x\_{t+1} = a \cdot x\_t \text{ mod } n$, with $a$ and $n$ large numbers that are relatively coprime.

This way, if you collect the numbers generated by this RNG, you need at least a couple of data points before you can make educated guesses about $x\_t$, and even then it's not easy. The period of the RNG is $n$.

The answer to your question about whether there exist easy-to-compute functions that are hard to invert is an open question, known as the existence of one-way-functions. Existence is known to imply **P $\not=$ NP**, so it probably won't be resolved for some time. That's for functions that are easy to compute in *one* iteration; functions that allow an arbitrary amount of time steps to be computed is a question on a whole other level.

Of course, if you relax the question to mean a function whose inverse requires, say, $\Omega(b^2)$ time to invert, rather than superpolynomial time, there are options. For example, you could keep the function $x\_{t+1}=a\cdot x\_t \text{ mod }n$. To invert that function, you need to find the the multiplicative inverse of $a \text{ mod } n$. This takes $O(b^2)$ time. Then you will be able to compute $x\_{t}$ given any $x\_{t+1}$ in, again $O(b^2)$ time, as $x\_t = x\_{t+1} \cdot a^{-1} \text{ mod }n$.

This function is easy to compute for several steps, if you are willing to do some precomputation. Note that $x\_{t+1} = a \cdot x\_t$ and $x\_{t+2} = a\cdot x\_{t+1} = a^2 x\_{t}$, so $x\_{t+k} = a^{k} \cdot x\_t$. Now you can precompute $a, a^2, \ldots, a^k$ up to some $k$, and from then on you will be able to compute $a\_{t+j}, 1 \leq j \leq k$ efficiently.
> 7 votes

# Answer
(A follow up to the accepted answer, to some degree...)

Using a hash function in this way is somewhat equivalent to fast forwarding a pseudorandom number generator.

A linear congruential generator (LCG) can be skipped ahead and back \[link\], in fact many PRNG's can be skipped/jumped ahead\[link\]. The problem with fast-forwarding any hash/PRNG is that if you know the cycle period (which you do with most PRNGs), you can effectively move back 1 state by fast-forwarding (period−1) steps.

Thus if we found a way to, say, move forward quickly with SHA-256, then the first person to correctly estimate its cycle period would also have the ability to move backward as well.

The only fix for this is to have a system with a huge number of varied cycles. E.g. having 256 bits worth of different cycles lengths, which each cycle being 64 to 256 bits in cycle length, fitting in 512 bits of state.

There is no known way of doing this, but should one be found, you've solved multiple comp-sci and cryptology problems, and made efficient signing of messages trivial.

tl;dr - if you can go forward and calculate its cycle length, you can go backward.
> 4 votes

# Answer
It's possible to construct a public/private keypair and an update function $f:S \to S$ with the properties that:

* computing $f$ takes $O(1)$ operations, given the public key;
* with the private key, you can compute $f^{n}$ (i.e., iterate $f$ $n$ times) in $O(\lg n)$ operations. In other words, anyone with the private key can compute the state at time $t+n$ from the state at time $t$ in $O(\lg n)$ operations -- not quite $O(1)$, but close.
* without knowing the private key, you cannot invert $f$ (you can't go backwards)
* with knowledge of the private key, it is possible to invert $f$ (to go backwards)

The primary drawback is that the private key allows both fast iteration and inversion. For some applications this might be OK; only you can tell whether it will work for you.

The function $f$ is just squaring modulo $N$, where $N$ is a RSA modulus ($N$ is the public key; the factorization of $N$ is the private key). See https://crypto.stackexchange.com/a/15141/351 for more details.
> 3 votes

---
Tags: algorithms, cryptography, pseudo-random-generators, random-number-generator
---


# Question
Title: How to find all shortest paths between two nodes in a weighted undirected graph?
How to find all shortest paths between node 1 and N in a weighted undirected graph? There can be multiple edges between two nodes.

I want to find all nodes that can be on a shortest path. For example:

> 10 11
>
> 1 2 1
>
> 1 3 1
>
> 3 4 2
>
> 4 5 1
>
> 5 6 1
>
> 5 10 2
>
> 1 7 1
>
> 7 8 3
>
> 7 9 2
>
> 9 10 2
>
> 8 10 1

The answer is

> 1 7 8 9 10

because there are two shortest ways

> 1 7 8 10

and

> 1 7 9 10

# Answer
To tell whether a vertex $v$ is along some possible shortest path from $s$ to $t$, compute $d(s,v)$ (the length of the shortest path from $s$ to $v$) and $d(v,t)$, and then.....

You can compute $d(s,v)$ for all vertices $v$ efficiently using....

(It's your exercise, so I'll let you have the pleasure of working out how to fill in the blanks.)
> 3 votes

---
Tags: graphs, shortest-path
---


# Question
Title: Minimum number of rounds to notify a hierarchy of people with DP
I'm trying to figure out a problem reported in Kleinberg (ch 6 no.16). I know that there are solutions based on ordering, anyway i'd like to understand if another way exists.

Basically, we have a hierarchy of people represented by a tree. The root person has to postpone a picnic due to rain: in a first moment he calls by phone his direct subordinates, one at a time. As soon as each subordinate gets the phone call, he must notify each of his direct subordinates, one at a time. This continues until everyone has been notified. Any person at a node can notify only his own children in the tree (e.g. no grandchildren).

You can view this process as being devided in rounds: in one round, every person who has been notified can call one of his subordinates (thus in parallel).

It's important to note that the number of rounds required to notify everyone depends on the sequence in which each person calls their direct subordinates. E.g. with the following tree we have 2 rounds if A notifies B first, or 3 rounds if A decides to start from D:

The problem requires an efficient algorithm that determines the minimun number of rounds. My approach is the following: like in largest independent set i obtain first a post order transversal $v\_1, v\_2, \ldots, v\_n$ of the whole tree. Then i define the following recurrence relation:

$$ OPT(v\_i)= \begin{cases} 0 \qquad \qquad \qquad \qquad \qquad \qquad \quad \hbox{if leaf} \\ \displaystyle\max\_{v\_j\ \text{child of}\ v\_i}\left\\{k(v\_i), 1 + OPT(v\_j)\right\\} \ \hbox{otherwise} \end{cases} $$

Where $k(v\_i)$ is the children count of the node $v\_i$, and $OPT(v\_i)$ is the minimum number of rounds required to notify the people contained in the subtree with $v\_i$ as root.

Let's consider a more complex tree:

Due to the recurrence we have $OPT(v\_i)\_{v\_i \in \left\\{C, E, F, G, H, I, L \right\\}} = 0$, $OPT(B)=4$, $OPT(D)=2$ and finally $OPT(A)=5$ that, as you can see, is exactly the minimum number of rounds to reach every node in the tree.

Please, if my approach is wrong can you give me some hint or counter example showing that ordering is required?

# Answer
I do not think it is correct.Please consider this example: Suppose $a$ has $k$ children. Two of them($b,c$) are chains of $k+1$ nodes the other are leaves. We have:

1. $OPT(b) = OPT(c) = k$
2. All other $OPT$ are zeroes.

According to your algorithm we should have $OPT(a)=1+k$ But it is not correct:

let order of notifitions be $b,c,.....$

($c,b..$ is the same and the other are suboptimal)

* Notification for the subroot of $b$ will stop at $0+(1+k)=1+k$ (time=0)
* Notification for the subroot of $c$ will stop at $1 + (1+k)=2+k$ (time=1)
* We don't really care about other leaves(they will all be notified by $k$)

This is different than the output to your algorithm. The approach that FrankW proposed is the correct one!
> 2 votes

---
Tags: dynamic-programming
---


title: number of subsets where GCD equals to X

text:
# Question
Title: number of subsets where GCD equals to X
The original statement for this problem can be found here

This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD equals to X.

**Eg:**

```
OriginalSet = {2, 3, 5, 6, 6}
numberOfSubsets(2) => 3 // there are 3 subsets where their GCD equals to 2
i.e. {2, 6}, {2, 6}, {2, 6}

```

**Limits:**

```
OriginalSet.length < pow(10, 5),
element_of_an_array < pow(10, 4),
X < pow(10,4)

```

I bruteforced the solution and it gives me TLE. I am stuck on this question for few days now. Could you explain me how to solve this efficiently.

**Edit**

* the subset size is not limited to 2. It is from the power-set.
* It guarantees that for a given query there is only 100 unique numbers.

# Answer
See the solution for "585E - Present for Vitalik the Philatelist" here where is says "Let's calculate the number of subsets with gcd equal to 1". I hope you can extend the logic from there to solve the problem for X.
> 2 votes

# Answer
You can use dynamic programming approach to solve this problem; however, you have not yet specified what the limitation on X is. This is too similar to the question Algorithm for finding maximum mutually coprime subset of a multiset of integers In that way, you could also use GCD instead of LCM to solve your problem since the question I gave is a special case of your question.
> 1 votes

---
Tags: algorithms, discrete-mathematics, number-theory, counting
---


# Question
Title: Proving that a language of Turing machine descriptions is/is not Turing recognizable
How to approach to solve this question and the likes of it?

> Let $L$ be the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length.
>
> a) Is $L$ Turing-recognizable? Prove your answer.
> b) Is the complement of $L$ Turing-recognizable? Again prove your answer.

Please have a look at my approach, is it correct? :

> Since the string representation of set of all the Turing Machines (say S) is Infinite countable and Recursively Enumerable, there fore there exists a Turing Machine that accepts S. Now, if we choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings, then the set we get (Say T) will also be Infinite Countable and recursively Enumerable and will have a Turing Machine which accepts it. That is why it is language T is Turing Recognizable. Similarly complement of T is Turing Recognizable.

@Rick if I use the following code :

```
RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject // accept as string in L complement
     if not rejected for any string then accept as a string in L

```

This code will select all the $M$ which accept all strings of even length and do not accept any string of odd length. Then now since we have a membership algorithm for $L$ (as well as for $\overline L$), then can we say that the $L$ and $\overline L$ are recursive?

# Answer
The problem with your proposed algorithm is where you say

> ... choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings.

How are you going to do this? If you could, then you would have answered your original question, i.e., you've fallen into the trap of assuming what you want to prove.

In fact, your language $L$ *isn't* recursively enumerable.

---

There are at least two ways to show that $L$ isn't r.e.. I'll give one, but it requires that you be able to show that $L$ isn't recursive. Rice's theorem is an immediate way, but you don't know it yet, so you'll have to reduce it from a known non-recursive language like the Halting language. That's not hard, but I won't give it now. Just accept for the moment that $L$ is not recursive.

Suppose that we wrongly guessed that $L$ was recursive and we wanted to build a recognizer for it. One way is to simply dovetail all strings and test whether $M$ accepted any odd-length strings (so we'd know then if $M$ wasn't in $L$). This gives us a proposed recognizer for $L$:

```
RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject

```

If $M$ accepts any odd-length string, sooner or later this program will find it and so will be able to recognize that $M$ is *not* in $L$. Of course this isn't what we wanted: we need to make a program that recognized if a given $M$ *is* in $L$. However, all is not lost---simply by changing the "reject" to "accept" we would have made a recognizer for the complement, $\overline{L}$, so we've stumbled across the interesting fact that $\overline{L}$ is recognizable.

So what, you might ask? Remember, if a language $A$ and its complement, $\overline{A}$ are both r.e., then $A$ must be recursive. We just showed that $\overline{L}$ is r.e., so if $L$ was also r.e., then we could conclude that $L$ was recursive. However, you've accepted that $L$ is not recursive, so we must conclude that $L$ must not be r.e..
> 2 votes

---
Tags: computability, semi-decidability
---


title: Stable Marriage Problem unique match

text:
# Question
Title: Stable Marriage Problem unique match
I'm having some thoughts and I'd like to have your opinion about it. Given a basic, normal instance of SMP *(men-women, men choose)*, we define $\mu$ to be the set of all *stable matches*.

Each member of $\mu$ consists of men-rank, which describes the satisfaction index of the men - which in this case the member with the highest rank is the *male-optimal* match.

So if we run the stable-match known algorithm, the output would be the match with the highest rank, because the algorithm always returns the *men-optimal* and *female-pessimal* match - **lets denote this match by $A$**.

Now, lets replace the roles, and run the algorithm again. We denote the output match by $B$ - which is the *female-optimal* and *male-pessimal* match.

Assuming $A=B$:

1. Can we say that this instance has a ***unique stable match***?
2. What else can we say about this instance?

# Answer
I will answer your first question.

By definition, a matching $A$ is *male-optimal* if for any male $m$ and stable matching $C$, $A(m) \succeq\_m C(m)$, that is, $m$ prefers $A(m)$ at least as much as $C(m)$, where $A(m)$ is the female assigned to $m$ by $A$.

Similarly, by definition, a matching $B$ is *male-pessimal* if for any male $m$ and stable matching $C$, $B(m) \preceq\_m C(m)$.

Now suppose that $A$ is male-optimal, $B$ is male-pessimal, and $A = B$. Take any male $m$ and any stable matching $C$. By definition, $A(m) \succeq\_m C(m) \succeq\_m B(m) = A(m)$, and so $C(m) = A(m)$. In other words, $C = A$, and so the stable matching is unique.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Can normal physics laws be simulated in Digital physics?
Physics is defined as the study of an object {matter or energy} with its interaction with other objects:

> Physics is the study of matter, energy, and the interaction between them.

On the other hand, Digital physics is based on computations and information.

> Digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable.

If we have a universal computer {a universal turing machine} and a program that can compute the evolution of the universe (Digital Physics) running on it, can this specific program simulate our normal physics laws like the classical mechanics laws or quantum mechanics laws ?

1- Can we simulate a universe with its fundemental laws {i.e physics} and change these laws by a universal computer accordingly ?

2- How a simulation of a universe (if any) with fundemental laws {like physics} would help to further understanding in physics ?

3- Is there any form of universal turing machine to apply these simulation ?

# Answer
> 7 votes
The laws of physics are stated in the form of mathematics. Differential equations are pretty popular, for example classical mechanics can be described with differential equations.

You can program a computer to take some initial state of the universe and apply all the laws of physics to it to get a new state of the universe. This comes with a couple of caveats. First, you need to somehow discretize the time steps you compute. Differential equations operate under continuous time, but a numerical simulations does discrete steps. It's reasonably well understood how to do that without losing too much precision. This brings us to a second problem, precision. Physics is generally formulated using real (or complex) variables, but computers only deal with finite precision. Usually this is ok, because in reality we can also only distinguish things with finite precision. Lastly, our laws of physics are not yet complete. There are a number of phenomena where we don't really know what's supposed to happen, so the simulation won't represent the real universe perfectly, even if we start with a proper starting state (which we can also only guess) and use sufficient precision and sufficiently small time steps.

Note that it is completely impractical to simulate all laws of physics as we know them on real computers. Even simulating single molecules with all relevant laws is very hard even for supercomputers.

Nevertheless, physicists simulate things all the time, sometimes using bold approximations to cut down the required computation. It's really important in physics to do simulations. Wikipedia has on overview article on Computational Physics and Richard Feynman has written a classic paper called Simulating Physics with Computers.

It is of course also possible to tweak the laws of Physics a bit and do your simulation. You can change the equations, or the constants and see what happens to your simulated system. You can for example find that changing some constants just a little produces an inhospitable universe.

Now I don't think it's possible to change fundamental mathematical truths in your simulated universe, because Physics makes no prediction about mathematics. You can't change the laws of Physics such that 1+1 != 2.

# Answer
> 1 votes
It is currently believed that physics requires real numbers. Digital computers cannot work with real numbers. We spend a great deal of time in simulations trying to cope with the difference between real numbers and IEE-754 floating point representations of those numbers. We also try to avoid operating in the known environments where those differences are resolvable (which occurs in many chaotic systems). We also abuse statistics, and seek to argue that a sampling of universes can describe a statistical variable in the real world.

One option would be to do symbolic manipulation, if you could identify a set of symbols which fully identified state of the universe. However, the ability to model *our* universe that way is highly questionable, due to self-referential issues. Read about Godel's incompleteness theorem if you're interested in questions about predicting the state of our universe, not just an arbitrarily specified universe.

# Answer
> 1 votes
This question is too broad to be useful I think. The general answer is, of course, **no** because all computers we have operate in a discrete manner while laws of physics seem to be pretty damn continuous (even with quantum mechanics in the way). So you'll always have rounding errors, steps which have nothing in-between and insufficiently random behavior.

I think the best example is just simple bouncing balls problem. If you have ever implemented it you know that, as the program goes on, balls get stuck in each other, as in this image I've drawn for you:

This is one of many possible cases where your program breaks laws of physics and what you have to do is to either calculate collision before it happens or calculate what should've happened once laws of physics have been broken.

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


# Question
Title: Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$
I am trying to prove a theorem (title) given in a starred problem in Sipser's book. I have absolutely no idea how I would go about showing it, and after trying a few different approaches came here looking for a hint. I don't want a full answer, but would really appreciate a few words to point me in the right direction. This is not a homework exercise.

# Answer
> 1 votes
A paper of Day gives the following hint: Show that for every $c$, *every* long enough string $z$ contains a prefix $x$ with $K(x) \< |x| - c$.

He also gives a hint to the hint: Use the fact that a machine for computing $x$ can use both the given program $\pi$ and its length $|\pi|$, which gives it an extra $\log|\pi|$ bits of information.

---
Tags: information-theory, kolmogorov-complexity
---


# Question
Title: Programming language where every expression makes sense
Per recommendation I am reposting this from Stack Overflow.

Recently I have been thinking about following issue.

Consider the code for a standard "Hello world!" program:

```
main()
{
    printf("Hello World");

}

```

Now almost any change in this code will make it completely useless, in fact almost every change will prevent the code from compiling. For example:

```
main(5
{
    printf("Hello World");

}

```

Now to the actual question. Is there a programming language where every possible combination of symbols - that is, every expression - makes sense? I tried thinking about some sort of solution and came up with two:

1. Postfix with a limited number of variables. Essentially all variables are already defined before you write any code and you have to work just with them. Theoretically you can than perform an arbitrary number of operations by forming a chain of many simple programs, each one of them feeding results to others. Code could be written as a series of characters in postfix notation;
2. "Postfix" with a stack of variables. Variables are stored on a stack; every operation takes two variables from the top and puts the result in their place. The program ends when it reaches the last operation or variable.

Personally I hate both of these. Not only are they limited, they are inelegant. They are not even real solutions, more like workarounds, essentially "offshoring" some work to an external process.

Does anyone have any other idea how to solve this problem?

# Answer
Redcode, the assembly language behind codewars, was explicitly written to have very few halting instructions, because the code often gets mangled before it finally gives out, and the more opportunities it has to halt, the less interesting the game is.

You see very few such languages in practice because we don't just want a program to run, we want it to run in the way we expect. If you can make a typo and change the way the program ran, it must be acceptably close to the original expected behavior, or the programmers with seethe in frustration.

There is some precedence for such things by using natural languages rather than formal languages, but it's not what I would call a large field when you compare it to the use of formal languages. If you're interested in such programming languages, the natural language processing community is where I'd look.

Another field you could look at is genetics. There are remarkably few genetic sequences which are simply invalid. Plenty of them that aren't very effective at reproductions, but very few invalid ones.
> 31 votes

# Answer
The idea of a universal Turing machine uses just such a "programming language": a coding of Turing machines as natural numbers, represented for example in binary, such that every natural number denotes a Turing machine, i.e., program. In this language, every string of zeroes and ones is a program.

If you're worried that some numbers might code invalid programs, this can be side-stepped as follows. Imagine writing out all strings in the character set of your programming language (say, Java), in lexicographic order, starting with strings of length one, then two, then three, ... Then, make a new programming language by letting the number $n$ stand for the $n$th string in the list that's a valid Java program. In the new programming language, programs are just natural numbers and every natural number is a valid program.

I'm sure there are also esoteric programming languages where every string is a program; however, if you're just asking for a list of those, I think your question is off-topic here.
> 16 votes

# Answer
Check out Jot, a Turing-complete language based on combinatory logic, where every sequence of 0s and 1s (including an empty sequence) is a valid program.
> 13 votes

# Answer
Extending a programming language so that every expression makes sense is always possible, but not interesting. For example, you can just assign the meaning “do nothing” to any expression that the original language rejects.

Designing a programming language where every expression makes sense in a “you can execute it” way is not particularly useful. A good programming language is not just one where a monkey can type on a keyboard and write a valid program, but one where a programmer can easily write the program that they intended to write. Writing valid programs is not the difficult part of programming: the difficult part is writing a program that performs what was expected of it. Rejecting obviously incorrect programs is very helpful in this respect.

Another way to tackle this is to fully define the semantics of all possible inputs, including specifying what compile-time, load-time or run-time error should be generated for each input if any. That is, “abort the program after printing `Syntax error at line 42` on the standard error stream” is part of the defined semantics of the language. Every expression “makes sense” in that it has a defined meaning. Is that a useful meaning? Maybe — after all, if the program is obviously wrong, rejecting it is useful.
> 12 votes

# Answer
One nice example is whitespace. In the language proper, any combination of operators are valid. The operators are space, tab and newline (specifically "\n"). **All other characters are considered comments**.

This answer, and indeed your question (as well as this entire web page) are examples of valid whitespace programs (though they may not do anything particularly interesting).
> 8 votes

# Answer
I would like to address the idea that many posters have given, that such a language would be "useless". Perhaps it would be useless for humans to write, manually, with the intention of solving some particular task. However, despite being a majority use-case for programming languages, that's certainly not the only use-case. Several use-cases come to mind where such a language is useful, and we can look to those fields for examples of such languages.

Firstly Cort Ammon's allusion to genetics is spot on: the program transformation in the question (substituting `)` for `5`) can be seen as a *mutation*. This kind of manipulation is common in the field of *evolutionary computation*; in particular *genetic algorithms* perform such transformations on *strings*, whilst *genetic programming* transforms *programs*. In either case, we usually want to assign meaning to every possibility, since that will produce the most compact search space.

Genetic algorithms rely on some sort of *evaluation function* for strings; if we use a programming language interpreter as our evaluation function, then we have a scenario where a programming language which assigns meaning to all possible strings is useful. In genetic programming, it is assumed that our evaluation function is a programming language interpreter, but we may choose various *representations* for our programs; for example, many systems operate on abstract syntax trees. If we choose strings as our representation, then we recover the same scenario as with genetic algorithms.

Another situation where we may want every string to be a valid program is when *enumerating* programs. This is related to the bijection mentioned by CodesInChaos, but we may prefer to operate on strings rather than Natural numbers for several reasons:

* If there is some structure in the language, eg. we can assign meaning to sub-strings, this may be lost when translating to Natural numbers. In this case we may prefer to use strings, in order to reason about and transform sub-strings locally, rather than representing the whole-program as a number. This is analogous to how we might prefer to use bitwise operations on an int rather than arithmetic expressions, when each bit has an individual meaning. This is basically a generalisation of the evolutionary scenario.
* We may want to generate the programs on demand; for example, we might begin executing a program which is completely undetermined, and only generate (eg. randomly) the individual instructions (eg. characters) when/if the instruction pointer reaches them. This is common in algorithmic information theory, where the program is a Turing machine tape, and the aim is to characterise the behaviour of randomly-generated programs. For example, we can formulate the Solomonoff prior over arbitrary strings as the probability that a universal Turing machine with a random tape will output that string.

In terms of example languages, many evolutionary computation systems are based on stack languages like the Push family. These tend to allow arbitrary streams of tokens (which we could represent as individual characters). Sometimes (like with BrainSlugs83's Brainfuck example) there are restrictions on balancing parentheses; however, we can relate this to *self-delimiting programs*, in that a string like `[` may not be a valid *program*, but it *is* a valid *program prefix*. If we imagine a compiler/interpreter reading source code from stdin, then it won't *reject* a string like `[`, it will simply wait for more input before continuing.

Languages like Binary Combinatory Logic and Binary Lambda Calculus arose directly out of work on algorithmic information theory, eg. from http://tromp.github.io/cl/cl.html

> This design of a minimalistic universal computer was motivated by my desire to come up with a concrete definition of Kolmogorov Complexity, which studies randomness of individual objects.
> 7 votes

# Answer
*Real* programming languages are to convey meaning to *people*, not computers. As plenty of fun texts with almost randomly shuffled letters floating around the 'ńet show, people can read gibberish and make sense out of it, even without overtly noticing the mangling. Just think back how hard it is to find typos and other such errors in texts.

A programming language like what you ask for would make people understand what they want to read, not what is written down. Debugging in languages where there are a limited set of legal statements, where there is not much ambiguity possible, is already hard enough. Good languages *reduce* possible interpretations due to e.g. transposed symbols or typos. Natural languages are also notorious for their redundancy, for the same sort of reason.
> 2 votes

# Answer
In the Brainfuck Programming Language, ***almost*** every possible binary expression can be interpreted as a program. -- That is, you could take a completely good program, type a bunch of garbage into it, and, it would still be compilable / interpretable without any issues.

*(**Edit:** It turns out you have to match opening and closing square brackets, but otherwise, the above is true.)*

It achieves this via these two simple methods:

1. All of the commands it understands are a single byte (In BF they are all single ASCII characters for example\*).
2. All of the characters it does not understand, it discards as comments.

The programming language is Turing complete (meaning, it can do anything that any other language can do).

**\*:** *It turns out not all BF commands are a single ASCII byte -- i.e. brackets MUST be matched -- so as is, that language doesn't meet the first criteria there. -- But any language that does meet both criteria would fulfill what the OP is asking for.*
> 0 votes

---
Tags: programming-languages, computation-models
---


# Question
Title: Is "flops" a reliable measure of deciding computational capacity?
Is "flops" a reliable measure of deciding computational capacity? If we do matrix multiplication and matrix addition of the same size of matrix, do the flops remain the same?

Referring to question https://stackoverflow.com/questions/329174/what-is-flop-s-and-is-it-a-good-measure-of-performance

I am curious to know if I do a 100x100 matrix multiplication and matrix addition, will the FLOPS remain the same? Can I say time required by the processor (and hence FLOPS) remain same regardless of operation?

Can someone also comment on how theoretical maximum FLOPS of a processor are determined. And if FLOPS is taken as standard measure of performance, then can someone use an algorithm that will always be highly efficient but not useful in scientific computing?

# Answer
Much computing is shuffling data around, from memory to CPU(s) and viceversa, from disk to memory, and so on. Performance could well be determined by non-processing needs. If there are several CPUs involved (many supercomputers really do the computing on graphics cards, which are massively parallel SIMD computers), jobs that can't be sped up by processing separate data streams with the same instructions will go much slower than extensively studied and paralellized to death computations like massive matrix operations.

So the answer is no, raw FLOPS aren't a good measure of performance. Again, the only reliable performance measure for your specific problem is the performance on it. "Performance" isn't a number, it is a vector with multiple independent aspects, and the requirements of your problem are also a vector, in the same dimensions. How well they match over a wide range of possible problems to a particular machine can't be reduced to a single number.
> 4 votes

---
Tags: parallel-computing, floating-point
---


title: General theory on Hash Functions?

text:
# Question
Title: General theory on Hash Functions?
I'm a computer engineer and I've met hash functions theoretically speaking in "algorithms and data structure" and then in several applications (like databases, operating systems, computer architecture etc).

But I was wondering if there's some general theory about these functions and, specifically, if there's a general way to build such functions.

# Answer
> 3 votes
There is a general cryptographic theory of provably secure hash functions. There are several inequivalent notions of security. Hash functions are a cryptographic primitive, and the goal of cryptography is to explore relations between different primitives – can one primitive be constructed using the other.

All of this, however, has no relevance on hash functions practically used, for various reasons. Practically, hash functions come in two flavors: cryptographically secure and not cryptographically secure. There isn't really any theory regarding the construction of both types. Cryptographically secure hash functions are constructed according to various and changing heuristic principles, but their strength lies in the community trying to break them and failing. Non-secure hash functions have other properties, and successful one have emerged from practice.

Don't construct your own hash function. If you attempt to construct a cryptographically secure hash function, you will probably fail unless you're an expert. Constructing a non-secure hash function is less harmful, but still, existing ones are probably better than one you would come up with.

If you want a hash function with a particular integer range $\[a,b\]$ (as indicated in the comments), there are two basic options:

1. If your function doesn't need to be cryptographically secure, you can use the formula $h \pmod{b-a+1} + a$, where $h$ is a general-purpose hash function. The range of $h$ should be large compared to $b-a+1$, unless $b-a+1$ happens to divide the range of $h$.
2. If your function does need to be cryptographically secure, you have to be more careful. In that case I suggest you ask a question on the dedicated crypto stackexchange site.

# Answer
> 1 votes
> A hash function is any function that can be used to map data of arbitrary size to data of fixed size.

So basically a hash function is just like a mathematical function that transforms one set of values to another.

The most useful set of Hash functions are the **Cryptographic Hash Functions**

They are widely used in **Password Salting**, **Data Integrity** a a LOT of another applications etc.

The reason they are used in many many many applications are because they are essentially **One-Way**. Once they are made, it is difficult to reverse them.

## Avalanche Effect

On theoretical foundation, which is the foundation of such One Way Hash Functions (And probably what you're looking for) is the Avalanche Effect.

The effect ensures that, `H(x)` is very very different than `H(x+1)`

Eg:

The more this effect, the harder it is is reverse a hash.

YOu might also be interested in this

# Answer
> 1 votes
For *searching*, you want a hash function that distributes the input data for a particular case with no (or little) collisions. If you know the data beforehand, you can construct a *perfect hash function* for that data. Useful if you are searching for a fixed set of keys, mostly.

If you don't know the data beforehand, you are restricted to work on some distribution of the input data and try to find a hash function that flattens that distribution to something uniform (since frequent hash values will tend to give collisions). Fun really starts the moment your potential input data is a very large set has a complex distribution (think English words as used in everyday text as a sample of the set of all possible strings), of which you select a small sample for each particular run (say the words used in this question and its answers, which has a particular extra twist as the word usage here isn't exactly everyday). Plus you want a simple function, that is fast to compute on the available hardware (a slow function negates the advantages of hashing).

Add the problem of *algorithmic attacks*, i.e., an attacker who knows the hash function shouldn't be able to feed it a large number of keys that collide, thus fouling up the hash search.

# Answer
> 0 votes
Since practical applications must be empirically driven, this paper uses Genetic Programming to ensure a more uniform distribution of hash vales: Repairing and Optimizing Hadoop

---
Tags: algorithms, data-structures, hash
---


# Question
Title: NLP: Automatically categorize words semantically into non-predefined classes
I am looking for a method to categorize a given word into semantically into classes. A simple example would be:

`chair -> furniture`

The most reasonable way to do so that comes to my mind, would be to create a tree containing words, where `chair` is a predecessor of `furniture`. Then one could define a threshold that describes the level of the tree predecessor that should be taken as the result.

Is there some existing research/tools or even trees that fulfill the described task? I cannot find anything in google because I do not know the specific term for my problem. *Keyword Clustering* as a technique seems a little different, because is works on existing data and return multiple matches.

# Answer
You're looking for Wordnet https://en.wikipedia.org/wiki/WordNet ...
> -1 votes

---
Tags: natural-language-processing
---


# Question
Title: Till which layer does the loopback packet goes?
I want to know exactly till which layer in the OSI model the 127.0.0.1 (loopback) packet goes till it is returned to the upper layer. I read some where it goes till data link layer. but as i was told data link layer cannot see the ip address then how data link layer decide that the packet has to be send "up" instead of "down".

# Answer
When you say "layer", you are probably thinking of the OSI model, also known as the seven-layer model.

However, real TCP/IP implementations don't actually fit the OSI model very well. The OSI model was designed by a standards committee 30 or 40 years ago, based on how the committee members thought network stacks *ought* to be designed -- but that was before the Internet and without the advantage of the experience we have today.

127.0.0.1 is an IP address, and the loopback functionality of 127.0.0.1 is associated with the IP protocol. The IP protocol can be thought of as most closely associated with the "network layer" (in the OSI model). So, you could say that the answer is "the network layer".

But, it's important to realize that this is a bit of a lie. In real operating systems, there's not necessarily a clean separation between the TCP stack and the IP stack; the two are closely hooked together. So, it's doesn't make sense to ask "the code that does loopback processing -- what layer is it at?". The code that does loopback processing could plausibly be considered part of the TCP/IP stack, and the TCP/IP stack combines elements of the network layer, the transport layer, and the session layer. Loopback processing might also be performed in a separate device driver that, from the operating system's perspective, looks like another device (just like another Ethernet card, but different), so one could even make an argument that the code is really part of the data link layer or physical layer. See how the seven-layer OSI model isn't really adding much insight here? The code is what the code is; trying to attach a label based on one of those seven layers is a human construct, one that in this case isn't a very good match to reality.

It's probably better to think of the OSI model as a plausible vocabulary for talking about network *protocols*, but it's less helpful when talking about the structure of networking *code*: the structure of the code doesn't necessarily correlate well to the seven layers of the OSI model.

TL;DR: the OSI model is a lie.
> 5 votes

# Answer
Simple answer: The 127.0.0.1 address is an IP layer concept, so it has to be handed to the IP layer for correct routing and so.

More complex answer: The 127.0.0.1 address might be common enough in practical use that upper layers of the TCP/IP stack in your particular operating system cut corners and handle it specially. Even your application might figure out it is supposed to talk to itself and never touch the TCP/IP stack.

No, the totally misguided (and finally dead and buried) OSI protocol stack has no relevance to any of this.
> 1 votes

---
Tags: computer-networks, protocols
---


# Question
Title: How can a device decipher spoken English words?
I want to know how it can process spoken English words and Pull out a matching response? Is it a chip or a installed software? Does it take up a lot of space? Thanks.

# Answer
You'll want to read about natural language processing. It's an entire field of research and practice. There are many textbooks and online resources that provide an introduction to that area.
> 1 votes

---
Tags: functional-programming
---


title: Logical equivalence and equality

text:
# Question
Title: Logical equivalence and equality
Let be $F=(A\land B)$ and $G=\neg(\neg A \lor \neg B)$. Which of the following statements are correct

$F=G, F\equiv G, \neg F=\neg G, \neg F\equiv\neg G$?

Is there a difference?

# Answer
*Equality* is a syntactic notion, *equivalence* is a semantic notion. Two expressions are *equal* if they are the same expression — in other words, an expression is only equal to itself. Two logical expressions are *equivalent* if they have the same truth value in every interpretation.

Two equal expressions are always equivalent, but the converse doesn't hold. For example, $A \equiv \lnot\lnot A$ but $A \neq \lnot\lnot A$.
> 7 votes

---
Tags: equality
---


# Question
Title: How to decide if a propositional formula is a well formed?
So, I have the following propositional formula: (((P → Q) ∨ S) ↔ T) How do I decide if it's well formed?

# Answer
> 3 votes
Perhaps this might help.

Well-formed: $(P \lor Q)$.

Not well-formed: $(P \lor Q$.

More generally, in class you must have been shown a definition of well-formed formulae. Use it.

---

Well-formed formulae are usually defined inductively. One possible definition is:

1. For every variable $v$, $v$ is a well-formed formula.
2. For every well-formed formula $\varphi$, $(\lnot \varphi)$ is well-formed.
3. For every binary symbol $\circ \in \\{ \land, \lor, \rightarrow, \leftrightarrow \\}$ and two well-formed formulae $\varphi,\psi$, $(\varphi \circ \psi)$ is well-formed.
4. "No other formula is well-formed."

The last "axiom" isn't quite formal. What we really mean is that a formula is well-formed only if it can be proved well-formed by using the first three axioms. (This is equivalent to the definition using least fixed points, which you might have seen in class.)

What all this means is that in order to show that a formula is well-formed, all you need to do is derive it from the axioms. Showing that a formula isn't well-formed could be more difficult. Since the set of well-formed formulae is context-free, there is an efficient algorithm which given a formula decides whether it is well-formed.

---
Tags: propositional-logic
---


# Question
Title: Complement of a Language which is set of Turing Machine descriptions
If $L$ is the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length.

What will be $\overline L$ ?

a) set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length as well as any strings of odd length.

b) set of strings $\langle M\rangle$ such that $M$ accepts all strings of odd length and does not accept any strings of even length.

# Answer
Neither. A machine $M$ is not in $L$ if either it rejects some even-length string or it accepts some odd-length string (or both).
> 2 votes

---
Tags: formal-languages, terminology, closure-properties
---


title: How to improve the binomial algorithm?

text:
# Question
Title: How to improve the binomial algorithm?
Good evening!

I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form:

$$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n$$

Then, tried to estimate the number of recursive calls that would be used by the method call `binomial1(100, 50, .25)`

```
public class Binomial {

    public static double binomial1(int N, int k, double p) {
        if (N == 0 && k == 0) return 1.0;
        if (N < 0 || k < 0) return 0.0;
        return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);
    }
    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        int k = Integer.parseInt(args[1]);
        double p = Double.parseDouble(args[2]);
        StdOut.println(binomial1(N, k, p));
        StdOut.println(binomial2(N, k, p));
    }

}

```

I think I have $2^N$ recursive calls of binomial1, that is to say 10000 calls with our exemple. Because of this line:

```
return (1.0 - p) *binomial1(N-1, k, p) + p*binomial1(N-1, k-1, p);

```

I would like to explain it better... I think my answer is too intuitive: each time I call the algorithm, I call it twice until N reach 0.

**How to improve with an implementation that would be based on saving computed values in an array?**

# Answer
The answer for your question *How to improve with an implementation that would be based on saving computed values in an array?* is to use memoization (sometimes known as dynamic programming), which incidentally is the same as *saving computed values*. But this is a somewhat odd solution to the problem. A better solution is computing the binomial coefficient according to the formula and recursion in vonbrand's comment, and use exponentiation to complete the calculation.

For completeness, here are the formula and the recursion: $$ \binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots (1)}, \qquad \binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}. $$

---

There are many ways to use memoization here. One natural way is to loop on `n`, and compute all values of `binomial1` in sequence. This only requires knowing the values of `binomial1` on `n-1`, which you save in an array. (Similarly you store the new values in a second array.) As an optimization, you only need to compute these values up to the given `k`.

I'll let you come up with matching code and runtime analysis.
> 2 votes

---
Tags: algorithms, efficiency, algorithm-design
---


# Question
Title: How to solve an arrangement problem at the Archive Nationale of France using graph theory?
Good evening! I'm actually doing an internship at the Archives Nationales of France and I encountered a situation I wanted to solve using graphs...

# I. The dusty situation

We want to optimize the arrangement of books of my library according to their height in order to minimize their archive cost. The height and thickness of the books are known. We already arranged the books in ascending order of height $H\_1,H\_2,\dots,H\_n$ (I don't know if it was the best thing but... that's the way we did it). Knowing each book's thickness, we can determine for each $H\_i$ class the necessary thickness for their arrangement, call it $L\_i$ (for example, the books that are $H\_i = 23\\,\mathrm{cm}$ tall might have total thickness $L\_i = 300\\,\mathrm{cm}$).

The library can custom manufacture shelves, indicating the wished length and height (no problem with depth). A shelf of height $H\_i$ and length $x\_i$ costs $F\_i+C\_ix\_i$, where $F\_i$ is a fixed cost and and $C\_i$ is the cost of the shelf per length unit.

Note that a shelf of height $H\_i$ can be used to store books of height $H\_j$ with $j\leq i$. We want to minimize the cost.

My tutor suggested I model this problem as a path-finding problem. The model might involve $n+1$ vertices indexed form $0$ to $n$. My mentor suggested I work out the existing conditions, each edge signification and how to work out the valuation $v(i,j)$ associated to the edge $(i,j)$. I would also be OK with other solutions as well as insights.

For instance we have for the *Convention* (a dark period of the French History) such an array:

\begin{array}{|c|rr} i & 1 & 2 & 3 & 4\\ \hline H\_i & 12\\,\mathrm{cm} & 15\\,\mathrm{cm} & 18\\,\mathrm{cm} & 23\\,\mathrm{cm}\\ L\_i & 100\\,\mathrm{cm} & 300\\,\mathrm{cm} & 200\\,\mathrm{cm} & 300\\,\mathrm{cm} \\ \hline F\_i & 1000€ & 1200€ & 1100€ & 1600€ \\ C\_i & 5€/\mathrm{cm} & 6€/\mathrm{cm} & 7€/\mathrm{cm} & 9€/\mathrm{cm}\\ \end{array}

# II. The assumptions of a trainee bookworm

I think I have to compute an algorithm between Djikstra, Bellman or Bellman-Kalaba... I'm trying to find out which one in the following subsections.

## 1.Conditions

We are here with a problem of pathfinding between a vertex $0$ and a vertex $n$, $n$ must be outgoing from $0$ (that is to say, a path (or a walk) must exists between $0$ and $n$

## 2.What to compute (updated (25/10/2015))

// *Work still under process as far as I don't know which vertices to and which edges to model...*

### My best guess

I think we get rid of at least one type of shelves every time we find a shortest path from the array, but that's only my assumption... ;).

I think the best way to model how to buy shelves and store our books must look like the following graph, *(but, please, feel free to criticize my method! ;))*

vertices:

* $i\in\[1,4\]$ are shelves we can use to store our books.
* $0$ is the state where no book is stored. Using this vertex allows me to use each cost formulas (edges).

edges: $F\_i+C\_ix\_i,i\in\[1,4\]$ are the cost using a type of shelve. for instance: $F\_1+C\_1x\_1$ fom 0 is the cost using only type 1 shelves to store our parchments, manuscripts...

Yet, from here I don't know how to create my shortest path problem.

Indeed, I would not know where would I have stowed all my books.

This leads me to another idea...

### another idea...

Here, I am searching for the shortest path from a given vertex to the 0 state, that is to say, knowing that the highest document is $type \ i$ tall, I am searching for the cheapest way to arrange my documents.

vertices:

* $i\in\[1,4\]$ are shelves we can use to store our books.
* $0$ is the state where all books are stored. Using this vertex allows me to use each cost formulas (edges).

edges: $F\_i+C\_ix\_i,i\in\[1,4\]$ are the cost using a type of shelve. for instance: $F\_1+C\_1x\_1$ from 3 is the cost using $type \ 1$ shelves after using $type \ 3$ shelves to store our parchments, manuscripts...

Yet, I don't know where to put $F\_4+C\_4x\_4$.

## 3.How to compute

I think that we have to start with the higher shelves as far as we can then store the smaller books...

Do

> We take $L\_n$ cm of with the $H\_{i=n}$ height in a shelve of their height + $z$ cm of an $H\_{i=n-1}$ height until it becomes more expensive than taking the $H\_{i=n-1}$ shelve. then $i=i-1$

While $i\neq0$

Finally, I don't know how to make $x$ varying...

That is to say how to choose to put $x\_i$ documents in $4$ or $3$ for instance.

# Answer
I see you as asking, "I want to solve this with Dijkstra's algorithm but I can't set up a good graph to run on," therefore I will present you with such a graph.

# A digraph where vertices are sets of shelved books.

Okay, we have books with heights $H\_n,$ $1 \le n \le N$ and widths $W\_n,$ with heights in ascending order for each book, and we want to group them into shelves.

Reuse these numbers for solution nodes $n,$ where that node represents a solution state "all books $i \le n$ have been shelved." We will therefore start at node $0$ and seek to get to node $N$ by the shortest path with Dijkstra's algorithm. These nodes are the vertices of our graph.

We then draw from node $i$ to any node $j \gt i$ a directed edge which assumes that all of those intermediary books will be shelved with one shelf, i.e. the length of this edge is $$L\_{ij} = F\_j + C\_j~\sum\_{n=i+1}^j W\_n,$$where I have assumed that when you were saying the cost of the sum was $F\_i + C\_i x\_i$ the subscript $i$ on the $x\_i$ was totally meaningless.

Dijkstra's algorithm will then give us a shortest-length path to node $N.$
> 5 votes

# Answer
---

I think I have a solution to your problem. Hopefully I haven't misunderstood something in the definition of your problem. Here it goes:

I'm going to describe a Dynamic Programming approach. It's an $O(n^{2})$ algorithm, which means that since the number of books is huge it's not going to help you a lot. (you need to modify it a bit!). With some work, you can turn said Dynamic Programming approach into an instance of finding the shortest path on a Directed Acyclic Graph. (Which itself is a dynamic programming algorithm :P)

Suppose there are $n$ books all of different height.

Suppose also that the optimal cost is achieved by assigning the books to $i$ shelfs of height $h\_{1},h\_{2},...,h\_{i}$ where $h\_{1}\<h\_{2}\<...\<h\_{i}$.

Let's prove the following two things:

A. $C\_{a}\>C\_{a-1}$

Suppose the contrary. Let $B\_{a-1}$ be the set of books assigned to shelf $a-1$ Then $cost = other,stuff + C\_{a-1}\*thickness(B\_{a-1})$

Since, we assumed, $C\_{a}\<C\_{a-1}$, let's transfer all books of shelf $a-1$ to $a$ (which is possible since $h\_{a-1}\<h\_{a}$.

So,now, $cost =other,stuff + C\_{a}\*thickness(B\_{a})$ which is lower than before. Hence, we have a contradiction due to the Optimality we assumed.

So $C\_{a}\>C\_{a-1}$ for all shelfs created

B. Let $j$ be a book that is assigned to shelf $a$. Let's prove that $height(j)\>h\_{a-1}$

This is fairly easy. If $height(j)$ was smaller than $h\_{a-1}$ we could put the book into shelf $a-1$ for a better cost (due to A).

Of the two things we've proven, B is the significant one.

Let $dp\[a\]$= the optimal cost for shelving books $1...a$ so that there is a shelf of $height(a)$. You have to find a way to define $dp\[a\]$ by the values $dp\[1\],dp\[2\],....dp\[a-1\]$

I'm going to stop here. If you are familiar with Dynamic Programming, using fact B, you will easily come up with the recurrence. Otherwise, ask :). As I said, this can be turned into a DAG problem. Knowing the relation above, it's easy to realize what the edge $(a,b)$ stands for and define its cost.

Last but not least, like I said above,as books are large, you cannot use the algorithm for each and every book. I think that representing its height by the sum of its thickness should do the trick. (I think it's already like that from your statement)

(I'm guessing number of different heights is much much less than number of books)

---
> 7 votes

# Answer
Sometimes just "zooming in" on the "nearest problem" in the literature can help understand the theory and background behind the problem, build an abstraction, and eliminate spurious details. The nearest problem in the literature to yours seems to be what is known as "variable size bin packing problem". Sample papers are included below. This problem is highly theoretically studied and some off-the-shelf software exists, it shows up in optimizing packing boxes in eg trucks shipping containers. There are also versions where one can adjust container size. There are many algorithmic approaches. eg, from 1st paper:

> The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into a minimum number of three-dimensional rectangular bins.
> 0 votes

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


# Question
Title: What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?
I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am assuming it means a path from s to t with maximum total capacities once you sum the capacities across the path. However, I am not sure what the term bottleneck adds to the definition nor was I sure if that was correct. Is that the correct definition?

# Answer
> 2 votes
While I suspect that the notion of "bottleneck" has been introduced in an earlier lesson, it's all in the document you link.

Page 8:

> Edmonds and Karp’s first rule is essentially a greedy algorithm:
>
> > Choose the augmenting path with largest bottleneck value.

Page 11:

> For any flow network $G$ and any vertices $u$ and $v$, let bottleneck $G(u,v)$ denote the maximum, over all paths $\pi$ in $G$ from $u$ to $v$, of the minimum-capacity edge along $\pi$.

This sentence is a bit hard to parse. Unfolded:

Let $P\_G(u,v)$ be the set of all $u$-$v$-paths in $G$, and $E(\pi)$ the set of edges that comprise a path $\pi$ in $G$. Then,

$\qquad\displaystyle G(u,v) = \max\_{\pi \in P\_G(u,v)} \quad \min\_{e \in E(\pi)} c(e)$.

Note that $\min\_{e \in E(\pi)} c(e)$ is the bottleneck (capacity) of $\pi$.

So Edmongs-Karp picks the $s$-$t$-path with the largest bottleneck (in the residual network), which means it picks the path it can send the most flow over (while maintaining conservation of flows).

---
Tags: algorithms, terminology, network-flow, max-flow
---


# Question
Title: The Interleaved Transition System for 2 Independent and Concurrent Transition Systems
This question is about **Model Checking** for **Software Formal Verification**
How do you model the joint behavior of 2 *independent* and *concurrent* transition systems?

Specifically, given the two independent and concurrent Transition Systems below; **TS1** and **TS2** (left to right).

A tutor proposed that the resulting Interleaving Transition System **ITS** is

I understand how all the shown states and transitions of this **ITS** were gotten, however, why is there no transition from state `(l1,q1)` to `(l3,q2)`--as would be expected if both **TS1** and **TS2** transitioned on action `a`?

# Answer
By definition, the interleaving operator is not synchronized, so any transition in $TS1\ |||\ TS2$ corresponds to a transition in a single component while the other one remains in whatever state it is.

More generally, in process algebras like CSP, the parallel composition operator $||$ can be parameterized with a set of symbols on which to synchronize - for example, you could consider $TS1\ |\[\\{a\\}\]|\ TS2$, which has the same states and $b$-transitions as $TS1\ |||\ TS2$, but only two (synchronized) $a$-transitions $(l\_1,q\_1)\to(l\_3,q\_2)$ and $(l\_2,q\_1)\to(l\_1,q\_2)$. In particular, $|||$ is the special case $|\[\emptyset\]|$.

The point is that (together with additional operations like hiding) this allows you to represent a far greater variety of models of interaction.
> 1 votes

---
Tags: model-checking, software-verification, transition-systems
---


title: What does $\log^{O(1)}n$ mean?

text:
# Question
Title: What does $\log^{O(1)}n$ mean?
What does $\log^{O(1)}n$ mean?

I am aware of big-O notation, but this notation makes no sense to me. I can't find anything about it either, because there is no way a search engine interprets this correctly.

For a bit of context, the sentence where I found it reads "\[...\] we call a function \[efficient\] if it uses $O(\log n)$ space and at most time $\log^{O(1)}n$ per item."

# Answer
> 16 votes
You need to ignore for a moment the strong feeling that the "$O$" is in the wrong place and plough on with the definition regardless. $f(n) = \log^{O(1)}n$ means that there exist constants $k$ and $n\_0$ such that, for all $n\geq n\_0$, $f(n) \leq \log^{k\cdot 1}n = \log^k n$.

Note that $\log^k n$ means $(\log n)^k$. Functions of the form $\log^{O(1)}n$ are often called *polylogarithmic* and you might hear people say, "$f$ is polylog $n$."

You'll notice that it's easy to prove that $2n=O(n)$, since $2n\leq k n$ for all $n\geq 0$, where $k=2$. You might be wondering if $2\log n = \log^{O(1)}n$. The answer is yes since, for large enough $n$, $\log n\geq 2$, so $2\log n \leq \log^2n$ for large enough $n$.

On a related note, you'll often see polynomials written as $n^{O(1)}$: same idea.

# Answer
> 9 votes
This is an abuse of notation that can be made sense of by the generally accepted *placeholder convention*: whenever you find a Landau term $O(f)$, replace it (in your mind, or on the paper) by an *arbitrary* function $g \in O(f)$.

So if you find

$\qquad f(n) = \log^{O(1)} n$

you are to read

$\qquad f(n) = \log^{g(n)} n$ for some $g \in O(1). \hspace{5cm} (1)$

Note the difference from saying "$\log$ to the power of some constant": $g = n \mapsto 1/n$ is a distinct possibility.

*Warning:* The author may be employing even *more* abuse of notation and want you to read

$\qquad f(n) \in O(\log^{g(n)} n)$ for some $g \in O(1). \hspace{4.3cm} (2)$

Note the difference between (1) and (2); while it works out to define the same set of positive-valued functions here, this does not always work. Do not move $O$ around in expressions without care!

# Answer
> 6 votes
It means that the function grows at most as $\log $ to the power of some constant, i.e. $\log^2(n)$ or $\log^5(n)$ or $\log^{99999}(n)$...

# Answer
> 2 votes
"At most $\log^{O(1)} n$" means that there is a constant $c$ such that what is being measured is $O(\log^c n)$.

In a more general context, $f(n) \in \log^{O(1)} n$ is equivalent to the statement that there exists (possibly negative) constants $a$ and $b$ such that $f(n) \in O(\log^a n)$ and $f(n) \in \Omega(\log^b n)$.

It is easy to overlook the $\Omega(\log^b n)$ lower bound. In a setting where that would matter (which would be very uncommon if you're exclusively interested in studying asymptotic *growth*), you shouldn't have *complete* confidence that the author actually meant the lower bound, and would have to rely on the context to make sure.

---

The literal meaning of the notation $\log^{O(1)} n$ is doing arithmetic on the family of functions, resulting in the family of all functions $\log^{g(n)} n$, where $g(n) \in O(1)$. This works in pretty much the same as how multiplying $O(g(n))$ by $h(n)$ results in $O(g(n) h(n))$, except that you get a result that isn't expressed so simply.

---

Since the details of the lower bound *are* in probably unfamiliar territory, it's worth looking at some counterexamples. Recall that any $g(n) \in O(1)$ is bounded in *magnitude*; that there is a constant $c$ such that for all sufficiently large $n$, $|g(n)| \< c$.

When looking at asymptotic *growth*, usually only the upper bound $g(n) \< c$ matters, since, e.g., you already know the function is positive. However, in full generality you have to pay attention to the lower bound $g(n) \> -c$.

This means, contrary to more typical uses of big-oh notation, functions that *decrease* too rapidly can fail to be in $\log^{O(1)} n$; for example, $$ \frac{1}{n} = \log^{-(\log n) / (\log \log n)} n \notin \log^{O(1)} n$$ because $$ -\frac{\log n}{\log \log n} \notin O(1) $$ The exponent here grows in magnitude too rapidly to be bounded by $O(1)$.

A counterexample of a somewhat different sort is that $-1 \notin \log^{O(1)} n$.

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


title: Hex to decimal conversion

text:
# Question
Title: Hex to decimal conversion
I'm converting hex ( in positional fractions) to decimal

question : 0x3c.e8

my attempt: $3\*16^1 + 12\*16^0$ yields $60$

$ 3c$ = $ 60 $ in decimal so i know its 60.

then $.e8 \*10 $ (since I want base ten) = $232$

my question is do I just say 60.232?

# Answer
> 3 votes
**Hint**:

The respective weights of the hex digits are (in decimal)

$$16,1,\frac1{16},\frac1{256},$$

hence

$$3\cdot 16+12\cdot1+\frac{14}{16}+\frac{8}{256}.$$

---
Tags: base-conversion
---


title: Is language regular?

text:
# Question
Title: Is language regular?
Suppose we have language $a^{\binom{n}{k}} n,k \in N$ is this language regular ? If it is not, I should use pummping-lemma? It it is regular, I will use proof by induction ?

# Answer
> 1 votes
**Hint**. For any integer $n\>0$, $\binom{n}{1}=n$, so can you specify what strings are in your language?

---
Tags: regular-languages
---


# Question
Title: Algorithm to decide whether two vertices are ancestors/descendants of each other
Is there an algorithm that performs the following:

**Input:** A directed graph and two vertices within that graph
**Output:** Whether one of the two vertices is the ancestor of the other

For example, in this graph:

A is an ancestor of D. B is neither the ancestor nor the descendant of C.

The best I can think of doing is performing a DFS/BFS from each of the two input vertices and seeing if either search includes the other vertex. This takes O(|V| + |E|) time. Is there a well-known, faster algorithm?

# Answer
> 5 votes
DFS only requires $O(|V|+|E|)$ time, not $O(|V| \cdot |E|)$ time. (Same for BFS.) Therefore, DFS is an efficient solution for this problem. This is about as efficient as you hope for, as it takes that much time just to read the entire input -- you can't hope for something faster.

The problem becomes more interesting if we're provided the graph $G$ and allowed to do some precomputation, and then want to answer many queries efficiently. This is considerably more challenging, but in some cases, it is possible to do better than running a DFS from scratch every time you receive a new query.

* For instance, if the graph is a tree, there is an efficient solution: do a DFS once, and store the pre and post numbers at every node; then each ancestor query can be answered by testing for interval containment.
* In a more general graph, this is known as a reachability query, and there are algorithms in the literature for this problem. See, e.g., https://cs.stackexchange.com/a/41432/755 and https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038. Without loss of generality, you can assume the graph is a dag (if not, first compute all strongly connected components in linear time, and label each vertex with its scc; then you only need to consider the dag of scc's).

---
Tags: graphs
---


# Question
Title: In the Curry-Howard isomorphism as applied to Hindley-Milner types, what proposition corresponds to a -> [a]?
(Using Haskell syntax, since the question is inspired by Haskell, but it applies to general Hindley-Milner polymorphic type systems, such as SML or Elm).

If I have a type signature `f :: a -> [a]`, what is the logical proposition encoded by that type signature?

I know that type constructors like `->`, `(,)` correspond to "operations" in your logic: `->` corresponds to the "implies" symbol $\rightarrow$.

I assume `[]` is a type constructor as well, and have a feeling that the answer may have something to do with its recursive definition, which I know could be implemented as something like:

```
data List a = Cons a (List a) | Nil

```

but I'm not sure what this means in logic-verse.

# Answer
> 5 votes
One way to interpret types as logic is as the existence conditions for values of the return type. So `f :: a -> [a]` us the theorem that, if there exists a value of type `a`, there exists a value of type `[a]`. The implementation of the function is the proof of the proposition.

Here's a more detailed explanation:

Basically, data constructors let us build similar things to sums and products (OR and AND), but we can have multiple variants, and we can specially "tag" the type with a name to distinguish it (like the name `List`).

They also let us build them recursively: for a proposition $a$, the proposition $\[a\]$ can be viewed as a solution to the equation $x(a) \iff \top \vee (a \wedge x(a) ) $

Things become a bit clearer when you write the definition of List using GADT-style, pseudocode similar to what you'd see in Agda:

```
data List : Type -> Type where
    Nil : ∀ a . List a
    Cons : ∀ a . a -> List a -> List a

```

This gives us two things: the constructors (or functions), which act as axioms for the propositions of `List`, and axioms for pattern-matching or deconstructing them.

Roughly speaking, it introduces the following axioms into the logic:

* For any proposition $a$, $\[a\]$ holds.
* If $a$ holds, and $\[a\]$ holds, then $\[a\]$ holds
* If $\[a\]$ holds, then either $\top$ holds, or $a \wedge \[a\]$ holds.

These are pretty useless when interpreted as logic, since we always know $\top$ holds, deconstructing there doesn't give us much useful information

Without quantifiers or more powerful type extensions (GADTs, Type Families, dependent types, etc.), you can see that we can't really prove interesting things, which is why you often don't see much about interpreting standard Haskell types as logic.

# Answer
> 3 votes
List types are a bit strange as proposition. They don't really correspond to anything directly familiar but it is easy to see what they are equivalent to. Because nil exists you can always prove `[a]` for any `a` so list types are always very easy to prove, in particularly they are trivially equivalent to any tautology that has already been proven. So introducing them is a bit uninteresting. Moreover the elimination rule has an issue with it. Namely you have to prove something from `[]` in order to eliminate a list which doesn't give you any new assumptions. Thus I can usually transform any proof using a list elimination into a proof not using it. However I might know something about the list that contradicted it being empty in which case it is a lot more interesting.

So a lot of the time it is kinda boring but other times it is actually somewhat interesting thanks to proof relevance. Haskell doesn't have proof relevance however so in Haskell lists are just boring.

In some sense (I'm fudging stuff here) lists in Haskell correspond to something that is equivalent to the constantly true boolean operator. So not negates a boolean, id keeps it the same, and the thing that list behaves like always gives true no matter what you plug into it.

---
Tags: programming-languages, type-theory, functional-programming, curry-howard
---


# Question
Title: Recalculating shortest path after changing the weights
I have a weighted, directed graph. I do the following. Given nodes $s$ and $t$ I compute shortest path. Then, I decrease weights of some edges and want to see if there is now another shortest path. Of course, I can recompute shortest path, but I want something faster.

For example, one approach would be to store shortest paths from $s$ to $t$ for every edge in the graph. Then, when I change the weights it takes constant time to check if the shortest path changed (even though, the first step takes much more time). The drawback is that I have to store many paths and to calculate all simple paths in advance, so I'm seeking for alternatives.

So my question is if it's possible to check if the shortest path changed after we decrease edge weights?

Edit: Apparently, this is a problem of dynamic graphs. I didn't delve into the algorithms, so, which algorithm can I use for this problem? I want to improve on running time Dijkstra algorithm.

# Answer
> 2 votes
The standard term for this kind of problem is "dynamic shortest paths" or "shortest paths in a dynamic graph". Here "dynamic" refers to the fact that the graph might be updated, and you want to update the shortest-paths information (hopefully more efficiently than re-computing it from scratch). There are many kinds of updates to the graph one can consider: deleting a vertex, inserting a vertex, deleting an edge, inserting an edge, increasing the length of an edge, decreasing the length of an edge. Your problem is the special case where we only have to deal with decreases to edge weights.

So, I suggest you search the research literature (e.g., using Google Scholar). You should find a bunch of papers that discuss algorithms for this situation.

# Answer
> 2 votes
For given graph $G$ calculate $ d1\[v\] $ for all vertices $v$ of $G$ where
$d1\[v\]=length\ of\ shortest\ path\ from \ s \ to \ v \ in\ G $.
For graph $G'$ which is graph $G$ with all its edges reversed calculate $d2\[v\]$ where
$d2\[v\]=length\ of\ shortest\ path\ from \ t \ to \ v\ in\ G'$

Let $spl$ be the length of shortest path from s to t in $G$.
For a weight change of edge $uv$ check if $d1\[u\] + new\\\_wt(uv) + d2\[v\] \le spl $.

If previously $uv$ was in some shortest path then $d1\[u\] + new\\\_wt(uv) + d2\[v\]$ will be less than $spl$. Else if it was not on shortest path and $d1\[u\] + new\\\_wt(uv) + d2\[v\] \le spl $ then it will be in shortest path.

(How to check if it was not on shortest path : $d1\[u\] + old\\\_wt(uv) + d2\[v\] \> spl $.)

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Why doesn't decision tree work in case find minimum
When we would like to prove lower bound comparison algorirthm, we often use decision tree, for example sorting by comparisons.
So let's consider find minimum in array $a\[1..n\]$ by comparison. Lower bound for that problem is commonly known - $n-1$ comparisons.

**However, how to use decison tree in order to prove lower bound ?**
It seems that it might be (analogously to sorting problem):
$n$ - number of possible results (similiar to $n!$ in sorting).
So the number of comparison (minimal height of tree) is $\log\_2(n) \< n - 1$.

Believe me, I have tried to understand it, but I can't.

# Answer
There is more than one technique to prove a lower bound on the depth of decision trees. One technique you have seen is bounding the depth of a decision tree by the logarithm of the number of its leaves. As you comment, this technique doesn't give the correct lower bound for the case of computing the minimum. However, we can lower bound the depth of a decision tree computing minimum directly.

Take any reachable leaf $\ell$ in a decision tree for minimum, and consider the entire path $p$ leading to it. Construct a graph whose vertices are the input elements $x\_1,\ldots,x\_n$, two elements $(x\_i,x\_j)$ being connected if they are compared in $p$. I claim that this graph must be connected, and I show this below. A connected graph on $n$ vertices must have at least $n-1$ edges, and this shows that the leaf must have depth at least $n-1$. In particular, the depth of the decision tree is at least $n-1$.

Now to the proof of the claim. Suppose that the graph contains more than one connected component, say it contains the components $C\_1,\ldots,C\_m$. Since the leaf $\ell$ is reachable, there is a linear ordering compatible with the results of the comparisons in each connected component $C\_i$. We can put together these linear orderings into a linear ordering of all elements in $m!$ different ways. In particular, we can have $C\_1 \> C\_2 \> \cdots \> C\_m$, and we can have $C\_1 \< C\_2 \< \cdots \< C\_m$. This means that it is consistent with the comparisons in $p$ that the minimum is in $C\_m$, and it is also consistent that the minimum is in $C\_1$. Hence whatever the tree outputs at $\ell$ will be wrong in at least one linear ordering consistent with the comparisons in $p$, showing that the tree doesn't compute the minimum.
> 4 votes

# Answer
In this case, the trivial lower bound $\Omega(n)$ holds, because you cannot tell the minimum until you have seen all the values. (By a simple adversary argument, it can take $n/2$ comparisons before the minimum value is processed.)

The information-theoretic bound (decision-tree height) always holds. But it is not always tight.
> 2 votes

---
Tags: lower-bounds
---


title: Induction proof of alpha-beta search

text:
# Question
Title: Induction proof of alpha-beta search
Is there a functional specification of alpha-beta search that makes it easy to prove by induction that the algorithm works?

# Answer
> 2 votes
The following is an easy to understand approach to tree pruning. It's easy to see why it's correct.

Let's start with ordinary minimax evaluation. If you are trying to evaluate position $p$ when it's the minimizing player's turn, you return $\min\\{\operatorname{eval}(p',\text{max}) \mid p'\text{ successor of }p\\}$.

To do tree pruning you change what $\operatorname{eval}(p',\text{max})$ does. Instead of returning a single value, it streams messages to you. Messages like "my final value will be at greater than 3", "my value will be greater than 20", "my value is 23". If the minimizer already got a message saying that one successor $p'$ has has value $5$, and it gets a message from $\text{eval}(p'',\text{max})$ saying that its value will be at least $10$ then the minimizer will close the channel with $\text{eval}(p'',\text{max})$.

It's easy to translate this into code and it's clear that it's functionally identical to minimax.

But it's not quite the algorithm presented on Wikipedia under alpha beta pruning.

---
Tags: optimization, recursion, game-theory, induction
---


title: Modified Clique Problem

text:
# Question
Title: Modified Clique Problem
We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}\_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}\_{2K}$ iff $G$ has two *SEPARATE* cliques $K\_1$ and $K\_2$ of size $\dfrac{N}{2}$ (where $|V| = N$). My speculation is that $\mathcal{G}\_{2K}$ is in NP and the corresponding existential problem is NP-complete, but I can't find any reduction form any well-known NP-complete problem.

## **Hence the question is: Is $\mathcal{G}\_{2K}$ in P or it's NP-complete?**

The question I asked is equivalent to these two questions: 1. Given graph $G=(V,E)$ and integer $k$, can we partition the vertices into two disjoint cliques of size $k$ and $|V|-k$. 2. Given graph $G=(V,E)$ can we partition the vertices into two independent sets of size $k$ and $|V|-k$?

# Answer
The problem is equivalent to deciding whether the complement graph of $G$ has a bipartition $(A,B)$ such that $|A|=|B|$. In order to check if such a bipartition exists, one can first compute an arbitrary bipartition $(A,B)$. If no such bipartition exists, we are finished. If it does exists, we must check whether we can flip single connected components of this bipartition (which mean all vertices in $A$ of a particular connected component are moved to $B$ and vice versa) such that we obtain a new partition where $A$ is equal to $B$. Using a dynamic programing approach similar to the partition problem, this can be decided in polynomial time. Thus the original problem is also in P and not NP-hard unless P equals NP.
> 5 votes

---
Tags: np-complete, clique
---