title: Universal memcomputing machines (UMM)

text:
# Question
Title: Universal memcomputing machines (UMM)
This paper on memcomputing seems like a really big deal, but it doesn't seem to be particularly popular. They prove that their UMM can solve NP problems in P, although they don't claim P = NP. In their next paper, they go on to build a physical model of this UMM with moderate success. Does this mean P=NP?

# Answer
The authors suggest a new computation model that solves NP problems in polynomial time. Another such model has been known for a long time – non-deterministic Turing machines. They can also solve NP problems in polynomial time. In fact, one common definition of NP is the set of problems solvable by non-deterministic Turing machines in polynomial time.

If the authors succeed in realizing their machine physically (which is doubtful), then this shows that the "efficient Church–Turing thesis", which states that all physically realizable computation models can be simulated by a Turing machine using only polynomial overhead – is false. Another candidate for refuting this thesis is quantum computers, but they are conjectured not to be able to solve all NP problems in polynomial time.
> 5 votes

# Answer
First, no this would not mean $P=NP$. That is a concept framed in the context of Turing machines. While it's been shown that UMMs are as expressive as Turing machines, it's not clear whether a physical realization of them would be Turing equivalent or simply *more* expressive than a Turing machine. If equivalence were to be proved (I don't think it's the case), then $P=NP$, otherwise a successful realization would have no implications for the question.

I can offer some context from my anecdotal experience about popularity: It's true that this wasn't particularly popular some time ago, but the idea is gaining traction, if you measure it by the attention it's getting in relevant fields. For instance, it's much easier for us to get NSF, DARPA, DOE funding now than 4-5 years ago. It seemed for a while that people would simply refer to Scott Aaronson's blogpost, which talked about a specific analog instantiation of UMMs, and then assume UMMs in general are a "non-serious" attempt at solving NP-complete problems in polynomial time. This ignores that the digital versions of UMMs are scalable (digital output doesn't require exponentially increasing precision to resolve), but most CS theorists would likely expect exponential complexity to still show up somewhere else (we disagree based on the physics involved and preliminary evidence is promising). To be fair to Scott, I don't think he was aware that digital versions existed. While the paper he criticized mentions it, it's easy to miss.

Right now, the idea is still not particularly popular among CS theorists (especially complexity theorists), who generally operate under the assumption that the extended Church-Turing thesis is true. We find less resistance from computer engineers, the unconventional computing community, and physicists. There are actually some good physical reasons to believe that UMMs are realizable (in a way that scales, see digital MemComputing machines, DMM).

For more information on the physical reasons we think this will be successful as well as empirical results for applications using simulated DMMs and more, see Di Ventra's textbook MemComputing: Fundamentals and Applications.(Published by Oxford University Press, so rest assured that it's peer reviewed).

A useful analogy to understand the power of UMMs is to compare and contrast it with quantum computation, which also leverages physics to compute (primarily quantum entanglement as opposed to a UMMs strong coupling that emerges from memory-dynamics, those concepts are somewhat analogous). For a comparison of this kind, see this article.
> 3 votes

---
Tags: complexity-theory, computability, turing-machines, computer-architecture
---


# Question
Title: Count the number of lines in binary image
Consider I have the following binary image (each pixel is either 0 or 255). How to count the number of lines (they could be straight or a little curvy). For example, in the picture, there are six lines except for the circle. The goal is to compute the number of cracks and its total areas.

# Answer
> 0 votes
This is not the kind of problem you can just look at a single image and expect someone to be able to tell you how to solve it. It is likely that a solution will require considerable experimentation. It is hard to know a priori what might work.

If you want to try classical computer vision techniques, you might start by using image processing operations, such as morphological operations, thresholding, followed by skeletonization and some kind of post-processing.

If you truly had straight lines, you could use the Hough transform to find lines. However your edit makes clear that these are not straight lines.

Likely you will need to try something, see how well it works on many images, identify failure cases, hypothesize possible solutions, try multiple ideas to see if any of them help, and repeat. Given the one image you have shown us, it is possible that this task might be quite challenging and it might take a lot of effort and knowledge of computer vision to make progress on it.

In practice, a more realistic solution might be to hire MTurk workers to hand-annotate the cracks for you, or to do it manually.

---
Tags: computer-vision, image-processing
---


# Question
Title: PDA recognising all strings with a $1$ in the second half
My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says:

> Let $\Sigma = \\{0,1\\}$ and $B$ is the collection of all strings that contain at least one $1$ in the second half. To state it more precisely: $B=\\{uv\mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast} 1 \Sigma^{\ast}, |u|\geq|v|\\}$. Give a PDA that recognizes $B$. Give a diagram to describe your PDA.

My question is why do I need a PDA or really a stack for this because all I am looking at is the second half which I can just epsilon to the second half and then when I read a $1$, go to the accept state. For example if $u=1001010101$ and $v=000011$, wouldnt I just loop around for a bit for u and then epsilon over to say I am now looking at $v$. Then when I read the first $1$, I just accept. I wouldnt need to use the stack at all would I? I'm not sure if I understand it correctly or not and would appreciate any help.

# Answer
The problem with your approach is that you are not checking that $|u| \geq |v|$ - for example the string $0100$ would be accepted. Remember that the 'magic' of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to.

So in this case, you still need to check that the size of the two parts are suitable, for which we need1 a stack.

As a side note, $B$ can also be expressed as $\\{u1v\mid u \in \Sigma^{\ast}, v \in \\{0\\}^{\ast}, |u| \geq |v|\\}$, not that this really changes much, but it's a little simpler (in terms of the PDA).

**Footnotes:**

1. As Babou points out in his answer, you don't *need* a stack as such, a simple counter suffices, but you do need something beyond what a DFA/NFA can manage.
> 3 votes

# Answer
You do not need a stack to do this, but you do need a counter. A counter automaton is a PDA with only a single stack symbol (there may be a second one used only to mark the bottom of the stack, and thus test emptyness). It is a strictly weaker type of automaton.

This is needed to identify the first half of your string that you want to epsilon away.

Then, non-determinism is your friend. You read the first half of the string, and epsilon it away, as you say. But you are careful to count the length of the first half in your counter/pushdown.

They you read the second half checking it contains a 1, but also decrementing the counter to check that the "second half" has the same length as the first. If both conditions are met, you accept, else you reject.

Non-determinism is used only to decide when you have reached the middle of the string. If you do the wrong choice, your computation fails. But if the string is in the language and you do the right choice, then the compuation succeeds ... which is all you want.
> 1 votes

# Answer
Here's a sketch of a PDA which does the job:

In state $q\_0$, push the symbol `|` (a tally marker) onto the stack and consume one input symbol, or do an epsilon transition to $q\_1$.

In state $q\_1$, on input $1$, pop a tally marker and transition to $q\_2$. On input $0$, pop a tally marker and stay in $q\_1$.

In state $q\_2$, accept. For example, on any input symbol, pop a tally marker. Maybe also pop a tally marker on epsilon.

The exact behavior in $q\_2$ depends on what counts as an accepting configuration in the particular definition of DFA you're working with.

I believe this deals with all even-length strings. By the precise definition given, the second half excludes the middle character in odd-length strings. To account for this, add a transition from $q\_0$ to $q\_1$ which consumes an input symbol without changing the stack.

Why do you need a stack? As others have pointed out, other bookkeeping structures such as a counter would suffice; in fact, I'm using the stack as a counter.

A more limited but still instructive question is then: where do I rely on the stack in my specific solution? How and why would it break if the stack was removed? (In other words: instead of asking "why does every solution need a stack?" we can ask "why does this one solution need a stack?".)

