title: Linear Temporal Logic, Idempotent law

text:
# Question
Title: Linear Temporal Logic, Idempotent law
in many lecture notes, I have seen the LTL idempotent law for `until` and its equivalence is described as $\phi U(\phi U \psi) \equiv \phi U\psi$ and also $(\phi U \psi)U\psi \equiv \phi U \psi$ . Also by definition of $G$, some formula holds in every state. So if globally $\phi$ holds until we see $\psi$ does it make every state after it true? question might sound weird but by formula is it correct to say that also $G(\phi U \psi)U\phi \equiv G(\phi U \psi) $

# Answer
> 1 votes
> Also by definition of $G$, some formula holds in every state.

Well, $\sf true$ holds in every state. I'm unsure about why you mention $G$ here.

> So if globally $\phi$ holds until we see $\psi$ does it make every state after it true?

A state can not be true or false, like 42 can not be true or false. This is meaningless.

> is it correct to say that also $G(\phi U \psi)U\phi \equiv G(\phi U \psi) $

Take $\phi = \sf false$ and $\psi = \sf true$. Then, $G(\phi U \psi)U\phi$ is equivalent to $\sf false$, and $G(\phi U \psi)$ is equivalent to $\sf true$.

---
Tags: linear-temporal-logic, temporal-logic, computation-tree-logic
---


# Question
Title: Is there a context-free grammar for $L = \{a^{2^n}| n \geq 1\}$?
I was trying to find a cf-grammar for $L = \\{a^{2^n}| n \geq 1\\}$ but I cannot seem to find one. Is there a cf-grammar or does it not exist because of the quadratic-exponent?

# Answer
It's a more or less standard result that the language in question isn't context-free, so the answer to your question is no. The same holds for a number of similar languages, like $$ L\_1= \\{a^{n^2} \mid n\ge 0\\}\quad\text{and}\quad L\_2=\\{a^p\mid p\text{ is prime}\\} $$ There's a nice property that can be useful in cases like this: any context-free language over a one-symbol alphabet is regular. This, combined with a characterization of regular languages over a unary alphabet implies that languages like the ones above cannot be context-free since they're too "sparse".
> 1 votes

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


title: How to proof HALT doesn't reduce to L?

text:
# Question
Title: How to proof HALT doesn't reduce to L?
What method(s) can I use in general to proof HALT doesn't reduce to given language?

# Answer
Mostly, show that $L$ is decidable, mostly by designing an algorithm to decide it.
> 1 votes

---
Tags: halting-problem
---


# Question
Title: Maximum connected cell length containing two different numbers
Suppose we are given an $n\times m$ matrix $M$ of positive integers. The adjacent cells of a particular cell is the up, down, left and right cells. Like for cell $M\[i\]\[j\]$ the adjacent cells are $M\[i-1\]\[j\]$, $M\[i+1\]\[j\]$, $M\[i\]\[j-1\]$ and $M\[i\]\[j+1\]$ respectively.

An area is a set of cells such that for each pair of cells $(u\_0,v)$ in the area, there is a sequence of cells $u\_1,\ldots,u\_k$ in the area such that $u\_{i+1}$ is an adjacent cell of $u\_i$ and $u\_k$ is an adjacent cell of $v$. The problem is to find out a maximum area (i.e. an area with maximum number of cells) of this matrix which contains exactly two different numbers.

For an example: $$M=\begin{bmatrix}5&3&2&5&5\\2&1&2&5&3\\6&1&5&2&5\\5&2&5&3&5\\4&6&8&9&6\end{bmatrix},$$ Here the maximum area contains 10 cells. And the area is: $$\begin{bmatrix}\*&\*&2&5&5\\\\*&\*&2&5&\*\\\\*&\*&5&2&\*\\5&2&5&\*&\*\\\\*&\*&\*&\*&\*\end{bmatrix}.$$ What is the most efficient way to find the maximum area?

# Answer
First you can transform the matrix to a graph, where every maximal area containing the same integer is transformed to a vertex with a weight that is the number of cells in the area, and there is an edge between two vertices iff the two corresponding areas are adjacent, that is, there is a cell in one area that is adjacent to at least one cell in the other area. Therefore, the matrix in your example is transformed to

```
5 - 3 - 2 - 5
|   | / |   | \
2 - 1   |   |   3
| / | \ |   |   |
6   |   5 - 2 - 5
|   | / | \ | / |
5 - 2   |   3   |
|   |   |   |   |
4 - 6 - 8 - 9 - 6

```

Now the problem turns out to be finding the connected subgraph with maximum sum of weights such that it contains exactly two integers. This transformation can be done in $O(mn)$ time.

Next, run the following algorithm:

```
maxS := empty set
While True:
    Search the next edge (u,v) that is not used
    If not found:
        return maxS
    Let x,y be the integers contained in u,v respectively
    (#) Do BFS from u where only edges between vertices containing x,y respectively are considered
    Mark all edges found during the BFS as used
    S := the set of vertices found during the BFS
    If the sum of weights in S > the sum of weights in maxS
        maxS := S

```

Note the (#) line, this algorithm requires us to, given a vertex containing integer `x`, efficiently find all its neighbors (as well as edges) containing `y`. You can sort all the neighbors for all vertices in advance, which takes $O(\sum\_v n\_v\log n\_v)=O(mn\log(mn))$ time ($n\_v$ is the number of neighbors of vertex $v$). Now compared to normal BFS, it takes extra $O(\log n\_v)$ time for each vertex $v$.

Basically, each BFS induces a maximal connected subgraph containing exactly two integers. This algorithm checks all such subgraphs and choose the optimal one. Note each edge belongs to only one such subgraph and each vertex $v$ belongs to $t\_v$ such subgraphs ($t\_v$ is the number of distinct integers among all neighbors of $v$), the time complexity of this algorithm is

$$O\left(mn+\sum\_vt\_v\log n\_v\right)=O\left(mn\log(mn)\right).$$
> 1 votes

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


title: Data Structure for State in Automata

text:
# Question
Title: Data Structure for State in Automata
When I read the word "state" I think of a global object with a bunch of properties like the "application state". But it seems that in automata that the state is pretty much just an empty value.

Wondering what specifically the data structure is for automata states in general.

For example, the following comes from here:

> An alternating register automaton over A consists of: a finite set $Q$ of states with a distinguished initial state $q\_0 ∈ Q$ and a set of accepting states $F ⊆ Q$, a finite set $R$ of registers, and a transition function $$δ : Q×A×Tests(\mathscr{R}) → B+(Q×P(\mathscr{R}))$$...

Register automata have a "memory" which I associate with state, but it seems clear it is separate from the actual states in $Q$. Just looking for the data structure for state, if it's just an incremented integer, a string label, or something else, typically.

# Answer
> 2 votes
A proper data structure can be a dictionary (a hash table). This can be done by encoding $Q\times A \times Tests(R)$ into a string like $q\\#a\\#t$ as a **key** that $q\in Q$, $a\in A$ and $t \in Tests(R)$. And the value of the key would be the result of transition function $\delta$.

# Answer
> 3 votes
As you say, the state of an automaton is just an abstract, unstructured value. As such, you don't need a data structure *per se*: you just need a variable type that can store different values, such as an integer.

---
Tags: data-structures, automata
---


# Question
Title: Is there any horn formula equisatisfiable to the clause that is a disjunction of two literals? Does an equivalent also exist?
I just want to know whether there exists a horn formula that is equisatisfiable to $(p\lor q)$. I would also be interested to learn if there exists an equivalent as well.

# Answer
The answer is no: this is not possible. I assume a horn formula is a CNF formula with at most one positive literal (=nonnegated variable) in each clause. Now, for the sake of contradiction, suppose we have a horn formula $\phi$ that is equisatisfiable to $p\vee q$. Since $\phi$ is a horn formula, each clause in it contains a negative literal OR there is a clause consisting of only one (positive) variable. If the latter is the case, that positive variable must be a helper variable, since if it were p, it would mean that p must be necessarily true for satisfaction, which is not the case in "$p\vee q$" (same argument for q). So in this case, we derive an equisatisfiable formula by replacing that variable with true. In this new formula, we have one less clause that contains only a positive variable. We repeat this process until this is no longer the case, until we have a formula that has a negative literal in each clause. But such a formula is satisfiable by setting every variable to false. However, that's not the case in $p\vee q$, hence the contradiction.
> 1 votes

# Answer
A simpler argument is the following:

Any horn formula $H$ has a minimal model $\mathcal{A}$, i.e. a model for $H$ such that for any other model $\mathcal{A}'$ of $H$ and any atomic formula $A$ we have $\mathcal{A}(A) \leq \mathcal{A}'(A)$ (where for any model $\mathcal{B}$ we define $\mathcal{B}(A) = 0$ iff $\mathcal{B}(A)$ is false and $\mathcal{B}(A) = 1$ iff $\mathcal{B}(A)$ is true and of course $0 \< 1$). This fact follows immediately from the usual linear time algorithm for the satisfiability of horn clauses, since this algorithm computes such a model.

Now, the formula $\varphi = A \lor B$ has three models, $(A = 1, B = 1)$, $(A = 1, B = 0)$ and $(A = 0,B= 1)$. None of this models is minimal. Hence the formula $\varphi$ cannot be a horn clause (or equisatisfiable to a horn clause)
> 1 votes

# Answer
If $p,q$ are atomic then the answer is trivial. I'll assume otherwise below.

Any Horn formula is satisfiable: $a\_1 \land \cdots \land a\_n \rightarrow b$ can be satisfied letting $b$ to be true.

$p\lor q$ is not necessarily satisfiable, so no Horn clause can be equisatisfiable with it, in general.
> 0 votes

---
Tags: logic, propositional-logic
---


# Question
Title: How can I have constant time initialization for multi-dimensional arrays?
For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in constant time because there are pointers to access and keep track of the elements in the array.

How can I extend the idea of using the Which, Data, and When pointers to have constant time initialization for multi-dimensional arrays? Would I have to have multiple Which, Data, and When pointers to keep track of n-th D array dimensions?

Or is the use of hierarchical tables, which stores multi-dimensional arrays as an array of pointers to tables, where each table contains a row of the array, and implementing the Which, Data, and When pointers to the hierarchical tables a correct way for having constant time initialization of multi-dimensional arrays?

**Edit:** Use C notation for simplicity. Let's say for a large `N` we have an array:

```
SomeType array[N];

```

If `N` is very large, and only a few of the array's elements are ever used, just initializing it can become the largest cost of an algorithm. A way around this is to have a self-checking structure that can be filled in on demand. To the above add (I'm not the original poster, so I will use my own names here):

```
int last_used = -1, place[N], order[N];

```

