# Question
Title: Why do functional languages disallow reassignment of local variables?
*Fair warning: I don't actually know a functional language so I'm doing all the pseudocode in Python*

I'm trying to understand why functional languages disallow variable reassignment, e.g. `x = x + 1`. Referential transparency, pure functions, and the dangers of side effects are all mentioned, but the examples tend to go for the low-hanging fruit of functions that depend on mutable globals, which are also discouraged in imperative languages.

My question involves variables created and mutated within the function. For example:

```
def numsum1(n):
    sum = 0
    i = 1
    while i <= n:
        sum = sum + i
        i = i + 1
    return sum

```

The functional way of doing this seems to be tail recursion, where the updated `sum` and `i` are passed from function call to function call. I know that there are existing higher-order functions for this, but I think this illustrates the similarity to `numsum1` more plainly:

```
def numsum2(n): return numsumstep(0, 1, n)

def numsumstep(sum, i, n):
    if i <= n:
        return numsumstep(sum + i, i + 1, n)
    else:
        return sum

```

`numsum1` and `numsum2` do the exact same thing (with tail call optimization) and are both referentially transparent. I do see why `numsum1` is internally referentially opaque; the expressions `i + 1` and `sum + i` change in value with each iteration and thus cannot be replaced by a constant value. But why does that matter if `numsum1` itself is referentially transparent? Are there examples of functions that become referentially opaque solely because of reassigning local variables?

# Answer
> 32 votes
In a pure functional programming language, there is no real notion of *time* at all. So, saying that a variable `x` has value *a* at one point and then *b* later simply doesn't make any sense – it's like asking a character in a painting why she always stares in the same direction.

The advantage of having no time is that you never need to worry about the order in which computations happen. If a variable is in scope then it also has the correct value, i.e. the value it has been assigned. (Which assignment may actually be “after” the computation in which it is needed – definitions can be reordered at will.)

Whereas in an imperative language – well, consider this program:

```
def numsum1(n):
    sum = 0
    i = 1
    while i <= n:
        sum = sum + i
        i = i + 1
    midterm = sum
    while i >= 0:
        sum = sum - i
        i = i - 1
    return (midterm, i)

```

If for some reason you need to refactor and pull the `midterm` definition behind the second loop, overlooking that it actually mutates `sum` again, then you would get the wrong result.

Now, you might well argue that this is defeated if you need to use recursion to basically fake mutation. Isn't there just as much, or even *more*, potential for mistakes if you have a recursive call using a parameter still called `x` that is effectively the same variable anyway?
– Not quite, because *outside* of the recursive calls the variable is guaranteed to stay the same. The refactoring problem with the above example wouldn't happen in a functional language.

Furthermore, as Odalrick already wrote, recursion isn't actually what's normally used to replace loops in functional languages. The idiomatic Haskell version of your program is

```
import Data.List (sum)

numsum :: Int -> Int
numsum n = sum [1..n]

```

...or, using more general-purpose tools,

```
numsum n = foldl' (+) 0 . take n $ iterate (+1) 1

```

---

That's a bit of an exaggeration. Of course, you do sometimes need to take *time* into account even in a functional language. Obviously, if it runs somehow interactively (`IO` monad in Haskell), then those parts are subject to latency considerations. And even for completely pure computations, one side effect that you can't possibly avoid is *memory consumption*. And that's indeed the one thing that Haskell truely isn't good at: it's really easy to write code that typechecks, works, is correct, but takes gigabytes of memory (when a few kilobytes should have been enough) because some thunks are never garbage-collected.

# Answer
> 11 votes
I can only share my perspective. The way I think of it is that mainstream functional languages typically combine two themes: (1) support for higher-order functions, and (2) a preference for pure computation (referential transparency, no side effects, no mutation). In principle those two could potentially be separable, but they often go together in many mainstream functional languages.

Why is it considered beneficial to avoid mutation? Arguably, avoiding mutation makes it easier to reason about the correctness of code. This is especially so in the presence of concurrency, and also relevant when you have complex mutable data structures that are shared among multiple code modules. Variable reassignment is one form of mutation -- perhaps not the most dangerous, but if you set out to build a language that prefers pure computation, there is a certain conceptual clarity and cleanness in avoiding all mutation.

You can certainly have a function that is referentially transparent, yet that internally reassigns to local variables. However, verifying referential transparency can be more challenging in the presence of mutation. In contrast, if there is no mutation whatsoever, then it is becomes more trivial to verify that code is referentially transparent. So, there can be value to restrictions that are stricter than absolutely necessary, if they make it easier to verify correctness of code. We see this idea all over the place in programming languages, including in type systems (e.g., type systems: code that violates type-safety can potentially still be correct, but may be harder to verify is correct).

# Answer
> 9 votes
If we want to be very precise with our words, we should say that in functional programming you don't *assign* a value to a variable, because *assignment* is a thing that you "do", and if you are telling the computer what to "do" then you are doing imperative programming instead of functional programming.

In a functional programming language, the code `let x = 1` is not an instruction to *assign* the value 1 to the variable `x`; it is a *declaration* that the variable `x` *is equal to* 1. That is, the `=` symbol is used in its mathematical meaning to say that those two things are the same, interchangeable; not in its imperative programming meaning as an instruction "take the value 1 and store it in the memory location labelled `x`".

So, variables cannot be reassigned because they cannot be *assigned* in the first place. If you write `let x = 1` and `let x = 2` in a functional language, you are declaring that `x` is equal to 1 *and* equal to 2, which means you are declaring that 1 is equal to 2, because mathematical equality is transitive. It would not be useful for a language to allow you to declare that 1 is equal to 2.

# Answer
> 7 votes
There are several reasons, but they boil down to three main points:

* It's easier to reason about correctness, *especially* in the context of complex semantics (e.g. existential types, lazy evaluation) and security.
* It allows for optimisations that are not possible if data can change underneath.
* It allows for a transparent models of multi-threading, since read-only data does not need to be protected.

It's worth noting that non-functional languages do it too, and for much the same reasons. Java, for example, has an immutable `String` type. This allows static string data to be stored in read-only memory (e.g. on a microcontroller or smart card), and also makes for a more efficient and easy-to-prove security model when running potentially untrusted code.

You can't pass a `String` to a security-conscious part of the standard library such as the `SecurityManager` and then modify it after the event or in another thread. Nor can you use a `String` as a key in a binary search tree or hash table and then modify it, thus invalidating the data structure's guarantees.

# Answer
> 6 votes
In functional programming, great pains are taken to be able to know *exactly* what a computation depends on. The way in which you make variables be mutable, there can be cascading effects on the rest of the language.

If you just make them mutable, in that they are reference cells, then what you are effectively doing is wrapping the entire language in a state monad, where every variable in every closure becomes part of global state. For example, this is something that mutable variables let you do (in Python 3):

```
def make_counter():
    val = 0
    def count():
        nonlocal val
        val += 1
        return val
    return count

c = make_counter()
print(c()) # 1
print(c()) # 2
print(c()) # 3

```

That is not so good for analyzing the behavior of a program. Analysis is much easier if you can ignore the order in which expressions are evaluated.

It is easier to simply disallow mutable variables entirely than to develop a well-designed system that gives you useful, safe, and analyzable mutation.

One language that seems to have succeeded in this regard is Lean 4. It has a system that automatically inserts the correct folds into a monadic do-notation block to implement mutable variables. Here is an example translation of your program (using $0 \leq i \< n$ rather than $1 \leq i \leq n$):

```
def numsum1 (n : Nat) : Nat := do
  let mut sum : Nat := 0
  for i in [0:n] do
    sum := sum + 1
  sum

```