The main idea of my construction is similar to yours (OP's): twiddle my thumbs while waiting for a $1$, then go to an accepting state. Of course, a $1$ in the first half of the string (or at the middle position) shouldn't cause the PDA to accept. I use the stack-as-a-counter to know (in a non-deterministic sense) whether the input symbol being consumed is in the second half of the string or not.

Without the stack-as-counter, well, I don't know what my construction would be, but if it was coherent it probably would accept $10$ even though it shouldn't.
> 0 votes

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


# Question
Title: Is complexity of computing $2^{2^n}$ in P?
According to this answer, given input $2^n$ (and thus input size $n$), this problem is not computable by a deterministic Turing machine in number of steps polynomial in the input size (though it is polynomial time computable under the Arithmetic model). Does this imply that the decision version of the problem is not in $P$?

# Answer
You did not specify what is the decision version of the problem you are interested in. I assume that it is the following:

Input: A pair $\langle x, k \rangle$ Where:

* $x$ is an integer of the form $2^n$ for some non-negative integer $n$ (encoded in base $2$).
* $k$ is a positive integer.

Notice that the input size is $\Theta(n + \log k)$.

Output: True if $2^x \le k$, false otherwise.

This problem is in $\mathsf{P}$. You can compute $2^x$ by iteratively multiplying $2$ up to $x$ times. As soon as the current product exceeds $k$, return false. If this is not the case after the $x$-th iteration, return true.

Notice that, in each iteration, the current product is at most $2k$. Therefore a single iteration can be implemented in time $O(\log k)$. There are at most $O(\log k)$ iterations (since the product doubles at each iteration) and hence the overall time spent is $O(n + \log^2 k)$, which is polynomial in the input size.
> 2 votes

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


title: Is regex with lookaround still regular?

text:
# Question
Title: Is regex with lookaround still regular?
It is well known that "regex" with back-reference is not a regular expression anymore. For instance, `(.*)\1` matches any string repeated twice. However, is it possible to construct a DFA for regex with lookaround?

I found this question and particularly this answer, which says

> Look-ahead and look-behind are nothing special in the world of finite automata as we only match whole inputs here. Therefore, the special semantic of "just check but don't consume" is meaningless; **you just concatenate and/or intersect checking and consuming expressions and use the resulting automata.**

(emphasis mine)

However, I'm not quite sure how to intersect the checking and matching automata. For simple cases such as `foo(?=bar)`, I can just concatenate them (`foobar`). But this won't work for more complex cases such as `foo(?=bar)(?=baz)`: since lookahead will not consume the input, what follows `foo` must match both `bar` and `baz`.

This answer suggests using Alternating Finite Automaton, but after reading through the tremendously ~~un~~helpful Wikipedia page, I am totally confused how this can help turn lookarounds into plain old DFA.

# Answer
> 4 votes
Lookaround assertions do not extend expressive power of regular expressions: it is still the set of regular languages. See \[1\] for proof. There is also a reference to the paper \[2\] where they prove this by conversion to a DFA.

\[1\] Berglund M, van der Merwe B, van Litsenborgh S (2021) Regular Expressions with Lookahead. JUCS - Journal of Universal Computer Science 27(4): 324-340. https://doi.org/10.3897/jucs.66330

\[2\] Takayuki Miyazaki, Yasuhiko Minamide, Derivatives of Regular Expressions with Lookahead, Journal of Information Processing, 2019, Volume 27, Pages 422-430, Released on J-STAGE June 15, 2019, Online ISSN 1882-6652, https://doi.org/10.2197/ipsjjip.27.422

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


# Question
Title: Prove a subset of a regular language is regular, context-free but not regular or not context free
I've been tasked with solving this problem, but I'm not sure where to begin:

> Let $L$ be a context-free language. $L'$ contains all the words that belong to $L$ which can't be defined as $z=uvwxy$, for which $|vx|\>0$ so that $\forall i \ge0$ we get $uv^iwx^iy\in L$.
>
> Is $L'$ a regular language, context free but not regular or not context free? Prove your answer.

So the immediate thought that occurs to me, this doesn't follow the pumping lemma for context free languages, but I suppose the answer isn't THAT immediate, right?

EDIT: I see now that they omitted the part where exists a natural number $n$ for which $|vwx|\<n$, but I cannot seem to connect this information with the proof.

Can you please give me some more insight to the problem? Thanks!

# Answer
Since $L$ is a context-free language, there must be some integer $p \ge 1$ such that any word $z \in L$ such that $|z| \ge p$ can be written as $z = uvwxy$ with $|vx|\>0$ and $uv^iwx^iy \in L$ for all $i \ge 0$.

This means that no word $z$ with $|z| \ge p$ can be in $L'$ and hence $|L'| \le \sum\_{i=0}^{p-1} |\Sigma|^i \le p |\Sigma|^{p-1}$. Therefore $L'$ is a finite language and, as such, it is regular (and context-free).
> 2 votes

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


# Question
Title: Determine the time complexity of repeated logarithm until not greater than 1
```
    t <- n
    while t>1 do
        t <- log_2(t)

```

I tried to do it this way: $f^\text{(1)}(t)=\log\_2(t) \\ f^\text{(2)}(t)=\log\_2\log\_2(t) = \log\_2^{(2)}(t) \\f^\text{(3)}(t) = \log\_2^{(3)}(t) \\ f^\text{(j-1)}(t) = \log\_2^{(j-1)}(t) \\ f^\text{(j)}(t) = \log\_2\log\_2^{(j-1)}(t) = log\_2^{(j)}(t) $

I consider $f^{(j)}(t)$ the function $f(t)$ iterated $j$ times.

Now I need to find out $\min\\{j: f^{(j)}(t) \> 1\\} = \min\\{j:\log\_2^{(j)}(t) \> 1\\}$.

But I can't find a way to determine $j$, so I think there's a different way to calculate the complexity of this algorithm, some idea?

# Answer
The complexity in terms of the number of logarithm evaluations is expressed by the *iterated logarithm* function. There is no better expression.

Note the following values:

$$\[0,1\]\to0\\\(1,2\]\to1\\\(2,4\]\to2\\\(4,16\]\to3\\\(16,65536\]\to4\\\(65536,2.003529930406\cdots\times10^{19728}\]\to5\\\cdots$$
> 1 votes

# Answer
I got it: this algorithm has a nearly-constant complexity, specifically the complexity is $\Theta(\log^{\*}(n))$ where $\log^{\*}(n) \le 5 \ \forall n \le 2^{16}$
> 0 votes

---
Tags: algorithms, complexity-theory, time-complexity, optimization
---


# Question
Title: Unable to understand how the while loop extracts the least number of coins with given sum
I was reading this classical Coin Problem (7.1): Given a set of coin values coins = {c1, c2,..., ck} and a target sum of money n, our task is to form the sum n using as few coins as possible.

I fully understood the discussion until I encountered the last code snippet of the section *Constructing A Solution*:

```
    int first[N];  // N is sufficiently large

    value[0] = 0;
    for (int x = 1; x <= n; x++) {
       value[x] = INF;
       for (auto c : coins) {
         if (x-c >= 0 && value[x-c]+1 < value[x]) {
            value[x] = value[x-c]+1;
            first[x] = c;
         }
       }
    }

    while (n > 0) {
       cout << first[n] << "\n";
       n -= first[n];
    }

```

My doubt is pertaining to the way array *first* is storing the coin denominations and how the while loop at the last is able to extract the required coins.

For example consider this case when I have coins of denominations {1, 4, 5, 10, 20}, with each coin available as many numbers as needed. So to form a sum of **22**, optimally I need one 20 unit and two 1 units. This is what the code gives as output, when properly coded.

But I am not able to undertand how this *first* array is storing the denomination values. So to understand this I printed out this *first* arrray and got this:

> 0 1 1 1 4 5 1 1 4 4 10 1 1 4 4 5 1 1 4 4 20 1 1

And I was more confused.

In short: please explain how *first* array stores values and how the **while** loop is able to print out only the required values.

# Answer
Let us take a look at line 3 and 4 of the following part of the code.

```
1       for (auto c : coins) {
2         if (x-c >= 0 && value[x-c]+1 < value[x]) {
3            value[x] = value[x-c]+1;
4            first[x] = c;
5         }
6       }

```

`value[x]` should store the least number of coins needed to form `x`.
`value[x-c]` stores the least number of coins needed to form `x-c`.
Line 3 means, if we take coin `c` *first* and use `value[x-c]` coins to form the rest, `x-c`, we will use `value[x-c]+1` coins to form `c+(x-c)=x`. So we can set `value[x]` to be `value[x-c]+1`.

Since `first[x]` is set to `c` at line 4, we can replace `c` by `first[x]`.
**Line 3 can be read again as, in order to use the least number of coins to form `x`, we can take coin `first[x]` *first* and then use the least number of coins to form the rest, `x-first[x]`.**

---

Let us read the while loop.

Initially, the target is `n`. Treating `n` as `x` above, we see that in order to use the least number of coins to form `n`, we can take coin `first[n]` *first* (so, we will print `first[n]` by `cout << first[n] << "\n";`) and then will use the least number of coins to form `n-first[n]`.

Now the target is `n-first[n]`. This is the same situation as the initial situation. So we will set `n` to `n-first[n]`, and repeat.

---

For example, when `n=22`.

Since `first[22]=1`, we will take coin 1 first.
The target to form next is `22-1=21`.
Since `first[21]=1`, we will take coin 1 first. (In fact, this is the second coin.)
The target to form next is `21-1=20`.
Since `first[20]=20`, we will take coin 20 first. (In fact, this is the third coin).
The target to form next is `20-20=0`. No more action is needed to form `0`.
> 0 votes

---
Tags: data-structures, dynamic-programming, arrays, coin-change
---


# Question
Title: Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?
Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

Given an undirected graph `G`, is there another graph, `H`, such that:

* all vertices of `G` are in `H`
* H is allowed extra vertices not in G
* if `a` and `b` are connected in `G`, `a` and `b` are also connected in in `H` (possibly with at least some of the extra vertices in the `H` path from `a` to `b`)
* if `c` and `d` are not connected in `G`, `c` and `d` are not connected in `H`
* each vertex in `H` has degree at most 3
* the edges of `H` can be enumerated in logspace given an input `G`

Maybe this could be called a logspace reduction of G to a graph that has max degree of 3 that preserves connectivity?

# Answer
For each edge $(u,v)$ in $G$, add vertices $w\_{u,v}$ and $w\_{v,u}$ to $H$, and add the edge $(w\_{u,v},w\_{v,u})$ to $H$.

For each vertex $u$ in $G$, if $u$ has edges $(u,v\_1),\dots,(u,v\_k)$, then add edges $(w\_{u,v\_i},w\_{u,v\_{i+1}})$ and $(u,w\_{u,v\_1})$ to $H$; and add edges $(w\_{v\_i,u},w\_{v\_{i+1},u})$ and $(w\_{v\_1,u},v)$ to $H$.

I believe this $H$ satisfies all of your properties. Also, I believe it can be constructed in logspace (please check me and verify for yourself).
> 5 votes

---
Tags: graphs, space-complexity
---


title: Computing biconnected components

text:
# Question
Title: Computing biconnected components
My question relates to Problem 22.-2 in Introduction to Algorithms 3rd edition.

There biconnected components are defined as maximal sets of edges such that any two edges in the set lie on a common simple cycle. The problems that I am having are the last two tasks of this problem, namely

1. proving that biconnected components of a graph partition the nonbridge edges of the grap (where a nonbridge is an edge which can be omitted without disconnecting the graph)
2. computing the biconnected components.

The first task seems rather easy since one could argue that "any nonbridge has to lie on some simple cylce and is therefore in a biconnected component" and that "if two biconnected components were to share an edge they would be the same biconnected component since one can then construct a path through any pair of edges". However, here I find the second argument too unspecific: How would this path look like? How can I really argue about that since any edge on the constructed path might be in both components.

To make it clearer, a picture:

Clearly, I can construct such a simple cycle here always, but what if some red edges were also blue? Wouldn't that blow up the whole proof?

The problem I am having with (2) is of a similar nature. Before the problem definition in the book, the concept of articulation points is introduced. These are defined a vertices whose removal disconnect a previously connected graph.

Solutions I found on the internet of the "computing biconncted components"-task (such as the linear-time algorithm in https://en.wikipedia.org/wiki/Biconnected\_component or 22.-2 h in https://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf) argue that "removing all articulation points respectively bridges yields the biconnected components of the graph". However, if I have the following graph

a removal of x would disconnect the graph whereas a removal of y would not. However, of the remaining graph (i.e. without x), y is an articulation point and there is no simple cycle on which e and f both lie (since y has to be visited twice in every cycle meaning it is not simple anymore). So removing articulation points alone does not suffice. The same applies to removing bridges alone with the upper graph.

How would I fix these problems?

PS:

PPS:

# Answer
#### Two different biconnected components does not share an edge

Claim: Let edge $u$ lie on simple cycle $\mathcal C\_u$. Let edge $v$ lie on simple cycle $\mathcal C\_v$. $\mathcal C\_u$ and $\mathcal C\_v$ share an edge. Then $u$ and $v$ must lie on a common simple cycle.

Proof: If $v$ is on $\mathcal C\_u$, we are done. So, assume $v$ is not on $\mathcal C\_u$.

Let us visit the edges of $\mathcal C\_v$ starting at $v$ on one direction, until we reach an edge on $\mathcal C\_u$ *the first time*. We must be able to reach such an edge, since $\mathcal C\_u$ and $\mathcal C\_v$ share an edge.
Do the same on the other direction.
The edges we have visited, slightly reordered, can be seen as a path on $\mathcal C\_v$: $f\_{i+1}, f\_i, \cdots, f\_2, f\_1, v, e\_1, e\_2, \cdots, e\_j, e\_{j+1}$, where

* $i\ge0$, $j\ge0$, $f\_\*$ and $e\_\*$ are edges, and
* the sequence $P\_v$: $f\_i, \cdots, f\_2, f\_1, v, e\_1, e\_2, \cdots, e\_j$ is a a simple path on $C\_v$ that is disjoint with $\mathcal C\_u$ and,
* Both $f\_{i+1}$ and $e\_{j+1}$ are on $\mathcal C\_v$ and on $\mathcal C\_v$.

There are two cases.

* If $f\_{i+1}$ and $e\_{j+1}$ are the same edge, this is the simple case illustrated by the first graph in the question.
* Otherwise, $f\_{i+1}$ and $e\_{j+1}$ are different. Since both edges are on $\mathcal C\_u$, there is a simple path $P\_u$ on $\mathcal C\_u$ from one endpoint of $f\_{i+1}$, say $x$, to one endpoint of $e\_{j+1}$, say $y$, that includes edge $u$.
Let us start at edge $v$, travelling along the $f\_\*$ edges until we reach $x$, then travelling along the $P\_u$ until we reach point $y$, then travelling along the $e\_\*$ edges back to edge $v$. We can verify that the edges we have thus visited is a simple cycle that contains both $u$ and $v$. (This cycle may or may not contain $f\_{i+1}$. It may or may not contain $e\_{j+1}$. It does contain $P\_v$ and $P\_u$.) $\checkmark$

The claim and its constructive proof above explains that "if two biconnected components were to share an edge they would be the same biconnected component since one can then construct a path through any pair of edges".

#### Two or more different biconnected components may share an articulation point

It looks like you misunderstand what you have read about "computing biconncted components".

Suppose we are given a graph $G$.

While $G$ is a disjoint union of its connected components, it is NOT necessarily a disjoint union of its biconnected components.

An articulation point of $G$ is a point that *joins* two or more different biconnected components ("joins" instead of "separates" is used so as to be consistent with the next statement. Either "joins" or "separates" is fine. By the way, the ordinary meaning of "articulation" means "the action or manner of jointing or interrelating"). An articulation point of $G$ belongs to each biconnected components that is directly connected to it. (Also note that a vertex of a biconnected component that is an articulation point of $G$ is not an articulation point of that biconnected component as a graph.) It does not make sense to remove any articulation point of $G$ if we want to list the vertices of each biconnected component of $G$.

We can see that "removing articulation points" is never involved when we try to find biconnected components. Articulation points serve as the shared boundary between different biconnected components, as illustrated in the following diagram from Wikipedia, where "cut vertices" are the same as "articulations points".

---

For the graph at the bottom of the question, vertex $x$ is the only articulation point. There are two biconnected components, which share vertex $x$.

* the biconnected component at the top that contains the top 2 vertices.
* the biconnected component at the bottom that contains all vertices except the topmost vertex.
> 2 votes

---
Tags: graphs
---


# Question
Title: Finding optimal combination with multiple constraints
I'm trying to find an optimal combination of players given certain constraints.

There are ~300 players. 10 players has to be chosen in the combination.

Each player has an assigned value. The goal is to optimize for the sum of their values.

Constraints:

* Each player has a price. The sum of their prices has to be less than x.
* Each player has a position (D, M, F). There has to be \[3..5\] D players, \[3..5\] M players and \[1..3\] F players, again, 10 players in total.
* Finally, each player has a team (20 different teams). There mustn't be more than 3 players from the same team.

Brute forcing this takes simply too much time because there are tons of permutations. As far as I've researched, this seems to be most similar to multi dimensional knapsack problem and proposed way to do it should be dynamic programming.

However, beyond this information, I'm still not sure how to translate it into code. I'm using python.

# Answer
I suggest you express this as an instance of integer linear programming, and use an off-the-shelf ILP solver. You will have a 0-or-1 variable $x\_i$ for each player, where $x\_i=1$ means that the $i$th player is selected and $x\_i=0$ means that the $i$th player is not selected. Each constraint you list can be expressed as a linear inequality over the $x\_i$'s. Then you can use an ILP solver to search for a feasible solution (or one whose price is minimal).
> 0 votes

---
Tags: algorithms, optimization, dynamic-programming, knapsack-problems
---


# Question
Title: Efficiently remove intersections among a set of spheres
I have a 3D space where N spheres of identical size, identified by the location of their centers, are continually inserted. When a new sphere is inserted, I have the ability to efficiently query the locations of any other spheres that may intersect with this sphere.

I can also compute the vector two intersecting spheres will need to move along in order to resolve their intersection in the shortest distance. However, I can't simply move the new sphere over along this vector and call it a day, since this may cause new intersections with other spheres that will then need to be resolved.

My question is, upon inserting a new sphere into this space and finding other spheres it intersects with, how can I efficiently compute the change in position of each of the N spheres in the space that will resolve all intersections in the space? An optimal solution should minimize the total distance traveled by the centers, but near-optimal solutions are fine, and in fact preferred if they are significantly more efficient.

The solution must guarantee that no intersections remain in the space. For my purposes, the 3D space is infinite, and two spheres aren't considered intersecting if they are tangent to each other. Any sphere in the space can be moved.

Example scenario: There are four identical spheres aligned horizontally. The middle two intersect, and the minimum distance required to resolve their intersection is 1. If one of the intersecting spheres moves a distance greater than 0.75 away from the other, it will intersect with one of the outer spheres. An optimal solution here would be to move each of the intersecting spheres away from the other by a distance of 0.5, which results in the least overall distance traveled, since no other intersections would have to be resolved subsequently.

# Answer
A plausible algorithm is to use a physics simulation of the balls: simulate moving that one ball along that vector, and let it bump other balls out of the way (which might in turn cause a cascading reaction, etc.). This probably won't yield an optimal solution but it will be an efficient way to obtain one plausible solution that might often be not too far from optimal.

One way to obtain an optimal solution is to use quadratically constrained quadratic programming. If you model the center of the $i$th ball as $(x\_i,y\_i,z\_i)$, then all of the constraints (e.g., no two balls are overlapping) are quadratic, and the objective function (minimize total distance travelled) is also quadratic, so this is a QCQP instance, and you could try using an off-the-shelf QCQP solver. As a heuristic, you could pick a subset of balls (e.g., those balls that are moved by the physics simulation of the first paragraph), and only allow them to move, and then use QCQP on that subset of balls.

I don't know whether there are better solutions.
> 2 votes

---
Tags: algorithms, optimization, computational-geometry, mathematical-programming
---


# Question
Title: For $L_1 \in NP, L_2 \in NPC$, does $L_1 \in P \Rightarrow L_2 \in P$ imply $L_1 \in NPC$?
Let $L\_1 \in NP, L\_2 \in NPC$. It is known that if $L\_1 \in P$ then $L\_2 \in P$.

Can we formally deduce that $L\_1 \in NPC$ (show that $\forall L'\in NP$ exists a polynomial reduction $L'\leq\_p L\_1$)?

# Answer
The implication is true if and only if $P = NP$.

If $P = NP$, the consequent $L\_1 \in NPC$ is true from the assumption $L\_1 \in NP$ because $NP = NPC$.

If $P \neq NP$, there exists an NP-intermediate problem. Now, assign $L\_1$ to be an NP-intermediate language, and assign $L\_2$ to be an NP-complete language. That means we have $L\_1 \notin P$ and $L\_1 \notin NPC$. The antecedent "$L\_1 \in P \implies L\_2 \in P$" true, but the consequent "$L\_1 \in NPC$" is false.
> 4 votes

# Answer
I think the answer is unknown.

In particular: suppose the way we know that "if $L\_1\in P$ then $L\_2 \in P$" is because we have a Cook reduction from $L\_2$ to $L\_1$. I believe it is not known whether this implies the existence of a Karp reduction from $L\_2$ to $L\_1$ (which is equivalent to $L\_1$ being NP-complete). So, I think it is not known whether this implies that $L\_1$ is NP-complete. See https://cstheory.stackexchange.com/a/18922/5038, Can we construct a Karp reduction from a Cook reduction between NP problems?, https://cstheory.stackexchange.com/q/138/5038.

In practice, if you ran across $L\_1$ naturally (without trying to craft some special language just to mess up this heuristic) and if you can prove "if $L\_1 \in P$ then $L\_2 \in P$", it would be natural to strongly suspect that $L\_1$ is probably NP-complete, so it is a good use of your time to try to find a concrete Karp reduction to prove it NP-complete.
> 1 votes

---
Tags: complexity-theory, computability
---


# Question
Title: What is the time complexity of the EMST problem in 3D space
We have an unstructured cloud of $N$ points in 3D space. What is known about the complexity of building the Euclidean Minimum Spanning Tree of the points ?

The tree is made of $N-1$ edges and can be built as a subset of the Delaunay triangulation in time $O(N^2)$, but I don't think that this is tight.

# Answer
> 1 votes
The current Wikipedia article has information:

> For three dimensions it is possible to find the minimum spanning tree in time $O((n \log n)^{4/3})$

And about approximation:

> it is possible to produce a $(1 + \varepsilon)$-approximation in $O(n \log n)$ time, whenever $\varepsilon$ is a constant.

In practice, worst-case quadratic algorithms are used because worst-case inputs are rare and fast enough most of the time.

---
Tags: algorithms, graphs, time-complexity, spanning-trees
---


title: Efficient search in a permutation

text:
# Question
Title: Efficient search in a permutation
Let $S$ be an array of length $n$ containing a random permutation of numbers from $0$ to $n-1$. What is the most efficient (in expectation) algorithm for finding the location of a given number $k$ in $S$? In other words, finding index $i$, such that $S\[i\]=k$.

---

I watched a video about a related puzzle and it seems that in expectation we can do better than a linear search. The idea is to search $S\[k\]$ then $S\[S\[k\]\]$ then $S\[S\[S\[k\]\]\]$ and so on. I think this will find the required index faster than checking every element (on average), but I am not sure.

I wrote some Java code to simulate this algorithm and here are the results for $n=3$. I show every possible permutation and the number of steps required to find every possible $k$. Each element of the permutation is written in the form "index:value".

```
0:0 1:1 2:2
0 found in 1 steps
1 found in 1 steps
2 found in 1 steps
maximum steps for this permutation 1

0:0 1:2 2:1
0 found in 1 steps
1 found in 2 steps
2 found in 2 steps
maximum steps for this permutation 2

0:1 1:0 2:2
0 found in 2 steps
1 found in 2 steps
2 found in 1 steps
maximum steps for this permutation 2

0:1 1:2 2:0
0 found in 3 steps
1 found in 3 steps
2 found in 3 steps
maximum steps for this permutation 3

0:2 1:0 2:1
0 found in 3 steps
1 found in 3 steps
2 found in 3 steps
maximum steps for this permutation 3

0:2 1:1 2:0
0 found in 2 steps
1 found in 1 steps
2 found in 2 steps
maximum steps for this permutation 2

average of maximum steps for all permutations 2.1666666666666665

```

This algorithm has an average for all permutations of 2.17 steps. Meanwhile the linear algorithm of checking every element will always have an element that requires the maximum steps of 3, so its average over all permutations will be 3, which is worse.

As $n$ increases the number of steps required by the above algorithm seems to approach $2n/3$.

But can we do better?

# Answer
Linear search.

Reading values from $S$ give you no information on where $k$ can be and you can't avoid exhaustive search. If the permutations are equiprobable, *whatever the order* in which you try the locations, the distribution of the number of trials is uniform. The expectation of the number of comparisons is $\dfrac{n-1}2$ (best case $1$, worst $n-1$).

Note that knowing the particular values (naturals $1$ to $n$) helps in no way.

---

**Update:**

The correct value of the expectation is

$$\frac{n^2+n-2}{2n},$$ my bad.
> 4 votes

# Answer
Lets take a smaller example. Consider you have $10$ positions $\[0, 1, 2, ..9\]$ and the numbers are distributed as position $i$ has the number $(i + 1)mod10$. Now pick any $k$, it's easy to see that you'll have to traverse all the positions. So asymptotically, you have no benefit.

As far as expectation is concerned @Yves Daoust's answer gives you why it's unaffected. Also, implementing such a strategy in code isn't particularly helpful, it will only obfuscate the code, may make it harder for the compiler to optimize and may invalidate cache benefits if you are dealing with extremely large arrays.
> 0 votes

---
Tags: algorithms, search
---


# Question
Title: Why do we care about computable functions in parametrized complexity definitions?
In a classical definition of the **FPT** complexity class, for a parametrized problem $L\subseteq \Sigma^\* \times \mathbb{N}$ we require an algorithm, solving an instance $(G,k)$ in time $f(k)\cdot n^{O(1)}$, where *$f$ is a computable function*.

Very simillarly, there is a notion of *parametrized reduction*, where we require an algorithm running in fpt-time transforming instance $(G,k)$ to instance $(G',k')$ and it holds that $k'\leq g(k)$ for *some computable function $g$*.

And so on.

It is good to note that some straightforward observations about reductions or FPT properties are true because composition of computable functions is computable.

For example the observation: *If $P\leq\_{\operatorname{fpt}}Q$ and $Q$ is FPT, then $P$ is FPT*. Or this one: *If $P\leq\_{\operatorname{fpt}}Q$ and $Q\leq\_{\operatorname{fpt}}R$, then $P\leq\_{\operatorname{fpt}}R$*.

My question is, why do we care that much so that the functions are computable? If i denote by $\sigma$ the busy beaver function, which is a familiar example of non-computable function, what would be the issue to have an algorithm with running time, say $\sigma(k)\cdot n^2$ ?

I know there is simillar notion of time- and space- constructible functions, which are required in hierarchy theorems and we indeed need the assumption that we can count $f(k)$ on some Turing machine in $O(f(k))$ time/space. But the assumption of computability in parametrized complexity seems superfluous to me.

# Answer
> 3 votes
## Definitions

Actually, there are three definitions of FPT, already in the Downey/Fellows book.

* The definition you cite is known as *strongly uniform FPT*.
* Dropping the computability requirement on $f$ (as you suggest) gives *weakly uniform FPT*.
* For *nonuniform FPT*, one requires an exponent $c$ and, for each $k$, an $O(n^c)$ algorithm solving instances of the form $(G,k)$. (The algorithms for different $k$ are allowed to be unrelated to each other.)

I don't have the book at hand. Yet I seem to recall that it proves that all three classes are, in fact, different.

For each of these definitions, there is a corresponding notion of reductions. The reducability notions are contained in each other the same way the FPT notions are.

## Tractability

I know of two natural ways to obtain tractability results.

* Provide a (uniform) algorithm and analyze its run-time. Likely, the analysis gives $f$ in a form that is clearly computable. Hence strongly uniform FPT. For example, the bounded-search-tree algorithm for parameterized vertex cover has $f(k)=2^k$.
* Use a meta-theorem. Let's consider parameterized vertex cover again. For each $k$, let $C\_k$ be the class of graphs that admit a vertex cover of size at most $k$. It is easy to see that $C\_k$ is closed under taking graph minors. A theorem by Robertson and Seymour then implies that $C\_k$ is decidable in time $O(n^3)$. Hence non-uniform FPT.

As noted above, I believe the Downey/Fellows book provides a problem in weakly uniform FPT that they prove not to be in strongly uniform FPT. Yet that is not a natural problem. Also, I would be unlikely to use such an algorithm in practice. The same goes for an algorithm which doesn't have a better bound than $\sigma(k)\cdot n^2$.

Showing that a problem is in strongly uniform FPT is a better (in the sense of stronger) result than showing it to be in weakly uniform FPT. As the technique used to prove the latter can usually be adapted to prove the former as well, that is what is being done.

## Intractability

Absolute intractability can be proved, for example, with diagonalization. Most of the time, however, we need to contend with relative intractability: If the problem at hand would be tractable, then so would be a famous other problem that is already believed to be intractable. The standard tool for relative intractability are reductions.

Again, the result is the better, the more restrictive the notion of reduction is. Hence strongly uniform FPT reductions are favoured over weakly uniform ones.

## Summary

If strongly uniform FPT had never been defined, we now would have largely the same picture, just that the notion of weakly uniform FPT would be used throughout. As you seem to suggest. The results we do have (using the notion of strongly uniform FPT and respective reductions) are stronger, and hence favourable from a technical perspective.

Side note: The notion of *bounded fixed parameter tractability* has been proposed, in which the function $f$ is restricted further. See, for example, the Flum/Grohe book.

---
Tags: complexity-theory, time-complexity, computability, parameterized-complexity
---


# Question
Title: Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular
Question: Use the Pumping Lemma to show $L\_1 = \Sigma^\*\setminus\\{0^n1^n: n\geq 0\\}$ is not regular, for $\Sigma=\\{0,1\\}$.

My thoughts: I understand that $L\_2 = \\{0^n1^n: n\geq 0\\}$ can be shown to be not regular using the Pumping Lemma by starting with a string in $L\_2$ of length at least the pumping length, and try to pump it outside the language.

So I've been trying, for $L\_1$, to start with something and pump it to $L\_2$, but I have been struggling to find a string such that all it's recompositions can be pumped into $L\_2$. As it seems whether I can perform the pumping successfully always depends on the decomposition...

Could you please help? Thanks!

# Answer
If $L\_1$ was regular, then its complement, $L\_2$, would be regular. This is a contradiction because you have shown that $L\_2$ was not regular.
> 0 votes

---
Tags: computability, automata, finite-automata, pumping-lemma, computation-models
---


# Question
Title: Lower Bounding Set Cover's Approximation Ratio
I am reading Slavik's paper A Tight Analysis of Greedy Set Cover. Specifically, Slavik considers the unweighted version of set cover where the ground set is ${U = \\{1,\ldots,m\\}}$ for arbitrarily large $m$. There is a collection of subsets ${S = \\{S\_1,\ldots,S\_n\\}}$ that is a cover of $U$. The goal is to find the smallest subcover ${S^\* \subset S}$ that is a cover of $U$.

Let ${\textrm{Opt}:= \vert S^\* \vert}$ be the size of the optimal solution and let $G$ be the size of the solution found by the traditional greedy algorithm that selects the subset that covers the most remaining elements. Slavik proves a bound that (see Eqs. (1) and (2))

$$ \ln m - \ln\ln m - 0.31 \< \frac{G}{\textrm{Opt}} \< \ln m - \ln\ln m + 0.78$$

What confuses me is how the approximation ratio can be lower bounded by a function of $m$. It seems to me that for arbitrary $m$, it would be possible for ${\frac{G}{\textrm{Opt}} = 1}$ (e.g., let $S\_1 \in S$ be set ${\\{1,\ldots,m-1\\}}$ and let ${S\_2 \in S}$ be set ${\\{m\\}}$ in which case it seems ${G = \textrm{Opt} = 2}$).

Clearly, I am missing something fundamental. Am I misunderstanding the lower bound on the approximation ratio entirely?

# Answer
Yes. You should read the lower bound as: there exists an instance with $m$ items such that $\frac{G}{\text{Opt}} \ge \log m - \log \log m - 0.31$.
> 3 votes

---
Tags: set-cover
---


# Question
Title: Floating-point rounding - bit patterns of values that are halfway between two possible results
I am working through the book Computer Systems: A Programmer's Perspective.

The authors explain that round-to-even rounding can be applied for values that are halfway between two possible results. For example, $10.11100\_2$ would be rounded up to $11.00\_2$ and $10.10100\_2$ would be rounded down to $10.10\_2$.

In general, they state that only bit patterns of the form $XX...XX...Y100...$, where $X$ denotes arbitrary bit values and $Y$ being the rightmost position to which we round, denote values that are halfway between two possible results.

Could someone explain to me why this is the case?

Thanks!

# Answer
Let us express any given binary number without a floating point in the following form $$\underbrace{XX\cdots X}\_{i\text{ digits}}~Y~\underbrace{ZZ\cdots Z}\_{j\text{ digits}}{}\_2=x\times2^{j+1} + Y\times2^j+z $$ where $X$ denotes arbitrary bit values and $Y$ being the rightmost position to which we round. $x$ is the number that corresponds to the first $i$ digits and $z$ is the number that corresponds to the last j digits.

Then two possible results are $$x\times2^{j+1} + Y\times2^j\quad \text{for round-down}$$ $$x\times2^{j+1} + (Y+1)\times2^j\quad\text{for round-up}$$ The average of two possible results, i.e., the number that is half way between them is $$x\times2^{j+1} + Y\times2^j+2^{j-1}$$ which is $$ \underbrace{XX\cdots X}\_{i\text{ digits}}~Y1~\underbrace{00\cdots 00}\_{j-1\ 0\text{s}}{}\_2$$

If there is a floating point in the given binary number, we can multiple it by a power of two to change it to an integer. Run the analysis above. Then divide the same power of two. The bit patterns do not change.
> 1 votes

---
Tags: floating-point, rounding
---


# Question
Title: How an insertion can be decoded in Varshamov and Tenengolts (VT) codes
I have a good idea of how deletion can be decoded in VT codes using Levenshtein algorithm. However, I don't have any idea how can an insertion be decoded? Can anybody give me a small example using a short VT code? Mostly papers say that a 1-deletion code can handle 1-insertion error as well, but I don't know how?

# Answer
> 1 votes
It's provable that any $e$-deletion code is usable as an $e$-insertion code, but the proof is nonconstructive and doesn't necessarily give you an efficient decoding process that would work. (There is a generally applicable brute-force approach – deleting each element individually to see which one gives you a valid codeword – but this is too inefficient in many cases.)

For VT codes specifically, though, there is an efficient algorithm. (I'll use binary VT codes for this example, but I don't think the generalized version is significantly different.) As usual for VT codes, we define the *VT syndrome* $S$ of a string $x\_1,x\_2,\ldots,x\_n$ (where $x\_i\in\\{0,1\\}$) as $\sum\_{i=1}^nix\_i \mod n+1$. Using this definition, a string is a VT codeword if $S=0$. In order to decode the insertion code, we're given a string that's a VT codeword with one bit inserted somewhere, and need to work out which bit was inserted.

I'll also define $n\_0$, $n\_1$ as the number of 0 bits and 1 bits respectively in the original string (so $n=n\_0+n\_1$); $S'$, $n'$ etc. as the value of $S$, $n$, etc. after the insertion occurs; and $n\_{0\leftarrow}$,$n\_{1\leftarrow}$,$n\_{0\rightarrow}$,$n\_{1\rightarrow}$ as the number of 0 bits and 1 bits to the left and right of the inserted bit.

There are two cases to consider: either a 0 bit was inserted, or a 1 bit was inserted.

* If a 0 bit was inserted, then $S'=S+n\_{1\rightarrow}$ (because the 0 bit doesn't have any value towards the syndrome on its own, but increases the $i$ for each 1 bit to its right by 1, and thus causes that 1 bit to have 1 more weight in the VT syndrome calculation). Thus, in this case $n\_{1\rightarrow}=S'\leq n\_1=n'\_1$ and (knowing the value of $n\_{1\rightarrow}$) we can decode the string by counting that many 1 bits from the right-hand end of the string, and then deleting the next bit, which (if we're in this case, i.e. a 0 bit was inserted) will always be a 0 bit.
* If a 1 bit was inserted at position $i$, then $S'=S+n\_{1\rightarrow}+i$ (for the same reason as in the previous case; the addition of $i$ is new because a bit that was inserted at position $i$ will have $i$ bits to its left, and a 1 bit at position $i$ contributes a weight of $i$ towards $S'$). $i=n\_{0\leftarrow}+n\_{1\leftarrow}+1$ (each bit to its left must be a 0 or 1 bit, plus 1 as these strings are 1-indexed); thus, $S'=S+n\_{1\rightarrow}+n\_{0\leftarrow}+n\_{1\leftarrow}+1=0+(n-n\_{0\rightarrow})+1$ and thus $n+1-S'=n\_{0\rightarrow}$. Knowing the value of $n\_{0\rightarrow}$, it's possible to decode the string in the same way as in the previous case, just with the 0s and 1s swapped.

It is almost always possible to distinguish these two cases from each other. For the insertion of a 0 bit, we have $S'\leq n'\_1$. For the insertion of a 1 bit, we have $S'=n\_{1\rightarrow}+n\_{0\leftarrow}+n\_{1\leftarrow}+1\geq n\_1+1=n'\_1$. There are only two ambiguous cases: $S'=n'\_1$; and $S'=0\equiv n+1 \mod n+1$ (because in the latter case we don't know whether the syndrome increased by $0$ or by $n+1$ due to the modular arithmetic). In every other case, the value of $S'$ uniquely determines whether a 0 bit or a 1 bit was inserted.

