# Question
Title: Functional Programming and Category Theory
I'm a math Ph.D. having done research in Algebraic Geometry and Algebraic Topology in grad school for my thesis and I've studied a fair amount of category theory in the process (e.g. having worked through most of "Categories for the Working Mathematician" as well as more specialized topics in Homological Algebra). Is there some good intro to functional programming that emphasizes the link with category theory in the process?

Context: In my workplace I've run into people that are into functional programming and like throwing around category theory jargon, but when you ask for details they typically fail to even be able to define what a category is. I'm hoping that there's more to it in programming than just abstract nonsense. In other words, for someone who actually knows category theory and has done some functional style programming (immutable classes, map, filter, reduce etc.) in imperative languages is there a good intro to FP in the context of category theory?

# Answer
These colleagues of yours, would they happen to be Haskell aficionados? They might have told you that Hask was a category made from Haskell, but that is a lie, notheless a very useful one that inspires new programming techniques.

If you would like to find out how category theory informs functional programming, I can recommend Bartosz Milewski's Category theory for programmers.

There is also the older Category theory for computer science by Michael Barr and Charless Wells, which is more of a straight introduction to category theory. It might be a good book for functional programmers who only ever learned the bastardized category theory through functional programming.
> 7 votes

# Answer
Category theory is useful only in a few places in functional programming:

* Implementing libraries that work with arbitrary type constructors. Category theory is good for this kind of highly abstract code. For example, one can define a product of arbitrary endofunctors, a co-product of arbitrary endofunctors, etc., in a library.
* Implementing certain advanced idioms of functional programming, such as "free monad", "optics", "Church encoding of initial algebras". Category theory is a good language for designing such idioms and proving their properties. See, for example, papers about "profunctor optics" or Wadler's "recursive types for free".
* Formulating laws for new typeclasses, such as "filterable", or for combining typeclasses, such as "monad and filterable and applicative and monoid at the same time". Without category theory, the typeclass laws appear to be chosen at random. Category theory provides good intuition and assurance that the laws are chosen correctly and consistently.
* Proving certain general properties that apply at once to all type constructors, or to all typeclasses, etc. For example, the product of two semigroups is a semigroup, the product of two monoids is a monoid, the product of two functors is a functor, the product of two monads is a monad, the product of two applicative functors is applicative, the product of two pointed functors is pointed, the product of two contravariant functors is contravariant, the product of two filterable functors is filterable, etc. All these examples are particular cases of a general theorem (the product of two typeclasses is again an instance of the same typeclass) that applies to many typeclasses at once. Category theory helps to formulate and prove that theorem using the language of F-algebras and F-algebra morphisms.

Other than that, category theory as such is not directly useful for programming. One can (and should) learn functional programming on its own, in its practical aspects, and category theory is not useful for that.

Category theory is also not useful for answering most of the theoretical questions directly related to practical programming. For example, if you want to prove that a given data type is a lawful monad or a lawful applicative functor, etc., category theory will not be directly helpful. You will need to use proof techniques specifically adapted to functional programming.

I recorded a talk: https://youtu.be/Zau8CxsfxOo with the title "What did category theory ever did for us (functional programmers)" where I gave examples in Scala for specific programming questions where category theory helps to get some answers.

Summary:

* Functional programmers do not require category theory in order to master the main features and design patterns that FP uses to write better code. For example, one can (and should) first learn how to use monads, functors, pattern matching, recursive algebraic data types, map/filter/fold, etc., in a concrete programming language with specific examples. Category theory will not help master these techniques even though the words "functor" and "monad" originally come from category theory.
* At a certain point, programmers will see examples of typeclasses with laws, and understand why those laws are important in practice.
* There will be lots of different laws. To make some order and system among those laws, we can formulate the laws as a generalized "lifting" type signature with "twisted" function types. At this point, it will be useful to write down the definitions that generalize all the examples. Those will be the definitions of category, morphisms, and functors.
* We can then use the definitions of category and functor as generalizations that cover the laws of functors, contrafunctors, filterable functors, filterable contrafunctors, monads, applicative functors, applicative contrafunctors, comonads, and perhaps other type classes.
* I show some examples of categories that are used to describe functors, monads, applicatives, and filterable functors.
* I cover filterable functors in more detail, with backdrop of category theory, because filterable functors are rarely explained as a separate typeclass.
* Another example where category theory is useful: "type constructor libraries", i.e. libraries with functions parameterized by a *type constructor*. Examples of these are free functor / free monad / etc., and Church encoding of types (including recursive type constructors, e.g. the Church encoding of a free monad). Programmers who need to implement these libraries will need to understand how these constructions are defined and what laws need to hold. Category theory provides some limited guidance about that.
* Conclusion 1: programmers need to learn functional programming and not category theory. The special knowledge required in functional programming (e.g., how to implement and use a free applicative functor in your programming language) is not going to be covered by any book in category theory.
* Conclusion 2: basic definitions of category theory (category, functor, natural transformation) are useful as condensed formulations of general laws for a number of typeclasses. Unless a programmer has experience dealing with all the different laws of those typeclasses, it is unlikely that an appreciation of category theory will be of much help. Even for advanced programmers who are working with high-level type constructor libraries, a study of category theory is unlikely to be of any use beyond a few basic concepts and definitions (category, functor, natural transformation, monoid, initial object, Yoneda identities, F-algebra).
* Conclusion 3: knowledge of category theory will not help us derive or prove laws for specific typeclasses, and will not help us implement those typeclasses correctly in code. The reason is that category theory is so general that it only talks about laws that apply generally to a large number of very different typeclasses (functor, monad, filterable functor, applicative functor, pointed functor, contravariant functor, etc.). For practical coding, e.g. to verify that our implementation of a specific monad is lawful, we need to learn not category theory but the techniques of symbolic derivation and proof.

I am writing a new free textbook ("Science of Functional Programming", https://github.com/winitzki/sofp) to develop and explain these techniques with practical programmers in mind. My book is going to be very light on category theory, and I'm not going to use any advanced abstract concepts unless there is a significant gain for practical work. Having written down several hundred step-by-step proofs, I have found what derivation techniques are useful and what definitions from category theory are helpful when proving the theoretical properties of practically relevant code.

Examples of category theory knowledge that has, so far, proved to be unnecessary and **not useful**:

* monad is a monoid in the category of endofunctors
* any monad comes from a pair of adjoint functors
* a free monad comes from the free/forgetful functor adjunction

In contrast, naturality laws are used in at least 30% of all proofs, and the functor composition law is also used in at least 30% of proofs. This shows the importance of learning the definitions of functors and natural transformations and getting some intuition about how to use those notions for programming.
> 1 votes

---
Tags: reference-request, functional-programming, category-theory
---


# Question
Title: How does conversion from fixed-point to floating-point happen?
I came across to the code that convert 32-bit signed fixed-point number (16.16) to a float and it looks like (pseudocode)

```
floating = fixed / 65536.0

```

Could you please explain me what's the essence of dividing by this? Why does this dividing works when fixed-point and floating-point numbers have different internal structures?

# Answer
Your code converts a fixed-point number into its value. It also works for converting a fixed-point number to a rational number, for example.

A fixed-point number of the form $16.16$ consists of 32 binary digits, the first 16 to the left of the decimal dot, the second 16 to its right. When you insert the decimal dot, you are dividing by $2^{16} = 65536$.

Here is a decimal example. Consider a number stored in decimal fixed-point $2.2$. What is the value of the number stored as $1234$? It is $12.34 = 1234/100$.
> 2 votes

# Answer
Your code snippet is a bit misleading.

```
floating = fixed / 65536.0

```

It would be more correct to write it as:

```
floating = float(fixed) / float(65536)

```

With the `float()` being the CPU's built-in operation for converting `int` to `float`.

If you're working with C/C++ the conversion to float (or double-float) is implicit, so it's easily overlooked.

**But how does all this actually work?**

When converting a fixed-point number to a floating-point number you have to copy the most significant bits of the fixed-point number into the mantissa and to calculate the exponent based on which bits you copied.

In your case you are storing the fixed-point number as a `int32` variable, which allows you to exploit the CPU's built-in operation for converting `int` to `float`.

But the CPU thinks it's working with an `int` and it does not know that some of the bits are used to store the fraction, so it returns a floating-point number with the wrong exponent.

Since our fixed-point number uses 16 bits to store the fraction we can fix our float by decrementing its exponent by `16`.

With floats the division operator is actually implemented by subtracting the exponents and dividing the mantissas.

The floating-point number `65536` i.e. `2^16` gives us a number with the exponent of `16` and mantissa of `1`.

By dividing by `65536` we are decrementing our exponent by `16` and dividing our mantissa by `1` (dividing by `1` does nothing).

It's a pretty smart peace of code for what's it worth.

This trick can also be used for converting very large fixed-point numbers by first bit-shifting the fixed-point number to the right until it can fit into `int32` (or `int64` if possible), then using your code snippet and finally incrementing the exponent by the number of times you had to bit-shift.
Of course you will lose bits by bit-shifting, but those wouldn't fit into the float anyway.
> 1 votes

---
Tags: floating-point, real-numbers, fixed-point
---


# Question
Title: My attempt at the "This statement is false" paradox
(I haven't read any literature on this paradox nor am I good at formal proofs, so this is just my intuitive thoughts on the paradox.)

If we assume the statement "This statement is false" as a function `f()` on a state machine `M`, where `M` has 2 states `S0` and `S1` representing `false` and `true`, we'd just be evaluating `M.f()` in a certain state. In this case, `M` is cyclic and has no initial or terminal state.

If we initialize with `M(S0)`, the first evaluation will result in `M.f() -> S1`, and vice versa. However, the paradox in question doesn't give an initial state. Therefore, the truthiness of the statement, basically the state of `M` is about as uncertain as Schrödinger's cat - we can't evaluate the state/truthiness of `M` until we've observed the internal state.

However, if we start off with `M(S0)`, evaluating the paradoxical statement would just be like `M.f().get_state()` which would give us `S1`, in which case we do have a definitive answer to the statement.

I think the same logic can be used for any statement (or state machine) without an initial state & a terminal state. If you start with an unknown input, you don't know the output, but if you know the input, evaluating the statement would just give you the result at that 1 state.

Does this work to (somewhat) solve the "paradoxical" aspect of the statement, or do I fundamentally misunderstand the relation between truth and functions?

# Answer
> 1 votes
The paradox which you seem to be alluding to is often referenced as the Liar's paradox or in another form, Russell's paradox which in such form technically speaking is set theoretic. The crux of such a paradox is a statement that seems to produce the following logical form:

**S1** If x is true, then x is false.
**S2** If x is false, then x is true.

Obviously if you were try to make such an argument on the stand in law, you'd annoy the judge. And if you iterate through the statements, you get a cycle. S1 implies S2, and vice versa. **What should be made of this thinking in the discipline of computer science?**

First, note that two logical statements are atemporal, that is, there is no variable related to time, event, state, etc. If you take truth to be atemporal, then you have a statement that seems neither to be true or false *at the same time* because it obviously IS true and false at the same time. In truth-conditional semantics, this is a problem because it violates the classical notion of the principle of bivalence:

> In logic, the semantic principle (or law) of bivalence states that every declarative sentence expressing a proposition (of a theory under inspection) has exactly one truth value, either true or false.  A logic satisfying this principle is called a two-valued logic or bivalent logic.... In formal logic, the principle of bivalence becomes a property that a semantics may or may not possess. It is not the same as the law of excluded middle, however, and a semantics may satisfy that law without being bivalent.

The formalism of an execution model of something like the Turing Machine, is NOT atemporal because Turing defined the model as a sequence of operations through time. In practice, for instance, state diagrams implicitly presume that transitions of states represent discrete increments of time. So, what should be made of your attempt to conflate the Liar's Paradox, an object of logical study with that of software engineering, an object of computational study?

First, that mathematical logic exists in its most complete form as model theory. Second, that models certainly can have a temporal variable. And lastly, that the paradox itself isn't and cant' be solved (if you continue to accept the principle of bivalence), but that it hints that adding additional temporal variables moves you from a static logical structure of truth, to one in which truth values can be opposed, and that's acceptable. I am wearing my hat. I am not wearing my hat. There is no contradiction (See Stanford Philosophy's "Dialetheism").

And yes, this post would be more at home on PhilSE (the average computer scientist gives the philosophical foundations and historical origins of thought of their discipline short shrift), though strictly speaking, **computational theory does examine the nature between functions and truth, since a computer can be modeled as a Lambda calculus, which plays heavily in understanding the Church-Turing thesis. This question is squarely in the philosophy of computer science**, and would be very comfortable in a course that uses Boolos's Computability and Logic. Don't be fooled into thinking that since a function is not a logic statement, the two are unrelated. That would be a sin.

# Answer
> 0 votes
> If we assume the statement "This statement is false" as a function `f()` on a state machine `M`

This is a good example of choosing the wrong concept to formalize something :)