This is using the "identity monad" and gets turned, effectively, into your `numstep2`. When it is compiled to C, it should even be a for loop with a mutable sum variable (though I didn't check).

Other monads, like the IO monad, also get local mutable variables through this system.

To be clear, the variable isn't "really" mutating since each iteration of the loop is essentially a new `sum` variable containing the updated value. However, the language doesn't have an interface where you can get a pointer to a `mut` variable, so you can't really say whether it is "really" updating in-place or not. And in fact, the runtime takes advantage of this with the Perceus functional-but-in-place paradigm.

# Answer
> 4 votes
What would it be like to have variable reassignment in functional programming?

First i is 0, then you do something and change i to 1 ...

But that is "do this, then that". *Imperative* programming; not functional.

Functional programming is declarative. You write a whole bunch of functions and the computer takes care of calling them as needed. If you had i = 0 and then a bit later i = 1 in the same scope, the compiler could decide to set i to 1 first and then to 0.

Obviously no one wants a language to do that so it is simply disallowed.

So the answer is ultimately, because it is a functional language. If it allowed reassignment it would be an imperative language.

---

edit: I think what you are actually after is a more loopish way of functional coding.

While recursion is common and powerful, the loop equivalent in functional programming is genererally `map` or `reduce`.

It's a bit awkward in Pyhon but:

```
import itertools
import operator

def numsum3(n):
    all_numbers = itertools.count(0)
    sums = itertools.accumulate(all_numbers, operator.add, initial=0)
    n_and_forward = itertools.islice(sums, n + 1, None)
    return next(n_and_forward)

```

Make a list of all the numbers. For all the numbers, sum the previous number and put it in an list. Discard all numbers up to the (n+1)th number (+1 because you used \<= ). Return the first number in that list.

It is awkward in Python, but in functional languages this would be much easier to write.

---

"computer takes care of calling them as needed"

Exacly how this works depends on the language. Haskell uses monads; Elm has a "core" that does things outside the language; Erlang has a VM that does stuff.

This is one of the strengths of functional programming. The programmer actually cannot write very specific code so the "compiler" is free to do whatever it needs to.

# Answer
> 2 votes
Optimizers in C++ turn traditional C++ code into static single assignment when it can.

You can think of traditional imperative programming as chaining together functional steps.

```
struct state {
  int sum;
  int i;
};

auto numsum1 = [](int n){
  return fpipe{} |
    []{ return state{0, 1}; }
    | while_loop( [n](state s){ return s.i<=n; }
    )(
      [](state s){ return {s.sum+s.i, s.i+1}; }
    )
    | [](state s){ return s.sum; };
}

```

this is a purely functional version of the same imperative code with no recursion in "psudeo-code" that I could literally make compile in C++. `[capture](arguments){body}` is a C++-esque definition of a lambda, and `|` represents "piping the previous return value as an argument to the next function".

In this case, everything is immutable, nothing can be changed in any line of code above.

Converting traditional procedural code to this format makes reasoning about it by the compiler insanely easier, which in turn makes optimization easier.

The same is true for a human who gets used to it. Variables don't change their meaning or value in a given function call; they always have the same meaning.

This pattern "variables mean one thing", "data flows are explicit", "build algorithms out of smaller algorithms" is pretty fundamental to functional programming.

# Answer
> 2 votes
The answer is really purity. Pure functional languages strive to be pure functional languages. That involves not doing impure things.

I'm just learning F# right now. I notice that it has a policy of "variables are immutable by default, but can be declared to be mutable." So F# would be an example of a language that chose not to go the purist route.

Thanks to the Church-Turing Thesis, we know that you can convert between any lambda calculus problem and a corresponding Turing machine. This implies that there's always a way to go from functional programming constructs to imperative constructs, and back. We can always construct a pure functional program which is *isomorphic* to a functional program that has some mutable variables. Yakk's answer points at Single Static Assignment (SSA) which is one algorithm which helps tease apart assignments, shepherding it towards pure functional languages if one wishes.

Its all a matter of the intent of the language designer. Most of the big functional languages I know of were designed by people who wanted to explore pure functional languages and who believed that the notation of functional languages was superior to that of imperative languages. Their languages reflect these philosophies.

As a practical manner, as a language designer, consider the details that have to be handled when permitting something like re-assignment in a functional language. You have to make sure of two things:

* Reassignment of variables does not break assumptions that you relied on for the effectiveness of your language (referential transparency being the big one)
* Your users need to not be surprised by where reassignment works, where it doesn't work, and how it acts. Surprised users are unhappy users when it comes to programming languages.

Personal anecdote: I just dealt with the fun of the opposite of the question you ask -- the addition of functional bits into an imperative language. I just found out that C++'s `std::function` does not provide any guarantees regarding the use of dynamic memory, even in situations where it is clear that such dynamic memory could be avoided. It depends on the language implementer to decide when and where dynamic memory is needed.

Having now written a library using `std::function` in an environment where such dynamic memory is forbidden, I now need to go back through it and basically rewrite the entire API... Its quite exciting. You can hear the thrill in my voice as you read this, can't you? I am a user that got surprised.

# Answer
> 2 votes
Disallowing assignment is part of the definition of "functional programming" and "functional language". On one level, you're simply asking why the definition of "functional language" is correctly being applied, so that languages which allow mutation of local variables are not eligible.

Why is variable mutation excluded from the definition of "functional"? Firstly, variable mutation will not achieve anything unless you have multiple execution code paths which can reach the same point. For instance:

```
let a = 0
if condition
  a = 4
else
  a = 5

```

but this doesn't exist in functional programming also. There are no statements. An if/then conditional in a functional language is an expression which calculates a value. In a functional language, the body of a function can consists of zero or more variable binding constructs, followed by an expression. Those binding constructs are not statements, though; they are just a way to factor out values from the body expression by giving them names, like in mathematics.

Since there are no statements in functional programming, variable assignments serve no purpose, because a variable assignment is a statement which alters a variable in order to induce a change in the calculation performed in other statements. And, not to mention, that since there are no statements and variable assignment is a kind of statement, it is ruled out that way.

A functional language can allow rebinding a variable in the same scope. For instance:

```
let x = 0
let x = x + 1

```

this is not assignment though; these are two different *x* variables, where the second one shadows the first one. A functional language would provide no way for the first `let x = 0` to be skipped; e.g. this would not be featured in a functional language:

```
goto label
let x = 0
label:
let x = x + 1

```

To reiterate, the `let` bindings are not imperative statements. The notation:

```
let x = 0
let x = x + 1
x + x  # body expression

```

is just a verbose spelling of:

```
let x = 0 + 1
x + x

```

which is just another spelling of:

```
1 + 1

```

which is just another spelling of

```
2

```

"Functional" is all about functions: calculating by applying functions to values. In the purest form of functional programming, lambda calculus, there are no variables, other than function parameters.

The Lisp language (not functional, by the way, but supporting functional programming concepts) originally had no `let` operator at all for binding local variables. `lambda` came first, and `let` was invented as a syntactic sugar for a `lambda`. So that is to say if we have:

```
(let ((x 1)
      (y 2)
  (+ x y))

```

This can be written as a call to an anonymous function:

```
((lambda (x y) (+ x y)) 1 2)
  ^^^^^^^^^^^^^^^^^^^^^ ^^^
    function            args

```

These two expressions notate exactly the same thing: binding *x* to 1, *y* to 2 and evaluating`(+ x y)` producing 3.

So when you think of a variable in the context of functional programming, you should think "function parameter". If you look hard enough, you will see the function.

When local variables are bound prior to the evaluation of some expression that references them, you can think of it as the parameters of an anonymous function receiving formal argument values.

In functional programming, **every variable is a actually a formal parameter, and the only way it receives a value is by receiving a formal argument as part of a function call**. And, so, that's the nutshell of why there is no assignment **and** why it's called "functional".

# Answer
> 1 votes
`numsum1` can be mechanically translated into `numsum2`. In fact, the translation is essentially the same as the one performed anyway by virtually all optimizing compilers, as Andrew Appel pointed out in the paper SSA is Functional Programming. *

Since it can be done automatically, you could argue that there's no reason to make the human programmer do it.

I think the strongest argument against this is that there's nothing stopping you from writing your entire program as one big function. Then you can mutate global variables, since they are local to the current function. The automatic translation to SSA/functional form will convert the globals to hidden parameters, so everything will work. But the larger the program gets, the more those parameters will truly be hidden from the human programmer, which is the problem that pure functional programming is meant to avoid.

If limited to small functions like your example, where the usage patterns are obvious, I think the automatic translation would be harmless, but also not very useful since it's easy to transform by hand. When it's difficult to do the transformation by hand, it's because it's hard to analyze all of the dependencies in the code, and that's when you should do it by hand, since functional programming is about making those dependencies explicit (and ideally minimizing them).

---

* I'd say rather "SSA is a hacky subset of functional programming", since the functional form includes the SSA flowgraph, the dominance tree, and additional information not found in either of them in a nice unified way, and I think it's easier to understand.

# Answer
> 1 votes
### It’s closer to what an optimizing compiler does

Back in the olden days, on compilers that couldn’t optimize worth a DRAM, it was necessary to tell the compiler to throw out the old value we no longer needed, and replace it with an updated one. Early programming languages tried to stay close to the low-level operations of the processor, which would update a variable in a register or memory. But modern compilers perform dependency analysis, code movement and register allocation. They’re better at figuring out when they can drop or spill a variable from a register than a human is. So you can now declare every variable you need as a static single assignment, and let the compiler transform your high-level computation into efficient code.

Traditional functional languages transform code into continuation-passing style, moving blocks of code around so that the computations execute after their dependencies. They also allocate registers so that any quantity that’s no longer needed gets discarded, freeing up a register for another quantity that will be needed soon. They do this better than humans ever could: if you keep around a variable that you no longer need, you wast a register, and if you drop it too soon, you cause a bug the compiler can’t catch.

Unmodifiable variables are in many ways easier to optimize, since you’ll know for sure that you can do the computation once and re-use the value, you know for sure when it’s safe to use a reference instead of cloning the object, you know for sure on modern processors that reading the variable is thread-safe, and so on. Some computer scientists go further and try to prove that certain program transformations are provably correct on pure functions, in category theory.

Even many compilers for procedural languages transform code like `x = x + 1` into a static single assignment, equivalent to `x_1 = x + 1`.=, and then treat `x` and `x_1` as if they were different, immutable variables with a dependency between them. More complicated expressions, such as conditional assignments, get transformed into phi functions on the right-hand side. There’s an efficient algorithm to transform an abstract syntax tree in SSA form into one in CPS form and then apply all the optimizations from that.

If the optimizer is going to try to produce good code by transforming the program into a series of pure computations anyway, it’s less likely to get confused if the source code is written that way.

### It prevents certain bugs

In this pseudocode,

```
y = f(x)

if (a > b)
  x = x + 1

z = g(x)

```

What is the value of `x` when `z` is computed? Are we sure that `x` always gets properly initialized? If this code gets refactored so `z = g(x)` gets moved right after `y = f(x)`, which you might want to do for clarity, its meaning sometimes changes, giving you a Heisenbug. If you’re reviewing a large function with many possible paths of execution, when we see `x` being used, how was it set in this context?

In a functional language (or even a hybrid like Rust), you might write something like

```
let y = f(x0)
    x1 = if   (a > b)
         then x0 + 1
         else x0
    z = f(x1)

```

In many languages, you could even initialize `z` before `x1`, and there will be no doubt what you meant. Declaring `x0` and `x1` is completely unambiguous and the meaning of the same symbol does not change if you move it elsewhere in the same block. You can also be certain that `x0` and `x1` were initialized once and only once, and what they were initialized to.

### It’s easier to analyze

It isn’t, in general, possible to deduce whether a code path in an arbitrary program is reachable. However, if you restrict the language so that only certain safe operations are possible, you can more safely prove what will and won’t happen. For example, when variables are immutable, many complex special cases involving modification through an alias cannot occur. C++ even introduced a special form of immutability, `constexpr`, specifically to make it possible for the compiler to perform calculations on constants at compile time and fold them into the executable.

Or, let’s take the great example you gave:

```
def numsum1(n):
    sum = 0
    i = 1
    while i <= n:
        sum = sum + i
        i = i + 1
    return sum

```

We want an optimizing compiler to be able to tell that this is all equivalent to `return n`. Optimizers for imperative languages are heavily-focused on analyzing loops, and this `while` loop is simple enough that I’d expect a modern C, C++, Java or Rust compiler to be able to figure the translation out.

### Functional languages have equivalents

A functional language can also have variables that mutate within each iteration of a loop, only it would refactor into a tail-recursive function:

```
numsum1 n = go 1 0 where
  go (n+1) sum  = sum
  go i sum = go (i+1) (sum+1)

```

Or, if we’re not worried about negative numbers as inputs (although we could easily handle those too):

```
numsum1 n = go 0 n where
  go sum 0 = sum
  go sum i = go (sum+1) (i-1)

```

Tail recursion on a pattern match like this is exactly equivalent to the loop: you perform a test at the beginning of each repetition to see whether you continue, and if so, increment the loop counter (which on a modern ABI means updating registers and re-using the same stack frame) and jump back to the start of the loop/tail-recursive function. Both versions have a local variable named `i` within the block of code whose value changes every time it runs. Since imperative-language compilers also want to be able to optimize tail-recursive functions, it’s simpler for the compiler to be able to rely on a great optimizer for recursive code, and not need to analyze arbitrary `while` loops too.

---
Tags: functional-programming, imperative-programming
---


# Question
Title: Number of operands to take when evaluating postfix notation?
* All sources I have seen list taking two operands from the stack once we encounter an operator.
* Why? What if not all of my operators are binary (taking two arguments)? What if I have custom unary and ternary operators?

# Answer
> 3 votes
I guess those sources innately assume binary operators. In a stack-based language (like postfix math notation) an $n$-ary operator takes $n$ items from the top of the stack as its input. Constants are often also viewed as arity 0, or *nullary* operators in this context.

---
Tags: efficiency, mathematical-programming
---


# Question
Title: What is the true space-complexity of saving all divisors, because $N$ can have more divisors than the length of $N$?
$6983776800$ in binary has 33 bits but has $2034$ positive divisors.

If a list of divisors were to be logarithmic in N, it needs to take less than 33 bits.

I believe there is an infinite amount of numbers with more divisors than the bits used to represent them.

Thus it is not possible for any algorithm to create a list using log-space.

So given the worst case, that $N$ has a vast amount of divisors what is the true space-complexity?

# Answer
“Saving all divisors” is just not a clever way to go about it. It’s much better to factor N into the product of powers of distinct primes, which has about the same size as N, and all divisors can be enumerated from that easily.

But then, if N has n bits, it can be the product of about n/log n primes of log n bits each, so there are about 2^(n / log n) possible products of n/2 bits each on average. So the logarithm of the size of all factors is about n/log n. I’m sure you can do this a bit more precise.
> 4 votes

---
Tags: space-complexity, factoring
---


title: Pivot algorithm in median of medians

text:
# Question
Title: Pivot algorithm in median of medians
The pseudocode for the `pivot` function for the Median of Medians algorithm is given in https://en.wikipedia.org/wiki/Median\_of\_medians.

On the last line, there is a mutual recursion call to the `select` function and you can see that the median of the subarray of medians is passed in as parameter `n` in the `select` function. Unfortunately, they use $n$ in the section above to represent the size of the array as well, but `n` in this function means "n-th smallest."

My question pertains to the  `return select(list, left, left + floor((right − left) / 5), mid)`.

If we are ultimately trying to find the n-th smallest number, should we be interested in the median of the subarray of medians, or should we be interested in the $n-th$ smallest median in the subarray of medians? If it's the latter, then shouldn't this `mid` be changed to the index for the n-th smallest median?

# Answer
> 1 votes
The goal of the *pivot* routine is to choose an approximate median. This guarantees that in the next iteration, the array shrinks by a constant amount.

Obtaining an approximate $n$'th smallest element wouldn't necessarily do the trick, at least in the short run. As an extreme example, if you're looking for the second smallest element and the pivot is the smallest element, then the array shrunk by just one element.

This example suggests that the strategy of using an approximate $n$'th smallest element might work; however, it is not completely clear how to find such an element, that is, whether the $n/5$'th smallest element of the median array is an approximate $n$'th smallest element in the original array.

In summary, the median-of-medians algorithm works. You might be able to modify it somehow using a different pivoting strategy while maintaining a linear running time; but the analysis might be more complicated. You can give it a go if you wish.

---
Tags: quicksort
---


# Question
Title: Given DAG $G(V,E)$, find $\forall v \in V$ the sum of the weights of vertices that are reachable from the $v$
> Given a DAG $G=(V,E)$ and a weights function on the vertices $w:V \to \mathbb{R}$, suggest an algorithm that computes for every $v \in V$ the sum of the weights of vertices that are reachable from it.

My idea is to use topological sort on the graph and then start from the end to the start, and for each vertex $v \in V$ set the sum to $S(v)=w(v)+\sum\_{(v, u) \in E} S(u)$.

But this can cause counting some vertices multiple times, which I am not sure how to fix while still solving the problem in linear time.

# Answer
> 1 votes
In order to avoid the double counting you can work with **sets** of vertices instead of their sums of weights. Let's denote $R(v)$ a set of all vertices, reachable from the vertex $v$. Then, similarly to your formula, you can calculate all the $R(v)$ sets scanning vertices in backward topological order:

$$R(v)=v \cup \bigcup\_{(v, u) \in E} R(u)$$

After this process is finished you can calculate the sum of weights for each vertex $v \in V$ using its $R(v)$ set. However this algorithm won't be linear - even the last step will take $O(|V|^2)$ time, because you'll need to process the set $R(v)$ for each $v \in V$.

These $R(v)$ sets actually represent the Transitive Closure of the graph $G$ \- finding the transitive closure of a DAG is a well known problem, and the best known algorithm for it takes $O(|V|^{2.373})$ time. Also please see this question (and its answers), which is very similar to what you've asked.

# Answer
> 0 votes
You can do better, so we propose a linear time algorithm.

Reverse the edges of $G$ in linear time, name it $G^R$, and start from the last node in topological order of $G$ in $G^R$, so propagate sum of values from the last node to other nodes that reachable from it in $G^R$. This can be done in $\mathcal{O}(n+m).$

---
Tags: algorithms, graphs, graph-traversal, weighted-graphs
---


title: Disconnected bipartite graph

text:
# Question
Title: Disconnected bipartite graph
I was searching whether a bipartite graph can have a vertex with 0 degree. I found this, but the answer there says it is possible. Wouldn't that make a graph tripartite?

Also, if a vertex with zero degree exists that will make König's theorem wrong. For example let bipartite graph edges be $(1,a),(2,b),(3,b)$ and $4$ with degree $0$. So maximum matching is 3 and minimum vertex cover is 4 here.

# Answer
> 3 votes
If graph is bipartite if it is 2-colorable. Equivalently, a graph is bipartite if its vertex set can be partitioned into two sets $A,B$, such that every edge connects a vertex in $A$ and a vertex in $B$. There are no further constraints. In particular, a bipartite graph could be disconnected, have isolated vertices, or even be empty.

In your purported counterexample to König's theorem, a minimum vertex cover is, for example, $\\{1,2,3\\}$, which indeed has size 3. (Recall that a vertex cover is a set of vertices touching all edges.)

---
Tags: graphs, discrete-mathematics
---


title: Is QMA known to contain Co-NP?

text:
# Question
Title: Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)