The case of $S'=0$ is easy enough to understand: in this case, either we inserted a 0 to the right of the rightmost 1 bit (i.e. $n\_{1\rightarrow}=0$), or we inserted a 1 to the right of the rightmost 0 bit (i.e. $n\_{0\rightarrow}=0$). As such, it's possible to determine what bit was inserted by looking at the rightmost bit of the string we're trying to decode.

The case of $S'=n'\_1$ is similar: it occurs when a bit was inserted that lengthened the leftmost run of the original string (either a 0 was inserted there and $S'=n'\_1=n\_1$, or a 1 was inserted there and $S'=n'\_1=n\_1+1$, but in both cases we can determine what bit was inserted by looking at the leftmost bit of the string we're trying to decode).

As such, the VT insertion code can be efficiently decoded by comparing $S' \mod n'$ to $n'\_1$. If $S'=0$, delete the rightmost bit; if $S'=n'\_1$, delete the leftmost bit; if $0\<S'\<n'\_1$, count $S'$ 1 bits from the right and delete the bit immediately to their left; if $n'\_1\<S'\<n'$, count $n'-S'$ 0 bits from the right and delete the bit immediately to their left.

Note that some codes "can't be decoded" by this method because the wrong sort of bit is being deleted; this is because VT codes, despite being perfect deletion codes, aren't perfect insertion codes (some strings cannot be created by inserting a bit into a VT codeword). However, for any string that can be created by inserting a bit into a VT codeword, this algorithm will reconstruct the original VT codeword, and thus decodes the insertion code.

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


# Question
Title: Can a strict right fold be implemented in a single loop?
A strict left fold is straightforward to implement as a loop, rather than with recursion:

```
foldl(fn, acc, list)
    loop until empty(list)
        acc ← fn(acc, head(list))
        list ← tail(list)

    return acc

```

For a strict right fold, the best I've been able to come up with is by maintaining a stack of partially applied functions, which gets unrolled at the end to evaluate the accumulator:

```
foldr(fn, acc, list)
    stack ← empty stack

    loop until empty(list)
        stack push λx ↦ fn(head(list), x)
        list ← tail(list)

    loop until empty(stack)
        acc ← (stack pop)(acc)

    return acc

```

The size of the stack, when full, will be the same size as the input list; so it has to iterate through twice. Moreover, a stack of partially applied functions is hardly different from the call stack that would be created when using recursion, so it doesn't really achieve much.

It is possible to implement a right fold using a left fold:

```
foldr(fn, acc, list)
    return foldl(λx,y ↦ fn(y, x), acc, reverse(list))

```

However, that `reverse` still implies a second iteration.

Is it possible to do better?

---

**EDIT** "Single loop" is a bit ambiguous. I suppose my question is: Can a strict right fold be implemented in $O(n)$ time and $O(1)$ space, without recursion, like a strict left fold can?

# Answer
I think I have solved this! After reading more about it, it seems my hunch about trampolining -- see my comment from my previous answer -- is exactly what I want. So here's what we do:

1. Convert the recursive `foldr` into continuation-passing style.
2. Wrap each function evaluation into a thunk so no recursion actually happens; instead each invocation returns the next element in the sequence.
3. Write a trampoline function (just a loop) that unrolls this sequence to give the final result.

Recursive `foldr`:

```
foldr(fn, acc, list)
    match list
        empty     => return acc
        otherwise => return fn(head(list), foldr(fn, acc, tail(list))

```

Convert to CPS:

```
foldr'(fn, acc, list, k)
    match list
        empty     => return k(acc)
        otherwise => return foldr'(fn, acc, tail(list), λx ↦ k(fn(head(list), x)))

```

Wrap the function evaluation in thunks (argument-less lambda functions):

```
foldr'(fn, acc, list, k)
    match list
        empty     => return k(acc)
        otherwise => return λ ↦ foldr'(fn, acc, tail(list), λx ↦ λ ↦ k(fn(head(list), x)))

```

Write a trampolining function:

```
trampoline(f)
    loop while thunk(f)
        f ← f()
    return f

```

Stitch it all together:

```
foldr(fn, acc, list)
    return trampoline(foldr'(fn, acc, list, λx ↦ x))

```
> 0 votes

# Answer
I believe I have come up with a solution, but I'm not convinced. We observe that, from `foldr(fn, acc, list)`, we can rewrite the intermediary steps as a series of single-valued functions:

$$ \begin{align} eval\_0 &: x \mapsto fn(list\_0,x) \\ eval\_1 &: x \mapsto eval\_0(fn(list\_1, x)) \\ \vdots \\ eval\_n &: x \mapsto eval\_{n-1}(fn(list\_n, x)) \end{align} $$

Then, where $n$ is the length of $list$:

$$ foldr(fn, acc, list) = eval\_n(acc) $$

For example:

$$ \begin{align} foldr((x,y)\mapsto x-y,0,\[1,2,3\]) &= eval\_3(0) \\ &= eval\_2(3-0) \\ &= eval\_1(2-(3-0)) \\ &= 1-(2-(3-0))) \end{align} $$