The idea is that `last_used` tells the last used entry, `place[i]` is the index of the `i`-th asigned element of `array`, and `order[k]` is the order in which the `array[k]` was initialized. Note that none of `array`, `place` and `order` are initialized, their initial values are arbitrary. `place[i]` and `order[k]` serve to check each other. To use `array[i]`, see if `order[i] < last_used` (it is in the right range, might have been set already; if not, it is clearly garbage) and also `place[order[i]] == i`. If so, the element has been used, go ahead. If not, do:

```
last_used++;          /* Another one is in use */
place[last_used] = i; /* The next one in use is array[i] */
order[i] = last_used; /* Point back */
initialize(array[i]); /* Prepare for use */
/* Furiously frob array[i] */

```

The time of this is bounded by a constant; so the initialization time, amortized over the initialized elements, is constant. For a practical implementation, this can be packaged conveniently in a C++ class (templated on `SomeType` and `N`) overloading `operator[]`.

**Remark:** This can clearly be extended to an array of such arrays.

# Answer
It is *amortized* constant time, independent of the number of elements eventually used (initialized). But going to that complexity might just not be worth the time saved (if any).

A more practical way (due to Kernighan and Pike, IIRC) is to allocate an initial number of elements for a linear array, if you run out reallocate twice the number and initialize the new elements. The amortized cost is again constant for each initialized element, with less hassle. This obviosly works only for the case in which elements are added (mostly) sequentially; but if the elements are allocated haphazardly you'll probably be better off with another type of structure, like a hash table or some sort of tree.
> 1 votes

# Answer
I think you can use the same pattern, but simply need index conversion routines to go from multi-dimensional indices back to linear indices. For example, if you want a 2-D array, of dimensions `A` and `B`, create a linear array with`N = A*B`. Then array, place, and order would all have size `N`. When you access the 2-D array with indices a and b, instead compute `n = a*B + b` and lookup the linear array at n. This generalizes to as many dimensions as you wish.

tl;dr; A multidimensional array *is* a linear array, with a convenience interface.
> 0 votes

---
Tags: data-structures, arrays
---


# Question
Title: Why is it called 'throwing' an exception?
I'm just wondering where the phrase "throwing" an exception came from. I understand "raising" an exception but I'm wondering if "throwing" has a reason or meaning behind it?

# Answer
> 6 votes
As far as I know, and Wikipedia confirms, exceptions in the software sense originated in Lisp. There's a good summary in *A Pattern of Language Evolution* by Gabriel and Steele. Exceptions (which were not yet called exceptions) arose from the need to specify the behavior of a program if an error occurs. One possibility is to halt the program, but this is not always helpful. Lisp implementations traditionally have had a way to enter the debugger on an error, but sometimes programmers wanted to include error handling in their program. So 1960s Lisp implementations had a way to say “do this, and if an error occurs then do that instead”. Originally errors came from primitive functions, but programmers found it convenient to deliberately trigger an error in order to skip some part of the program and jump to the error handler.

In 1972, the modern form of exception handling in Lisp appeared in MacLisp: `throw` and `catch`. The Software Preservation Group lists a lot of material on early Lisp implementations, including The MACLISP Reference Manual Revision 0 by David Moon. The primitives `catch` and `throw` are documented in §5.3 p.43.

> `catch` is the LISP function for doing structured non-local exits. `(catch x)` evaluates `x` and returns its values, except that if during the evaluation of `x` `(throw y)` should be evaluated, `catch` immediately returns `y` without further evaluating `x`.
>
> `catch` may also be used with a econd argument, not evaluated, which is used as a tag to distinguish between nested catches. (…)
>
> `throw` is used with `catch` as a structured nonlocal exit mechanism.
>
> `(throw x)` evaluates `x` and throws the value back to the most recent `catch`.
>
> `(throw x <tag>)` throws the value of `x` back to the most recent `catch` labelled with `<tag>` or unlabelled.

The focus is on *nonlocal* control flow. It's a form of goto (an upward-only goto), which is also called a *jump*. The metaphor is that one part of the program *throws* the value to return to the exception handler, and the exception handler *catches* that value and returns it.

I don't know when software people started using “raise” for exceptions, or for that matter when they started calling them “exceptions”. I think both terms originated from hardware, but I don't know for sure. They were well-established by the mid-1980s, for example it's the terminology used in ML (see Monahan's thesis *Data Type Proofs using Edinburgh LCF*, 1984) and in Ada (defined in 1983).

---
Tags: terminology, programming-languages
---


# Question
Title: Lack of time hierarchy theorem for probabilistic machines
The Wikipedia page on the time hierarchy theorem states:

> A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has advice.

However, wouldn't the usual time-hierarchy theorem suffice in this case? For instance, we know that $BPP \subset EXP$, and since the ordinary time-hierarchy theorem implies that $EXP \subsetneq 2EXP$, we likewise know that $BPP \subsetneq 2EXP$. Could we not repeat with the bounded probabilistic version of $EXP$, and so on?

# Answer
> 2 votes
The deterministic time hierarchy theorem is based on our ability to simulate "weaker machines" (namely, those which run in time $T$ whereas the simulator is allowed to run in time $T\log T$), and know their response on a given input. This way, we can construct a machine running in time $T\log T$ which differs from every machine running in time $T$ on at least one input (simple diagonalization).

In the context of BPP however, the response on a given input (i.e. whether or not it belongs to the language accociated with the given probabilistic machine) is determined by the probability of accepting that input, namely if it exceeds some agreed upon threshold. You can of course compute this probability in a naive manner, and diagonlize just like in the deterministic case. This is similar to what you suggested, but calling this a time hierarchy theorem for probabilistic time is hardly fair, since the jumps are big enough to allow you to simply apply the deterministic time hierarchy theorem, avoiding any probabilistic issues. This does not answer for example whether or not $BPTime(n)\subsetneq BPTime(n^2)$.

---
Tags: complexity-theory
---


# Question
Title: I have a question about resource alocation to avoid dead lock
In the code below, three processes are competing for six resources labeled A to F.How can I modify the get request in each procedure in this graph to avoid dead lock You cannot move requests across procedures, only change the order
inside each procedure.

# Answer
> 0 votes
The main resources to be focused here are the common ones : $B$ , $C$ and $D$. To prevent deadlock from ever occurring you should focus on breaking $circular wait$, which is one of the 4 necessary conditions for deadlock.

For that lets make the common resources request as early as possible: Consider this:

$P\_{o}()$ $\ $$\ $$\ $$\ $$\ $$\ $$\ $ $P\_{1}()$ $\ $$\ $$\ $$\ $$\ $$\ $$\ $ $P\_{2}()$

$get(B)$ $\ $$\ $$\ $$\ $ $get(B)$ $\ $$\ $$\ $$\ $ $get(C)$

$get(C)$ $\ $$\ $$\ $$\ $ $get(D)$ $\ $$\ $$\ $$\ $ $get(D)$

$get(A)$ $\ $$\ $$\ $$\ $ $get(E)$ $\ $$\ $$\ $$\ $ $get(F)$

The proof that the above sequence never leads to deadlock is easy and can be got by considering the **different orders in which common resources are acquired**.

---
Tags: operating-systems, deadlocks, resource-allocation
---


title: LPA* implementation keeps looping

text:
# Question
Title: LPA* implementation keeps looping
### Short story

I am currently trying to implement LPA\* in an existing navigation system and find the algorithm seems to loop forever, expanding the same vertices over and over again. I am wondering what is causing this to happen, and what I can do to rectify this.

### Long story

The navigation system uses Dijkstra so far. As I am extending it to react to changes in the traffic situation (and thus edge costs) by changing the already-calculated route, I decided to go for LPA\*, as it is essentially an evolution of Dijkstra.

The existing Dijkstra implementation diverts from the canonical one in a few ways:

* The cost of a vertex is the cost to reach the destination from that vertex. Cost thus descreases as we travel along the route, the destination (theoretically) has a cost of zero. This way, the route graph remains valid as the vehicle position changes, as long as the destination remains the same.
* If the destination is off-road, it is not directly represented by a vertex. Instead, a handful of nearby vertices are given a cost slightly above zero and inserted in the priority queue. (That initial cost can still be lowered—it is as if each of these nodes were directly connected to the destination with a vertex whose cost is equal to the cost of the node.)
* Current position works in a similar way: it may be off-road or in the middle of a vertex, so we simply add a penalty to the nearest vertex.
* The algorithm terminates after the last vertex in the graph has been visited, even if all vertices around the current position have already been expanded. That allows us to keep the route graph even if the vehicle takes a wrong turn and ends up in a place from which the destination is much more expensive to reach.
* Each vertex maintains a pointer to the next edge along the cheapest path from that vertex to the destination. Where ambiguities exist, the pointer may point to any acceptable edge (the decision is probably stable across multiple runs, but not guaranteed to be).
* Instead of infinity, we use $2^{31} - 1$, or `0x7FFFFFFF` (largest positive signed 32-bit integer) as pseudo-infinity. Since cost represents travel time in tenths of seconds, the maximum is in the order of magnitude of several years, and any numbers likely to be encountered in practice are several orders of magnitude below it.
* Most edges are traversable in both directions (and, technically, if they aren’t, their cost is simply pseudo-infinity). Therefore, most successors of any given vertex are also predecessors of it, and vice versa.

I have maintained these diversions and kept the existing data structures, adding just a `rhs` member to the vertex data structure. Further deviations from canonical LPA\* I introduced:

* For the moment, Dijkstra is still used for the original route (I am planning to move everything to LPA\* in a later step). When a vertex is visited, I set its `rhs` member to its value so it will appear locally consistent to a subsequent LPA\* run.
* I use a fixed heuristic, $h = 0$. This is valid for A\* (effectively turning it into Dijkstra) and thus also for LPA\*, and makes it easier for Dijkstra and LPA\* to coexist.
* Because $h = 0$, there is no need for the two-dimensional keys in the priority queue (as both elements if each key would always be identical). That permits me to keep using the Fibonacci heap for the priority queue in the same manner as with Dijkstra.
* Rather than a simple addition of edge and route costs, I use a function with some overflow protection. If one of the two operands is `0x7FFFFFFF` (pseudo-infinity), this is also returned as a result.
* Similar to the Dijkstra implementation, I do not terminate until the entire route graph is flooded.

However, if I change some edge costs in an already-flooded route graph and then run my LPA\* implementation on it, it keeps looping. Debug output shows me that it is expanding the same vertices over and over again, with their costs increasing. What appears to happen here:

* A vertex $v$ is updated.
* All vertices in $Succ(v)$ (essentially all neighbors of $v$) are updated.
* For each $u \in Succ(v)$, all vertices in $Succ(u)$ are updated. Since (in most cases) $v \in Succ(u)$, $v$ is updated again and the cycle starts over.