First of all, you really mean a function on the *set of states* of the state machine M. But more importantly, the "state machine" part is really completely irrelevant -- it's just a function on the set of Booleans: `f: Bool -> Bool`. Remember that for state machines it's necessary that they have one transition function *for each alphabet symbol.* Here, there's no input alphabet and only one transition function, so thinking of it as a state machine is likely to overcomplicate things. (It's not incorrect, per se -- you can think of it as a state machine with no input alphabet, or with an input alphabet consisting of a single character, `f` -- but it's not super helpful, either.)

> I think the same logic can be used for any statement (or state machine) without an initial state & a terminal state. If you start with an unknown input, you don't know the output, but if you know the input, evaluating the statement would just give you the result at that 1 state.

I do think you have some insight here! Let me rephrase: you can think of self-referential Boolean statements as functions, `f: Bool -> Bool` (or generalized to multiple inputs: `f: Bool^n -> Bool^n`.) Each time you evaluate the function, it updates the truth value assigned to each input. Then perhaps the meaningful statements are those which are fixed: repeatedly evaluating `f` always leads to a fixpoint (even if you don't know the initial state!). The not-well-defined functions, when iterated, never converge to a fixpoint. But as the other answer states, this is really a question for the philosophers and logicians.

> I have a question about the relation between functions and truth, such as that discussed in the Church-Turing thesis.

This doesn't have much of anything to do with the Church-Turing thesis! Your question, and formalization here, is related to the study of Boolean logic and truth values.

---
Tags: propositional-logic, check-my-answer, philosophy
---


title: Partially sorted Max Heap

text:
# Question
Title: Partially sorted Max Heap
I need to convert a Max Heap to a "Partially Sorted Max Heap" such that all keys at depth i are smaller than all keys at depth i-1. What is the most efficient way of doing this? Can this be done in O(n)?

# Answer
> 1 votes
Let $H$ be the max-heap represented as an array. We assume that the elements of the heap occupy the non-zero indices of $H$ e.g. the maximum element is at index 1. Also, I will use depth instead of level but that should not be a problem.

Notice that all elements at depth $d$ of the heap and their children, which are the elements at depth $d+1$, form a contiguous subarray, $H\[2^{d}\], ,..., H\[2^{d+2}-1\]$. Call this subarray $H\_d$.

## Algorithm

For $d = 0$ to $ (\log n) - 1$, repeat the following:

1. Find the element that must be placed at index $j = 2^{d+1}-1$ when $H\_d$ is in reversed sorted order. Call this element $m\_j$. Since the elements at depth $d$ occupies the indices from $2^d$ to $2^{d+1}-1$, this element must be the minimum element among the elements at depth $d$ if $H\_d$ is reversed sorted.
2. *Reverse partition* $H\_d$ around $m\_j$. That is, all elements greater than $m\_j$ must be placed on its left and those that are less must be on its right.

## Analysis

As noted above, $m\_j$ is the minimum element among the elements at depth $d$. Hence, after each reverse partition, it is guaranteed that all elements at the left-side of $m\_j$ are those that will be on depth $d$, and they are greater than those on the right-side, which will be the elements at depth $d + 1$. This satisfies the partially sorted property while also maintaining the max-heap order. Since this process is applied from top to bottom, the entire heap is transformed.

As for the running time, the selection of $m\_j$ can be performed in time proportional to the size of the subarray $H\_d$ using the linear time deterministic selection algorithm. The size of $H\_d$ is at most $2^d + 2^{d+1} = 3\times2^{d}$. Summing up the cost for each $d$ gives

$$3\*\sum\_{d=0}^{(\log n) -1}2^{d}= 3(2^0 + 2^1 + ... + 2^{\log n/2}) = O(n)$$

As for the partition step, this can also be performed in time proportional to the size of $H\_d$. Therefore, the total time of all the partitions is also $O(n)$. Which means that the entire algorithm takes $O(n)$ time.

## Note

I feel that using the linear time selection algorithm is kind of an overkill, but I cannot find a simpler method to find $m\_j$. But, overall the algorithm shows that in theory the problem can be solved in $O(n)$ time.

# Answer
> 2 votes
I came across a simple solution: Ignore the fact that it is a heap, reverse pardition around the median, and repeat this log(n) times, each time for the left half of the previos part...

---
Tags: heaps
---


# Question
Title: Describe the language accepted by the DFA
Describe the language accepted by the DFA shown above

# Answer
The DFA accepts strings of the language $(ab)^{\*}$.

Informally, the string $ab$ repeated an arbitrary number of times is accepted by the DFA.
> 0 votes

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


# Question
Title: Book references for combinatory logic as applied in Haskell?
I am looking for book references on combinatory logic. Is there a book focused on how combinatory logic is applied in the context of pure functional languages like Haskell?

I found "Combinators: A Centennial View" by Stephen Wolfram (2021), but it has too much advertising in it. Every second page Wolfram tries to sell the reader his programming language. Is there any well-written book with less advertisement?

# Answer
This isn't a complete answer, but you could do a lot worse than to go through the relevant sections of *The Implementation of Functional Programming Languages* by Simon Peyton-Jones, particularly the chapter on SK combinators. The book is now free.
> 1 votes

---
Tags: functional-programming, haskell, combinatory-logic
---


# Question
Title: Visualizing How of KD-tree Data Structure Splits Space
I am trying to understand how KD-tree works when we insert a node and how it splits the xy plane, please. Below $\[5, 4\]$ splits the xy-plane into left and right parts while $\[2,6\]$ splits it into top and bottom. Why don't we say that $\[2,6\]$ again splits the space into left and right?

# Answer
The root will choose the split in one direction (in your case, (5,4) creates a vertical split). Then any nodes at the next level in your tree will split horizontally, then the nodes in the next level of the tree will split vertically again.

If you are only splitting one way - like you suggest with only vertical splits - then you are essentially storing everything in a binary search tree with respect to the x-coordinate (and the data structure completely ignores the y-coordinate). But to make use of both coordinates and create a kind of two-dimensional binary search tree, this alternating levels thing is done.
> 1 votes

---
Tags: data-structures, binary-trees, search-trees, binary-search-trees, kd-tree
---


# Question
Title: CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}
The question is the following:

Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}.

I am able to construct CFG for the set of all palindromes as below:

**S --\> aSa | bSb | a | b | ϵ**

I am not able to figure out how to make |w| divisible by 3 in my CFG.

# Answer
> 1 votes
Use additonal "state" information to the variable $S$ that specifies the number of terminal symbols generated, mod 3.

So we have three variables $S\_i$, $i=0,1,2$, each keeping track of derivations for a string of length that remainder after division by three.

One example of a new production would be $S\_1 \to aS\_2 a$.

Thus, if $S\_2 \Rightarrow^\* w$ with $w\in\\{0,1\\}^\*$ and $|w| = 3k +2$, then $S\_1 \Rightarrow^\* w'$ with $|w'| = (3k + 2) + 2 = 3(k{+}1)+1$.

*Background information*: The derivation trees in the new grammar are basically the same in those from the old grammar. Just relabel the variables in a bottom-up way depending on the length of the terminal string below. This approach can be adapted for any context-free grammar if we want to restrict the length of derived words modulo a number. Even more general this is how we can show that context-free languages are closed under intersection with regular languages, via grammars and not via push-down automata as one often sees.

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