So the loop algorithm looks something like:

```
foldr(fn, acc, list)
    eval ← λx ↦ x

    loop until empty(list)
        eval ← λx ↦ eval(fn(head(list), x))
        list ← tail(list)

    return eval(acc)

```

I say I'm "not convinced" as implementing this is tricky. The `eval ← λx ↦ eval(...)` line is self-referential: informally we know it means "eval becomes a function of the *previous* eval", but in reality this gets interpreted as infinite recursion. So you end up having to keep a stack in memory either way.
> 0 votes

---
Tags: algorithms, recursion, functional-programming, loops
---


# Question
Title: If computers only work with intuitionistic/constructivist logic, so how it works with binary code?
Constructivist mathematics states that in order to prove something, we must construct this something, in a notion similar to computation, where things don't spring out of nowhere from some "mystery platonic relationship". The theory behind this I already know. A thing that I just can't understand is, if computation requires that the law of excluded middle be false, then why it's possible through binary code (a system based in 1/0 or true-false, like excluded middle).

# Answer
> 2 votes
If I were to attempt to make a computing analogue of this question, it would be this: instead of relating 0 and 1 with 'false' and 'true', suppose we called them 'diverge' and 'halt'. Now by encoding all data as bits, we have a computational system where every (data) building block has been associated with definitely halting or not halting, and we can just test the bit to decide which one it is. But, the halting problem for Turing machines with this naming scheme remains undecidable. Why?