# Answer
> 4 votes
This is not currently known. In my MSc. thesis, I show that, if it were true, then a consequence would be that $NP^{NP}\subseteq QMA$ (Theorem 21, below). I conjecture that in fact $coNP\subseteq QMA$ implies $PH\subseteq QMA$, but I was not able to prove that.

**Lemma 14.** $NP^{QMA\cap coQMA}\subseteq QMA$.

**Theorem 21.** If $QMA$ contains $co\text-NP$, then $NP^{NP}\subseteq QMA$

*Proof.* If $QMA$ contains $coNP$, then, equivalently, $NP\subseteq coQMA$, so we have $NP\subseteq QMA\cap coQMA$. Plugging this in, we get $NP^{NP}\subseteq NP^{QMA\cap coQMA}\subseteq QMA$. $\square$

The thesis contains other consequences, and variations and generalizations of this theorem.

---
Tags: np, complexity-classes, quantum-computing
---


# Question
Title: Are the number of entries in the TLB(Translation Lookaside Buffer) limited?
If not, then why aren't all the pages loaded into the TLB so that TLB misses never happen.

# Answer
> 1 votes
The number of entries in the TLB is limited and keep in mind that there are multiple levels of TLBs. So the higher the level, the more entries they typically have. For more detailed information have a look at the following page for Skylake.

Wat you are referring to is a minor page fault; so there is no matching entry for a page in the TLB, but the page is in memory.

You can also have a major page fault, the entry isn't in the TLB + isn't in memory. It needs to be loaded from disk into memory first before and entry can be placed in the TLB.

So even if your TLB would be infinitely large, you still need TLB misses to deal with major page faults.

# Answer
> 0 votes
The TLB is part of the CPU. So once you bought a CPU and put it in your computer, it's limited. Another more expensive CPU might have a larger TLB, which is still limited.

I can buy a computer with 1500 GB of memory. You'd need a bloody big TLB to have no TLB misses whatsoever.

---
Tags: operating-systems, memory-management, memory-hardware, memory-access, virtual-memory
---


title: Tiny question on residual networks

text:
# Question
Title: Tiny question on residual networks
Is it true, that the number of edges in residual network is always less than twise the number of edges in the original flow network? My thoughts, that it's false, because in residual network quantity of edges is always $2 * E\_{G\_{f}}$, even some of them are zero edges. Am I right?

# Answer
There are different (equivalent) definitions of residual networks (depending on whether you keep edges with capacity $0$ or not).

Anyway, the claim is false since we can select the original network as a graph with no edges (meaning that the only feasible flow is the empty flow, as long as the source and the sink vertices are distinct). Then, the residual network is the graph itself which clearly cannot have less than $0$ edges.
> 1 votes

---
Tags: network-flow
---


# Question
Title: Can a non-deterministic finite automaton die out before reading the entire string?
I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by:

However, my problem is: If the string does not start with $a$ then the machine will die out in such a case and will not read other letters in the given string, is this fine? I have read somewhere that the machine should not die out till the string is completely read (even if the string is not accepted), and such is not the case here.

**Furthermore, if this is not the case then, why should the state $q\_2$ needs to have an arrow over itself? Do I really need to care? Once the string is having an "$ab$" in the beginning, the machine knows it has to accept the input and can die out.**

I am just confused, the given NFA confers that the machine can die out even without reading the whole string, Is this fine? And If it is and why to put a self-arrow over $q\_2$?

# Answer
Formally the transition function $\delta$ of a NFAs is a total function with domain $Q \times \Sigma$ and codomain $\mathcal{P}(Q)$, where $Q$ is the set of states and $\Sigma$ is your alphabet and $\mathcal{P}(Q)$ is the power set of $Q$.

The NFA accepts a string $s=s\_1s\_2s\_3 \dots$ iff there is a sequence of states $q\_0,q\_1, \dots, q\_n$ where $q\_0$ is the initial state of the NFA and, for $i=1,\dots,n$, $q\_i = \delta(q\_{i-1}, s\_i)$.

As a consequence, if there is no possible sequence of states that satisfies the above condition (what you seem to call "die out"), the NFA rejects.

A way to check whether an accepting sequence of states exists is that of keeping track of a set $S$ of states while simulating the NFA on the input string. Initially $S = \\{q\_0\\}$, where $q\_0$ is the initial state. Then, for each character $s\_i$ of $s$, in order, update $S$ to $\bigcup\_{q \in S} \delta(q, s\_i)$. At the end of this process, accept if and only if $S$ contains a final state.

This shows that if $S$ becomes empty at any point during this process, then it will remain empty and the input string will be rejected.

Regarding your second question, 'Design an NFA that starts with "ab"', doesn't mean much. Maybe you wanted to design a NFA that recognizes *all strings that start* with "ab", i.e., those described by the regular expression $ab(a\mid b)^\*$. If that's the case then if you were to remove the self-loop from $q\_2$ you wouldn't be accepting all the needed strings. For example "abb" would be rejected.
> 1 votes