# Question
Title: Dynamic programming: optimal order to answer questions to score the maximum expected marks
You have $n$ questions in an exam. Question $i$ is answered correctly with probability $p\_i \> 0$. If question $i$ is answered correctly, you get $R\_i$ marks. You can choose to answer the questions in any order. As long as you are giving correct answers, you can accumulate all the marks. However, whenever your answer to a question is incorrect, the examination is over and you are not allowed to answer any other question. Given $R\_i$ and $p\_i$, what is the optimal order in which you should answer the questions to maximize the total expected marks you score?

Here is my approach - Let $F\_t(S\_t)$ be the expected max score you can have when $t$ questions are remaining, and the set of questions remaining is $S\_t$. We get the recurrence as $$F\_t(S\_t)=\max\_{i \in S\_t} \[p\_i(R\_i+F\_{t-1}(S\_t-\\{i\\}))\]$$ with $F\_0(\phi)=0$.
Now, $F\_1(\\{i\\})=p\_iR\_i$. $F\_2(\\{i,j\\})=\max(p\_i(R\_i+p\_jR\_j),p\_j(R\_j+p\_iR\_i))$. We see that the first term is larger when $$\frac{p\_iR\_i}{1-p\_i}\>\frac{p\_jR\_j}{1-p\_j}.$$ This hints that the ordering may be based on the value of $\frac{p\_iR\_i}{1-p\_i}$, but I am not sure how to give a formal proof, or how to solve the recurrence efficiently?

# Answer
> 5 votes
First, if any $p\_i=0$, then immediately throw it away since you're guaranteed to lose. If any probability is $1$ then immediately ask it! (after all why *risk* not getting the reward when you're guaranteed to get it!). So I'll assume we're now considering probabilities in the range $(0,1)$.

Suppose you **know** that the ***optimal order*** is $1,...,n$ because a magical *fairy* told you so. What is your expected score? Well, it is

$$E\_1 = p\_{1}R\_{1} + p\_{1}p\_{2}R\_{2} + p\_{1}p\_{2}p\_{3}R\_{3} + .... + \prod\_{j\leq n}p\_{j} R\_{n}$$

Now suppose you decided to switch indices $i$ and $i+1$ in the order that the fairy told you, so now your order is $1, ..., i-1,{\bf i+1,i}, i+2, ...,n$. What is your expectation now? Well, it is

$$ E\_2 = p\_{1}R\_{1} + p\_{1}p\_{2}R\_{2} + .... + \left(\prod\_{j\<i}p\_{j}\right)p\_{i+1}R\_{i+1}+\left(\prod\_{j\<i}p\_{j}\right)p\_{i+1} p\_{i}R\_{i} + ....+\left( \prod\_{j\<n}p\_{j} \right)R\_{n} $$

Because $E\_1$ is optimal, then it must be $E\_1 \geq E\_2 \implies E\_1 - E\_2 \geq 0$ (otherwise the cheeky oracle lied to us!). But notice that $E\_1, E\_2$ are only different in their $i$ and $i+1$ terms, all other terms are **exactly** the same (verify this!). So:

$$E\_1-E\_2 = \left(\prod\_{j\<i}p\_{j}\right)p\_{i}R\_{i}+\left(\prod\_{j\<i}p\_{j}\right)p\_ip\_{i+1}R\_{i+1} -\left(\prod\_{j\<i}p\_{j}\right)p\_{i+1}R\_{i+1}-\left(\prod\_{j\<i}p\_{j}\right)p\_{i+1}p\_{i}R\_{i} \geq 0$$

Since all probabilities are positive, we divide by $\prod\_{j\<i} p\_j$ to get:

$$ p\_{i}R\_{i} + p\_i p\_{i+1}R\_{i+1} - p\_{i+1}R\_{i+1} - p\_i p\_{i+1}R\_{i} \geq 0 $$ Or rearranging

$$ p\_i R\_i (1-p\_{i+1}) \geq p\_{i+1}R\_{i+1} (1-p\_i)$$

Or:

$$ \frac{p\_i R\_i }{1-p\_i} \geq \frac{p\_{i+1} R\_{i+1} }{1-p\_{i+1}}$$ Wait a minute! This is a condition on the optimal ordering the fairy gave us! So we actually don't need the fairy! Just sort by this order, and that's your optimal ordering!

---
Tags: algorithms, optimization, probability-theory, greedy-algorithms
---


# Question
Title: Can contiguous arrays be lazily evaluated?
Contiguous arrays with variable length, such as C++'s `std::vector`, have been a major sequential container for languages whose evaluation is eager. However, it has been commonly considered that contiguous arrays do not mix well with lazy evaluation. Indeed, `Array`s that Haskell provides are strictly evaluated for its entries. Not to mention that strictly evaluated arrays cannot have infinitely many entries, unlike lazily evaluated lists can.

Yet I don't think arrays cannot be lazily evaluated *anyway*. I aimed to build a datastructure that can represent infinitely many entries like lazily evaluated lists can, while still being randomly accessible. To give a sketch, I think such datastructure can be implemented as **cached** lists. That means, the datastructure could consist of a strictly evaluated array and a lazily evaluated linked list, where the strict array acts as caches for already identified entries, and where the lazy list contains unevaluated entries. This should give amortized random access.

Yet still, I don't think Haskell can do this natively. All memory allocation/deallocation operations that Haskell provides are bound within the `IO` monad. If the idea above can be implemented in our machines anyway, I would conclude that this is just language design fault of Haskell. So can contiguous arrays be lazily evaluated anyway? If so, what programming languages do have that?

# Answer
> 3 votes
Haskell supports immutable arrays in the obvious way. This is an extremely useful data structure when used in conjunction with lazy evaluation, because you can store unevaluated thunks in the array which get evaluated at most once when you read them.

Many dynamic programming algorithms become much simpler when you implement them this way, but there are also exotic uses such as hash consing (akin to the flyweight pattern in OOP). Haskellers sometimes to refer to this technique as memoising CAFs, since an immutable array is a constant applicative form.

For mutable arrays, there are essentially two possibilities: persistent and non-persistent.

Non-persistent mutable functional arrays store updates so they can be undone to get to a previous point in time. This is more common in logic languages, since they have a notion of backtracking.

Persistent functional arrays give you the best of all worlds: arbitrary updates, and they don't alter existing arrays. Of course, something has to give, and that means either storage (e.g. copying the whole array on every update; the standard library of Mercury has a `slow_set` operation which does this) or access time complexity (e.g. representing the array as a binary tree).

However, there is a middle-ground. What you might like is for the array to have:

* $O(n)$ initialisation time
* $O(1)$ read time on the original array
* $O(1)$ (amortised?) modification time
* $O(\log k)$ read time on a modified array, where $k$ is the number of modified array entries since initialisation

The idea here is that you start with an array, but it slowly turns into a tree as it gets modified. Something like ropes will do this. The idea is to implement a binary tree whose leaves are either a new entry, or a sub-range of the original array.

---
Tags: data-structures, programming-languages, arrays, language-design, evaluation-strategies
---


# Question
Title: Difference between function and search problems?
I am a bit confused on what the difference between a "function problem" and a "search problem" is.

The specific problem I have been studying is known as End-Of-The-Line:

> Given two functions, $P(x)$ and $N(x)$, a value $v$ is said to be balanced if $N(P(v)) = P(N(v)) = v \lor N(P(v)) \neq P(N(v)) \neq v$. Given that $0^N$ is not balanced, find another value that is not balanced.

How is this *not* a search problem? This problem is complete for the class $PPAD$ which is a class of function problems, but the problem is essentially asking us to search a graph for an unbalanced node.

From wikipedia:

> In the mathematics of computational complexity theory, computability theory, and decision theory, a search problem is a type of computational problem represented by a binary relation. Intuitively, the problem consists in finding structure "y" in object "x".

In End-Of-The-Line, the "y" structure is an unbalanced node that isn't $0$, and $x$ is the whole graph.

Is there something I'm not getting?

# Answer
> 2 votes
$\mathrm{PPAD}$ is a class of search problems, not of function problems. The notion of search problem is more general than that of function problem, which in turn is more general than a decision problem.

For a decision problem, we get an input and we need to answer *yes* or *no*.

For a function problem, we get an input and we need to compute a uniquely specified output.

For a search problem, we get an input and we need to compute some valid output.

---
Tags: complexity-theory, search-problem
---


# Question
Title: Why is DFS considered to have $O(bm)$ space complexity?
According to these notes, *DFS* is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space.

The same is said in this Wikibook page on *Uninformed Search*.

Now the "infobox" of the Wikipedia article on DFS presents the following for the space complexity of the algorithm:

> $O(|V|)$, if entire graph is traversed without repetition, $O($longest path length searched$)$ for implicit graphs without elimination of duplicate nodes

which is more similar to what I thought was the space complexity of DFS, i.e., $O(m)$, where $m$ is the maximum length reached by the algorithm.

*Why do I think this is the case?*

Well, basically we don't need to store any other nodes than the nodes of the path we're currently looking at, so there's no point of multiplying by $b$ in the analysis provided both by the Wikibook and the notes I'm referred you to.

Moreover, according to this paper on *IDA\** by *Richard Korf*, the space complexity of DFS is $O(d)$, where $d$ is considered the "depth cutoff".

So, what's the correct space complexity of DFS?

I think it may depend on the implementation, so I would appreciate an explanation of the space complexity for the different known implementations.

# Answer
> 7 votes
It depends on what exactly you call DFS. Consider for example the algorithm DFS-iterative described in Wikipedia, and suppose that you run it on a tree so that you don't have to keep track of which nodes you have already visited. Suppose that you run it on a complete $b$-ary tree of depth $m$. We can identify nodes in their tree with words over $\[b\]$ of length at most $m$. The algorithm operates as follows:

1. Start at the root. Push $1,2,\ldots,b$ to the stack (in reverse order).
2. Pop $1$, and push $11,12,\ldots,1b$ to the stack.
3. Pop $11$, and push $111,112,\ldots,11b$ to the stack.
4. $\ldots$
5. Pop $1^{m-1}$, and push $1^m,1^{m-1}2,\ldots,1^{m-1}b$ to the stack.

At this point, the stack contains

$$ 1^m,1^{m-1}2,\ldots,1^{m-1}b,\ldots,112,\ldots,11b,12,\ldots,1b,2,\ldots,b, $$