The answers are similar. Even though you can describe a Turing machine as a bunch of bits that you have called "halt" and "diverge", the halting problem is about what the described machine *does*, not some simple aggregation of the bits in its description.

The relation of classical logic to bits has to do with the former having (in the simplest case) two "truth values". So, you can describe those two values with states of a bit, and given a finite propositional calculus formula and bits for the truth values of the variables, you can calculate a bit for the truth value of the whole proposition. It also happens that the bit calculated for $P ∨ ¬P$ this way is $1$ regardless of the bit for $P$.

However, this is not what is done when we give computational meanings for (first/higher order) intuitionistic logic formulas. Formulas are not interpreted as bits but as specifications for machines or programs. And which programs meet the specification is not determined by what bits they are built out of, but what they *do*. In some cases, this might be very simple, like:

* Every program meets the specification for truth, or $⊤$.
* No program meets the specification for false, or $⊥$.

But there are complex examples like:

* A program for $A ∨ B$ must output $0$ together with a program for $A$, or $1$ together with a program for $B$
* A program for $A → B$ must accept a program for $A$ and produce a program for $B$.
* A program for $∀ n:ℕ. P(n)$ must accept a natural number $k$ and produce a machine for $P(k)$.

Importantly, this means that a machine meeting the specification for $P ∨ ¬P$ must *decide* $P$, where $P$ is *not* just a bit, but a specification for machines. And the logic is rich enough that it can encode undecidable computational programs as machine specifications. So, because there are undecidable computational problems, there is in turn no hope of the principle $P ∨ ¬P$ holding generally. For instance, $∀n. P(n) ∨ ¬P(n)$ could have to be a machine that decides the halting problem, because $P(n)$ is an encoding of, "the $n$th machine (under some numbering) halts."