What I have tried:

* After updating $v$, specifically exclude its shortest-path predecessor (i.e. the next vertex towards the destination) from being updated. That causes the LPA\* implementation to terminate in a time simila to Dijkstra, but leaves me with loops in the route graph (i.e. two adjacent vertices both pointing to the edge connecting them).
* If, in addition to the above, while updating a vertex, I skip other vertices which would create a loop condition, that leaves me with the part of the route graph “upstream” from the changed segments having maximum cost.

Where is the error, and how can I fix it?

### Full story

https://github.com/mvglasow/navit/tree/traffic. The commit which added the actual LPA\* implementation is 61d9a1a; some preparation work was also done in the previous ones.

# Answer
I have solved the issue, and my LPA\* implementation now gives me a valid route that is identical to the one I get when I run Dijkstra from scratch on the updated route graph for the test cases that I have tried.

Fist off: The two things that I tried above would break LPA\*, so I reverted them.

The first fault was simply a sign error when calling the function to determine edge costs, leading the program to use costs for the wrong direction (though only in one place, not in another).

The other fault was in the call to the function which determines edge costs. Arguments passed to it are a vehicle profile (which determines which edges are usable and what their costs are), the edge, a direction (i.e. first to second vertex or vice versa) and, optionally, a vertex.

The vertex argument was misleadingly named `from`. In reality, when specified, it is the vertex at which we **leave** the edge and move on to the next when following the route to the destination. If that vertex has the edge pointer (see above) set to the edge being examined, the function will report the cost of the edge from to be pseudo-infinity (as traversing the edge in that direction will move us further away from the destination). Documentation was scarce and I had to dig through the source code to infer what that argument really was supposed to do.

I found I passed the wrong vertex to the function; fixing this now-obvious error made some of the simpler test cases work.

I also now clear the edge pointer at the beginning of `updateVertex()` (it is set again in the function as we examine each edge); though this may not be relevant to the issue here.

About predecessors and successors, we can simply use all immediate neighbors (any vertex directly connected to the current one by an edge). If an edge cannot be traversed in a particular direction, we assume its cost in that direction to be infinity.

With these fixes, I get a correct route for simpler test cases. For the more complex ones, LPA\* would terminate in a timely manner, but when iterating through the route graph, I would encounter a loop.

Further investigation revealed that this was due to “loop” edges in the graph, which connect a vertex with itself. If the edge pointer of the vertex pointed to that faulty edge, the iteration would loop forever upon hitting one of these points. Dijkstra apparently never picked up such edges as part of the cheapest path (I didn’t investigate this further), but LPA\* did.

Due to the way the implementation works (position and destination need not correspond to points on the route graph), such loops can be legit (think of a circular road with only one single access road connecting to it), and parts of it can even become part of the cheapest path when the current position or destination is located on such an edge. However, there is no legit reason to have such a segment appear in the middle of the cheapest path.

I resolved this by checking for this in the cost function: if the segment is a loop and it is not connected to the position or destination, its cost is assumed to be pseudo-infinity to prevent it from becoming part of the cheapest path.
> 1 votes

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


# Question
Title: Find shortest path in undirected graph that goes through all vertices and returns to starting vertex
I have an undirected weighted graph like this one

My task is to find the fastest path (with least weight) that goes from specified vertex goes through all vertices and returns to the starting vertex without repeating a vertex.

```
Graph
1 3 time 5
3 2 time 5
2 4 time 5
4 1 time 5
4 3 time 4
1 2 time 5

Starting vertex 3
Path 1: 3->1->4->2->3
Path 2: 3->2->1->4->3
Time 1 and 2: 5+5+5+5=20

Path 3: 3->1->2->4->3
Path 4: 3->4->2->1->3
Time 3 and 4: 5+5+5+4=19 -> fastest

```

Is there a fastest way than DFS to solve the problem?

# Answer
Travelling salesman problem looks almost the same but I can't repeat a visited vertex.

Going from vertex 3 to vertex 5 I can't do that 3 -\> 2 -\> 3 -\> 1 -\> 3-\> 4 -\> 3

A solution is: 3-\>1-\>2-\>4-\>3

That's my function:

```
private static List<HashMap<Integer,Integer>> graph = new ArrayList<>();

public static void dfs(int currentVertex,Stack<Integer> visited,long currentTime) {
    if(visited.size() == graph.size()-1) {
        if(!graph.get(currentVertex).containsKey(targetVertex)) {
            return;
        }

        currentTime += graph.get(currentVertex).get(targetVertex);
        if(currentTime < fastestTime) {
            fastestTime = currentTime;
        }
        return;
    }

    for (Map.Entry<Integer,Integer> vertex: graph.get(currentVertex).entrySet()) {
        if(!visited.contains(vertex.getKey())) {
            visited.add(vertex.getKey());
            dfs(vertex.getKey(),visited,currentTime + vertex.getValue());
            visited.pop();
        }
    }
}

```
> -2 votes

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


# Question
Title: What is the most used way to write for-loop as pseudocode?
* **for** $e\leftarrow1$ to 8 **do**
* **for** $e\in\[1,8\]$ **do**
* **for** $e\in\\{x\in\mathbb{N}|1\le x\le8\\}$ **do**

What is more preferred?

# Answer
> 0 votes
Just use whatever is clearest in your particular situation. Pseudocode is not a formal language with formal syntax.

Note that **for** $e\in \[1,8\]$ **do** doesn't necessarily imply that the values $1$, $2$, ..., $8$ are assigned in any particular order. Note that $\\{x\in \mathbb{N}\mid 1\leq x\leq 8\\}$ is somewhat redundant: an algorithm can't possibly loop over all the reals or rationals between $1$ and $8$, so the set can only really be a set of natural numbers. Finally, note that the association $\mathrm{e}=2.71828\ldots$ is very strong, so $e$ is often a poor choice of variable name.

# Answer
> 0 votes
Pseudocode does not need to be so mathematical just for the case of being fancy. Making your algorithms understandable is always priority number one.

```
S = Dynamic array with integers
P = New empty AVL Tree

for every element x in S
    P.insert(x)

```

Something like this is very easy to follow and does not include any form of formal descriptions. If the formal descriptions are important to understand, then we could of course show them just to clearify. The most preferable for the one receiving your pseudocode is that its simple and easy to follow.

# Answer
> 0 votes
The first one is much more compact and widely used specially in books like Introduction to Algorithms ,pseudocodes are meant to be simple and every reader with a little background of knowledge would be able to understand it

---
Tags: loops, pseudocode
---


# Question
Title: Is there any difference between Time Complexity and Running time?
Is time complexity and running time of the program/algorithm one and the same thing? Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that program took to run. So, can we say that running time is same as computer complexity?

# Answer
The terms, as they are used in computational complexity theory are different.

**Running time** is a property of an *algorithm*. It is the maximum number of steps the algorithm can run for, as a function of the length of the input.

**Time complexity** is a property of a *computational problem*. It is, essentially, the running time of the fastest possible algorithm for that problem.

Thus, we might talk about the time complexity of the sorting problem, and the running time of heapsort. Informally, people often refer to the "time complexity" of an algorithm. Strictly speaking, this is incorrect, but there's only really one thing it could mean.

Note that we usually only quote the asymptotic behaviour of running times and time complexities, since we're usually not interested in the exact function, and it's usually too hard to figure out, anyway.

Note also that, in applied computing, "running time" may refer to the time taken for some program to run, as you might measure with a stopwatch.
> 7 votes

# Answer
No. The difference is well explained by Steve Jessop: "Running time is how long it takes a program to run. Time complexity is a description of the asymptotic behavior of running time as input size tends to infinity.

You can say that the running time "is" O(n^2) or whatever, because that's the idiomatic way to describe complexity classes and big-O notation. In fact the running time is not a complexity class, it's either a duration, or a function which gives you the duration. "Being O(n^2)" is a mathematical property of that function, not a full characterisation of it. The exact running time might be 2036\*n^2 + 17453\*n + 18464 CPU cycles, or whatever. Not that you very often need to know it in that much detail, and anyway it might well depend on the actual input as well as the size of the input."

Soure: https://stackoverflow.com/questions/4915842/difference-between-time-complexity-and-running-time

EDIT: Here is the video that might be helpful for your edited question: https://www.youtube.com/watch?v=8syQKTdgdzc
> -1 votes

# Answer
They're both essentially trying to describe the same thing (performance) but in different ways.

**Running time** is how long it takes for a computer to perform a specific task. This could be measured in nanoseconds, milliseconds, etc.

In contrast, **time complexity** is a more abstract and general way of expressing performance, and is a generalized and more abstract representation of run time. To be specific, it's a representation of the *asymptotic behavior* of the run time as the run time approaches infinity. I'm not sure if you're familiar with notations such as big O notation, but it looks something like this:

$$O(1)\\O(n)\\O(\log{n})$$

and the list goes on. The Wikipedia article I linked has a good list of the notations regarding time complexity.

When I first ran into time complexity, it was difficult for me to grasp (aside from personal factors like I had no background knowledge in computer science) because I just didn't know what expressions like "asymptotic behavior" meant and I couldn't wrap my head around the formal definitions either (obviously).

When I asked my professor about it, he told me to think of it more as *growth rates*. The lower the growth rate, the better (this statement is terribly generalized, but let me explain).

Let's say you have two functions, $y = x^2$ and $y = x$. If you graph them, they look like this:

As you can see, $y = x^2$ "grows" at a much faster rate than $y = x$. But in terms of complexity, lower growth rates are better because it means the time it takes for the program to run is that much closer to being linear, and that's why in terms of time complexity $O(n)$ is better than $O(n^2)$.

I hope my answer helps. Good luck!

**EDIT**

To answer your edited question, no; run time and computational complexity are not the same thing.

Computational complexity, as you mentioned, talks about the resources that a computing device needs to perform a task. Therefore, run time is a factor of computational complexity and so they aren't equal.
> -1 votes

---
Tags: time-complexity, terminology, asymptotics, runtime-analysis
---


# Question
Title: Is every planar graph a possible dual graph of a voronoi diagram?
My question is: Given a planar graph defined by its adjacency matrix. Can I always find a set of points, so that the dual graph of the voronoi diagram of that set of points is the same as the planar graph?

# Answer
No. The dual graph of a Voronoi diagram is the Delaunay triangulation of its point set so, in particular, every interior face of it is a triangle. But there are plenty of planar graphs (e.g., the $4$-cycle) that have non-triangular interior faces.
> 1 votes

---
Tags: graphs, planar-graphs, voronoi-diagrams
---