for a total of $(b-1)m + 1$ nodes. You can check that this is the pint in time in which the size of the stack is maximized.

# Answer
> 3 votes
There are two points here to make:

1. In case you introduce into the stack all the descendants of the current node, then effectively, the space complexity is $O(bd)$ where $b$ is the branching factor and $d$ is the maximum length. Yuval Filmus' reply refers to this case indeed. However, note that in general $d$ is much much larger than $b$. Moreover, in many domains, such as the sliding-tile puzzle, $b$ is upper bounded by a constant (in that specific case, 4) and hence we can safely say that DFS has a space complexity which is $O(d)$.
2. Admittedly, however, this is not always the case. For example, in the Pancake puzzle, the branching factor grows with the length of the optimal solution and they both have similar values. Still, the space complexity is $O(d)$. To see this just simply tweak the expansion procedure of any node: Instead of inserting all descendants of the current node (as suggested by Yuval Filmus) insert them in order. You first generate the first descendant and *immediately after* you proceed in depth-first order ---as a matter of fact, *you do not need all the other descendants at this point*. In case you ever backtrack to this node, then its descendant has been removed from the stack. Next, generate the second descendant and proceed in depth-first order again. In case you backtrack to this node, then generate the third and so on until there are no more descendants. Proceeding this way you will only have $d$ nodes in your stack, no matter of the branching factor, $b$.

Summarizing, I would never say that DFS has a space complexity which is $O(bd)$ and, instead, I claim its space complexity is $O(d)$.

Hope this helps,

# Answer
> 0 votes
Your answer is partially correct. In case of recursive dfs algorithm, the time complexity will be **O(m)** as the system stack will only contain all the parent node states which will not be affected by the branching factor. But, in case of iterative dfs algorithm, the stack we create must store all the first child nodes to remember it has to visit them as well ... so it will have b-1 nodes in stack at the m depth which will give you **O(m\*b)** space in worst case. Thus, it would depend on way of implementation of the algorithm.

But of Course, we could do a little optimization in iterative method to simulate the recursive approach (by storing the number of child to be iterated next and doing some change in algorithm) and this will again get you **O(m)** time complexity.

So, in conclusion, it is correct to say that dfs space complexity is **O(m)** in my opinion.

---
Tags: graphs, algorithm-analysis, graph-traversal, space-analysis
---


# Question
Title: Ackermann Function without Recursion or Stack
I have been studying the necessity of a WHILE loop when defining the Ackermann Function. I am looking to write a program to compute the Ackermann function in a high level language such as Python or JavaScript to compare it to the WHILE language.

The Ackermann function is defined recursively, and recursive calls do not exist in the WHILE language.

Every program with an alternative method to recursion has used a stack. Stacks do not exist in the WHILE language. Is there any way to program the Ackermann function in a HLL without a stack or recursion?

# Answer
Good question! It is possible using only natural numbers and arithmetic to implement a stack, due to Gödel numbering.

What's the basic idea? Well, a stack is basically a nested sequence of pairs: the stack $(1, 2, 3)$ (with $1$ on top) can be thought of as $(1, (2, 3))$. And in turn, we can encode pairs using this neat formula: $$ \texttt{encode}(a, b) = a + \binom{a + b + 1}{2} = a + \frac{(a + b + 1)(a + b)}{2} $$ This is called a pairing function and this one is due to Cantor. Some examples may make the function more clear: $$ \texttt{encode}(0, 0) = 0 + 0 = 0\\ \texttt{encode}(0, 1) = 0 + 1 = 1 \\ \texttt{encode}(1, 0) = 1 + 1 = 2 \\ \texttt{encode}(0, 2) = 0 + 3 = 3 \\ \texttt{encode}(1, 1) = 1 + 3 = 4 \\ \texttt{encode}(2, 0) = 2 + 3 = 5 \\ \texttt{encode}(0, 3) = 0 + 6 = 6 \\ \cdots $$

Then we can also define a corresponding function $\texttt{decode}(n)$ which returns a pair of integers, so that $\texttt{decode}(\texttt{encode}(a, b)) = (a, b)$. The kicker is that both encode and decode are definable as WHILE programs!

## Implementing encode and decode

It should be clear how to implement $\texttt{encode}$: WHILE programs have arithmetic, so we can simply compute the answer in a single assignment statement. For $\texttt{decode}$, there are some more efficient ways, but one way that works is simply to loop over all pairs integers and try encoding them:

```
decode(n):
  a := 0
  b := 0
  done := 0
  while done == 0:
    c := encode(a, b)
    if c == n:
      done := 1
    else if a > 0:
      a := a - 1
      b := b + 1
    else:
      a := b + 1
      b := 0

```

The line `c := encode(a, b)` is a subprocedure: it can be simply replaced inline with the definition of encode.

## Implementing a stack

What operations does a stack data type need to support? There are basically just four operations: `empty: S` returning an empty stack; `push: (S, nat) -> S` pushing a new value; `pop: S -> (S, nat)` popping the top value, and `is_empty: S -> bool` to check whether the stack is empty. Each of these can be implemented using `encode` and `decode`. For the empty stack, we can use the natural number 0. For push, we can use

```
push(stack, n) = encode(stack, n) + 1

```

and for pop, we can use:

```
pop(stack) = if stack == 0 then (0, 0) else decode(stack - 1)

```

where the return value, an ordered pair, is stored into two designated variables. Finally, `is_empty` is just checking whether `stack == 0`.

## Implementing Ackermann

As you noted, recursive functions can be implemented using WHILE loops and a stack. So implementing the Ackermann function is just a matter of applying the stack implementation above. Each time you want to push or pop from the stack, you replace with the above procedures. You can have as many stacks as you want, stored in different natural number variables.

The same trick works to implement *any* recursive or Turing-computable function; this is why WHILE is Turing-complete.

## Notes

Finally, two caveats. First, none of these encodings are particularly efficient. Even the basic `encode` function is quite unwieldy; nested calls to it to create a stack creates absolutely astronomical integers very quickly.

Second, for any of this to work, it's important that the natural numbers in the WHILE language are *true* integers, not the fixed-width integers that are common in real computer architectures. For fixed-width integers, the WHILE language is certainly weaker than arbitrary computation -- it cannot implement any nontrivial Turing-computable functions, let alone the Ackermann function.

As a result of both of these limitations, in practice, WHILE is not really sufficient for general computation with recursive functions. Instead, real compilers rely on the program stack and dynamically allocated memory on the heap to implement complex data structures and computations.
> 24 votes

# Answer
*Note: this answer assumes one more rule on the WHILE language (which is not in the paper linked by OP), which is that the variables within are limited to a certain size. It does not matter which size, but they are bounded by some arbitrary number (which could even be specific for each program, and itself arbitrarily large, but still a fixed upper bound). If you specifically wish to allow for the "encode/decode" answer posted elsewhere, then one should reasonably expect a similar addendum to the language to the opposite effect, i.e. allowing arbitrarily large numbers. In my opinion, this is an omission in the language definition, mostly irrelevant, but not for this question.*

The WHILE statement as described in the paper linked by OP has these features:

> It is a simple imperative language, with assignment to local variables, if statements, while loops, and simple integer and boolean expressions

Specifically, it has neither memory storage nor stack nor recursion nor any other unbounded feature. Each program in the WHILE language is of fixed size, with a fixed amount of variables, and no way to be dynamic in this regard.

(N.B. it is unclear to me why they mention "local" variables - the language has no functions, and thus no scopes, and thus no differentiation between local and global would make much sense.)

While another answer suggests to use the fact that the language does not bound the size of individual variables, and thus is able to store unlimited storage in a single variable, I will provide the opposite answer, assuming that the *intention* of the language is not to have this feature.

The language is clearly a constructed language to explore implications of such a basic set of features. The paper, as usual for these kinds of theoretical languages, does not care about the size or boundedness of its variables, but the spirit of the wording ("simple imperative language", "simple integer and boolean expressions") and the fact that they do not even analyze the language itself, but an assembly-like version WHILE3ADDRESS instead, makes quite clear that the *intention* behind the language is not to have infinitely sized variables as a cop-out to achieve Turing-completeness.

So for me, the fact that the paper does not mention a bound on the size of the individual variables, having unbounded variables would transform the language from "simple" to completely unsimple. As it stands now, this language is clearly meant to be one step below Turing-completeness (i.e., it is designed to have all features of Turing-completeness except for recursion and storage).

As such, the language, as it stands now, represents an excessively simple language without RAM, with a fixed (and thus bounded) amount of variables. It is not Turing-complete, since that would require unlimited recursion or unlimited memory.

The Ackermann function needs unbounded storage or recursion, and thus cannot be calculated by the WHILE function.

To look at only the subject of the question ("Ackermann Function without Recursion or Stack"), the answer is also "no" if there is also no other unbounded amount of storage (i.e., no RAM and no infinitely-sized integers).
> 3 votes

---
Tags: algorithms, computability
---


# Question
Title: Minimum number of skips needed for shortest path
In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $\leq W$. In our given graph there is no such path but we have the ability to skip as many edges as we like.

How can I create an algorithm that calculates the number of minimum skips needed to find a path from s to t with weight $\leq W$?

Thoughts: In general we can use Dijkstra's algorithm to find a shortest in the given graph.

If the number of skips available in the graph was given the solution would be solution

# Answer
Well, the answer from Codeforces is still correct, you just need to find a suitable upper bound for how many layers you will need. An obvious upper bound would be the number of vertices, but a better estimate can be made by just running BFS in order to find the shortest unweighted path from $s$ to $t$; if there is a $(s,t)$-path consisting of $k$ edges, you would never need to skip more than $k$ edges. Then, you can for each layer $\ell$ from 0 to $k$ calculate the distance from $s\_0$ to $t\_\ell$ and stop when it dips under $W$.

And, one note: In the answer it is not stated that the weight 0 edges must be directed (from layer $\ell$ to layer $\ell+1$). This is necessary in order for the shortest path algorithm to not go up and down layers and thereby skipping more edges than is allowed.
> 0 votes

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