The bit version of things can be embedded into the specification framework. For propositions that *do* correspond to decidable problems, the specification does correspond to some other expression involving bits, and machines deciding the problem will answer according to the classical truth value represented by the bit. But, of course, this only works for problems/propositions that are decidable.

---
Tags: computability, logic
---


# Question
Title: Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)
I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than

```
O(N²)

```

**Eg:**

**Input:**

```
 {(Jhon, 10),(mary,20),(paul,10),(joseph,15)}
 Sum:30

```

**Expected results:**

```
{(John, Mary), (Mary, Paul) }

```

The worst scenario i can imagine is where every person has the same age and the target sum is `2*age`. What i think is in this scenario you would need to do the combination nC2 which is `O(n²)`. I dont know if my approach is wrong or there is any algorithm to solve this scenario in less than `O(n²)`.

# Answer
There are cases where the output has size $\Omega(n^2)$, showing that the problem cannot be solved in time $o(n^2)$ in general.

An example is the one you propose. E.g., the age of every person is $0$ and the target age is $0$.
> 1 votes

# Answer
Agreed that worst case is $O(n^2)$, so you cannot find an algorithm in general that works better.

If you modify the output to instead say a person followed by the corresponding people that would add up to the desired age, then you can do this in $O(n)$ with a modified 2-sum solution.

Basically you would create a dictionary $D$ of $\text{age} \to \text{set(names)}$, as a preprocessing step, and you would output for each person $p\_i$ with age $a\_i$, the tuple

$$(p\_i, D\[S-a\_i\])$$

where $S$ is the desired sum. Notice there are duplications of $p\_i$ in the set retrieved, so you could run a set remove of $p\_i$ in that set, but you still run into "pairs" that are duplicated, since if $a\_i + a\_j = S$, then you will output $(p\_i, S \text{ containing } p\_j)$ and $(p\_j, S \text{ containing } p\_i)$.

Just wanted to add this answer here, since the original problem sounds very close to 2-sum.
> 1 votes

---
Tags: dynamic-programming, search-algorithms, hash, combinatory-logic
---


# Question
Title: Are pure functions always computable functions?
**Are pure functions always computable functions?**

**In computer programming, a **Pure function** is a function that has the following properties:**
(1) the function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams), and

(2) the function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams).

****Computable functions** are the basic objects of study in computability theory.**
Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output.

**Alternative versions of similar questions:**
How do we define the term "computation" across models of computation?

To what extent is an x86 machine equivalent to a Turing Machine?

How can I tell if my C function is a computable function in computer science?

# Answer
You can define the Halting problem as a decision problem, where the function takes in a program and input, and determines whether the program will terminate or not. This is a pure function, but it's well-known that the Halting problem has no algorithm.
> 2 votes

# Answer
It depends what you mean by "pure function". You have to carefully define it.

If "pure function" refers to computer code to compute some function, and if that code is guaranteed to always terminate, then yes, it computes a computable function.

If "pure function" refers to computer code to compute some function, and if that code is not guaranteed to always terminate, then no, it doesn't necessarily compute a computable function.

If "pure function" refers to a mathematical function (rather than an implementation in code), then it might or might not be computable.

When you need a precise definition, Wikipedia is not a reliable source. Terms like "computable function" are a mathematical concept that have a precise definition. To find the exact definition, I recommend studying a good textbook on the subject of computability. You might find discussion of computable functions in many places (including Wikipedia), where people talk informally about the notion of a computable function; there they speak with the understanding that others who have studied the subject can translate that informal discussion into precise mathematics if needed. I am speaking informally here in my answer. It is beyond the scope of an answer on this site to teach you the subject of computability theory; that's self-study you'll need to do on your own.

In my experience, the term "pure function" does not have a standard, accepted definition. Different people may use that phrase in similar but slightly different ways. So if you are working on a subject where the exact definition matters, you may need to define what you mean by "pure function" (which particular definition you are using) to enable clear communication and clear thinking.
> 2 votes

---
Tags: computability, functional-programming
---


# Question
Title: time complexity to convert string to integer and vice a versa
just given solution on this post

i had mention the time complexity to convert string to int is O(n), also verifying this post

now in one of comment fellow SO user, corrected me with example also mention in solution, that for every 10x increase in size time is increased by 100x time.

so i found, post where it mention the time complexity is O(n) is wrong, which is actually O(n\*n).

so can anyone explain this, what is the time complexity of converison ?

# Answer
> 1 votes
It depends on whether the string representation is in base 10 or base 16.

## Conversion to/from base 10

Normally, when an integer is represented as a string, it is represented in base 10. Then here is the running time:

It depends how you count. Theoretical analysis requires a model of the time it takes to do different operations, and depending on which model you choose, you get a different answer.

One way to count running time is to assume that each basic operation takes one unit of time, and that you can add, subtract, multiply or divide two integers (no matter how large) in one step. If you adopt this approach, then it is possible to do the conversion in $O(n)$ time.

Another way to count running time is to assume that each basic operation takes one unit of time, but each operation can only work on a fixed-size value: for instance, you can add or multiply two 32-bit integers in one step, but you cannot add/multiply arbitrary-size integers in one step (that might require many steps). If you adopt this method of counting, then the natural algorithms for conversion take $O(n^2)$ time.

The former approach to modelling runtime is typically more appropriate when working with small numbers (e.g., that fit into a single machine register). The second is often more appropriate when working with very large numbers.

## Conversion to/from base 16

However, the main answer there proposes converting to base 16 (without really highlighting that is what it is doing). It turns out that converting to/from base 16 is much faster: it can be done in $O(n)$ time with a straightforward algorithm, regardless of how you count running time.

---
Tags: time-complexity, algorithm-analysis, strings, integers
---


# Question
Title: complexity of a function that depends on n%3
```
T(1)=1
Func_two (n,b)
1) if (n=0)
2)   then return 1
3) else if (n=1)
4)   then return b
5) else if (mod(n,3)==0)
6)   then return Func_two(n/3,b)
7) else
8)   return b*Func_two(n-1,b)

```

How do I calculate this?

I see that $\mathcal{O}(\log(n))\le T(n) \le \mathcal{O}(n)$ because either we decrease by $1 $ all the time or by $\frac{n}{3}$.

Also dividing gets us much closer to $T(1) $ then reducing by $1 $ so I assume the solution is $ T(n)=\mathcal{O}(\log(n))$.

Got stuck trying to prove this with induction, can't even reach the $T(n) $ reccurence formula from the given pseudocode.

# Answer
Write $n$ in the ternary base. If the lowest order digit (trit) is a $1$ or a $2$, $T$ is called once or twice and $n$ becomes a multiple of $3$. Then the last digit (now a zero) is dropped.

Hence, the total number of calls equals the sum of the trits of $n$ plus the number of trits.

E.g. $n=43\_d=1121\_t\to1+1+2+1+4$ calls.

You can also observe that the number of multiplies is the number of trits. The function returns $b$ to the power equal to the sum of the trits, here $b^5$.

---

Note that the number of trits is given by

$$\lfloor\log\_3n\rfloor+1$$

so that the number of calls varies between $\lfloor\log\_3n\rfloor+1$ and $3\lfloor\log\_3n\rfloor+3$.
> 1 votes

---
Tags: time-complexity
---


# Question
Title: Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular (without using complement closure)
Question: Use the Pumping Lemma to show $L\_1 = \Sigma^\*\setminus\\{0^n1^n: n\geq 0\\}$ is not regular, for $\Sigma=\\{0,1\\}$ (without using the complement closure property).

My thoughts: I understand that $L\_2 = \\{0^n1^n: n\geq 0\\}$ can be shown to be not regular using the Pumping Lemma by starting with a string in $L\_2$ of length at least the pumping length, and try to pump it outside the language.

So I've been trying, for $L\_1$, to start with something and pump it to $L\_2$, but I have been struggling to find a string such that all it's recompositions can be pumped into $L\_2$. As it seems whether I can perform the pumping successfully always depends on the decomposition...

Could you please help? Thanks!

# Answer
> 1 votes
Suppose towards a contradiction that $L\_1$ is regular and let $p$ be its pumping length.

Since $0^{p}1^{p+p!} \in L$ there must be some $1 \le k \le p$ such that $0^{p+ik} 1^{p + p!} \in L\_1$ for every integer $i \ge -1$.

Choosing $i=\frac{p!}{k}$ (this is an integer since $k$ is a factor of $p!$) yields the following contradiction: $$ 0^{p+\frac{p!}{k} \cdot k} 1^{p + p!} = 0^{p + p!} 1^{p + p!} \in L\_1. $$

---
Tags: computability, automata, finite-automata, pumping-lemma, computation-models
---


# Question
Title: Finding the (probable) maximum of a large set of integers *without* iterating over all of the values
As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers. Importantly, I do not have direct access to the full list of integers, but I do have a function $f(n)$ which returns true/false if $n$ is in the set. The function $f(n)$ is expensive and I would like to minimize the number of calls I must make to it.

The integers might or might not be consecutive, or have large gaps between them (i.e. might be sparse or dense). There is no prior-known upper bound on the largest integer in the set, which can go off to infinity in theory.

Is there a well-trodden algorithm for doing this? My inkling is to do some kind of random sample to determine the density, and then try to find the upper bound within some certainty. I'm not sure how to bound my initial sample properly then though, or which distribution I might assume the integers have based on that sample.

Thanks.

# Answer
Without more a priori information on the distribution, **no algorithm can work**. Because you can never be sure that there is no larger $n$ than those already tried.

---

The best (?) you could do is an exhaustive search: this guarantees that *you will someday* find the maximum $n$, though you will not know when.
> 1 votes

# Answer
Tricky.

As an approximation, assume that the number n is in the set with a probability p (n), and the sum of p (n) over all integers n is finite, so we may guess that the set is finite.

You'd have to check enough values n to make some reasonable assumptions about p (n), and then based on those assumptions make a reasonable guess about the upper bound.

But let's say that p (n) = $1 / n^2$. The probability that there is any element n ≥ N is about 1/N. So 10 is an upper bound with probability 90%, 100 is an upper bound with probability 99% and so on. On the other hand, your checks will likely show that 1 is an element and find no others. p (n) could be any of a gazillion of possible probabilities.

Your chances are much better if you have some knowledge about the distribution.
> 0 votes