# Question
Title: Is the existence of an oracle such that $P^O = NP^O$ nontrivial?
This famous paper proves the existence of both oracles $A$ and $B$ such that $\textbf{P}^A = \textbf{NP}^A$ and $\textbf{P}^B \neq \textbf{NP}^B$, therefore proving that any resolution to the **P** versus **NP** problem must be nontrivial in the sense that it cannot relativize.

I understand the significance of the oracle separation given by the latter oracle $B$: it shows that it certainly isn't *trivially* true that **P** = **NP** (of course, this result is incredibly obvious anyway!). But while I'm sure I'm wrong, the existence of the former oracle seems kind of obvious to me.

I would naively expect that for *any* complexity classes **A** and **B**, there would exist some oracle $O$ such that $\textbf{A}^O = \textbf{B}^O$. Just let $O$ be any oracle for a language that is complete for any complexity class **C** that is "sufficiently larger" than $\mathbf{A} \cup \mathbf{B}$ (in some sense which I suspect could be made precise). Then the oracle $O$ would be so much more powerful than the abstract machines whose capabilities define **A** and **B** that the most efficient solution to any tractable problem would simply be to consult the oracle and call it a day. In this case the oracle would "eat up" the original abstract machines and we would simply have $\mathbf{A}^O = \mathbf{B}^O = \mathbf{C}$. As a rather overpowered example, isn't it trivially true that $\mathbf{P}^\mathbf{R} = \mathbf{NP}^\mathbf{R} = \mathbf{R}$?

(Sorry, this question probably shows that I lack a basic conceptual understanding of how relativization works.)

# Answer
The existence of an oracle with respect to which $\mathsf{P} = \mathsf{NP}$ shows that $\mathsf{P} \neq \mathsf{NP}$ cannot be proved using techniques that relativize such as diagonalization. In contrast, the time and space hierarchy theorems do relativize, disproving your claim that any two complexity classes are equal relative to some oracle.

The easy observation that $\mathsf{P}^\mathsf{R} = \mathsf{EXP}^\mathsf{R}$ seems to contradict the fact that the time hierarchy theorem relativizes. Tthe definition of $\mathsf{X}^\mathsf{R}$ that you use is $$ \mathsf{X}^\mathsf{R} = \bigcup\_{A \in \mathsf{R}} \mathsf{X}^A.$$ The time hierarchy theorem shows that $\mathsf{P}^A \neq \mathsf{EXP}^A$ for every *language* $A$, but not for every *family of languages*.

The oracle with respect to which $\mathsf{P} = \mathsf{NP}$ is a single language. One possible choice is any $\mathsf{PSPACE}$-complete language. This is very similar to using an arbitrary recursive language, with a crucial difference – there are languages in $\mathsf{PSPACE}$ which are complete with respect to polynomial time reductions.
> 3 votes

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


# Question
Title: Specific example of a problem that shows why **NP** isn't low for itself
Wikipedia says

> Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that **NP** isn't low for itself unless **NP** = **co-NP**, which is considered unlikely... .

This line of reasoning is a bit abstract for me. Is there a concrete example of a simple problem that can be shown to be in $\textbf{NP}^\textbf{NP} \setminus \textbf{NP}$ under reasonable assumptions? That is, a problem that can't be solved efficiently by a nondeterministic Turing machine, but *can* be solved efficiently by a NTM with oracle access to *another* NTM?

# Answer
> 3 votes
As Pål GD mentions in the comments, $\mathsf{NP}^\mathsf{NP}$ is usually knows as $\mathsf{\Sigma}\_2^P$, the second level of the polynomial hierarchy. If $L$ is any $\mathsf{\Sigma}\_2^P$ complete problem, then $\mathsf{NP} \neq \mathsf{\Sigma}\_2^P$ is *equivalent* to $L \in \mathsf{\Sigma}\_2^P \setminus \mathsf{NP}$. So any $\mathsf{\Sigma}\_2^P$-complete problem is a concrete example for a problem in $\mathsf{\Sigma}\_2^P \setminus \mathsf{NP}$ under the reasonable assumption that $\mathsf{\Sigma}\_2^P \setminus \mathsf{NP} \neq \emptyset$. In other words, these are the problems "most likely" to be the concrete examples you seek.

One canonical complete problem for $\mathsf{\Sigma}\_2^P$ is $\exists \forall\mathsf{SAT}$: given a formula $\varphi$ on variables $\vec{x},\vec{y}$, is is true that there exists an assignment $\alpha$ to $\vec{x}$ such that $\varphi|\_{\vec{x} = \alpha}$ becomes a tautology? It is easy to see that this can be solved by an $\mathsf{NP}^\mathsf{NP}$ machine: the machine guesses $\alpha$, and uses the oracle to verify that $(\lnot \varphi)|\_{\vec{x} = \alpha}$ is unsatisfiable.

Generally speaking, the assumption $\mathsf{NP} \neq \mathsf{\Sigma}\_2^P$ seems stronger than $\mathsf{P} \neq \mathsf{NP}$, and when proving conditional results, we prefer assuming the latter rather than the former. But it is generally conjectured that the entire polynomial hierarchy is strict, a much stronger assumption.

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


# Question
Title: Subset sum into a consecutive range vs. standard subset sum
The following problems live in integer domain.

I want to find a subset of $\\{x\_0, x\_1, \ldots, x\_{n-1}\\}$ such that the subset's elements sum to any number in a prescribed interval $\[X,X+k\]$, $k\geq 1$.

We call the above problem A.

An obvious approach is to solve $k+1$ standard subset sum problems with targets $X, X+1,\ldots,X+k$ . I would be satisfied once my algorithm finds a solution to any of these problems.

Now I am wondering, does there exist a single standard subset problem B: $\\{y\_0,y\_1,\ldots,y\_{m-1};Y\\}$ where $Y$ is the target, such that if I solved B, I equivalently solved A, additionally, the conversion from B's solution to A's solution is fast, preferably in linear time.

To make it simpler, I am only considering $k=1$.

Thank you!

# Answer
This answer assumes that a Yes instance of your problem with elements $x\_0,\ldots,x\_{n-1}$ and targets $\[X,X+1\]$ is one in which there is a subset summing to either $X$ or $X+1$.

Given an instance of your problem with elements $x\_0,\ldots,x\_{n-1}$ and targets $\[X,X+1\]$, construct an instance of subset sum with elements $x\_0,\ldots,x\_{n-1},1$ and target $X+1$. You take it from here.
> 2 votes

---
Tags: algorithms, combinatorics, subset-sum
---


# Question
Title: Difference Between Tree Automata and Tree Transducers
Wondering what the differences are between Tree Automata and Tree Transducers.

Wikipedia says:

> Tree transducers extend tree automata in the same way that word transducers extend word automata.

And about word transducers it says:

> A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton that maps between two sets of symbols.\[1\] An FST is more general than a finite-state automaton (FSA). An FSA defines a formal language by defining a set of accepted strings while an FST defines relations between sets of strings.

But I don't understand what the implications are and what the differences really are, even though there is the extra tape. Not sure about the tapes in the Tree Transducers.

All I see so far is tree transducers have the extra "output alphabet" for constructing a new tree (which you plug the state into):

$$ {\displaystyle q(f(x\_{1},\dots ,x\_{n}))\to u}$$

For instance:

$${\displaystyle q(f(x\_{1},\dots ,x\_{3}))\to g(a,q'(x\_{1}),h(q''(x\_{3})))}$$

but the automata have pretty much the same signature, just using the input alphabet only:

$$q(f(x\_1,...,x\_n)) → f(q\_1(x\_1),...,q\_n(x\_n))$$

# Answer
> 2 votes
A tree automaton accepts trees. A tree transducer maps trees into trees. Although string automata generally work natural from left to right, there is no such natural choice for tree automata: they can process the tree from top to bottom, from bottom to top, and there are even models that walk over trees (like two-way string automata walk over the input).

As far as I understand, you example has the following meaning. Your automaton is working top to bottom.

$q(f(x1,\dots ,x3))\to g(a,q′(x1),h(q′′(x3)))$

To the right of the rule we read $q(f(x1,\dots ,x3))$. This means the input is a tree that has a root labelled with symbol $f$. This root has three children represented by the variables $x1,\dots ,x3$. The transducer is at state $q$ when it visits the root labelled $f$.

To the right we see the tree that is constructed when the rule is applied. The tree has a root labelled $g$ and three children. The first child is a leaf labelled by $a$. The next two subtrees are computed by two copies of the original transducer. The second child (of the output) $q′(x1)$ means a copy of the transducer starts at the first child "$x\_1$" of the input tree in state $q'$, and the third child $h(q′′(x3))$ indicates a tree with node labelled $h$ which has a single child computed by another copy of the transducer started at the third child "$x\_3$" of the input in state $q''$.

---
Tags: automata
---


# Question
Title: Do we need both path compression and union by rank together in disjoint set data structure?
I was studying disjoint set data structure. I studied path compression and union by rank. Initially all the elements are single in their own set and by performing unions we can combine different sets. Now since we are performing union by rank the height of the resultant tree is always minimum. At this point i think that we might not need path compression at all. Am i right? If i am wrong please explain me with an example.

# Answer
> 2 votes
No, you are not right, at least not if you want the fastest possible running times. Using both is faster than using just one of them alone. Using just Union by rank gives you a $O(\lg n)$ amortized running time per operation, whereas using both Union by rank and path compression gives you a $O(\alpha(n))$ amortized running time per operation, which is asymptotically faster. Here $n$ is the number of elements and $m$ is the number of operations performed on them. See https://en.wikipedia.org/wiki/Disjoint-set\_data\_structure#Time\_complexity.

---
Tags: data-structures
---


# Question
Title: Build all valid parenthesis in polynomial time
Given some binary operator $\otimes : X\times X\to X,$ and list $x\_1,\dots,x\_n$ where $x\_i\in X,$ can all possible expressions in $\otimes$ be computed within a number of operator applications polynomial in $n$?

We say an *expression* in an operator $\otimes$ and list $x\_i$ is formed by placing $\otimes$ between all $x\_i$ in order with some choice of parentheses. For example given the list $x,y,z,$ valid expressions are $(x\otimes y)\otimes z$ and $x\otimes (y\otimes z)$. Alternatively, an expression in $x$ is precisely $x$ and an expression in $x\_1,\dots,x\_n$ is an expression in $x\_1,\dots,x\_{k-1},x\_k\otimes x\_{k+1},x\_{k+2},\dots,x\_n$ for some $1\le k \< n.$

We assume that there are no more than polynomially bounded amount of setting the parenthesis (because its given in the assignment) and thus it has to run in polynomial time.

---

I'm doubting my solution so far, here it goes:

We define two working sets

$ result = \\{ \\}$

$ vars = \\{\\}$

Every **single** input variable is a valid expressions if it is paired with another valid expression ( since our operand is two-valued), and we add them to the vars set.

Now iterate through lengths $ 2, \\\_,n$ and build all valid expressions like so:

For length $2$ we build all valid strings like so: $w\_1 = (x\_0 \circ x\_1) , w\_2 =(x\_1 \circ x\_2) \ldots $ and add them to the $vars$ set.

For length $\>3$ we greedily iterate through the biggest available chunks in the $vars$ set and try to fill up the voids with items from our vars set until we reach length 3.

Once we reach length $n$ we add all generated expressions to the $res$ set and return.

One thing I'm stuck on right now is the complexity analysis, one iteration of the subexpression generation takes $n^2$ steps at most, when we reach length $n$ we get $n^3$ complexity (much like CYK, which is very similar to this algorithm).

---

But something feels fishy, I feel like I've made a mistake somewhere, can someone point me in the right direction ?

This is an assignment so full answers are discouraged, please give hints, once I get the grading of the answer I'll post it here for the afterworld to admire.

# Answer
> "We assume that there are no more than polynomially bounded amount of setting the parenthesis"

Your assumption is wrong. There are exponentially many such expressions. In particular, each such expression corresponds to a full binary tree with $n$ leaves (i.e., a binary tree where each non-leaf node has exactly 2 children). There are exponentially many such trees. Consequently, there are exponentially many such expressions.

It follows that you can't generate the list of all such expressions in polynomial time, since it takes exponential time even just to write down the answer (let alone to find it in the first place).
> 2 votes

---
Tags: time-complexity, dynamic-programming
---


# Question
Title: Is the halting problem decidable by an "infinite Turing machine"?
It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not.

However, I'm wondering, if we want to decide for the set of Turing machines $T$, whether a turing machine $t$ halts, and we somehow have access to "infinite Turing machines" $I$, which have the property $P$: "They can calculate an infinite amount of steps in finite time", would it then be possible to grab a $i$ from $I$ that decides the halting problem for all $t\in T$?

The proof of the undecidability of the halting problem no longer applies here, because it would require one of the $t\in T$ to contain $i$, but then we might possibly have that $t\in I$ (since $t$ now simulates $i$, which is in $I$).

**So my question is, can we prove that in this case, the halting problem is decidable?** If not, are there other constructions of $I$ than the one I came up with that would make it possible?

(is there a name for what I've called "infinite turing machines"?)

# Answer
> 3 votes
It is true that infinite Turing Machines as you have defined them can solve the halting problem **for regular Turing Machines**. That is, there exists an infinite TM, $I(t,x)$, that returns $1$ iff $t(x)$ halts. To see this, just have your first step be “run t(x) for infinitely many steps” and the rest is easy after that. Yes, there are some issues formalizing this idea, but it can be done. This is called a “Hyper Turing machine”

There’s an interesting question lurking here though... is there an infinite TM that solves the halting problem **for infinite Turing Machines**? The answer to that is no, and if you know the diagonalization proof of the incomputability of the halting problem that applies here too.

# Answer
> 0 votes
There... might just be a way. But it is going away far from what is known to be a Turing Machine.

As PJTraill wrote, we have to get some idea of "infinite steps". I propose our special machine $S$ has (countably) infinite tapes. Given a TM $T$ and input $x$ our infinite steps $S$ would do in finite steps would be that on tape $i$ the content of the tape of $T$ and its state on input $x$ after $i$ simulated steps of $T$ are encoded. We further should allow $S$ to have at least countably infinite many states. After each tape $i$ has been finished being constructed (which, as we remember basically happens in the traditional TM way), $S$ assumes a special tape state $0.a\_1\ldots a\_i$ with $a\_i=1$ if the tape $i$ does not differ from tape $i-1$ and else $0$. When we now allow some mechanism that, after doing all the infinite steps in finite time, changes from our always finitely digited $0.a\_1\ldots a\_i$ to some infinite sequence $0.a\_1\ldots$ - or in more mathematical terms, allow our machine to calculate the limit of the (in general uncomputationable) sequence of special tape stape states $q\_i$ when $i\rightarrow\infty$ - then we could be finished, when the state $0.0000\ldots$ returns "TM halts" and all others with infinite digits return "TM does not hold".

I would like to add two things. First, this machine $S$, while halting after a finite number of steps by definition, could not be used to prove that it or machines with the same generalizations would halt. We are using the fact that a TM only has a finite number of states, so it can be encoded on each tape of $S$ using only finite space. Only using finite space on a tape is important so the tape itself can be traversed in finite steps. $S$ is so close to a TM as possible and as long as no infinite steps are done by it, its evaluation to a certain fixed point can be simulated by a normal TM. We were also using that the simulated TM only has (one or) finitely many tapes. We can simulate any such TM by a 1-tape TM, but with countable finite tapes, I don't know but doubt that's possible.

The second thing to mention is that this machine $S$ is by far not the thing Turing and like-wise minds of the time envisioned. They thought about what would be possible for a computator, e.g. a human with instructions, to calculate. It does not seem like this constructed machine $S$ would fall into this category.

---
Tags: undecidability, halting-problem
---


# Question
Title: Are there any known implementations of a functional Heap's Algorithm?
*TL;DR*: Is an implementation of the Heap's Algorithm adhering to the principals of functional programming possible, and are any implementations of it known? And by "adhering to the principals of functional programming", I mean mainly not relying on the mutation of an object to carry out the algorithm.

---

I decided to write a function that generates permutations of a list

```
(permutations [1 2 3])
=> [[1 2 3] [2 1 3] [3 1 2] [1 3 2] [2 3 1] [3 2 1]]

```

And after some quick searching, somewhat arbitrarily picked Heap's Algorithm.

The problem is, I'm writing in Clojure, trying to adhere to proper FP principals as close as possible, and the entire algorithm seems to hinge on mutating a "global" array while recursing. I worked on this for a couple of hours, and could not find a way of sanely getting the results passed "back up the stack", since the recursive calls just kind of float between mutations:

```
(defn- swap-v [v i1 i2]
  (let [x (get v i1)]
    (-> v
        (assoc i1 (get v i2))
        (assoc i2 x))))

(defn permutate [coll]
  (let [coll-atom (atom coll)
        result-atom (atom [coll])]
    ((fn rec [n]
       (when (> n 1)
         (let [n-even? (zero? (rem n 2))
               swap-pos #(if n-even? % 0)]

           (doseq [i (range (dec n))]
             ; Recursive call
             (rec (dec n))

             ; Mutate the "array" by swapping two elements
             (swap! coll-atom swap-v (swap-pos i) (dec n))

             ; Then mutate the results array so they can be returned later
             (swap! result-atom conj @coll-atom)) ; Mutate the

           ; ... And another recursive call down here
           (rec (dec n))))

      (count @coll-atom)))

    @result-atom)) ; Dereference the atom and return the results

```

I tried changing the `doseq` to a reduction, then I had the results returned nicely, but seemingly nothing to do with them.

I ended up giving up on a FP approach, wrote the above code, and tried to find an example of an FP approach to the algorithm to see where I had gone wrong. To my surprise, I wasn't able to find any. The closest I could find was a Haskell implementation, but honestly, I have no clue what most of the code is doing; it's pretty obscure. I see `unsafe` in a few places though, so I think they snuck some mutation in there.

Is this possible?

Note, I'm not looking for a review of the code here, since I'm aware this is very imperative-styled, and I already has a review request open.

# Answer
I'm really not very familiar with clojure. I think this is probably the longest clojure program I've written so far. But I guess it provides some sort of answer.

On the whole, functional enumerations of permutations are going to suffer from the O(n) cost of creating a new permutation vector on each iteration. Pretty well all of the common imperative solutions make some attempt to avoid this cost, and many of them can produce amortised O(1) complexity (for a single permutation). Heap's algorithm is interesting in an imperative environment largely because it guarantees to perform a single swap on each iteration, which is clearly a minimal total number of mutations. That's particularly useful if the goal is to perform some sort of aggregate computation over the permutation which can be incrementally computed from the previous value and the modifications.

Heap's algorithm is not the only algorithm which performs just a single swap to produce the next permutation. The possibly even more famous bell-ringers' algorithm (often called the Steiner-Johnson-Trotter algorithm) produces sequences in which consecutive permutations differ only by a swap of two *adjacent* elements. This could be even more valuable for updating of aggregate computations, but it is more complicated to figure out which two adjacent elements to swap at each iteration. (Indeed, although tables of plain changes for up to seven bells were produced several centuries ago, the precise algorithm used to produce these table has not, as far as I know been recorded. However, the results line up with the algorithm proposed independently in the 1960s by the three mathematicians after whom it is named.)

The plain changes algorithm was motivated in part by the desire to keep the various bell ringers' attention on the changes; if a bell stays in the same position in the change for too long, its ringer may become bored and lose their place in the sequence. (In fact, current change ringing sequences try even harder to avoid leaving a bell in the same position for too long, so they no longer use the STJ algorithm.)

For many combinatorial problems, though, the opposite criterion is desired. For example, it may be useful to generate the permutations in lexicographic order, which means that the first item retains its value for (n-1)! iterations. Lexicographic ordering can still be performed in amortised O(1), and it involves O(1) mutations at each iteration, but the number of mutations may be as great as n-1 (or `n`, if the permutation sequence is circular, since the last permutation in lexicographical order is the reverse of the first one).

If the vector to be permuted may have repeated elements, and only unique permutations are desired, then lexicographic order is far and away the easiest solution. Furthermore, it is very easy to describe the next-permutation algorithm for lexicographic ordering:

1. Start with the vector sorted from left to right.
2. At each iteration:

1. Find the shortest suffix which is not monotonically non-increasing. (In other words, find the last element for which some subsequent element is greater.) If the entire vector is monotonically non-increasing, then it is the last permutation and the process is done.
    2. Sort that suffix by shifting its first element to the right, and then reverse it. (This can be done by a modified reversal algorithm with k/2 swaps where k is the length of the suffix, but doing it in two steps is conceptually simpler.)

I think that algorithm would be quite simple to implement in functional style.

But let's get back to Heap's algorithm. Heap developed his algorithm in 1963, about the same time as Trotter and Johnson independently published the change ringing algorithm. (Steinhaus had published his version of the algorithm in 1958, but since he was writing in Polish it was relatively unknown until it was translated into English in 1963.) Heap's paper was a simple description of his algorithm, without formal proof, and it probably would have remained in the dusty archives of computer science had it not been rediscovered by Robert Sedgewick a decade later. In 1977, Sedgewick wrote a long survey on permutation algorithms, in which he devoted quite a bit of attention to Heap's algorithm, including producing an optimised implementation in a kind of virtual machine code. He concluded that for typical hardware architectures (in 1977), "Heap's method will run faster than any other known method."

A couple of years later, he presented a public lecture on permutation algorithms, during which he repeated this claim, and Heap's algorithm became the permutation algorithm of choice for programmers with a performance fetish. Unfortunately, the presentation slides (which are rather more easily found online than any of the other sources for Heap's algorithm) had a minor error in the algorithm pseudocode (not present in the 1977 paper, which presents a number of variant implementations, all impeccable). And because the presentation slides are rather more accessible than any of the academic references, that particular error has plagued implementations of Heap's algorithm ever since. Ironically, the error causes the algorithm to both run more slowly and to generate an incorrect sequence in which consecutive permutations sometimes do not differ by a single swap.

I have a certain affinity to Heap's algorithm because a few years ago, a question appeared on StackOverflow asking for help with that algorithm; the poster had carefully implemented the algorithm based on pseudocode in Wikipedia, and discovered that their code did not work as expected. In the course of reviewing the code, I soon realised that the poster's code was an entirely accurate implementation of the Wikipedia write-up, and in the course of trying to validate Wikipedia, I tracked down the history of the error which I summarised in the preceding paragraph. A Wikipedian noticed the answer and fixed the Wikipedia page. (Constant vigilance is necessary, however; every couple of months some aspiring computer science expert compares the pseudocode on Wikipedia either with Sedgewick's buggy slide or with one of the many buggy implementations floating about the internet, and "corrects" the Wikipedia page.)

The beauty of Heap's algorithm is the simplicity of enumerating the swaps. The algorithm is similar to a lexicographic algorithm, in reverse, in that it always does a complete permutation cycle of a prefix of the elements before changing the next element. So the higher index of the swapped elements follows a kind of factorial variant on the ruler function, in which element `i` appears every `i!` iterations (except for the iterations which are multiples of a larger factorial). The lower index follows an only slightly more complex pattern: for prefixes with an odd number of elements, the lower index is always 0; for prefixes with an even number of elements, the lower index starts at 0 and is sequentially incremented. So, for example, in the case of a four element permutation sequence, the swaps are:

```
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0
1 2 1 2 1 3 1 2 1 2 1 3 1 2 1 2 1 3 1 2 1 2 1

```

(Note that the element with index 3 appears as the larger index every 3! == 6 iterations, and the element with index 2 appears as the larger index every 2! == 2 iterations, except the ones which have already been taken by index 3.)

This sequence of pairs of indices is very easy to produce recursively, but one really wants it as a sequence. There is a non-recursive algorithm which effectively involves maintaining an explicit stack, but since the published algorithms tend to mutate this stack, I chose to use the recursive algorithm. In many Scheme's, one would use some kind of continuation to turn the recursive algorithm into a sequence, but since clojure doesn't have continuations (as far as I could see), I did it with nested calls to `mapcat`, the same approach as is taken by clojure's `tree-seq` standard library function.

Once you have the list of pairs of indices to swap, they can be repetitively (and lazily) applied to permutations by using `reductions`, which generates the result of successively applying a sequence of values to a seed value, using an arbitrary binary function. You can see that in the last line, where `reductions` is applied to the sequence generated by `swaps` using the `swap-v` function to turn each successive permutation into the next one.

I hope that's enough narrative to explain the (possibly non-idiomatic) clojure program which I came up with:

```
(letfn [(even-swaps [n]
            (if (= n 2) [[0 1]]
              (drop 1 (mapcat (fn [i] (cons [(- i 1) (- n 1)]
                                            (odd-swaps (- n 1))))
                              (range n)))))
          (odd-swaps [n]
            (drop 1 (mapcat (fn [i] (cons [0 (- n 1)]
                                          (even-swaps (- n 1))))
                            (range n))))
          (swaps [n]
            (cond
              (< n 2) '()
              (even? n) (even-swaps n)
              :else (odd-swaps n)))
          (swap-v [v [i j]] (assoc v i (v j) j (v i)))]
  (defn heap [sq]
    (let [v (vec sq)]
      (reductions swap-v v (swaps (count v))))))

```

Sample output:

```
user => (run! prn (heap '(a b c d)))

[a b c d]
[b a c d]
[c a b d]
[a c b d]
[b c a d]
[c b a d]
[d b a c]
[b d a c]
[a d b c]
[d a b c]
[b a d c]
[a b d c]
[a c d b]
[c a d b]
[d a c b]
[a d c b]
[c d a b]
[d c a b]
[d c b a]
[c d b a]
[b d c a]
[d b c a]
[c b d a]
[b c d a]

```
> 4 votes

---
Tags: functional-programming, permutations
---


# Question
Title: How can we prove Schwartz Zippel PIT is applicable to natural polynomials?
The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it?

Perhaps: SZ shows natural polynomials are equal iff it shows those polynomials are equal over integers. Integer polynomials are equal iff some sequence of algebraic manipulations transforms one into the other. Since these manipulations do not involve subtraction for our case (because no negatives), if they transform integer polynomials, they will also transform two natural polynomials.

But is that a proof? Is it even the right idea?

---

This question is based on the answer to Is there an efficient algorithm for expression equivalence?

We have two polynomials over the natural numbers. Are they equivalent?

If we take the same polynomials over integers (or some other ring)

$$f=g \implies f-g=0$$

But the reverse is not true, because $f-g$ may have roots, i.e. be zero without $f$ and $g$ being equal. The Schwartz Zippel lemma say how likely we are to have hit a root by chance, with a ramdom guess. By making repeated guesses we can be as sure as we like that we didn't get a root every time, (And if we ever get a non-zero, we know $f\neq g$.)

I've tried to simplify the question here, to focus on just one aspect, but maybe I've got it wrong and/or omitted important details.

# Answer
> 2 votes
Suppose that $P$ is a multivariate polynomial with integer coefficients. Then $P$ vanishes on all natural inputs iff it vanishes on all integer inputs. You can prove this by showing that if $P$ is not the zero polynomial then there is a natural input on which it is non-zero. This, in turn, you can prove by induction on the number of variables.

The base case is when $P$ is a univariate polynomial. In this case it is not hard to check that $P$ is non-zero for sufficiently large integer input. Suppose next that $P$ is a $(d+1)$-variate polynomial. Choose one variable $x$ which appears in some monomial of $P$, and write $P$ as a univariate polynomial whose coefficients are $d$-variate polynomials. Suppose that the highest power of $x$ that appears in $P$ is $x^n$, and that the corresponding coefficient is the $d$-variate polynomial $Q$ in the other variables. The induction hypothesis shows that there is an input on which $Q \neq 0$. Applying the base case again, we find a non-zero input for $P$.

# Answer
> 1 votes
You want to know if you can show two *natural* polynomials are equivalent by showing that the same polynomials are equivalent, if taken to be *integer* polynomials.

(This is so you can use subtraction in $P-Q=0$, to check for $P=Q$, even though $P,Q$ are *natural* polynomials).

**Definitions** By natural (or integer) polynomial, we mean the coefficients are naturals (or integers); and the inputs and outputs are naturals (or integers) - i.e, they are functions with natural (or integer) domain and range.

**Steps** Firstly, taking these purely as expressions (ignoring inputs and outputs), polynomials with natural coefficients are a subset of polynomials with integer coefficients (because $\Bbb N \subset \Bbb Z$). Therefore, every *natural* polynomial expression is also an *integer* polynomial expression.

Next, if we have two *integer* polynomial expressions which have *natural* coefficients (so they are also *natural* polynomial expressions), and they give the same *integer* values for all *integer* inputs, then they must also give the same outputs for all *natural* inputs (again, because $\Bbb N \subset \Bbb Z$). This covers *natural* **inputs**.

Finally, we want to show that the **outputs** will also be *naturals*. Because the coefficients and inputs are *natural*, and polynomials are calculated by addition and multiplication of coefficients and inputs, and addition and multiplication are closed over *naturals*, the output will also be *natural*.

**Conclusion** Therefore, we have shown that if two polynomials with *integer* coefficients, inputs and outputs are equivalent, then (assuming these particular coefficients are also *natural*) the same two polynomials with *natural* inputs and outputs are also equivalent. Thus, we can use equivalence of *integer* polynomials to show equivalence of *natural* polynomials (specifically, we can use $P-Q=0$ to check for *natural* polynomial equivalence, even though subtraction isn't closed over *natruals*).

BTW I haven't shown that two polynomials being equal for all possible inputs means they are equivalent, but I think that's the definition, isn't it? By "equivalent", I mean things like $a+ab+b=a(1+b)+b$, and whether $a+ab+b - (a(1+b)+b) = 0$ for all values of $a,b$.

PS This procedure, of checking a *natural* polynomials with *integers*, reminds me of some differential equations, with real coefficients and real solutions, but can only be solved by using complex numbers in between.

---
Tags: decision-problem, polynomials
---


# Question
Title: Why does the Turing Machine allow for multiple final states?
Why does the Turing Machine allow for multiple final states when it would be simpler yet equivalent to work with just one? Why allow additional unnecessary states?

Is there some historical reason for this? Is the concept of multiple final states useful in any way? (Perhaps something akin to the ease of use of multi-track Turing machines, even though they're equivalent to standard ones?)

# Answer
I've never seen a definition of Turing machines that allows multiple final states. All the definitions I've seen either have a single "halt" state or one "halt and accept" state and one "halt and reject" state.

There's no benefit to having multiple final states, though there's no real harm, either. In a finite automaton, it makes sense to have multiple final states because the automaton terminates when it runs out of input and whether or not the last state is final determines whether or not it accepts its input. (I prefer the term "accepting state", for this reason.) But, for Turing machines, the machine halts precisely when it enters a final state, regardless of what's happening on the state. So, if you have a Turing machine with multiple final states, you could just delete all but one of them and rewrite the transition function to jump to the one that remains, instead of the ones that were deleted.
> 2 votes

# Answer
The formal definition of a standard Turing machine $M$ is as follows (from *An Introduction to Formal Languages and Automata, 6e - Peter Linz*): $$M = (Q, \Sigma, \Gamma, \delta, q\_0, □, F)$$

Aside from the other elements, $F$ is the symbol that denotes the finite set of accepting (a.k.a. final) states, and $F \subseteq Q$.

There is no restriction that states how many accepting states a particular Turing machine must have. The machines will differ from problem to problem. Nor is there any statement that states having a single accepting state is the best, and that other accepting states are "unnecessary."

I'm not sure if this is comparable to multi-track Turing machines vs. standard Turing machines, though. As you said, multi-track Turing machines are usually for the sake of simplicity and are equivalent to their standard counterparts, whereas the number of final states is usually a necessity depending on the language. The two seem to be fundamentally different issues to me.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: proof of correctness for greedy knapsack algorithm
I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement 1 if statement 1 ≥ statement 2 but I don't really know how. Any help on this matter will be really appreciated. Thanks!

Statement 1 and Statement 2 refers to the red highlighted boxes, from the attached picture, tagged as 1 and 2 respectively.

Original source: http://oucsace.cs.ohiou.edu/~razvan/courses/cs4040/lecture15.pdf

# Answer
Slides are not a substitute for a textbook or careful exposition. This is especially true when reading a proof. Slides are intended for presentation in real-time, and as a result often leave out some details. If there is some aspect you don't understand when reading a set of slides, usually the best thing to do is to find a proper *written* exposition of the subject -- usually a textbook (but sometimes written lecture notes can be adequate, if written in enough detail).

In this case, on the previous slide, the statement of the theorem mentions "nonincreasing order of $p\_i/w\_i$", which means that $p\_1/w\_1 \ge p\_2/w\_2 \ge \cdots$. In particular, $p\_k/w\_k \ge p\_i/w\_i$ when $k\<i$. The inequality you are referencing then follows.
> 1 votes

---
Tags: correctness-proof, greedy-algorithms, knapsack-problems
---


# Question
Title: Is there a meaningful difference between O(1) and O(log n)?
A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n\<2^{64}$. If I somehow had an array of $2^{1000}$ elements to process, even an $O(1)$ operation such as an index lookup will start to take longer as the index has to be calculated in multiple operations. I think it will take at least $O(\log n)$.

Similarly even if an algorithm has $O(\log n)$ complexity, $\log n$ cannot possibly grow larger than about a hundred, so could be ignored as no larger than a small constant.

So, is it really meaningful to treat $O(1)$ and $O(\log n)$ as different?

The same applies of any difference of $\log n$, like between $O(n)$, $O(n\log n)$ and $O(n/\log n)$.

# Answer
> 12 votes
There are actually all sorts of cases where $\log n$ gets way bigger than 100. For example, if you're working with variable-length integers - say, for cryptography - $\log n$ represents the number of bits in the integer, which can get up to 4096 or higher in practice. Those bits will be spread out over many machine words, so the $\log n$ term refers to how many machine words the number occupies and therefore definitely has an impact on the runtime.

Similarly, $O(1)$ does not mean "constant time only if $n \< 2^{64}$." Yes, the computer has a fixed word size, but that doesn't mean that an $O(1)$-time algorithm given a gigantic input can't run in a fixed amount of time. Taking large integers as an example, consider the problem of checking whether an integer is even or odd. That just requires you to look at the last digit, which takes time $O(1)$ even if the number is spread out over thousands of machine words.

The last detail is that typically, we assume that we work with a machine model where the word size scales with the log of the size of the input. This allowance a to safely assume that you can do array accesses in time $O(1)$ because array indices are assumed to fit into a constant number of machine words.

# Answer
> 7 votes
There are several answers to your question. The first is: on such a finite machine, asymptotic notation makes no sense at all, and all algorithms have finitely bounded running time. That's a rather boring model, though.

> so could be ignored as no larger than a small constant.

Why is 100 small? If my computer booted 100 times longer than it does I would be quite upset. Moden algorithm engineering fights for percents, and in scientific computing probably for fractions of that!

Also, don't forget that your logarithmic term may have another constant factor assigned to it. What if the running time is $\sim 10^{-10} \cdot n + 10^6 \cdot \log n$?

> The same applies of any difference ...

There *are* people who dismiss polylogarithmic factors, probably for similar reasons than you do. They use the *soft* Landau notation to hide them away conveniently.

# Answer
> 2 votes
For not very large n, log n can be around 20. A factor log n matters about as much as it matters to have a computer built in 2016 and not one built in 1999.

On the other hand, O (n log n) can be faster than O (n) for practical n if the constant factor in the O (n) algorithm is say 50 times larger than for the O (n log n) algorithm.

A factor log n for say n ≥ 100 cannot be ignored *if everything else is equal*. Sometimes everything else *is* equal, sometimes it isn't.

# Answer
> 1 votes
Saying $O(\log{}n)$ can't get above about 100 doesn't make sense when talking about about Big-O notation. The "$\log$" in $O(\log{}n)$ doesn't refer to any specific base. Big-O is about how the computational cost grows as $n$ gets larger, within a constant factor. Changing the base just changes that constant factor, so I can make the argument that $O(\log{}n)$ can be as arbitrarily large (or small) as you want to make it. But the growth stays the same! That's what's important when discussing Big-O. If you double $n$, the cost still increases in an $O(\log{}n)$ algorithm, unlike an $O(1)$ algorithm, but much less than the cost increase in an $O(n)$ algorithm.

The cool thing about $O(\log{}n)$ is that increasing the problem size makes it "easier" to increase the problem size even further. Increasing the problem size from $10^2$ to $10^3$ will increase the computational cost by $1/2$, but going from $10^3$ to $10^4$ will only increase the cost by $1/3$. So for very large $n$ the additional cost keeps decreasing, but it never reaches $O(1)$.

So no, $O(1)$ and $O(\log{}n)$ are not the same. In practice, which is faster will likely be problem dependent, but if it gets large enough $O(1)$ will win.

# Answer
> 1 votes
There can be. The obvious case is when $n$ is really huge. But there is another case which is very common. It depends on the constants involved. Let me give an example from data structure: a red-black tree has operations which are $O(\lg n)$. This seems good enough if the constants are small. However think about the situation where we have a huge amount of data in each node and we cannot keep the whole tree in the memory and have to use hard disks to store it. The access time to hard disk is huge compare to memory. Every access counts. If we have to access $\lg n$ times to the disk to get the value of the block we want it would be a huge drop in performance. That is the reason for data structure like B-trees. Not only $\Theta(\lg n)$ and $\Theta(1)$ differ a lot in practice even $2$ access and $3$ access can have a significant effect.

# Answer
> 0 votes
Consider a function:

```
int foo(int n)
{
    //mysterious code details
}

```

It can be implemented in a few different ways, and you've managed to come up with an easy algorithm in O(log(n)) but you think there might be a tricky one in O(1). You choose the easy path because there's not much of a difference, right?

Well, you're not looking at the big picture. Sean, the guy in the cubicle next to you, likes your function foo and decides he's going to use it in his code:

```
void main()
{
    print(bar(9999999999999));
}

int bar(int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                for (int l = 0; l < n; l++)
                {
                    sum += foo(i) * foo(j) * foo(k) * foo(l);
                }
            }
        }
    }
    return sum;
}

```

Do you think it matters now?

# Answer
> 0 votes
The assumption "A computer can only process numbers smaller than say $2^{64}$" does not hold in the frame of asymptotic behavior computation. $n$ is considered unbounded and the algorithm runs on a theoretical computer with unlimited resources.

It is not the peculiar values of $f(n)$ that matter, but how the function grows with $n$.

If you take the finiteness of the representation into account, *all* algorithms are running in time $O(1)$, even the super-duper-exponential ones.

And in practice, an $O(1)$ algorithm can run much slower than a $O(\log(n))$ one.

May sound weird, but that's the way it is.

---

**Final remark:**

On modern machines, the access times to memory really depends on the number of elements. This effect has an effect much larger than $\log n$, so that relying too much on the *idealized* computer model is misleading.

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


# Question
Title: Relation between "undecidability of arithmetic" and "godel's incompleteness theorem"?
There is a theorem that states that arithmetic is undecidable: i.e. $Th(\mathcal N)$, the set of all sentences in the standard arithmetic structure $\mathcal N=(\mathbb N,+,\cdot , 0,1)$ where the symbols are interpreted in the standard way, is undecidable.

Godel's first incompleteness theorem states that there does not exist a set of axioms from which we can prove all true arithmetic statements: There does not exist a set of first order formula's $\Phi$ that is consistent and decidable, such that for any first order $(+,\cdot,0,1)$ sentence $\phi$, we have $\Phi\vdash\phi$ or $\Phi \vdash \neg \phi$. By the completeness theorem we could have instead written "$\Phi\models\phi$ or $\Phi \models\neg \phi$"

But since we can construct a first order proof system that is complete, in the sense that all valid sentences can be proven, doesn't this boil down to the same thing?

**Isn't godel's incompleteness theorem simply an implication of the undecidability of arithmetic?**

# Answer
> 1 votes
Yes, if we know that $Th(\mathcal{N})$ is undecidable then we know that it is not computably axiomatizable, and in particular we know that no computably axiomatizable theory consisting only of true sentences of arithmetic is complete.

*Here I'm adopting a Platonist view with regards to $\mathcal{N}$: I assume that "the" set of natural numbers exists, and "true" means "true in that structure*.

However, there are a couple points here:

* How do we know that $Th(\mathcal{N})$ is undecidable?
* What about *strengthenings* of Godel's theorem, like "No consistent computably axiomatizable theory of arithmetic extending PA (or even ) is complete"? *(This is an extension due to Rosser of the theorem as originally proved by Godel, but is basically just one clever idea on top of the usual proof.)*

Ultimately, (1) really already uses the key idea/argument of Godel's theorem, while (2) points out the limitations of measuring the complexity of a single structure.

So this shouldn't be construed as trivializing Godel's theorem in any way; in particular, I object to the word "simply" in the last line.

---
Tags: undecidability, arithmetic, incompleteness
---


# Question
Title: Balance groups based on average, element constraints and size
It's a complex situation, where I want to balance *groups* of numbers based on the *average* of these numbers, while keeping the *group size* unchanged and *not breaking elements constraints*.

Let me explain in detail what I mean:

I need to **switch** elements between the groups in order to **balance the group average**. However the elements with the **same color needs to stay in the same group**, and the groups **must not change size**.

What would be a good approach for solving this problem? I'm using ***c++*** to code a matchmaking system for a game, and that's the mathematical problem I'm stuck with currently.

*My knowledge of mathematical notations are quite weak, so I would prefer some sort of **pseudo-code** as answer (if possible)*

# Answer
This is a combinatorial optimization problem. It is NP-hard (it is easy to see it is as hard as the partition problem). Consequently, you should not expect any general problem that is efficient, scales to large problem sizes, and always returns the optimal answer.

Instead, you probably will want to use some kind of heuristics. One approach worth considering is to use integer linear programming or some variant of it. If your objective function is minimize the spread between largest group average and the smallest group average, then the problem can be encoded as an instance of integer linear programming (ILP) and then you could use an off-the-shelf ILP solver. If your objective function is to minimize the standard deviation of the group averages, then the problem can be encoded as an instance of integer quadratic programming (MIQP) and then you could use a MIQP solver. You might want to run them for a limited amount of time and use the best solution found within that time period, rather than run as long as needed to find the exact optimal solution.

The encoding of the problem as integer programming is tedious but fairly straightforward. You introduce zero-or-one integer variables $x\_{i,j}$, with the intended meaning that $x\_{i,j}=1$ means that the $i$th item is assigned to the $j$th group. (When you have multiple elements of the same color, treat them all as a single item with the same value of $i$; they just add more than one to the number of elements in that group.) Then the number of elements in the group is a linear function of the $x$'s, and the group average of each group is a linear function of the $x$'s, so you can write down constraints for these to be a valid solution as linear inequalities.
> 1 votes

---
Tags: algorithms, mathematical-programming, pseudocode
---


# Question
Title: Is the halting problem theorem really proven
Here is a popular proof of the halting problem theorem:

Suppose there exist a procedure h(x, y) so that for any procedure p(x) and any data d, the execution of h(p, d) will halt, where halt means return by a "return" statement so a system crash means doesn't halt, and if h(p, d) returns 1 then the execution of p(d) will halt, otherwise h(p, d) returns 0 then the execution of p(d) will not halt.

Consider the following program:

```
001 int h(x, y); // suppose the detail of h(x, y) is in a library.
002
003 int c(x) {
004   if (h(x, x) != 0) {
005     while(TRUE) {
006       ;
007     }
008   }
009   return 0;
010 }
011
012 int main() {
013   h(c, c);
014   c(c);
015 }

```

At line 13, if h(c, c) doesn’t halt, this is in contradiction with the claim of h(x, y).

If h(c, c) at line 13 returns 1, then when c(c) at line 14 is run, at line 4, the h(x, y) is in reality h(c, c) so it should return 1. Then, the program will go to line 5 which will start a perpetual loop. That is, c(c) will not halt which is in contradiction with h(c, c) returns 1 predicates c(c) will halt.

In another side, at line 13, if h(c, c) returns 0, the execution of line 4 when line 14 is running will be followed by the line 9. And c(c) will returns 0 which is in contradiction with h(c, c) returns 0 predicates c(c) will not halt.

So, either h(c, c) will not halt or it cannot predicate the behavior of c(c). So, such an h(x, y) as what is claimed cannot exist. That is, the halting problem is unsolvable.

But now the question is, what is the reason for the step "If h(c, c) at line 13 returns 1, then when c(c) at line 14 is run, at line 4, the h(x, y) is in reality h(c, c) so it should return 1" ?

The proof uses, in reality and implicitly, the hypothesis that the return value of h(x, y) depends uniquely on its parameters. Let's call this hypothesis the hypothesis h(c, c) = h(c, c) here. So, the proof proves in reality only that if h(x, y) depends only on its parameters, then h(x, y) cannot solve the halting problem of c(c), instead of proving the halting problem theorem.

To explain why h(x, y) should not depend only to its parameters, we can look at a metaphor: there are three persons P, C and A. C challenges P by saying “you cannot predicate whether I’ll go to bed this evening before or after 10 PM, let A be the arbiter”. Suppose it’s known by everyone that the strategy of C is to do what is contrary to whatever will be said by P. This is similar to the behavior of c(x) in the proof. If P announces his answer aloud, that is, gives the same answer to both C and A as supposed by the hypothesis h(c, c) = h(c, c), P will lose. But if P doesn’t announce his answer aloud, instead, he answers “before 10 PM” when he is asked by C and “after 10 PM” when he is asked by A, then, P will win. To require P to announce his answer aloud is just unfair. To limit the h(x, y) to depend uniquely on its parameters would be incorrect because it imposes a non relevant limit.

Moreover, the meaning of the return value of h(x, y) should be more precisely defined: its return value predicates the answer to the halting problem of p(d) if it were called at where h(p, d) is called.

With this more precisely defined h(x, y), it could be known that if c(c) were called inside c(c), it will not halt so the h(c, c) at line 4 should return 0. Then, the c(c) at line 14 will halt because the h(c, c) at line 4 returns 0. Then, the h(c, c) at line 13 should return 1. That is, h(x, y) can solve the halting problem of c(c) if it doesn't depend uniquely on its parameters.

Finally, to let h(x, y) doesn't depend only on its parameters is in reality possible. Who has some programming experiences would understand that it’s possible to construct the procedure call history by analyzing the system stack. In fact, most of the debuggers provide this service. That is, when the execution of a program is paused in a procedure, it’s possible to obtain a list of 2-tuplets (P(N), A(N)) N=0, 1, …, M, where P(N) is a procedure name, A(N) is the line number of the statement in P(N) at where P(N+1) is called. And it’s in P(M) at A(M) that the paused procedure was called.

If h(x, y) analyze also the system stack, then in the h(c, c) at line 13, it can know that it's called by main() at line 13. It's not called inside an execution of c(c). So, it should return the result of a complete analysis of c(c), that is, 1, to predicate c(c) will halt. When c(c) at line 14 is run, the h(c, c) at line 4 can know that main() at line 14 called c(c), and then it was called by c(c) at line 4. That is, it knows that it's called in an execution of c(c). So, it should return 0.

So, the ultimate question is, does the well known proof really proves the halting problem theorem ?

# Answer
Any proof of the undecidability of the halting problem is specific to some model of computation. The proof is usually stated using Turing machines, which don't have call stacks or any other bells or whistles. For Turing machines, the assumption that the behaviour of any program (or, rather, machine) depends only on its inputs is completely valid.

You've changed the model of computation to some other system, which does have call stacks and possibly also bells and/or whistles, but you've not updated the proof to take this into account. In particular, you should consider the call stack to be a part of the input to the procedure, since you've proposed a mechanism by which it affects the output.
> 14 votes

# Answer
As David Richerby says, the details of the proof of the Halting Problem depend on the model of computation you're using. A proof using the lambda calculus will look very different from a proof using the Game of Life, though both proofs exist and work.

In this case, you seem to be using Turing machines as your model of computation. And a Turing machine has no concept of a program stack or subroutines: its output really does depend only on its input. Anything else, like a program stack, has to be either built into the machine (and therefore constant) or part of its input.

The key here is what's called the Universal Turing Machine Theorem, which basically says "given a Turing machine that computes `f(x)`, and a Turing machine that computes `g(x)`, you can build a Turing machine that computes `f(g(x))`". Here, these are functions in a mathematical sense: every input corresponds to one and only one output. The details are rather technical, but it involves using a Turing machine to simulate another Turing machine. (In fact, you can make a Turing machine that can simulate *any* other Turing machine. Hence "universal".)

So the reason why `h(x,x) = h(x,x)` is because `h` is at heart a Turing machine, and the output of a Turing machine depends only on its input.
> 4 votes

---
Tags: logic, halting-problem
---


# Question
Title: Minimum square side length to enclose n circles of radius r
I thought of a problem but have no idea how to solve it. The problem is as follows:

Given 2 numbers, ***n*** and ***r***, find the side length (***S***) of the smallest square that encloses ***n*** circles each of radius ***r*** without any overlap among any of the circles.

I though about a greedy approach that would find the optimal position for each circle locally and placing it before moving onto the next one, but realized that it would be difficult without being given definitive positions of each of the circles. Is there a solution to this problem?

# Answer
> 2 votes
This is known as circle packing in a square. The Wikipedia article I link to has a citation to this webpage, which lists the best packings known for $n \le 10000$, and also has many references to papers that study this problem. I suggest studying them to see what methods they have used.

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


# Question
Title: stable marriage/residency problem with multiple matches
Consider the stable marriage problem, where both sides want to match with multiple individuals from the other side (perhaps a fixed number, or perhaps within some range). Something like, if doctors could choose to go to more than one medical school at the same time.

Is there a variation on the deferred acceptance algorithm to handle this generalization? Can I just have each "doctor" propose to n hospitals at each step, where n is the number of hospitals he is trying to attend at once? Also, what if hospitals do not have preferences?

# Answer
> 1 votes
Suppose you have a doctor that you want to assign to three hospitals. Replace that doctor by three copies of him. In other words, instead of a single vertex for Dr. Smith, you have three clones, Dr. Smith #1, Dr. Smith #2, and Dr. Smith #3. They all have the same preference list.

Suppose you have a hospital that wants two doctors. You can do the same thing: instead of a single hospital, you have one entity per open position at that hospital. They all have the same preference rankings.

Now use the standard stable marriage algorithm on the resulting set of clones and open positions. This will find a stable matching that obeys the multiplicity constraints you identified; that follows directly from the correctness property of the standard algorithm.

---
Tags: algorithms, optimization
---


title: Type-0 grammar and terminal symbols

text:
# Question
Title: Type-0 grammar and terminal symbols
The question is pretty short, but I've been thinking about it quite some time: Are terminal symbols that are not in the defined alphabet still valid?

# Answer
No. The grammar is defined like this:

G = (V,SIGMA, R, S) where V is your set of variables (non-terminals) and SIGMA is your alphabet (terminals). All the symbols you are allowed to use in the substitution of a rule are the union of V and SIGMA. If you simply cannot use a symbol out of that set, since it does not exists in the context of your grammar.
> 1 votes

---
Tags: automata, finite-automata, chomsky-hierarchy, termination
---


# Question
Title: Assumption: A PSPACE-hard problem can be solved in polynomial time
Under the assumption that a PSPACE-hard problem `A` can be solved in polynomial time, is the following argumentation valid?

Since every problem in PSPACE can be reduced to `A` in polynomial time, every problem in NP which is a subset of PSPACE is included. That means that each Problem in NP is solvable in polynomial time and therefore P = NP.

Since coNP is a subset of PSPACE as well, we can argue that every problem in coNP can be reduced to `A` and therefore be solved in polynomial time as well, which means that P = coNP.

Therefore we can say that P = NP = coNP.

I don't see a problem with this argumentation at the moment, but it seems a bit too simplistic to me, so is this a valid way of arguing for the equality above?

# Answer
> 4 votes
Your argument is perfectly fine. However, you actually do not even have to argue with polynomial reduction. Since $\textsf{P} \subseteq \textsf{NP}, \textsf{coNP} \subseteq \textsf{PSPACE}$, under the assummption that there is a $\textsf{PSPACE}$-hard problem solvable in polynomial time (i.e. it is in $\mathsf{P}$), you also have $\textsf{PSPACE} \subseteq \mathsf{P}$. Now $\textsf{NP}, \textsf{coNP}, \textsf{PSPACE}$ are sandwiched in $\mathsf{P}$ and thus, equality holds for the $\subseteq$ relations above.

---
Tags: complexity-theory, complexity-classes
---