# Answer
Formally speaking, an NFA or DFA never “dies out”: for every state $q$ and for every character $a$ in the input alphabet, there is a state $q'$ such that there is a transition $q \xrightarrow{a} q'$. The state $q'$ is $\delta(q, a)$ where $\delta$ is the transition function in the definition of the automaton. The automaton only stops when it reaches the end of the input.

There is a very common convention when drawing automata to omit one hidden “dead” state $q\_\dagger$ which is not accepting. Any missing transition in the drawing is a transition to $q\_\dagger$, including transitions from $q\_\dagger$ itself. If the automaton enters this state, it remains in this state. Nothing interesting happens once $q\_\dagger$ is reached and we know that the input won't be accepted as soon as it's reached, so it's a dead state (More generally, any state from which it is impossible to reach an accepting state is called a dead state. Merging all the dead states into one doesn't change what language the automaton accepts, so it's common to speak of “the” dead state even though there could be many and some automata don't have one. If an automaton doesn't have a dead state, you can add one without changing the language; that state will be unreachable.)

So, for example, the automaton you drew has 4 states $\\{q\_0, q\_1, q\_2, q\_\dagger\\}$, and has 4 transitions that are not drawn: $q\_0 \xrightarrow{b} q\_\dagger$, $q\_1 \xrightarrow{a} q\_\dagger$, $q\_\dagger \xrightarrow{b} q\_\dagger$ and $q\_\dagger \xrightarrow{a} q\_\dagger$.

Hiding the implicit dead state simplifies the drawing. Making the dead state implicit, rather than defining the transition function as a partial function, simplifies reasoning about automata. It would be possible to define (non)deterministic finite automata with a partial transition function (DFAWAPTF/NFAWAPTF), and their theory would be basically identical to the theory of DFA/NFA, but reasoning would be more complicated since you'd have to have separate cases for $(q,a)$ pairs with a transition and $(q,a)$ pairs without a transition. Since every DFAWAPTF has a matching DFA and NFAWAPTF has a matching NFA, there is no point in reasoning about the WAPTF variants.

The state $q\_2$ does need transitions to itself. If these transitions were not present, then an input such as $aba$ would lead to the sequence of transitions $q\_0 \xrightarrow{a} q\_1 \xrightarrow{b} q\_2 \xrightarrow{a} q\_\dagger$, so $aba$ would not be accepted. Without the transitions from $q\_2$, the automaton would only accept the exact string $ab$, and not any other string starting with $ab$.
> 1 votes

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


# Question
Title: Can someone explain me how the code is working and what is the time complexity?
Can someone explain me how the code is working and what is the time complexity ?

```
def foo(n):
    r = 0
    for i in range(1, n):
        for j in range(i, n):
            for k in range(1, j):
                r += 2
                print(r)

x = int(input("Enter a number : "))
foo(x)

```

# Answer
> 0 votes
It's trivial to see that r is increased at most $n^3$ times. It's slightly less trivial to see that for i = 1 to n/2 the loop for j iterates at least n/2 times, and for n/4 of those iterations k iterates at least n/4 times, which means at least $n^3 / 16$ operations.

---
Tags: data-structures
---


# Question
Title: Why is the communication complexity of f on disjunction of x and y is bounded above by 2D(f)
Let f be a Boolean function on n variables. Let $DC(g)$ and $D(g)$ denote the deterministic communication complexity and the decision tree complexity of $g$. Why is the following inequality true:

$$DC(f(x \land y)) \leq 2 D(f)$$

# Answer
Given a decision tree for $f(z)$, we can simulate it in the communication model in the following way: whenever the decision tree queries $z\_i$, Alice sends $x\_i$ and Bob sends $y\_i$, and now both of them know $x\_i \land y\_i$ and can proceed. We are using two bits of communication per query, hence the bound.
> 2 votes

---
Tags: complexity-theory, communication-complexity
---


title: Complexity of checking graph separation

text:
# Question
Title: Complexity of checking graph separation
Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). There are several ways to check this (via graph connectivity, DFS, brute force search over all paths, etc.).

My question is: *What is the optimal computational complexity of this problem?*

# Answer
The actual complexity might depend on the specific input representation. A reasonable representation uses adjacency lists for the graph and lists the elements in $A$,$B$,and $C$ explicitly in any order.

Assuming this input representation you can solve your problem in linear time and is asymptotically optimal.

Simply add a new vertex $s$ and all edges $(s,a)$ for $a \in A$. Then run a breadth first search from $s$ on the resulting graph while ignoring vertices in $C$ and check whether any of the reached vertices in in $B$. This requires time $O(|V|+|E|)$.

To see that this is optimal notice that you need to spend $\Omega(|V|)$ time even when $G=(\\{1,\dots,n\\}, \\{(1,2), (2,3)\\})$, $A=\\{1\\}$, and $B=\\{3\\}$ since this amounts to checking whether $2 \in C$ and you can have $|C|=\Theta(n)$. You also need to spend $\Omega(|E|)$ time just to decide whether two vertices $a$, $b$ are connected in $G$ when $C=\emptyset$. Indeed if you spend $o(|E|)$ time then there is at least one edge from the input that is not examined and that edge might the only bridge between the connected component containing $a$ and the connected component containing $b$.
> 2 votes

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


# Question
Title: Where is the error in this logic for halting Turing machines?
Let $\mathbb{H}$ be the set of all Turing machines that *halt* on all inputs. Consider the following Turing machine $T$. On input $\langle S \rangle$ where $S \in \mathbb{H}$ (note that the angle brackets indicate a string encoding of $S$), $T$ does the following:

1. Simulate $S$ on $\langle S \rangle$.
2. If $S$ accepts, *reject*. If $S$ rejects, *accept*.

Because $S \in \mathbb{H}$, $S$ will always halt. Thus, $T$ will always halt, which implies $T \in \mathbb{H}$. Note that $T$ decides the language

$$\\{\langle S \rangle \mid \text{$S \in \mathbb{H}$ and $S$ rejects $\langle S \rangle$}\\}.$$

But $T$ accepts $\langle T \rangle$ if and only if $T$ rejects $\langle T \rangle$—this is a contradiction. Where is the error in this logic?

# Answer
> 2 votes
It is false that $T$ decides the language $$L = \\{\langle S \rangle \mid \text{$S \in \mathbb{H}$ and $S$ rejects $\langle S \rangle$}\\}.$$

In particular consider a turing machine $M$ that does not halt on all inputs but halts and rejects on input $\langle M \rangle$. Then $T(\langle M \rangle)$ accepts but $\langle M \rangle$ is not in $L$ since $M \not\in \mathbb{H}$.

# Answer
> 0 votes
I just realized where I went wrong. The Turing machine $T$ that I gave does not actually exist.

In particular, I required that $S \in \mathbb{H}$ for an input $\langle S \rangle$. But this implicitly tasks $T$ with verifying that $S \in \mathbb{H}$ before executing steps 1 and 2. This requires $T$ to solve the halting problem (or some variant of it).

---
Tags: turing-machines, halting-problem
---


# Question
Title: If problem A reduces to an NP-Complete problem B, can we say that A is in NP?
I was reviewing All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

I understand that the general way we show a problem A is in NP is to show there exists a poly-time certifier for A. However, I am confused if say, we know nothing about A, and it reduces to an NP-Complete problem B, can we now say that A is in NP?

I understand that all problems in NP reduce to any NP-Complete problems, but I'm not sure if this will prove anything. I also understand to show a problem is NP-Complete, we first show it's in NP with a poly-time verifier/certificate and then reduce an NP-Complete problem to it. But confused about this other scenario:

Let A be an unknown problem. Let B be a known problem in NP-Complete. A reduces to B What does this tell us about A?

# Answer
Yes (assuming you meant poly-time reductions).

Being in $NP-complete$ is equivalent to being in both classes:

1. NP
2. NP-hard

In particular, $B\in NP$. Now, $A\in NP$ since $A\le\_p B$ and $NP$ is closed under poly-time reductions (you can easily see how to create a non-deterministic poly-time TM for $A$ given the reduction $f$ and a TM for $B$)
> 1 votes

---
Tags: np-complete, reductions, np
---


# Question
Title: Uncomputability of least member selection
I want to show that there is no TM $f$ such that whenever $W\_x$ is nonempty then $f(x)$ is defined and is the least member of $W\_x$, Where $W\_x=\\{w:w \in \Sigma^{\*}\text{ and } M\_x \text{ on }w \text{ Halts}\\}$

Usually when I want to show that such a problem is not member of RE, I use Rice's theorem, diagonalization, the recursion theorem, or I show that if such a problem is computable then $\overline{HP}$ is computable. But I think I did not fully understand this question. *(Edit: Before i read comments i did not know what is the definition of $W\_x$)*

# Answer
According to the comments, The problem is:

> Show that there is no Turing machine $M\_f$ such that if $W\_x \neq \emptyset$, then $M\_f$ halts on $x$ and returns $\min W\_x$

To solve this, We assume $f \in RE$ then we show $HP\in R$ which is a contradiction.

Now we build a TM $HP\_{TM}$ such that $HP\_{TM}(\langle M,w \rangle)=1 \Leftrightarrow M \text{ halts on }w$ and we use $M\_f$ to build that.