---
Tags: algorithms, search-algorithms, sampling, upper-bound
---


# Question
Title: Prove that the grammar $S\rightarrow (S)|SS|\epsilon$ generates precisely all well-balances parentheses
**Question**: prove that the grammar $G = (\\{S\\}, \\{(,)\\}, R, S)$ where $R$ consists of three rules:

$S \rightarrow (S)~|~SS~|~\epsilon$

generates precisely all well-balanced parentheses.

I found a source where it used induction on the length of string and the length of CFG derivation.

First of all, it seems for the backward direction (all strings in the language are generated by $G$), they assumed $x$ is derivable from $G$ in the inductive hypothesis, then showed that $x$ is derivable from $G$. Is this prove valid? Shouldn't they show that all legal string of $|x|+1$ is derivable instead?

On the other hand, the proof seems more complicated than needed. Is it possible that there is a simpler proof in both directions?

Many thanks!

# Answer
I didn't read the source you linked, but to prove that $G$ generates **precisely** all well-balanced parentheses you need to show two things:

* all words $w$ with well balanced parenthesis are generated by $G$, and
* all words $w$ generated by $G$ are well-balanced.

A grammar that needs to satisfy the first condition but not the second could simply generate $\\{(,)\\}^\*$. A grammar that need to satisfy the second condition but not the first could simply generate the empty language.

In order to prove the former condition for you grammar you can proceed by induction on the length $|w|$ of $w$. The case $|w|=0$ is trivial since $\varepsilon \in L(G)$. For $|w| \ge 1$, notice that the first symbol of $w$ must be "(". Since $w$ is balanced we can write $w=(x)y$ where the ")" symbol is the paranthesis matching the first one, and $x$ and $y$ are (possibly empty) balanced words. Since $|x| \< |w|$ and $|y| \< |w|$ we can invoke the induction hypothesis twice to conclude that $x,y \in L(G)$, i.e., $S \rightsquigarrow x$ and $S \rightsquigarrow y$. Then $w \in L(G)$ by the following derivation $S \to SS \to ( S ) S \rightsquigarrow (x)y$.

For the latter condition, you can prove that all parentheses in any sentential forms $\alpha$ of $G$ are well-balanced. The proof is by induction on the number of applied productions. If no productions are applied then $\alpha = S$, which contains no parentheses and hence its balanced. Otherwise consider the last applied production. The only production that involves parentheses is $S \to (S)$. Before applying this production, the sentential form was balanced by induction hypothesis and the production $S \to (S)$ keeps the sentential form balanced.
> 1 votes

---
Tags: algorithms, computability, context-free, computation-models
---


# Question
Title: Why are nodes added from left to right in last level in a Heap?
I understand that in Heaps we add them from left to right. I understand how to add and delete. But why is it from left to right, is there something that prevents it from being right to left or something like that. My intuition tells me that it has something to do with the index.

# Answer
> 0 votes
If you are referring to the binary heap, then you are right that it has something to do with the index. The left child of a node is at index $2\*i$ while the right child is $2\*i+1$, where $i \> 0$ is the index of the parent in the array representation of the binary heap. Since a new element is added at the smallest empty index in the array, this element will be a left child when its parent has no children.

---
Tags: algorithms, trees, heaps
---


# Question
Title: Confused by Sipser's proof of equivalence of R and NFAs
I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression then it is regular" on Page 67.

I **don't understand how this proof guarantees that there will be an NFA for R1 and R2** in the first place. I understand that if there were NFAs for them then I could construct an NFA for their union/concatenation/star.

# Answer
Let's consider $R\_1$ only but the idea applies to $R\_2$ as well. It should be clear that $R\_1$ is a regular expression. Thus, it must be one of the six cases. If it's the first 3, then you are done - construct the NFA for $R\_1$ using one of the 3 cases. Otherwise, you can decompose $R\_1$ into smaller regular expression satisfying one of the remaining 3 cases, e.g. $R\_1 = R\_3 \cup R\_4$. Recursively apply the construction to the smaller expressions of $R\_1$. When you have recursivley constructed the smaller NFA for the components of $R\_1$, apply the union/concatenation/star (depending on what kind of exression $R\_1$ is) construction of NFA to create $R\_1$.
> 1 votes

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


# Question
Title: Is it always possible to order grammar rules so that all the symbols on the left will be contained on the right in a previous rule?
This is about unrestricted grammars

Assume `S` is the start symbol. Assume `1` and `0` are terminal symbols. Assume all other symbols are non-terminal.

**Given a set of (non-trivial) grammar rules,**

**is it always possible to order them, such that,**

**all the symbols on the left:**

* **will be contained on the right in a previous rule**
* **or be the start symbol?**

A grammar rule is trivial if discarding it does not change the language generated by it.

Example trivial rule:

```
S -> 1
S -> 0
A -> B

```

`A` is on the left of the third rule. `A` is nowhere to be found in the other rules. Therefore the rule with `A` can be removed without changing the grammar.

Another example trivial rule:

```
S -> 1
S -> 0
A -> B
B -> A

```

Now `A` is found in another rule, but both rules containing `A` together are trivial, since `A` and `B` are not found in other rules.

Example grammar:

```
S -> S T
T -> S (T is on the left; T is in the previous rule)
T -> 1
T -> 0

```

The second, third and fourth rule all start with `T`, which is on the right hand side of a previous rule, therefore these rules are ordered as desired.

# Answer
Yes.

---

Given a grammar $G$ that contains no trivial production rules, here is a simple algorithm that lists all grammar rules such that all the symbols on the left of a rule except $S$ are contained on the right of a previous rule.

1. Let $ordered\\\_rules$ be an empty list of rules.
2. Let $available\\\_symbols$ be a set that contains $S$. Besides $S$, $~available\\\_symbols$ will always contain all the symbols on the right of a rule in $ordered\\\_rules$.
3. As long as there is a rule in $G$ but not in $ordered\\\_rules$, find a rule $r$ such that all the symbols on the left of $r$ are in $available\\\_symbols$.
    1. Add all the symbols that are on the right of $r$ to $available\\\_symbols$.
    2. Append $r$ to $ordered\\\_rules$
4. Return $ordered\\\_rules$.

---

Why does the algorithm above work?

Suppose there is a rule in $G$ but not in $ordered\\\_rules$.

Since no rule in $G$ can be discarded, there is a word $w$ that is generated with at least one application of a rule not in $ordered\\\_rules$. Consider the very first moment that a rule not in $ordered\\\_rules$, say $r$ is applied in a derivation of $w$. By the choice of that moment, all the symbols on the left of $r$ must have been either $S$ or on the right of rules in $ordered\\\_rules$, i.e., they are in $available\\\_symbols$.

Hence, step 3 of the algorithm will loop until all rules are in $ordered\\\_rules$.
> 8 votes

# Answer
Yes. Use the following greedy algorithm:

* Mark the start symbol $S$
* While there exists an unselected transition such that (\*) all the nonterminals in $\alpha$ are marked:
    + Select an arbitrary transition $\alpha \to \beta$ that satisfies (\*).
    + Mark all nonterminals in $\beta$.

The order in which transitions are selected satisfies your requirement by construction. To see that unselected transitions are trivial notice that it is not possible to generate all nonterminals on their left-hand-side from $S$.
> 5 votes

---
Tags: formal-grammars
---


title: What complexity class is this?

text:
# Question
Title: What complexity class is this?
***Disclaimer 1: I am a beginner in this domain and I am self-learning these concepts. Please take this in consideration when reading my question.***

***Disclaimer 2: All corrections to this question are highly encouraged. All self-learning PDF books etc. that helped you better understand these particular concepts are highly desired.***

Hello,

In this question, I assume I have some formal definition of the Turing machine such that:

1. any Turing machine (say $M$) can receive exactly:
    * one input $i$, where $i \in \\{0,1\\}^\*$ ;
    * one witness $w$, where $w \in \\{0,1\\}^\*$ and $\exists \\, a \in \mathbb{N} : |w| \le |i|^a$. I call such a witness "a witness of the input $i$". By $|x|$ I mean the length of the string $x$.
2. $M$ is able to compute with $i$ and $w$ and:
    * loop, if the computation lasts forever. I write $M(i, w) = {\nearrow}$ to denote this
    * halt, if the computation ends at some point. Here, there are two "types" of halting:
        + accept, if the computation ends in some accepting state. I write $M(i, w) = 1$ to denote this
        + reject, otherwise. I write $M(i, w) = 0$ to denote this.

I have recently read on Wikipedia that the definition of the $P$ class is the following:

> A language L is in P if and only if there exists a deterministic Turing machine M, such that
>
> * M runs for polynomial time on all inputs
> * For all x in L, M outputs 1
> * For all x not in L, M outputs 0
>
> https://en.wikipedia.org/wiki/P\_(complexity)

I adapted the definition to my Turing machine model as follows:

> A language L is in P if and only if there exists a Turing machine M, such that
>
> * For all inputs x, $\exists \\, a \in \mathbb{N} : \mathbb{T}\[M,x,\varepsilon\] \le |x|^a$. I write $\varepsilon$ for the empty string. By $\mathbb{T}\[M,i,w\]$ I mean the number of time units required in the computation of $M$ with $i$ and $w$.
> * For all x in L, $M(x, \varepsilon) = 1$
> * For all x not in L, $M(x, \varepsilon) = 0$

I am searching to define a complexity class where exactly the same rules of $P$ apply to both the input and the witness. Therefore, ***I want to define this***:

> A language L is in ... (insert complexity class name here) if and only if there exists a Turing machine M, such that
>
> * For all inputs x and for all witnesses w of x, $\exists \\, a \in \mathbb{N} : \mathbb{T}\[M,x,w\] \le |x|^a$
> * For all x in L and for all witnesses w of x, $M(x, w) = 1$
> * For all x not in L and for all witnesses w of x, $M(x, w) = 0$

As I see it, it would obviously be a superset of $P$ (since for all inputs $i$, we have $\varepsilon \in \\{ w : w \text{ is a witness of } i \\}$).

***QUESTION: Did someone already propose before a complexity class that satisfies my above definition?***

What I don't know is whether there is a widely-known name for this specific complexity class (as we have with $P$, $PSPACE$, $EXP$ etc.) or I should define it on my own (with some arbitrary name, say $P\_{+W}$?)

Thank you for looking over my question!

**P. S.** I have previously found the class $ZPP$ as an almost-good candidate for the answer to my question, but because I read on Wikipedia the following:

> if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer
>
> https://en.wikipedia.org/wiki/ZPP\_(complexity)

I have understood that the average running time (i.e., the ***average*** of all running times) will be polynomially bounded, whereas, with my class, I want ***all*** running times to be polynomially bounded, just like in $P$. Did I understand anything wrong with this?

# Answer
> 0 votes
First, this