# Question
Title: How to schedule ELO-based, fair games with n players and dynamic teams?
The setting is the following: There are **n** players that want to compete in a specific game over the course of an event. A game is played between 2 teams of 2 players each (so a 2v2). Each player as a general rating value based on the ELO-System and it is assumed that the combined rating of a team is the mean of the members ratings. Over the course of one event the ratings of the players are not changed, that is done after all games are finished.

The task is the following: For those **n** players and an input number **k**, calculate a schedule of **k** matches to be played such that:

1. Every player should play equally many times, if possible, and if not, no player **a** should play two games more than another player **b**.
2. One team can only play in one match. (So if player **a** and player **b** are matched in one game playing against some enemy team, they will not be matched for a team again)
3. The matches should be as fair as possible, fair meaning that the ratings of the opposing teams are roughly equal. I am not sure what the best metric for that might be, but I suppose using something like a mean squared error over the differences in rating of all the matches generated should do.

I think solving this perfectly is probably a very hard problem, so I guess I am looking for some kind of estimation. Condition (1) is the most important and must always be satisfied.

Until now I only have a solution for generating good teams instead of games based on a weighted maximum matching problem (approach coming from here), but I would love to implement the problem described above.

**Edit:**

It does not matter in which order the generated games take place and all games are played out sequentially, not in parallel (which means there is no need to optimize for games happening at the same time).

# Answer
There are many plausible approaches, but one that would be easy to implement would be to formulate this as an instance of integer linear programming (a classic technique in operations research, which your problem could be considered an example of).

Introduce zero-or-one variables $x\_{a,i,t}$, with the intended meaning that $x\_{a,i,t}=1$ means that player $a$ plays on team $t$ ($t=0$ or $t=1$) in the $i$th match. Also introduce variables $m$, the minimum number of matches per player, and $d\_i$, the difference in rating between two teams who are playing each other in round $i$. (I am using the sum of differences in ratings in each round rather than mean squared difference as my metric of "roughly equal", to make this expressible as integer linear programming.) Also introduce variables $y\_{a,b,i,t}$, with the intended meaning that $y\_{a,b,i,t}=\min(x\_{a,i,t},x\_{b,i,t})$, i.e., $y\_{a,b,i,t}=1$ iff both $a$ and $b$ are paired together on team $t$ in the $i$th round.

Then we can introduce linear inequalities to enforce that these variables are set consistently and comply with your requirements, e.g.,

* $m \le \sum\_{i,t} x\_{a,i,t} \le m+2$ for all $a$
* $\sum\_{i,t} y\_{a,b,i,t} \le 1$ for all $a,b$ with $a \ne b$
* $\sum\_a \text{rating}(a) \cdot x\_{a,i,0} \le \sum\_a \text{rating}(a) \cdot x\_{a,i,1} + d\_i$, $\sum\_a \text{rating}(a) \cdot x\_{a,i,0} \ge \sum\_a \text{rating}(a) \cdot x\_{a,i,1} - d\_i$ for all $i$
* $y\_{a,b,i,t} \le x\_{a,i,t}$, $y\_{a,b,i,t} \le x\_{b,i,t}$, $y\_{a,b,i,t} \ge x\_{a,i,t} + x\_{b,i,t}-1$
* $\sum\_a x\_{a,i,t} = 2$ for all $i,t$
* $x\_{a,i,0} + x\_{a,i,1} \le 1$ for all $a,i$

Then your goal is to minimize $\sum\_i d\_i$.
> 0 votes

---
Tags: algorithms, optimization
---


# Question
Title: How do XFast and Y Fast Tries compare to B trees in performance?
I learned that Y fast tries support amortized loglog(u) time insertions , deletions. and loglog(u) time membership, successor and predecessor operations with O(n) space. So when n is closer to U in dense big data environments Y fast tries seem better than B trees.

But most database systems use Btrees internally. I was wondering whats the reason behind it. Does Xfast tries and Y fast tries have a high constant factor? I think the implementation is complex as Xfast tries require threaded tries (with strings as bits of integers in u) and a doubly linked list. And Y fast tries require Xfast tries to store maximum elements of each Balanced Binary Search tree used internally, and also merging and splitting of these Balanced BSTS. Is the complexity of implementation the reason behind them not being used as widely as B trees. Can someone give an intuition on why B trees are preferred against X fast tries and Y fast tries?

# Answer
> 4 votes
Apart from their more complex structure, Y-fast and X-fast trie assumes that data to be stored are integers, while balanced BSTs only assumes that data be from some ordered universe, not necessarily integers.

Also the Y-fast trie uses balanced BST as a secondary structure.

In addition to the points I highlighted, I believe you will be interested in this similar question about the use of Y-fast and X-fast trie in real-world application. The accepted answer for this question along with the other answer have more detailed discussion.

# Answer
> 4 votes
On top of the other answer, the reason why any data structure tends to be preferred by databases over any other data structure (e.g. B+-trees over anything else) usually boils down to two factors:

* Disk I/O performance. You want to minimise the number of disk accesses needed to use or modify the data structure, while also maximising the amount of work that you can do per access.
* Concurrency and transaction safety. You would like a data structure which can control concurrent access efficiently, and has support for safe transactions with rollback and commit.

For these reasons, databases prefer data structures that are page-structured. Each node or leaf in a B-tree (or variant thereof) can be understood as a fixed-size page.

This eliminates external fragmentation. A "page" is a natural unit for disk I/O which works efficiently with real hardware (medium-sized "bursts" of I/O tend to be more efficient than small accesses on modern busses). And a page can be protected for concurrent access more efficiently than individual nodes in a smaller-ply tree.

---
Tags: big-data, b-tree
---


# Question
Title: Is von Neumann's randomness in sin quote no longer applicable?
Some chap said the following:

> Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.

That's always taken to mean that you can't generate true random numbers with just a computer. And he said that when computers were the equivalent size of a single Intel 8080 microprocessor (~6000 valves). Computers have gotten more complex, and I believe that von Von Neumann's statement may no longer be true. Consider that an implemented software only algorithm is impossible. They run on physical hardware. True random number generators and their entropy sources are also made of hardware.

This Java fragment put into a loop:

```
      file.writeByte((byte) (System.nanoTime() & 0xff));

```

can create a data file which I've represented as an image:

You can see structure, but with a lot of randomness as well. The thing of interest is that this PNG file is 232KB in size, yet contains 250,000 grey scale pixels. The PNG compression level was maximum. That's only a compression ratio of 7%, ie. fairly non compressible. What's also interesting is that the file is unique. **Every generation of this file is a slightly different pattern and has similar ~7% compressibility.** I highlight this as it's critical to my argument. That's ~7bits/byte entropy. That will reduce of course upon use of a stronger compression algorithm. But not reduce to anything near 0 bits/byte. A better impression can be had by taking the above image and substituting its colour map for a random one:-

Most of the structure (in the top half) disappears as it was just sequences of similar but marginally different values. Is this a true entropy source created by just executing a Java program on a multi taking operating system? Not a uniformly distributed random number generator, but the entropy source for one? An entropy source built of software running on physical hardware that just happens to be a PC.

# Supplemental

In order to confirm that every image generates fresh entropy without a fixed pattern common to all, 10 consecutive images were generated. These were then concatenated and compressed with the strongest archiver I can get to compile (paq8px). This process will eliminate all common data, including auto correlation leaving only the changes /entropy.

The concatenated file compressed to ~66%, which leads to an entropy rate of ~5.3 bits/byte or 10.5Mbits /image. A surprising amount of entropy $ \smile $

# Supplemental 2

There have been negative comments that my entropy by compression test methodology is flawed, only giving a loose upper bound estimate. So I've now run the concatenated file though NIST's official cryptographic entropy assessment test, SP800-90B\_EntropyAssessment. This is as good as it gets for non IID entropy measurement. This is the report (sorry this question is getting long, but the issue is complex):-

```
Running non-IID tests...

Entropic statistic estimates:
Most Common Value Estimate = 7.88411
Collision Test Estimate = 6.44961
Markov Test Estimate = 5.61735
Compression Test Estimate = 6.65691
t-Tuple Test Estimate = 7.40114
Longest Reapeated Substring Test Estimate = 8.00305

Predictor estimates:
Multi Most Common in Window (MultiMCW) Test: 100% complete
    Correct: 3816
    P_avg (global): 0.00397508
    P_run (local): 0.00216675
Multi Most Common in Window (Multi MCW) Test = 7.9748
Lag

Test: 100% complete
    Correct: 3974
    P_avg (global): 0.00413607
    P_run (local): 0.00216675
Lag Prediction Test = 7.91752
MultiMMC Test: 100% complete
    Correct: 3913
    P_avg (global): 0.00407383
    P_run (local): 0.00216675
Multi Markov Model with Counting (MultiMMC) Prediction Test = 7.9394
LZ78Y Test: 99% complete
    Correct: 3866
    P_avg (global): 0.00402593
    P_run (local): 0.00216675
LZ78Y Prediction Test = 7.95646
Min Entropy: 5.61735

```

The result is that NIST believes that I have generated 5.6 bits/byte of entropy. My DIY compression estimate puts this at 5.3 bits/byte, marginally more conservative.

-\> The evidence seems to support the notion that a computer just running software can generate real entropy. And that von Neumann was wrong (but perhaps correct for his time).

---

I offer the following references that might support my claim:-

Are there any stochastic models of non determinism in the rate of program execution?

WCET Analysis of Probabilistic Hard Real-Time Systems

Is there a software algorithm that can generate a non-deterministic chaos pattern? and the relevance of chaotic effects.

Parallels with the Quantum entropic uncertainty principle

Aleksey Shipilёv's blog entry regarding the chaotic behaviour of nanoTime(). His scatter plot is not dissimilar to mine.

# Answer
> 78 votes
Just because you can't see a pattern doesn't mean that no pattern exists. Just because a compression algorithm can't find a pattern doesn't mean that no pattern exists. Compression algorithms are not silver bullets that can magically measure the true entropy of a source; all they give you is an *upper bound* on the amount of entropy. (Similarly, the NIST test also gives you only an upper bound.) Chaos is not randomness.

It takes a more detailed analysis and examination to start to get some confidence in the quality of randomness obtained in this way.