$HP\_{TM}(\langle M,w\rangle) = \left\\{ \begin{array}{ll} \text{1- Build a new machine }T (x) = \left\\{\begin{array}{ll} \text{If }(x\geq2)\text{ then ACCEPT}\\ \text{If }(x=1)\text{ then do:}\\ \hspace{14pt} \text{1- Simulate }M\text{ on input }w\\ \hspace{14pt} \text{2- ACCEPT}\\ \end{array}\\ \right.\\ \text{2- Compute }M\_f(T)\\ \text{3- If }M\_f(T)=1\text{ then ACCEPT}\\ \text{4- Otherwise REJECT} \end{array}\right.$

Clearly we can build a TM $T$ in finite amount of time in Stage 1. Observe that $W\_t \neq \emptyset$ and $1 \in W\_t \Leftrightarrow \langle M,w\rangle \in HP$ hence $HP\_{TM}$ decides $HP$ therefore $HP \in R$. We know $HP \notin R$ so this is a contradiction and we can conclude $f\notin RE$.

$\blacksquare$
> 0 votes

---
Tags: computability
---


# Question
Title: Why does this branch data hazard happen during the instruction decode stage?
Suppose I have the following MIPS code on a CPU with forwarding enabled:

```
L1: LW   R2    0(R1)
    ADDI R2    R2    2
    SW   R2    0(R1)
    ADDI R1    R1    8
    SUB  R4    R1    R3
    BNEZ R4    L1

```

The last two lines are of importance for me.

My intuition is that the output to `R4` is calculated during the `EX` stage of the pipeline, and should be ready in time for the `BNEZ` instruction to `EX` in the next cycle. However, I'm getting this output from WinMIPS64:

Why is there a hazard during the `ID` stage? Forwarding is enabled, so it ought to know `R4` will be available at the next stage of the pipeline, when it needs to evaluate if `R4 == 0`, but it still adds a bubble.

What am I missing here?

# Answer
In the MIPS pipeline, for branches and jumps, all of the arithmetic is done in the instruction decode portion of the pipeline. See this MIPS handbook pg. 9, or this handy UCSD ppt. explaining the rationale for this design choice on slide 14.

It used to be the case that all of that stuff would happen during the `EXE` stage, and the program counter would be updated in the `MEM` stage; however, by adding hardware to evaluate those things during the `ID` stage, an incorrect branch prediction only comes with a 1 cycle penalty.

See the difference visualized here:

Evaluating the condition during `EXE` and updating the `PC` during `MEM`:

Vs. Evaluating the condition and updating the `PC`during `ID`

Thus, in my original question, the reason there's a RAW hazard during the `ID` stage is because the `R4` operand isn't ready in time to be evaluated during the `ID` stage. Using the old architecture, the hazard would be avoided, but an incorrect branch prediction would result in a far worse stall.
> 2 votes

---
Tags: computer-architecture, cpu-pipelines, mips
---


# Question
Title: Machines for context-free languages which gain no extra power from nondeterminism
When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.

For the first and last levels1 (regular languages and recursively enumerable languages), it makes no difference to the power of the model whether we consider deterministic or nondeterministic machines, i.e. DFAs are equivalent to NFAs, and DTMs are equivalent to NTMs2.

However for PDAs and LBAs, the situation is different. Deterministic PDAs recognise a strictly smaller set of languages than nondeterministic PDAs. It is also a significant open question whether deterministic LBAs are as powerful as nondeterministic LBAs or not \[1\].

This prompts my question:

> Is there a machine model that characterises the context-free languages, but for which non-determinism adds no extra power? (If not, is there some property of CFLs which suggests a reason for this?)

It seems unlikely (to me) that it would be provable that context-free languages somehow *need* nondeterminism, but there doesn't seem to be a (known) machine model for which deterministic machines are sufficient.

The extension question is the same, but for context-sensitive languages.

**References**

1. S.-Y. Kuroda, "Classes of Languages and Linear Bound Automata", Information and Control, 7:207-223, 1964.

**Footnotes**

1. Side question for the comments, is there a reason for the levels (ordered by set inclusion) of the Chomsky hierarchy to be number 3 to 0, instead of 0 to 3?
2. To be clear, I'm talking about the languages that can be recognised only. Obviously questions of complexity are radically affected by such a change.

# Answer
> 1 votes
A nondeterministic machine leaves choice points open: points at which multiple continuations can be taken.

Two ways to 'determinize' this:

* backtracking: follow the tree of possibilities in depth-first order
* GLR: follow all branches at once, in parallel, breadth-first order

The resulting parsers are deterministic; they can be defined as automata. Do they satisfy your request? If not, why not?

# Answer
> 0 votes
As far as I know, we do not know whether Non- deterministic context-sensitive languages are more powerful than deterministic context-sensitive languages. And the simplest reason behind this is: Till now no-one has been able to give a language that is accepted by the non-deterministic LBA and not accepted by the deterministic LBA. So if someone can come up with one such language that is accepted by ND LBA and not accepted by deterministic LBA then only this will be proven. As we know this method of proving is called proof by contradiction. Because proving something is TRUE is a hard problem but proving something FALSE is easy, just get one instance where it fails and we're done.

# Answer
> -2 votes
In my understanding of theory of computation, the only situation non-determinism  **does not**  give you extra flexibility (i.e,.. power) is at the recursively enumerable/ recursive level. This is primarily because of the halting problem and it's limitations on the TM's capabilities in decidability, which I believe this answers one of your questions in the foot notes as well as a sidebar. The Chomsky Hierarchy is a logical representation of moving up the *flexibility* latter (if I might say), allowing more power to the machine. Does this help any with your question/thoughts?

As far as the PDA's and LBA's I will have the other accomplished folks here in the community help with that, my experience has been more with TM's and the theory associated with the higher (more RE) part of the hierarchy (at least as taught in my undergrad).

Peter Linz theory of computation

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd\_sbs\_14\_img\_0?\_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4

---
Tags: formal-languages, computability, context-free, computation-models, context-sensitive
---


# Question
Title: What is the space-complexity of the Newton-Raphson algorithm?
What's the space-complexity of Newton-Raphson? I think it reduces to the space-complexity of storing the inverse hessian matrix.

# Answer
No, it reduces to the space complexity of *solving* a linear system using the Hessian matrix.

As with all situations where you need to solve a linear system, computing and storing the inverse explicitly is a bad idea for any problem larger than about 4 by 4. The inverse of a matrix is usually not as well-conditioned as the matrix itself, the inverse of a sparse matrix is typically not sparse... all the usual reasons apply.
> 2 votes

---
Tags: space-complexity, matrices
---


# Question
Title: Is this a valid encoding of a tree structure using set theory and a valid way to extract the leaves from it?
I'm looking to formally define a tree and then extract the leaves from it in a concise way. Does this look ok? What is the best way of doing this?

$ Y = \\{a,b,c,d,e,f,g\\} \\ R = \\{a \mapsto b, a \mapsto d, d \mapsto e, d \mapsto f, f \mapsto g\\} \ \text{, where R is a relation on Y.} \\ R^+ = \\{a \mapsto b, a \mapsto d, d \mapsto e, d \mapsto f, a \mapsto e, a \mapsto f, a \mapsto g\\} \ \text{, where $R^+$ is the transitive closure of R.} \\ leaves = \\{x \in range(R^+) \mid \ x \notin dom(R^+) \\} $

# Answer
> 2 votes
How about this: $leaves = Y \setminus Preimage(R)$

---
Tags: trees, sets, transitivity
---


# Question
Title: Find a transducer that maps a given deterministic process to another
Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, the description is given through the $n\times n$ transition matrices $T^{(a)}$ with elements $T^{(a)}\_{ij}=Pr(s\_{t+1}=j,A\_t=a|s\_t=i)$, which encode the probability of being in state $i$ and upon emitting symbol $a$ transitioning to state $j$. For example the process for generating the sequence $...010101010101..$ would have the representation $$ T^{(0)}=\begin{pmatrix} 0 & 1 \\ 0 & 0 \\ \end{pmatrix}\\,,\\, \\, T^{(1)}=\begin{pmatrix} 0 & 0 \\ 1 & 0 \\ \end{pmatrix} $$

One can also construct deterministic transducers, that is, input-dependent Hidden Markov Models that take a deterministic process to another deterministic process. The description is similarly given through input-dependent transition matrices $T^{(b|a)}$, with elements $T^{(b|a)}\_{ij}=Pr(s\_{t+1}=j,B\_t=a|s\_t=i,A\_t=a)$. For example, a deterministic transducer with two states and input and output alphabets $\\{0,1\\}$ that either performs the identity or a bit flip could be represented as $$ T^{(0|0)}=\begin{pmatrix} 1 & 0 \\ 0 & 0 \\ \end{pmatrix}\\,,\\, \\, T^{(1|0)}=\begin{pmatrix} 0 & 0 \\ 0 & 1 \\ \end{pmatrix} \\,,\\, \\, T^{(0|1)}=\begin{pmatrix} 0 & 0 \\ 1 & 0 \\ \end{pmatrix} \\,,\\, \\, T^{(1|1)}=\begin{pmatrix} 0 & 1 \\ 0 & 0 \\ \end{pmatrix} $$ and would map the previous defined process of alternating zero and one to the process that generates $...001100110011...$. This process' description would be $$ \hat{P}^{(0)}=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ \end{pmatrix} \\, \\,\\, \hat{P}^{(1)}=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix} $$ After these definitions and example, I am ready to state my questions.

**Question 1:** Given two known processes $S$ and $P$ how can one find a transducer that maps one to the other (in general there is no unique solution). More importantly, is there a way to construct a transducer with minimal amount of hidden states? Is there an algorithm to do any of these two tasks?

**Question 2:** Given a representation of process $S$ with a HMM with $n$ states, how can one find the representation that has minimal number of states? In other words, is there an algorithm that takes a process with $n$ states and generates another with $m$, such that $m\leq n$ and equality if and only if the original representation of the process is already minimal?

PS: I do not have a formal background in CS but only maths, so please forgive me if my notation is weird and I am lacking in knowledge of basic results.

# Answer
Your processes are just deterministic finite-state transducers.

Question 1: It sounds like you are asking, given two deterministc finite-state transducers $S,P$, can we find a deterministic finite-state transducer so that $S \circ T = P$.

Question 2: You seem to be asking if we can minimize a deterministic finite-state transducer.

I don't know the answer to either of these questions -- they are very reasonable questions -- but hopefully this gives you some terminology you can search for.

Regarding Question 1, I believe you can find a non-deterministic finite-state transducer $T$ such that $S \circ T = P$. Basically, you use the product composition; $T$ tracks the sequence of states traversed by $S$, and simultaneously guesses the sequence of states traversed by $P$. Maybe you could construct such a non-deterministic transducer, then check whether it can be determinized.

Regarding Question 2, Wikipedia claims that transducers can be minimized and gives a reference.
> 1 votes

---
Tags: formal-languages, automata, finite-automata, hidden-markov-models, transducers
---


# Question
Title: Regular expression vs rational expression
Let $M$ be a monoid (e.g. $M = \Sigma^\*$) and $L \subseteq M$.

Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows:

* $|L| \< \infty \implies L \in \mathsf{RAT}(M)$
* $L\_1, L\_2 \in \mathsf{RAT}(M) \implies L\_1 \cup L\_2 \in \mathsf{RAT}(M)$
* $L\_1, L\_2 \in \mathsf{RAT}(M) \implies L\_1 \cdot L\_2 \in \mathsf{RAT}(M)$
* $L \in \mathsf{RAT}(M) \implies L^\ast = \bigcup\_{i \geq 0} L^i \in \mathsf{RAT}(M)$ with $L^0=\\{1\_m\\}$ and $L^{i+1} = L^iL$

And in my understanding, a rational expression is then an expression using only the operations in this definition, i.e. $$L\_1 \cup L\_2 \cup L\_3L\_4 \cup L\_3^\*$$.

On the other hand we have the definition of regular languages where $\mathsf{REG(M)}$ is the set of regular sets inductivly defined as follows:

* $\emptyset$ is a regular expression
* $\epsilon $ is a regular expression
* $a \in \Sigma$ is a regular expression
* if $\alpha$ and $\beta$ are regular expressions, then $\alpha\mid\beta$ is a regular expression
* $\alpha^\*$ and $\alpha\beta$ are regular expressions

Futhermore we know that regular languages are closed under complement unlike rational languages.

**Question:** It is often stated that regular expressions are the same as rational expressions. But hence this defintion of a rational expression doesn't allow for example "the decision"-operator, ($a \mid b$), it seems that regular expressions cover more than rational ones. What am I missing out? Are they really the same and if not, where are they distinct?

# Answer
> 1 votes
A late but detailed answer.

First of all, the term *regular* is one of the most overloaded term in mathematics (see the impressive list Regular/Mathematics on Wikipedia). In particular, if you ask for the definition of a regular language to a computer scientist, some people will say that it is a language recognised by a finite automaton and some other people will say that is a language defined by a regular expression.

This is fine as long as you talk about languages since Kleene theorem tells you that the two definitions are equivalent. This is another story when you deal with abstract monoids (not necessarily free!). As you recalled in your answer, the set of rational subsets of a monoid $M$ is the smallest set of subsets of $M$ containing the singletons and closed under finite union, product and star (where $L^\*$ is the submonoid of $M$ generated by $L$). But there is also another definition, which can be seen as an abstract version of recognition by a finite device:

**Definition**. A subset $L$ of $M$ is *recognizable* if there exist a finite monoid $F$, a surjective monoid morphism $f\colon M \rightarrow F$ and a subset $P$ of $F$ such that $L = f^{-1}(P)$.

Unfortunately, Kleene's theorem does not extend to arbitrary monoids, that is, rational and recognizable are not in general equivalent notions. For instance, I let you verify that $\\{0\\}$ is a rational subset of the additive monoid $\Bbb{Z}$ but is not recognisable. Thus it would be highly confusing to use the term *regular* in the context of monoids and I strongly recommend against it.

Just for the record, let me mention a weaker property, that holds for finitely generated monoids.

**Theorem** \[McKnight 1964\] Let $M$ be a monoid. The following conditions are equivalent:

1. $M$ is finitely generated,
2. every recognizable subset of $M$ is rational,
3. the set $M$ is a rational subset of $M$.

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


title: Words in computer's memory

text:
# Question
Title: Words in computer's memory
I don't know much about memory. Here are some lines from CLRS:

The words in a computer memory are typically addressed by integers from 0 to $M - 1$, where $M$ is a suitably large integer. In many programming languages, an object occupies a contiguous set of locations in the computer memory. A pointer is simply the address of the first memory location of the object, and we can address other memory locations within the object by adding an offset to the pointer.

Now, what does 'word' mean here? Does it mean a finite sequence of characters from the keyboard? If yes then I know that we can set $M = 256$ so that ASCII would cover all these characters but then the problem is that $M$ wouldn't be that large as it should be and also it should have been said 'letters in a computer memory', not 'words in a computer memory'.

# Answer
> 2 votes
No, it refers to a word in a computing sense. Here, a word is just a unit of data, whatever is natural for a particular processor. For instance, an x86-64 processor, which I'm currently using, has a word size of 64 bits. So a single word in this case consists of 64 bits.

---
Tags: memory-access, memory-allocation
---


# Question
Title: Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
I was asked to give an example of a graph that has edges with negative weight, but Dijkstra's algorithm will still give us the correct output. It was part of a prove/disprove question. The claim was.. *"If a graph has negative edges, Dijkstra's algorithm will return the wrong output"*.

# Answer
> -1 votes
Suppose graph $G$ is directed, and acyclic such that just some of edges of source $s$ have negative weight, hence Dijkstra's algorithm does work in a such case.

# Answer
> 39 votes
Take a look at the simplest possible example: Our graph has only two nodes: $s,t$, and a single edge between them.

In this example, it won't matter what is the cost of this single edge (it can be negative), and Djikstra will always return the only single path between $s$ and $t$: which is directly $s\rightarrow t$.

# Answer
> 4 votes
Yet another way to prove the existence is to take any graph G, and replace one edge E with weight W by two new edges and an intermediate node N. Let the first new edge have weight -W/2 and the other new edge +3W/2.

Any path through these two new edges will still have a contribution W from the two edges together . You still need to prove that Dijkstra works for paths that begin or end in the new node N, but that's fairly straightforward.

# Answer
> 4 votes
Dijkstra's algorithm sometimes works when there are negative weights, and sometimes not, others have given several examples. Allow me to give a few ideas that may make it easier to find an example on your own.

Dijkstra's algorithm *never* works when there is a negative weight cycle. If a graph has negative weights, but no negative weight cycles, it is possible to modify the graph into a graph where Dijkstra can be applied and the results transformed to find shortest paths in the original graph. One such technique is known as Johnson's algorithm. I think this fact makes it more intuitive that negative weights are not an essential problem for Dijkstra's algorithm, and so we should expect some examples where it just works.

# Answer
> 2 votes
One other setting where Dijkstra will always work is where the only negative edges in the graph are ones leaving the start node $s$ and there are no other edges leaving $s$. The idea is that the algorithm can’t be “surprised” by finding a path whose cost drops as more edges are added in. It’s a great exercise to prove that this indeed is the case; it’s basically a generalization of the regular proof of correctness for Dijkstra’s algorithm.

(This generalizes the excellent answer by @nir shahar.)

---
Tags: graphs, dijkstras-algorithm
---


# Question
Title: Does padding with dummy bits allow an NP-problem to be solved in fast exponential time?
Take this example mentioned here: NP-hard problems with very fast exponential-time algorithms

> We can create such problem by padding assuming ETH. Take an NP-complete problem $L$ such that $L$ is decidable in time $O(2^n)$, by padding $L$ with some dummy 1's, create $L'=\\{1^{n−(\log\_21.01)n}x:|x|=(\log\_21.01)n∧x∈L\\}$. it is easy to prove that $L'$ is complete for NP and the running time of $L'$ is exactly $O(1.01^n)$.

Because I'm a newbie in mathematics and computer science, I don't quite understand this answer. Does it mean that padding an NP-problem that can be solved in $O(2^n)$ with a string of dummies 1, we can construct a new variant of the original problem that can be solved in fast exponential time $O(1.01^n)$?

As an additional question: can I apply this technique to Levin's universal search (http://www.scholarpedia.org/article/Universal\_search)?

# Answer
> 3 votes
Here is a more extreme example: $$ \mathrm{SAT\_{PAD}} = \\{1^{2^n} 0 \phi : \text{$\phi$ is a satisfiable CNF on $n$ variables}\\}. $$ This language is decidable in polynomial time.

What padding accomplishes is it constructs a language in a lower complexity class; it doesn't actually help you solve the original problem. All it does is artificially modify the parameter $n$.

Running an algorithm for $L$ on the language $L'$ results in a running time which is $O(1.01^n)$, where $n$ is the size of the *padded instance*; the running time is still $O(2^n)$ in terms of the size of the original instance.

I don't see any relevance to universal search. The main application of padding is to relate results about different complexity classes. For example, if P=NP then EXP=NEXP, since given any language in NEXP, you can pad it so that it is in NP, use the assumption to deduce that the padded language is in P, and then interpret the corresponding algorithm as proving that the original language is in EXP.

---
Tags: np-complete, search-problem
---


# Question
Title: Maximum number of cliques of size $\ge 2$ of a graph with exactly $m$ edges
Let $G=(V,E)$ be an undirected graph with $|E|=m$ edges.

Given that any clique of size $\ge 2$ can be identified with its corresponding edges, and at most every subset $S\subseteq E$ creates a clique, $G$ can have at most $|P(E)|= 2^m$ cliques of size $\ge 2$.

However, based on the intuition that it's better to arrange the edges into bigger cliques, I'd assume arranging the $m$ edges into one big clique of size $c$ is optimal (whenever it's possible). If $c$ is the size of that clique, we have $m=\binom{c}2 \rightarrow c\le 4\sqrt m$, and I'd therefore assume that one can get an upper bound of the form $2^{4\sqrt m}$.

How would one show this upper bound?

Noting in above simple proof that only subsets $S$ with size $\left|S\right|=\binom{i}2$ for some $i\in \mathbb N$ can ever be edge sets of a clique doesn't seem to help.

# Answer
> 2 votes
In this paper with DOI 10.1007/s00373-007-0738-8 we have the following theorem:

> Let $n$ and $m$ be non-negative integers such that $m ≤ \binom n2$. Let $d$ and $l$ be the unique integers such that $m =\binom d2+l$, where $d ≥ 1$ and $0 ≤ l ≤ d − 1$.
> Then the maximum number of cliques in an $(n, m)$-graph equals $ 2^d + 2^l + n − d − 1$.

Here, an $(n,m)$-graph is a graph with $n$ nodes and $m$ edges.

This graph has $n$ 1-cliques and $1$ 0-clique.

Therefore its number of cliques of size $\ge 2$ is $$ 2^d + 2^l − d − 2 \le 2^{d+1} − d − 2\le 2^{d+1} $$ and $d$ is the biggest integer with $m\ge \binom{d}2$.

So we further have $$ d\le \frac{\sqrt{8·m+1}+1}2 $$

Assuming $m\ge 1$, we have $$ \frac{\sqrt{8·m+1}+1}2\le \frac{\sqrt{9m}+1}2 = \frac{3\sqrt m+1}2\le 2\sqrt m $$

And with that, we get that the number of cliques of size $\ge 2$ is upper bounded by $$ 2^{2\sqrt m+1}=2\cdot 4^\sqrt m $$

---
Tags: clique, upper-bound
---


# Question
Title: Importance of study of mathematics in algorithm design and other computer science fields
I am looking for a discussion state that, why study of mathematics in designing algorithms, and find out efficient solution for algorithmic problems is so important?

# Answer
Take a look at my answer here.

Basically, the different areas of math are used in different areas of computer science as well.

Specifically for algorithms, for example, knowing probability theory can help with defining and designing probability-based algorithms - which have a potential to be more efficient than regular old deterministic ones.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Predicting continuous variables using image and text input to neural network
I am looking to create a neural network architecture that takes two kinds of inputs: image and text, and outputs a predicted continuous variable. More specifically, I will have multiple images of a house as an input alongside numerical/text data like square meters, number of beds, baths, carspaces, latitude, longitude, features etc. I want to use this to output the predicted price value of the given house.

I understand you can combine image and text inputs as seen here:

Could I use a similar model for the situation I described? If so, what kind of neural network architecture should I use for the image and numeric/text input streams, and how would I combine them?

# Answer
> 1 votes
Yes, that is a reasonable architecture. You could use any architecture for processing images, and have it output a representation of the image (take any classification architecture, and remove the last layer). You could also use any architecture for text, and have it output a representation of the text. Finally, for other inputs, you could use a fully connected architecture. Then, concatenate those representations and run them through another fully connected network. That would be a reasonable architecture to try.

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


# Question
Title: Will we ever move towards 128 bit architecture?
Will the IBM PC ever move towards 128 bit architecture? Is that even possible or is the 64 bit architecture we have now the ceiling?

# Answer
> 6 votes
> Will the IBM PC ever move towards 128 bit architecture? Is that even possible or is the 64 bit architecture we have now the ceiling?

Those are really two completely separate questions, so I am going to answer them separately.

> Is that even possible or is the 64 bit architecture we have now the ceiling?

That really depends on how you define "IBM PC". The IBM PC is a 16 bit architecture, and has been dead since the early 1990s. So, technically speaking, no, you can't have a 128 bit IBM PC, because the IBM PC is 16 bit, and if it were 128 bit, then it wouldn't be an IBM PC anymore.

However, there is nothing stopping anyone from doing what Intel did when they introduced the IA-32 architecture by extending the x86 architecture from 16 bit to 32 bit, or what AMD did when they introduced the AMD64 architecture by extending the IA-32 architecture from 32 bit to 64 bit.

There is also nothing stopping anybody from introducing a 65 bit or 96 bit or 512 bit architecture.

So, yes, it is definitely possible to design an architecture that is a careful extension of the current mainstream AMD64-based "PC successor" architecture. It wouldn't be an IBM PC, though, just like what we had since the 1990s weren't IBM PCs either.

> Will the IBM PC ever move towards 128 bit architecture?

"ever" is a really long time, but I doubt it.

The current (and all currently known future planned) implementations of the AMD64 architecture, regardless of whether they are being designed and manufactured by Intel, by AMD, or someone else, are limited to a virtual address space of 48 bit and a physical address space of 48 bit. This means that the limit for both virtual memory and physical memory is 256 TiByte. However, there are currently no known or planned motherboards or chipsets that support even close to that amount of memory. (Also, I believe that while current CPUs support 48 bit physical addresses, they typically do not actually have 48 address pins, so the actual maximum is even lower.)

The virtual address space can theoretically be extended up to the full amount of 64 bit. The physical address space is limited by the page table format to 52 bit (4 PiByte).

So, a more conservative first step before we move to 128 bit would be to redesign the page table format such that the full 64 bit can be used.

At the moment, the 48 bit limitation does not seem to be a problem, even remotely. But even if we assume that we are going to run out of 48 bit address space tomorrow, and that address space requirements will grow similar to Moore's Law, doubling every 1.5–2.5 years, it will take another 20–40 years until we run out of 64 bit address space.

The largest supercomputer in the world, Fugaku consists of 158976 compute nodes. Each node has 32 GiByte of RAM, for a total of 4.85 PiByte. Each group of 16 nodes has a 1.6 TByte SSD as level 1 storage, for a total of 15.53 PByte. Plus, there is a shared 150 PByte cluster filesystem (Lustre) for the whole cluster.

So, the total amount of storage of the largest computer in the world currently is about 171.4 PByte or 152.2 PiByte, which could be byte-addressed with 57.24 bits, and even if you want to address every single individual bit, you would only need 60.24 bits. So, even if we assume that all supercomputers are this big, 64 bit would still be enough to address every single individual bit of the total combined storage of the TOP 10 supercomputers in the world. But note that this is the total sum of storage (not just RAM, but hard disk and network filesystem) in the entire cluster (not just each node), and that we normally address bytes, not bits.

In reality, there is not a single OS kernel running on the entire cluster that needs to address all that storage, each of the 158976 nodes is running its own OS kernel, and only needs to address its 32 GiByte of local RAM.

There is a general trend in the industry, where computers aren't getting "bigger" but are instead getting "more". For example, the total amount of RAM in my home has grown by a factor of 200 over the last 20 years, but 20 years ago, it was all in my desktop, and now it is distributed among my two laptops, two phones, two tablets, router, and NAS, so even my "largest" computer only has about 50 times as much RAM as my old desktop. (I am cheating a bit because I also use cloud services heavily, but those are actually also not a big computer but hundreds of thousands of medium sized ones, each with their own individual address space.)

The clock frequency per core in the current top supercomputers is only about 10 times that from 2000. The memory per node is about 10–50 times that from 2000. (For example, the top supercomputer in 2000, ASCI White, had 12 GiByte per node, Fugaku has 32 GiByte per node, so only less than 3 times the amount of RAM.) But the number of cores is about 1000–10000 times that of 2000! Each Fugaku node has 48 cores, meaning Fugaku has 7.6 *million* custom ARM64 cores. The supercomputer with the most number of cores in the TOP 10 supercomputers of November, 2000 has 9632 cores (interestingly, that one is not the fastest), and there are even two supercomputers in the TOP 10 from November, 2000 that only have 100 and 112 cores (and again, interestingly, they are not the slowest).

So, in 20 years, the physical address space requirements for the world's top supercomputer have only grown by less than 1.5 bit from 33.6 bit for 12 GiByte to 35 bit for 32 GiByte.

The thing is, humans are very bad at understanding exponential growth and tend to severely underestimate it. When Intel moved from 8 bit to 16 bit, they didn't double the address space, they increased it by a factor of 256. When Intel moved from 16 bit to 32 bit, they didn't double the address space, they increased it by a factor of 65536. When AMD moved from 32 bit to 64 bit, they didn't double the address space, they increased it by a factor of over 4 billion.

So, I personally doubt that we will ever see a 128 bit architecture. We *might* see more than 64 bit someday, but I believe it is more likely to be an 80 bit or 96 bit architecture than 128 bit.

Note that this does not mean that there might not be "labels" that need more than 64 bit. For example, IPv6 addresses are 128 bit. The IBM AS/400 (which still exists to this day as IBM i, after many name changes) had 128 bit object labels even back in the 1980s, but these contain not just a memory address but also type information, ownership information, access rights, bookkeeping data, etc. The actual CPU architecture, however, was never 128 bit. It was originally a custom 48 bit CISC architecture specially designed for the AS/400, which was later replaced with a slightly extended 64 bit PowerPC architecture and has now been merged into the POWER architecture.

While I believe it is possible that we might see bigger-than-64 bit architectures in the future, I seriously doubt that we will see another big change to the "PC successor" architecture. All current mainstream Operating Systems are highly portable (for example, Linux runs on a dozen architectures or more, both macOS and Windows NT run on AMD64 and ARM64, and have run on even more architectures in the past, e.g. macOS on PowerPC and m68k, Windows NT on Sparc, PowerPC, MIPS, Alpha, and i860). Which means that Operating Systems aren't really tightly tied to a specific architecture anymore. And the rise of platforms such as Java and .NET, the rise of high-level languages like, well, pretty much every language except C, C++, and (maybe) Rust, the rise of Web Applications and the Cloud mean that switching architectures is rather painless. (And actually, a lot of modern C and C++ code tends to be rather high-level and mostly platform-independent as well.)

Even for native code that we have lost the source for, modern emulation and re-engineering technologies make it possible to move them to a new architecture. Heck, I am writing this very answer from an ARM64 laptop that executes native AMD64 code in emulation almost as fast, sometimes even faster than my twice as expensive AMD64 laptop!

So, it simply does not make sense to keep piling band-aid after band-aid on a 1970s architecture, when we could just as easily design a 2030s architecture instead.

# Answer
> 4 votes
My CPU has 128 bit registers. Yours probably does too. The overwhelmingly most common use is to store lots of smaller values (e.g. two 64-bit values or four 32-bit values).

My CPU also does not support a 64-bit *physical* address space (more like 48 bits, IIRC). It does support a full 64-bit *virtual* address space, although half of that is reserved for the operating system.

Forever is a long time, however for the foreseeable future (say, the next few decades at least), it doesn't look like 128 bit addressing of memory will of any practical benefit.

64-bit values seem to be a "sweet spot" for a lot of real-world-sized values. Take money as an example. About 54 bits is enough to store the amount of M3 money in the world measured in Japanese Yen.

Or take time. At the moment, it seems impractical for consumer hardware to measure times smaller than a nanosecond, because light travels about 300mm (11.8in) in one nanosecond, and this roughly the scale of a consumer device. A 32-bit integer can record measurements of about 4.3 seconds in nanoseconds, but a 64-bit integer can record measurements of over 500 years, which is probably a reasonable upper bound on how long a computer can be left on without rebooting.

Nonetheless, 128 bit arithmetic, both integer and floating point (most logic operations are already supported), are probably coming in a few iterations. Internal busses are already wide enough to support the 128-bit and 256-bit registers that are common today.

While 128-bit integer operations are already quite fast on modern superscalar CPUs, there are applications that would benefit from 128-bit floating point, even if only for use in intermediate values or for evaluating special functions to 64-bit precision.

---
Tags: computer-architecture
---


# Question
Title: Given a string which was produced by mixing up a string of digits, find the original digits
I encountered the following problem:

> Given a string which was produced by mixing up a string of digits (0-9), for example: "otetwonhree" was produced by "onetwothree"~123, find the original digits (without importance of order). in our example we would return "123". Another example: "oneoneeon", we return "111".

My question is, is there necessarily a unique way to interpret such a string? meaning, could there be a string with 2 different correct interpretations? I feel like it is complicated to show that (if we know that there isn't such a string, then the solution is easy, otherwise the problem doesn't really have a solution).

More generally, given some codes $\sigma\_1, ..., \sigma\_n$ instead of digits, each has a unique fitting string of letters, could we decide if any string which was created similarly as in the original problem, has a unique interpretation? It's easy to find some codes for which the answer would be no, which is why I find this problem also difficult.

I'll mention I haven't studied any computability courses yet so I am mainly looking for an answer rather than a full solution (but feel free to post such if it is of any interest to anyone else), this problem just made me curious. If there is a solution which could be somewhat understood with only basic algorithms background I wouldn't mind that.

# Answer
> 4 votes
The solution to this problem is linear algebra, rather than algorithms. The same apprach works for your example as for the general case.

The letters in the garbled message come from the number of times a code was used. In a forward way: if the code for "7" occurs $x\_7$ times we have $2x\_7$ e's, and $x\_7$ n, s, v each.

For decoding we in reverse try to determine the number $x\_i$ of times that code for "i" is present, for each $i=0,1,\dots,9$.

As an example, the total number of e's in the message equals $\\#e = x\_0+x\_1+2x\_3+2x\_7+x\_8+x\_9$. The number of f's equals $\\#f = x\_4+x\_5$.

I will not do this for every symbol, but after doing this we get a system of equations from which the numbers $x\_0,\dots,x\_9$ can be determined (if the system has no dependencies). Note that for some letters we might be lucky, like $\\#z = x\_0$.

---
Tags: algorithms, computability
---


title: Minimal element in logarithmic time

text:
# Question
Title: Minimal element in logarithmic time
Suppose $A$ is an array of distinct natural numbers. We call an element $A\[i\]$ minimal if it's less than both the element before and after it (if any). Present a worst-case $O(\log n)$ algorithm for finding a minimal element. I wanted to find the minimum (since it's less than all the elements) and then use binary search with it as a key but you can't find minimum in logarithmic time. My other idea was to categorize the elements into three-element groups but it doesn't work as well. We should probably solve this question with divide and conquer approach.

# Answer
You can do a "sort-of" binary search to find such an item.

* When $A\[i\]\le A\[i-1\]$, go "forward" in the search (increment the left pointer)
* When $A\[i\] \> A\[i-1\]$, go "backward" in the search (decrement the right pointer)
> 1 votes

# Answer
Your problem is equivalent to **1D Peak Finding**, check this link, that use binary search approach to find a peak (if exists).

Note that, in your idea, because of you search for minimum element, the running time will be $\Omega(n)$, but you can solve your problem in $\mathcal{O}(\log n)$.
> 0 votes

---
Tags: divide-and-conquer
---


title: A problem about $2-SAT$

text:
# Question
Title: A problem about $2-SAT$
My algorithm $n$ times checking that $n$ clauses with $2$ variable, are satisfiable or not? (i.e. $n$ times my algorithm check $2-SAT$ Problem with different variable) that each time $2-SAT$ need's $O(n)$, so the running time will be $O(n^2)$. Are there a hint or idea such that prohibit my algorithm from doing repeated work?

# Answer
> 1 votes
You have $n$ instances of $2-SAT$, each with size of $m$.

You have a total of $n\cdot m$ symbols, and you will *have* to at least read all of them (to solve a particular $2-SAT$ instance you need to read the entire $2-SAT$ formula).

Hence you need at least $\Omega(n\cdot m)$.

---
Tags: algorithms
---


title: Is any sudoku solver an SAT solver?

text:
# Question
Title: Is any sudoku solver an SAT solver?
I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning this is true if column 1, row 1 is filled by 1). The method I have done this does not take in a large clause of variables, but *implicitly* solves a large proposition (which can be generated) for each puzzle.

Due to the lack of universality, that it can't take in any clause for any other np-complete puzzle, does this still count as an SAT solver? And are there multiple ways of reducing sudoku into SAT (i.e. could you have many different ways of having that large proposition)?

Edit: the way I have created the sudoku solver is by representing each cell by 9 variables, which are classes in the solution. The program converts the user's input into a Boolean proposition made specifically for sudoku (i.e. obeying all sudoku constraints). It then solves the proposition. Due to the fact that sudoku has been reduced to SAT and solved, I'm wondering if the program counts as an SAT solver (to which I believe the answer is no, because it won't take any propositional formula and solve it). However, I also want to know of the 'uniqueness' of sudoku is in a way lost when converted to SAT, because 'real' sudoku problems only have one solution, but as far as I know, SAT only wants to know if there is a possible solution or not.

# Answer
Your program is not a SAT solver. A SAT solver takes as input a SAT formula and outputs whether it is satisfiable or not. Your program doesn't take as input a SAT formula, so it isn't a SAT solver.

Yes, there are multiple ways of reducing Sudoku to SAT.

With standard Sudoku puzzles, we are promised that there exists exactly one valid solution. With SAT, there might be 0, 1, 2, or more satisfying assignments, and we are asked to determine whether there exists 0 satisfying assignments or 1+ satisfying assignments. Valiant and Vazirani considered the following problem: given a SAT formula with the promise that it has either 0 or 1 satisfying assignments (not more than 1), determine whether it has 0 satisfying assignments or 1 satisfying assignments. They showed a randomized polynomial-time reduction showing that this problem is at least as hard as SAT (specifically, there is no polynomial-time algorithm for this problem either, unless NP=RP).

More generally, we could ask about the following problem: given a SAT formula with a promise that it has exactly 1 satisfying assignment, find the satisfying assignment. This problem is the analogue of Sudoku (where we're given a Sudoku puzzle with the promise that it has exactly 1 valid solution, and we're asked to find that solution). It follows from Valiant and Vazirani's result that this problem is at least as hard as SAT under randomized polynomial-time reductions; if you could solve this problem in polynomial time, you could solve SAT in (randomized) polynomial time. So, the promise that a SAT formula has exactly 1 valid solution doesn't make it any easier to find the solution.

Further reading: UniqueSAT and UnambigousSAT at https://en.wikipedia.org/wiki/Boolean\_satisfiability\_problem#Extensions\_of\_SAT, https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani\_theorem, https://cstheory.stackexchange.com/q/1639/5038, Unique SAT complexity clarification, Proof of SAT is randomly reducible to UNIQUE-SAT, https://cstheory.stackexchange.com/q/22093/5038.
> 4 votes

# Answer
Its assumed you implemented a generalized Sudoku solver and not a 9x9 one. First you will need a parsimonious 1-to-1 reduction from 3SAT (SAT to 3SAT is easy) to Sudoku. This is because your sudoku solver may use assumptions of a unique solution. This leads into the another solution problem (ASP) but parsimoniety covers this. There are known reductions from 3SAT to the triangulation problem or finding a tripartite graph division problem. Latin squares also directly reduce to the tripartite graph problem. From there you can map from the Latin square problem to Sudoku with a careful mapping. I suggest seeking out the already published results in this area.

I've never seen a tool which takes a unique SAT equation and generates a Sudoku instance whose unique solution represents the original unique SAT. Note we are talking about the generalized sudoku so the grid could presumably be very large, likely absurdly and impractically large. Going from Sudoku to SAT is easier and many resources are available for this direction yet by the sheer large size of the constant in the polynomial reduction in both directions, likely much larger from SAT to Sudoku unless a very efficient, even more so than what is known is used to convert the Latin square to Sudoku process is used. Just consider reasonable 9x9 SAT instances of classic sudoku have hundreds of variables and thousands of clauses. So the other direction is probably incomprehensibly big and visualizing it would be mere novelty.
> 1 votes

---
Tags: reductions, satisfiability, boolean-algebra, sat-solvers, sudoku
---


# Question
Title: If a computer can demonstrate singleton sets are closed, is the space Hausdorff?
In Haskell, I made a class of admissible (that is, second-countable and $T\_0$) spaces:

```
{-# LANGUAGE TypeFamilies #-}

class Admissible a where
    type BasisElem a -- Type of a basis element
    semidecide :: a -> BasisElem a -> [Bool] -- Semidecides whether an element is in a basis element
    countFirst :: a -> [BasisElem a] -- Computes a countable basis at an element
    countSecond :: a -> [BasisElem a] -- Computes a countable basis (the parameter is dummy)
    countDense :: [a] -- Computes a countable dense subset

```

`semidecide` outputs a list having a `True` if and only if the element is in the basis element. Generally, it is not a decider; the output may be an infinite list of `False`s.

I tried to make a class of Fréchet ($T\_1$) spaces and a class of Hausdorff ($T\_2$) spaces. The sketch was:

```
class Admissible a => Frechet a where
    frechet :: a -> [BasisElem a]

class Frechet a => Hausdorff a where
    hausdorff :: a -> a -> [Bool]

```

`frechet` outputs the open set whose complement is the singleton set of given element.

`hausdorff` semidecides the inequality $≠$.

But apparently, if `frechet` is present, `hausdorff` is redundant? Like this:

```
weaveOmegaSq :: [[a]] -> [a]
weaveOmegaSq = go 1
  where
    go n xss = let
        partitioned = do
            (us, vs) <- fmap (splitAt n) xss
            [us, vs]
        in case partitioned of
            [] -> []
            xs:yss -> xs ++ go (1 + n) (go2 yss)
    go2 [] = []
    go2 [xs] = [xs]
    go2 (xs:ys:xss) = (ys ++ xs) : go2 xss

hausdorff x y = weaveOmegaSq (fmap (semidecide x) (frechet y))

```

`weaveOmegaSq` is a bijection from the ordinal $\omega^2$ to $\omega$.

Does this mean, if a computer can demonstrate singleton sets are closed, the space is Hausdorff? What's the rigorous proof?

# Answer
Indeed, having your map frechet available and having your map hausdorff available is equivalent. You can find this in my article Topological aspects of the theory of represented spaces (arXiv). The proof is a very straight-forward currying/uncurrying affair.

If you are only working with second-countable spaces, this is essentially the end of the story. But beyond them, it gets a bit tricky because there the semidecidability of inequality no longer implies the topological characterization of Hausdorffness, namely that there are disjoint open sets separating the points. Matthias Schröder has found a few examples, eg the one-point compactification of the Baire space has semidecidable inequality, but the point at infinity is not separated from the others by any pair of disjoint open sets.
> 3 votes

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


# Question
Title: Longest path between two nodes of a graph
I have a graph $G$ (NOT directed). $SP$ is one of the shortest paths between $a$ and $b$ ($a$ and $b$ are nodes of $G$). $e$ is the edge of $SP$ between the nodes $j$ and $k$ ($j$ is before $k$ if we go from $a$ to $b$). If I remove $e$ from $G$, in the new graph there is a path between $a$ and $b$.

Can I say that, in the given $G$, there is at least a longest path between $a$ and $b$ that does not contain $e$?

# Answer
Yes (assuming you meant that we can choose $e$ freely. If it isn't the case, the answer is "no").

Let $P\_1:=a\rightarrow v\_1\rightarrow v\_2\rightarrow \dots \rightarrow b$ be the shortest path.

By your assumption, that there is still a path between $a$ and $b$ even if we remove some edge $e=(v\_i,v\_{i+1})$, we get that there is another path $P\_2:= a\rightarrow u\_1\rightarrow u\_2\rightarrow \dots \rightarrow b$ which has at least one different edge, hence $P\_2\neq P\_1$.

By our assumption, $P\_1$ is a shortest path and hence $len(P\_1)\le len(P\_2)$. Now, let $P$ be a longest path from $a$ to $b$. Notice, that we know that $len(P)\ge len(P\_2)$ since it is maximal.

Now, lets split into two cases:

1. $len(P\_2)\>len(P\_1)$. In this case, we get that $len(P)\ge len(P\_2)\>len(P\_1)$ and hence $P\neq P\_1$. Therefore there is a longest path $P$ which is not $P\_1$
2. $len(P\_2)=len(P\_1)$. In this case, either that $len(P)\>len(P\_1)$ (and thus $P\neq P\_1$ just as we did before), or $len(P)=len(P\_1)$. In this case, we get that $len(P\_2)=len(P)$ and hence $P\_2$ is a longest path, while still we know that $P\_2\neq P\_1$ and hence there exists a longest path which is not $P\_1$.

Therefore, there must be some path $P\neq P\_1$ which is a longest path.
> 2 votes

---
Tags: graphs
---