> For all inputs x, $\exists \\, a \in \mathbb{N} : \mathbb{T}\[M,x,\varepsilon\] \le |x|^a$.

is wrong for the definition of P. Every terminating Turing machine will satisfy this condition. Why? Because the choice of the exponent $a$ depends on the input $x$, the time complexity can be $|x|^{|x|}$ for example.

The correct definition uses the swapped order qualifiers like $\exists a\forall x, T(x) \leq |x|^a$.

Now, the main question

> * For all x in L and for all witnesses w of x, $M(x, w) = 1$
> * For all x not in L and for all witnesses w of x, $M(x, w) = 0$

This is just P. You wrote:

> As I see it, it would obviously be a superset of $P$ (since for all inputs $i$, we have $\varepsilon \in \\{ w : w \text{ is a witness of } i \\}$).

but this argument actually shows the language class in the question is a *subset* of P.

Think this way: you are given a Turing machine satisfying the conditions. Can you recognize the given language in polynomial time? Yes, we can simulate $M$ with the empty witness, and output the result.

It is also easy to show the language class in the question contains P because the witness can just be discarded. Therefore, the language class in the question is P.

---
Tags: algorithms, complexity-theory, formal-languages, turing-machines, finite-automata
---


title: Algorithm for Unique Selections

text:
# Question
Title: Algorithm for Unique Selections
Suppose I have $k$ sets with $n$ elements in each. Define a *selection* as one element taken from each set.

A selection is *unique* if there's one and only one way it can happen—that is, one and only one mapping from the elements in the selection back onto the original sets. For example, if my sets are $\\{1,2,3\\}$ and $\\{1,2,4\\}$, then $(1,2)$ and $(1,3)$ are both valid selections, but only the second one is unique.

I'd like to find the number of unique selections, given a list of sets. But my first attempt is $O(n^k)$, which is pretty bad. (Generate all $n^k$ possible selections, then discard all duplicates, and count how many are left.)

Is it possible to do better than this? If so, how?

(If it simplifies things, you can assume the order of elements in a selection either does or does not matter. To switch from one "version" to the other, just multiply or divide by $k!$ at the end; no unique selection can contain two identical elements, after all.)

# Answer
We will use the following method to efficiently solve your problem for the case $k = 2$ :

We will firstly compute: $$ \begin{array}{rl} S & := A \\, \Delta \\, B \\ & = (A \setminus B) \cup (B \setminus A) \\ & = (A \cup B) \setminus (A \cap B) \end{array} $$ i.e. the symmetric difference of $A$ and $B$ . Then, we have the following cases:

* $card(S) = 0$ \- There is no unique selection.
* $card(S) \> 0$ \- There are unique selections. Let: $$\begin{array}{rl} x & := A \cap B \end{array}$$ and $$\begin{array}{rl} a & := S \cap A \\ & = A \setminus x \end{array}$$ and $$\begin{array}{rl} b & := S \cap B \\ & = B \setminus x \end{array}$$ Then, the unique selections are the elements of the set: $$ T := \Big( \big(a \times B \big) \cup \big(b \times A \big) \Big) \setminus \big( a \times b \big) $$ Since you are interested in the number of unique selections, you just have to calculate $card(T)$ .

You may find this article on symmetric difference useful, since it adapts your initial algorithm idea and makes it more efficient, at least for the case $k = 2$ (the new algorithm yields a worst-case time complexity of $O(m + n)$ for the symmetric difference of two arrays, with their respective lengths $n$ and $m$, where $n \le m$, instead of $O(n^2)$).

Best regards!
> 1 votes

# Answer
Partial answer: it is NP-hard to find a maximum-cardinality partial unique selection, at least if the condition "every set contains the same number of elements" is dropped.

Consider the problem in terms of bipartite graphs. As observed, selections with duplicated elements are not unique. Therefore, a selection corresponds to a bipartite matching (that uses all of the "set" vertices).

It turns out that a partial unique selection corresponds to an *alternating cycle-free matching* defined as \[1\]:

For a matching, a simple cycle is *alternating* if every other edge is in the matching. A matching is *alternating cycle-free* if the graph has no alternating cycle.

To see the equivalence, notice that the selection is not unique if and only if there exists a non-identity permutation of the used sets that retains the matching. Any non-identity cyclic component of that permutation corresponds to an alternating cycle.

Müller proved the maximum-cardinality alternating cycle-free matching problem in bipartite graphs is NP-hard \[1\]. However, it is not immediately clear how to reduce the maximizing problem to the problem of using all vertices of one side.

* \[1\]: Müller, H. (1990). Alternating cycle-free matchings. Order, 7(1), 11-21.
> 1 votes

---
Tags: algorithms, time-complexity
---


title: Guessing number game "hot" or "cold"

text:
# Question
Title: Guessing number game "hot" or "cold"
I thought up this problem and am trying to come up with an optimal solution.

> I am thinking of a number uniformly randomly between 1-100, inclusive.
>
> * If you guess the number, you "win".
> * Else if you guess incorrectly, but are within 10 of the number, I will tell you "hot".
> * Else, I will tell you "cold".
>
> For example, if the number I'm thinking of is 37, guessing any value in \[27,36\] or \[38,47\] will be "hot". Any guess not in those ranges except 37 will be "cold".
> You are not allowed to guess a number outside of 1-100.

My current approach:

1. Guess in increments of 11. I guess 11, if it's hot, the number is in \[1, 10\] or \[12, 21\]; if it's cold, I guess 33, 55, and so on.
2. Suppose the true number is "hot" at 11. Then, I can guess 1. If 1 is hot, the number must be within \[2,10\], else \[12,21\]. I could have also guessed 21 here for similar effect.
3. Suppose the true number is within \[12,21\]. My goal is to split the search space in half again. So I guess 6: if hot, it must be within \[12,16\], else \[17,21\].
4. Repeatedly split the search space in half this way.

Is there a better algorithm? What would be the runtime?

# Answer
A "cold" answer removes 21 possibilities from consideration. So you'd better try the positions 11, 32, 53 and 74 to avoid any overlaps. And if you get four "cold", you know that the number is in 85-100.

When you have a "warm", dichotomic search will indeed be the most effective. The runtime will be approximately from one to four queries plus \[one to\*\] five queries.

\*Depends on the exact rule of the game, see my comment.

---

Due to the fact that the domain is finite, there are boundary effects. It is not impossible that shifting the initial trials by a few units will impact the expected case slightly. But this analysis would be lengthy.
> 1 votes

---
Tags: algorithms, binary-search, optimal-strategy
---


title: Is this a good proof of correctness?

text:
# Question
Title: Is this a good proof of correctness?
I am currently being introduced to algorithms and I am trying to learn about showing the correctness. For training I chose the very basic linear-search algorithm and I would like to know if this is a correct proof. Thank you for your feedback!

**Algorithm-Pseudocode:**

```
function LinearSearch(Array A, int v):
  for j=1 in A.length:
    if A[j] == v:
      return A[j]
  endfor
  return NULL

```

**My proof:**

Invariant: At the beginning of every iteration of the for-loop the subarray `[1,..., j-1]` doesnt contain the searched element `v`.

Initialization: For `j = 1` it's obvious that `v` is not contained in the array before this iteration since `A[0]` doesn't exist.

Maintenance: For every new iteration it is certain that the subarray `A[1,..,j-1]` doesn't contain `v` and the invariant holds. If `v` would have been part of the subarray the algorithm would have already terminated due to the if-clause.

Termination: If `v` is not found earlier, the algorithm will terminiate by reaching `j > A.length = n` and returning `NULL`. In relation to the invariant this means that the subarray `[1,n]` did not contain `v`. Therefore the invariant is fulfilled and the algorithm terminates correctly.

# Answer
```
LinearSearch( Array A, int v):

    { forall i<1: A[i] != v } (vacuously true)
    for j= 1 in A.length:
        { forall i<j: A[i] != v } (invariant)
        if A[j] == v:
            return A[j] {A[j] == v} (this postcondition is sufficient)
        { forall i<j+1: A[i] != v } (by conjunction of the invariant and "else" condition)
    endfor

    { forall i<A.length+1: A[i] != v } (invariant and exit condition of the loop)
    return NULL

```

---

If you wand to be picky, you can prove that the algorithm returns *the first* occurrence of `v` in the array. In this case, the postcondition is a little stronger.

---

Note that the algorithm is so simple that it can be proven in a straightforward way.

1. if the algorithm returns a non NULL, the condition `A[j] == v` holds for some `j`, proving that `v` was found;
2. if the algorithm returns NULL, every `A[j]` has been tested (the loop is a pure `for`) and found different from `v`.
> 1 votes

---
Tags: algorithms, correctness-proof
---


# Question
Title: Is $k$-means clustering strictly NP-hard?
I've had lectures and read other threads claiming that $k$-means clustering is NP-hard. The fact that they never mention NP-completeness makes me suspect that *strict* NP-hardness is what's meant. This makes intuitive sense to me: problems in NP can be verified in polynomial time w.r.t. the input, and it seems like receiving a set of clusters can only be verified to be optimal by solving the entire problem once again.

Obviously, "I can't find a verification method" doesn't mean "there is no verification method". So, is $k$-means strictly in NP-hard, or is it NP-complete?

# Answer
> 2 votes
NP is a class of decision problems, i.e., problems where the answer is "yes" or "no". Whether $k$-means clustering is in NP depends on how you formulate it.

One standard formulation would be as an optimization problem:

> **Optimization:** Given $n$ points, find a partition into $k$ clusters that minimizes the sum of squared distances between each point and the centroid of its cluster.

Optimization problems like this aren't technically in NP, just because the output is not just "yes" or "no" (it's a $k$-partition of the points). However, we call them NP optimization problems because the natural corresponding decision problem is in NP. Here's the natural corresponding decision problem for the above formulation:

> **Decision:** Given $n$ points and a number $d$, is there a partition into $k$ clusters such that the sum of squared distances between each point and the centroid of its cluster is at most $d$?

This problem is almost the same as the original problem. In particular, given a solution to the decision problem and by binary searching on $d$, we can find out what the optimal sum of squared distances is fairly accurately. It's trickier to extract the actual partition from a solution to the decision problem, but in practice we usually find that algorithms for the decision problem also turn into algorithms for the optimization problem. So while the decision problem might technically be easier (it's certainly no harder, as a solution to the optimization problem also solves the decision problem), we view them as roughly the same complexity.

And the decision problem is in NP. A certificate is a partition of the points, which can be encoded in $n \log k$ bits. We can verify that the partition achieves the claimed distance by computing the centroid of each cluster and then the sum of squared distances. We need to prove that these computations only need a polynomial number of bits to be sufficiently accurate, but because it's just a linear number of additions and multiplications, this is true.

---
Tags: complexity-theory, np-complete, np-hard, clustering
---