There *are* reasons to think that we can probably obtain some amount of randomness by exploiting clock jitter and the drift between two hardware clocks, but it's delicate and tricky, so you have to be careful. I would not recommend trying to implement your own. Instead, I would suggest you use a high-quality source of entropy (usually implemented in most modern operating systems). For more details, see also Wikipedia, haveged, and https://crypto.stackexchange.com/q/48302/351 (which it seems you are already aware of).

Lastly, a comment on your opener:

> "Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin."
>
> That's always taken to mean that you can't generate true random numbers with just a computer.

No, that's not how it is usually taken, and it's not what it is saying. It's saying you can't generate true random numbers *by deterministic means*. Whether you can do it on a computer depends on whether the computer is deterministic or not. If the computer is deterministic, or your program uses only deterministic operations, you can't. However, many computers contain non-deterministic elements, and if your program uses them, more detailed analysis is needed before you can decide whether they can be used to generate random numbers. In your case `nanoTime()` is non-deterministic.

# Answer
> 101 votes
If you're using some hardware source of entropy/randomness, you're not "attempting to generate randomness by *deterministic* means" (my emphasis). If you're not using any hardware source of entropy/randomness, then a more powerful computer just means you can commit more sins per second.

# Answer
> 21 votes
I've always understood the quote to mean that a deterministic algorithm has a fixed amount of entropy, and although the output can appear "random" it can't contain more entropy than the inputs provide. From this perspective, we see that your algorithm smuggles in entropy via `System.nanoTime()` \- most definitions of a "deterministic" algorithm would disallow calling this function.

The quote - while pithy - is essentially a tautology. There's nothing there to disprove and there's no evolution of hardware possible that can make it no longer true. It's not about hardware, it's about the definition of a deterministic algorithm. He's simply observing that determinism and randomness are incompatible. For any deterministic algorithm, its entire behavior is predicted by its starting conditions. If you think you've found an exception, you're misunderstanding what it means to be deterministic.

It is true that a process running on a shared computer with a complex series of caches and which receives various network and hardware inputs has access to much more entropy than one running on simple, isolated, dedicated hardware. But if that process accesses that entropy it is no longer deterministic and so the quote doesn't apply.

# Answer
> 18 votes
> Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.

When you interpret "living in a state of sin" as "doing a nonsense", than it's perfectly right.

What you did is using a rather slow method `System.nanoTime()` to generate rather weak randomness. You measured some

> ... entropy rate of ~5.3 bits/byte ...

but this is just the upper bound. All you can ever get is an upper bound. The real entropy may be orders of magnitude smaller.

Try instead filling the array using a cryptographic hash like MD5. Compute a sequence like `md5(0), md5(1), ...` (from each value taken one or more bytes, this doesn't matter). You'll get no compression at all (yes, MD5 is broken, but still good enough to produce incompressible data).

We can say, that there's no entropy at all, yet you'd measure 8 bits/byte.

When you really need something random, you not only have to use a HW source, you also have to know *a sure lower bound on* how much entropy it really produces. While there most probably is some randomness in `nanoTime()`, I'm unaware of any non-trivial lower bound on it.

When you need randomness for cryptography, then you really have to resort to something provided by your OS, your language or a good library. Such providers collect entropy from multiple sources and/or dedicated HW and quite some work has been put into such entropy estimations.

Note that you usually need hardly any entropy. A good (deterministic) PRNG initialized with a few random bytes is usable for cryptography, and therefore also for everything else.

# Answer
> 15 votes
I thought I'd chime in on the meaning of "random". Most answers here are talking about *the output of random processes*, compared to the output of deterministic processes. That's a perfectly good meaning of "random", but it's not the only one.

One problem with the output of random processes is that they're hard to distinguish from the outputs of deterministic processes: they don't contain a "record" of how random their source was. An extreme example of this is a famous XKCD comic where a random number generator always returns `4`, with a code comment claiming that it's random because it came from a die roll.

An alternative approach to defining "randomness", called Kolmogorov complexity, is based on the data itself, regardless of how it was generated. The Kolmogorov complexity of some data (e.g. a sequence of numbers) is the length of the shortest computer program which outputs that data: data is "more random" if it has a higher Kolmogorov complexity.

Your use of compression algorithms like PNG, and comparing the length before and after compression, is similar to the idea of Kolmogorov complexity. However, Kolmogorov complexity allows data to be encoded as a program in any Turing-complete programming language, rather than a limited format like PNG; "decompressing" such encodings (programs) is done by running them, which may take an arbitrary amount of time and memory (e.g. more than is available in our puny universe).

Rice's theorem tells us that we can't, in general, distinguish between programs which loop forever and programs which output our data. Hence it's very hard to find the Kolmogorov complexity of some data: if we write down a program which generates that data, there may actually be a shorter program (i.e. a lower complexity), but we didn't spot it because we couldn't distinguish it from an infinite loop. Kolmogorov complexity is hence uncomputable, although if we knew the Busy-Beaver numbers we could compute it by using those to bound the amount of time that we check each program.

In the case of your example data, to find its Kolmogorov complexity (i.e. "intrinsic randomness") we would need to find shortest deterministic program which outputs that same byte sequence, and take its length.

Now we can answer your question from the point of view of Kolmogorov complexity, and we find that the quote is correct: we cannot generate random numbers (high Kolmogorov complexity) by deterministic means.

Why not? Let's imagine that we write a small computer program and we use it to generate a sequence of random numbers. One of the following situations must apply:

* We generate a vast amount of output. However, since we *know* that this output is generated by a small program, the output (by definition) has low Kolmogorov complexity, and hence it's not "random" in this sense.
* We generate so few numbers that writing them all down would take about the same, or even fewer, bits than writing down our short generating program. In this case, the numbers are relatively incompressible, which indicates that they're quite random in the Kolmogorov sense. However, since the amount of output is comparable to what we put in (the source code for the program), it's fair to say that the program didn't "generate" the randomness, *we* did by choosing that program. After all, in this case our generating program might as well have just been a list of these exact numbers (e.g. `print([...])`).

In either case, we're not "generating" more randomness than we put in (the "randomness" of our generating program's source code). We might try to work around this by using a longer generating program, to avoid the output having a short generator, but there are only two ways to do that:

* Systematically "bloat" the code in some way. However, Kolmogorov complexity doesn't care about the particular program that *we* used to generate the data: it only cares about *whichever* generating program is the smallest. Systematic bloat doesn't add Kolmogorov complexity, because such patterns in the code can themselves be generated with a very small amount of code. For example if we take `run(shortGenerator)` and add a whole load of systematic bloat to get `run(bloatedGenerator)`, a short generator still exists of the form `run(addBloat(shortGenerator))`.
* Add bloat *non-systematically*, i.e. without any patterns, so that an `addBloat` function would have to end up being just as bloated as the code itself. However, being so devoid of patterns is exactly what makes something random (high Kolmogorov complexity). Hence bloating the generating program in this way *does* increase the randomness (Kolmogorov complexity) of the output, but it *also* increases the amount of randomness (Kolmogorov complexity) that we have to provide in the form of source code. Hence it's still us who are providing the "randomness" and not the program. In the above example of just writing `print([...])`, adding non-systematic bloat is equivalent to just writing more "random" numbers in that hard-coded list.

# Answer
> 7 votes
Compression isn't an accurate test of randomness, and nor is looking at an image and saying "that looks random".

Randomness is tested by empirical methods. There are in fact suites of specially designed software/algorithms for testing randomness, for example TestU01 and the Diehard tests.

Furthermore, your image is in fact a 1D string of number mapped onto a space, and thus isn't a good representation of certain patterns that can appear.

If you were to examine your image pixel by pixel, you would most likely find many short patterns of increasing value before a sudden drop. If you were to create a graph with the x value being the sample number and the y value being the value obtained from the 'random' function, you would most likely find that your data in fact looks like a sawtooth wave:

This is the pattern made by values that increase under modular arithmetic (which your computation is an example of: time increasing at a near constant rate, and the `& 0xFF` acting as `mod 256`).

# Answer
> 5 votes
You are confusing the concept of random numbers from "numbers that appear to be random."

To understand von Neumann's quote, we have to understand what it means to "generate random numbers." Warbo's answer links an excellent XKCD to this end:

When we talk about random numbers, we're not talking about the values themselves. Obviously a 4 is no more random than a 3. We are talking about the ability for a third party's ability to predict this value better than random chance. A random number is one which is not predictable. Sometimes we'll add conditions to this. A Cryptographically-secure pseudo-random number generator (CSPRNG) generates numbers which cannot be predicted bettr than random chance *if* an attacker does not know the seed/key, but if we're talking about truly random numbers (not pseudo-random), its usually defined to be a number that is not predictable, even with complete knowledge of the system, including any keys.

Now, your example, as many have pointed out, is not deterministic. The program does not specify what value comes out of `System.nanoTime()`. Thus it is not in the same class as using a CSPRNG to generate pseudo random numbers. The former may be nondeterministic while the latter is deterministic if the value of the key is deterministic. The former contains operations which are not defined to have deterministic values.

However, you will note that I said it *may* be nondeterministic. Do be aware that `System.nanoTime()` is not designed to provide values for this purpose. It may or may not be sufficiently nondeterministic. An application might adjust the system clock such that the calls to `System.nanoTime()` all occur on multiples of 256 nanoseconds (or close). Or you may be working in Javascript, where the recent exploits of Spectre have lead major browsers to intentionally decrease the resolution of their timers. In these cases, your "random numbers" may become highly predictable in environments that you did not plan for.

* So generating random numbers with deterministic processes... sin.
* Generating random numbers with dedicated random hardware... not sin.
* Generating random numbers with nondeterministic aspects of computers... maybe sin.

It all depends on what you intend. If you are encrypting your love letters to Sponge Bob so that your sister cannot read them, the demands placed on your so-called-random-numbers are pretty low. `System.nanoTime()` used as you did is probably good enough. If you're protecting nuclear secrets against an advanced foreign State which is actively seeking them, you may want to consider using hardware that's designed to be up to the challenge.

# Answer
> 4 votes
I don't think you have understood the claim. The point is that if there is a deterministic procedure for generating a 'random' number series (or anything, really), then finding the pattern is merely the task of finding this procedure!

Hence, there is always exists a deterministic method to predict the next integer. This is precisely what we don't expect to happen if we assume randomness!

> Any sufficiently complex deterministicity is indistinguishable from stochasticity.

--From Wrzlprmft's user page

Hence, even if something *looks* random, why on earth would we model it as 'random' if we have a deterministic procedure to generate it?

This, I think, is the key problem. You have only shown some form of *indistinguishability* of the PRNG and 'true randomness'.

However, that these concepts are therefore equal does not follow. In particular, randomness is a mathematical, *theoretical* concept. We have already shown above, that in theory, considering PRNG as 'true randomness' leads to a contradiction. Hence, they cannot be equal.

# Answer
> 3 votes
I think that others already pointed it out, but it was not that emphasizes, so let me also add to the discussion.

As others already pointed out, there's the issue of measuring the entropy. Compression algorithms may tell you something, but they are source-agnostic. Since **you know more** about how the data was generated, you probably **could construt a much better** algorithm to compress it, and that means that true entropy is much lower.

Furthermore, you're somewhat mistaking meanings of phrases "on computer" and "deterministic". You certainly **can perform nondeterministic** operation on the computer.

Furthermore, in fact, *you just did it*, but it's not that apparent at the first glance.

A typical **deterministic** algorithm for a random number generation is ie. PRNG like linear congruential generator. They are stateful. Inner state means less entropy since next state is determined by previous. I won't delve in that, it's probably obvious to you. Important point is that fully deterministic algorithm depends only on previous state, whatever would it be.

Now look at your algorithm. What it is based on? How much state do you have? Is it deterministic?

```
  file.writeByte((byte) (System.nanoTime() & 0xff));

```

Let's ignore `file.write` and any the issues of flushing buffers, waiting for I/O (did you try to add heavy noise on the harddrive cables for a moment? no? hey you could do it. hey, it's nondeterministic then! :) ), and let's focus on the source, it's more important.

The **time** is some kind of a state. It varies, but most of it is the same. That's why you tried to circumvent it and took &0xFF to drop **most** of the state. But you have not dropped it all, some state of the previous read may leak to the next one, so it's certainly not fully nondeterministic \*)

But we're not interested in that. To "prove" that the quote is wrong:

> Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.

You need to prove it by a deterministic means.
What we are interested in, is: **is your algo certainly fully deterministic**?

..and it's obvious that it is not.

```
  System.nanoTime() & 0xff

```

That's a time measurement. **Time** and **measurement**. Measurement part may make it deterministic, if the value is cached. **I assume** it is not, otherwise this function would have no sense. Then, if it's read on the fly from the source, we have time-based value. Since (**I again assume**) you've not ran that on a single-task dedicated hardware, then you **may** have context-switching kicking in sometimes. Even if you had a single-task dedicated hardware, time measurement may still be not deterministic, because of temperature/humidity drifts in the time source, bus clocking times, etc.

I totally agree I'm exagerrating here. Drifts won't be that large to make much impact (though for a real `nanotime` they could be). More importantly, `nanotime` is meant to be fast. It doesn't read from real time source. It's based on processor's inner instruction/cycle count. That is actually deterministic, if you ensure no context switches.

My point is, it may be actually very hard to run a truly 100% deterministic algorithm if you base it on time, and you have no right to disprove that quote unless you do have fully deterministic means.

\*) Interestingly, you probably could increase the actual randomness if you go the hardcore way. Do &0x01, bit by bit, and thread-wait a noticeable time, before reading each bit. Generating data that way would be ridicously long, but I actually would argue that it could be considered to be almost truly random, IIF you're running on non-RTOS and also IFF in each 'noticeable time' is high enough to ensure that underlying OS either went to sleep, or context-switched to another task.

# Answer
> 2 votes
I think the answer you need starts with this comment you yourself made in reply another answer:

> The pattern is a result of the interplay of Java, the JVM, the OS, the CPU + caches, the hard disk, the Trance music I was streaming that consumes CPU /RAM cycles and everything in between. The pattern simply arises from the one line of Java code inside a for/next loop. A significant part of the entropy comes from the underlying hardware circuits.

You already realize this, I think: you didn't use *deterministic* means to create the pattern.

You used a computer, a non-negligible part of which is deterministic, but the entropy came from external non-deterministic (or at least, non-deterministic for all practical intents and purposes at the moment) sources: you or the external world interacting with the computer (and to a lesser extent, any physical imperfections in the computer hardware that might effect the timings of things).

This, by the way, is a big part of how modern operating systems seed their random number generators that are available to programs: by harnessing the entropy in interactions with its hardware and the user that we hope are not predictable to an attacker.

By the way, external-world entropy is actually a problem that has to be dealt with to this day in otherwise well-coded cryptography: computers that *have predictable behavior* upon boot and during their runtime, such as those with read-only storage or which boot from the network, and which have a predictable network environment (either not attached to a network or the workload on the network is low enough that everything is delivered within a reliable amount of time), and which run the same limited set of software with roughly consistent behavior, might grossly over-estimate the entropy they are getting from these assumed-to-be-unpredictable components, and end up generating far more predictable numbers than you'd get on a typical work-station that's doing all sorts of other stuff for you (streaming music, syncing with dropbox, whatever) in the background.

I think most answers are getting focused on whether checking the last eight bits of time measurements in nanoseconds taken in a loop is a good way to harvest that entropy. This is a *very* important question to properly answer *before* you use the method in your example as a random number generation scheme *in practice*, *but* it's a separate question from what I think you are asking about.

# Answer
> 0 votes
To add to previous answers, here's an easy way to think about this question.

It's all about the difference between *random* and *deterministic*. We'll come to Von Neumann and what he was saying, afterwards.

# Random numbers

A true random number generator would have no pattern, not even hidden in the background, which we could use to predict the next number given the sequence so far. In an ideal world, you could know everything there is to know in the physical universe, and about the system, nanosecond by nanosecond, and it still would be useless to try and predict the next number produced.

That's an ideal case - in practical terms we get there by mixing together many sources that are "not bad approximations" to random, or are truly random, or which mathematically mix things up enough that you can mathematically prove they get very close to unprediuctable and lack bias to any specific numbers or patterns.

* "Good" sources are things similar to waiting for a radioactive decay process, or other quantum process that's inherently unpredictable. Output from a heat sensitive semiconductor. Random noise in a diode or other electrical material. Counting photons from the sun.
* Mixed into this, we can also add some that we consider "not bad" which help as they don't have any connection to these: Waiting for the next mouseclick or network packet. Last bit of microtime on next file write. Output of a "known but mathematically pretty random" pseudorandom number generator function. Previous entropy from previous uses of random numbers.

The aim here, is to get a number which *still cannot be predicted*, **whatever in the universe you know**, and is statistically as likely to be this as that, with no mathematically detectable pattern, bias or predictability, and no correlation to an event that could be monitored and used for prediction. (Or if correlated with an event, then it's done in a way that makes the connection incredibly tenuous, such as "nanosecond digit only of time of last mouse click")

# Deterministic numbers

Mathematicians can prove things about formulae and functions. So it's possible to prove that a function, when repeatedly called, doesn't give any bias or preference to any pattern, other than the simple pattern "these are the outputs of that function if repeatedly called".

So for example, if you pick a number say between 1 and 10 million, write it in binary, and "hash" it repeatedly, you'll get a pretty random looking sequence of digits. It's almost random - but it isn't actually random at all. You can predict given the algorithm and any state, what the next number will be.

We call it "pseudorandom" because it looks and seems to be mainly random, even if it isn't.

Here's a good example. Think about this sequence of 3 digit "random numbers": 983, 367, 336, 244, 065, 664, 308, 602, 139, 494, 639, 522, 473, 719, 070, 217. Let's say that I tell you I can generate a million numbers the same way. You can pass then to a statistician who will confirm (say) that they are distributed equally or whatever it may be. There's no obvious predictable patternb. They look pretty random, right? But now I tell you that they are actually

> the 500th+ digit of Pi, grouped in 3s.

Suddenly, however random the

> digits of Pi

may be, you can immediately predict that the next 2 numbers will be 986 and 094.

To be clear, I don't know exactly how random the

> digits of Pi

are. It will have been studied and the answer well known. But the point is this: *In principle, the same conclusion is true for **any** source that is produced following a deterministic process*.

# In between

In between the two, are a whole range of "things that look random and are often random to some degree". The more randomness and near randomness one can mix in, the less prone the output is to being able to have any pattern detected or any output predicted, mathematically.

# Back to von Neumann and your question

As you can see, deterministic outputs might look random, but and might even, statistically, be randomly distributed. They might even use "secret" or fast-changing data that we have no realistic hope of knowing. But as long as it's deterministic, the numbers can **still never truly be random**. They can only be "close enough to random that we're happy to forget the difference".

That's the meaning of the quote you gave. A deterministic process just cannot give random numbers. It can only give numbers that seem to be, and behave quite like, random numbers.

We can now rephrase your question like this: "My (or any modern) computer's output can look and behave totally randomly, does that mean von Neumann's quote is now outdated and incorrect?"

The problem is still this: **Even if your computer's output may look and behave randomly, it still may not be *truly* random**. If it's only calculated deterministically, that means there is nothing that wasn't prediuctable cause-effect about gettinbg the next number (that's what "deterministic" means in this sense). We start with some existing data (known), we apply a known process (complex or messy or whatever), and we get what seems a new "random number" out. But it's not random, because the process was deterministic.

If you say that your method will include a true hardware random generator, to fix that (like a random number generated from radioactive decay or noise in a semiconductor), then your answer could now be random - but your method by definition is no longer deterministic, **precisely because you can't predict the outputs (or effects) given the inputs/initial data (causes) any more**.

Von Neumann wins both ways, almost by definition!

# Answer
> 0 votes
Just for the record, the actual quote uses the word "arithmetic" rather than "deterministic" and is from John von Neumann in "Various Techniques Used in Connection With Random Digits" published in a symposium proceedings on the Monte Carlo Method in June 1951; the symposium itself was in July 1949.

> Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method. (It is true that a problem that we suspect of being solvable by random methods may be solvable by some rigorously defined sequence, but this is a deeper mathematical question than we can now go into.) We are here dealing with mere "cooking recipes" for making digits; probably they can not be justified, but should merely be judged by their results. Some statistical study of the digits generated by a given recipe should be made, but exhaustive tests are impractical. If the digits work well on one problem, they seem usually to be successful with others of the same type.

You do have to look at the context. This was during a time when Monte Carlo simulation and computers were available only to very high-end (and usually defence-related) laboratories, and the RAND corporation had created some kind of electric circuit ("A random frequency pulse was gated by a constant frequency pulse, about once a second, providing on the average about 100,000 pulses in 1 second...." to generate a million digits that were later published as a book. Arithmetical methods such as the middle-square method ("A ten-digit number (we took 1,111,111,111) is squared and a middle ten is selected; i.e. the right five digits are dropped and the next ten retained to give "random" digits and to continue the process.") were the "state of the art".

Today we've got lots more statistical tests for randomness and lots more "recipes" for generating numbers deterministically that pass statistical tests with a certain threshold of confidence, along with more rigorous notions of information theory.

If you use the terminology precisely, deterministic pseudorandom number generation is valid to meet the requirements of certain uses. Sufficiently long output sequences of pseudorandom number generators will fail statistical tests, which is why you have to apply these sequences appropriately.

The term "random" bandied about by itself is not precise. (As is the term "sin".)

---
Tags: randomness, data-compression, entropy, random-number-generator
---


# Question
Title: Reddiag being a calculable function (Gödel, Escher, Bach)
In Gödel, Escher, Bach Chapter XIII: BlooP and FlooP and GlooP, Douglas Hofstadter states that:

> This puts us in the uncomfortable position of asserting that people can calculate Reddiag\[N\] for any value of N, but there is no way to program a computer to do so.

How come this is true? What if `Reddiag[N] = 1 + Reddiag[N]`? I understand how this is not computable, but how is it calculable? Is the idea that a person could notice that this is a sum of an infinite series of 1's, and either calculate that the answer is "infinity" or something like "-1/12" and therefore terminate?

Thanks :)

**Update**

The `Reddiag` is defined as `Reddiag[N] = 1 + RedProgram[#N][N]`, where `RedProgram` is any function written in a Turing complete language that takes one integer as an input, and we know that it is guaranteed to terminate with all inputs.

# Answer
> 3 votes
The passage in question has a **standing assumption that `RedProgram` enumerates all computable total functions.** Since `Reddiag` is total and different from every function enumerated by `RedProgram`, we conclude that it is not computable. The text continues to reach the conclusion that the standing assumption is false, by a standard argument in computability theory.

Let me also address your question about `Reddiag[N] = 1 + Reddiag[N]`. This is not possible because there is no natural number such that `n = 1 + n`.

---
Tags: computability
---


title: NP-hardness of particular problem

text:
# Question
Title: NP-hardness of particular problem
Suppose given two sets $\\{a\_1,a\_2,\dots,a\_n\\},\\{b\_1,b\_2,\dots,b\_n\\}$ of positive real numbers. We try to find a subset $I\subseteq\\{1,2,3\dots,n\\}$ such that: $\sum\_{i\in I}b\_i$ maximized and $\sum\_{i\in I}a\_i\leq 5$.

I think this problem is NP-hard but I can't reduce from famous problem like partition problem. Any help will be apricated.

# Answer
> 2 votes
This is the optimization form of the 0-1 Knapsack problem (Wikipedia).

In a 0-1 Knapsack problem, you have a set of items, each item having a weight and value. You have to select a set of items such that the sum of the values is maximized, but that the total weight of the items does not exceed the total capacity of the Knapsack. Here, the set $\\{a\_1, a\_2, \ldots, a\_n\\}$ corresponds to the set of weights and the set $\\{b\_1, b\_2, \ldots, b\_n\\}$ to the values, with the maximum weight being $5$.

The problem you posit is not a decision problem, and therefore is outside the classical definition of NP-hardness. However, it's easily converted into a decision problem asking whether a total value $V$ can be reached without exceeding the weight limit $W$. This version of the problem is NP-complete.

---
Tags: algorithms, np-complete
---


# Question
Title: Are there any other language classes of time complexity between the P language class and the NP language class?
$P$ is the language class that is decidable in polynomial time by a deterministic Turing machine.

$NP$ is a language class that is decidable in polynomial time by non-deterministic Turing machines and can be decidable in exponential time by deterministic Turing machines.

So are there any other language classes of time complexity between the P language class and the NP language class?

# Answer
> 2 votes
PMar's answer is correct. Having said that, there are several language classes "between" $P$ and $NP$.

An example is $RP$, the class of languages accepted in randomised polynomial time. A language is in $RP$ if it is accepted by an $NP$ machine with these properties:

1. If the answer is "yes", at least $\frac{1}{2}$ of computation paths accept.
2. If the answer is "no", all computation paths reject.

Clearly $P \subseteq RP \subseteq NP$. It is not currently known if $P = RP$ or $RP = NP$.

It's a similar story for $ZPP = RP \cap \mathrm{co}RP$.

# Answer
> 0 votes
Not if P = NP. Phrased differently, the provable existence of an intermediate language class would constitute proof that P != NP.

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


# Question
Title: How is the Subset Sum Problem NP-Complete?
You can't find a solution online for it that doesn't run in polynomial time complexity, when using dynamic programming. Have all these sites secretly solved P=NP, and no one knows about it?

# Answer
> 8 votes
The dynamic programming approaches only solve the problem in pseudopolynomial time.

Recall that the definition of (nondeterministic) polynomial time is that the problem must be solvable by a (nondeterministic) Turing machine whose running time is bounded by some polynomial in the size of the input. The size of the input is the number of bits required to write it down.

Suppose we want to solve a subset sum instance where the set has size $k$ (i.e., contains $k$ integers), and suppose this takes $n$ bits to write down. The dynamic programming approach builds up a table with $k$ rows and one column for each possible partial sum. How big is this table? Well, surely $k\leq n$, since we can't write down more than $n$ numbers in only $n$ bits. However, a partial sum is the sum of some number of integers, each of which takes about $n/k$ bits to write down. So that sum is also going to take roughly $n/k$ bits to write down. That means that there are roughly $2^{n/k}$ columns in our table, so our table is exponentially large and we can't populate it in polynomial time.

The algorithm runs in pseudopolynomial time, which means that it runs in time bounded by some polynomial in the numbers represented in the instance, rather than in the number of bits required to write them down.

(In fact, this dynamic programming approach uses even more memory than doing dynamic programming on subsets. Suppose, for example, that your set is $\\{1,100\\}$. There are only three nonempty subsets but you're likely to decide that a partial sum could be anywhere between $0$ and $101$, giving a table with two rows and $101$ columns, instead of two rows and three columns.

# Answer
> 6 votes
There are indeed no polynomial time algorithms to solve subset-sum, but there are **pseudo**-polynomial time algorithms. What does this mean ? That their running time is polynomial in the numeric values, but exponential in the length of the input, because that is logarithmic in the numeric values ( binary representations, and not unary ).

That is by the way the difference between strong and week NP-completeness.

# Answer
> 0 votes
The subset sum problem can easily be solved in polynomial time in the number of items, and the sizes of the items. However, to be in NP, the solution must be in polynomial time in the problem size. Say all items are \<= 9999, then I only need 4 digits to write down a number. If all items are less than a billion billion billions, then I need only 27 digits to write down each item size. 1000 such items, there are solutions in polynomial time in 1000 and a billion billion billions. NP wants polynomial time in 1000 and 27.

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


# Question
Title: Which temporal logic is the one described in Manna & Pnueli's "The Temporal Logic of Reactive and Concurrent Systems: Specification"?
The Wikipedia article on temporal logic lists many varieties of temporal logic, such as LTL (linear temporal logic), CTL (computation tree logic), CTL\*, and others. Which of these is the logic described in Manna & Pnueli's textbook *The Temporal Logic of Reactive and Concurrent Systems: Specification*?

I've started to read Manna & Pnueli's textbook. I'd like to read other accounts of the same theory. But to do so I need to know the name of the theory, so I can look for other textbooks about it.

# Answer
LTL.

PS The very book you mention has a historical note section discussing various other temporal logics near page 271.

**Edit (leaving the above intact for the comments to make sense):** None of the named logics in the wikipedia article (at the time of writing this) is the same as/equivalent to Manna and Pnueli's. The name LTL has however a different and broader meaning in the community.
> 1 votes

---
Tags: temporal-logic
---


# Question
Title: Am I right that Reed-Solomon codes can be used to implement arbitrary-parity RAID schemes?
I guess the question does not apply just to CS as I'm trying to understand how it applies to RAIDs, but I guess it's maybe the most suitable place to ask anyway.

There's a lot of info that RS codes are often used to implement second parity for RAID-6. There are some systems that implement triple-parity.

Am I right that by using enough Reed-Solomon parity bits I can implement 4-way parity etc., up to arbitrary-way parity (as long the the stripe is long enough, e.g. by writing each n bit stripe as k data bits + t parity bits)?

I'm just surprised why, if it's true, parity counts \> 3 are not implemented in any production systems.

# Answer
A Reed-Solomon code applied to 512-byte (4096-bit) sectors can support up to $n=2^{4096}$ drives in an array, of which any fraction may be parity drives. The limits of real-world RAID setups come from practical considerations, not theory.

RAID can defend against the random failure of up to $t$ drives, but it can't defend against a power surge or fire or software bug or anything else that destroys the entire array. There is some $t\_\text{max}$ such that for $t\ge t\_\text{max}$ the probability of failure is largely independent of $t$ because failure modes that can't be prevented by RAID dominate. Probably $t\_\text{max}\approx 3$.
> 4 votes

# Answer
More broadly, the issue of repairing Reed-Solomon codes currently employed in industry has been discussed in the literature. It is important to find algorithms with low-bandwidth repair schemes for codes of short lengths with typical redundancies.

A recent paper is a good place to start since it has tables of current best repair schemes for $\[n,k\]$ Reed-Solomon codes over $\mathbb{GF}(2^8)$ with $4≤n≤16$ and redundancy $r=n−k∈{2,3,4}. $The tables cover most known codes currently used in the distributed storage industry. For convenience, I have reproduced a figure from that paper which has examples of the codes used in industry.

See the paper available here.
> 1 votes

---
Tags: coding-theory, error-correcting-codes
---