# Question
Title: Possibility to prove that a function in big-theta is in big-O and little-o
I understand that many similar questions of this sort have been asked, but in this case, the solution does not appear to be provable - or is it?

Question: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = O(h(n))$

Current solution:

$f(n) = \Theta (g(n))$ implies that $c\_1 . g(n) \le f(n) \le c\_2 . g(n)$ for $c\_1, c\_2 \in \mathbb{N}$ and $\forall n \ge k\_1$ Call this equation $1$.

$g(n) = o(h(n))$ implies that $g(n) \< c\_3 . h(n) $ for $c\_3 \in \mathbb{N}$ and $\forall n \ge k\_1$ Call this equation $2$.

Multiply $2$ by $c\_2$.

$c\_2 . g(n) \< c\_2 . c\_3 . h(n)$ Call this equation $3$.

From $1$ and $3$ it can be inferred that:

$f(n) \le c\_2 . g(n) \< c\_2 . c\_3 . h(n)$

Which means that $f(n) \not\le c\_4 . h(n)$ (where $c\_4 = c\_2 . c\_3$) and therefore $f(n) \not = O(h(n))$. Is this way of approaching the problem correct, or is it - as my intuition tells me - I've missed something entirely obvious?

# Answer
Yes, it looks like that you missed something obvious.

A stronger claim: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = o(h(n))$.

---

Sketch of a proof: $f$ is bounded both above and below (up to a constant factor) by $g$ asymptotically, which is informally understood as $f$ and $g$ are the same asymptotically. $g$ is dominated by $h$ asymptotically. Hence $f$ is dominated by $h$ asymptotically.

(Sure, the above sketch is no more than rephrasing the claim in English. Well, that is how you (or at least I) would like to understand and reason about the situation)

---

Here is a detailed proof.

$f(n) = \Theta (g(n))$ implies that $c\_1g(n) \le f(n) \le c\_2 g(n)$ for some $c\_1\gt0,\\,c\_2\gt0,\\,k\_1$ and any $n \gt k\_1$.

$g(n) = o(h(n))$ implies that $|g(n)| \< c\_3 h(n) $ for some $c\_3\gt0,\\,k\_2$ and any $n \gt k\_2$.

Let $k\_3=\max(k\_1,k\_2),\\, c\_4=\max(c\_1,c\_2)c\_3\gt0$. Then for any $n\gt k\_3$, $$\begin{align} |f(n)|&\le \max(|c\_1g(n)|, |c\_2g(n)|)\\ &\lt\max(c\_1c\_3h(n),c\_2c\_3h(n))\\ &=\max(c\_1,c\_2)c\_3h(n)\\ &=c\_4h(n) \end{align}$$ Note the first inequality above is guaranteed by the fact that $f(n)$ is bounded between $c\_1g(n)$ and $c\_2g(n)$ since $n\>k\_1$.

---

Finally, note that $f(n)=o(h(n))$ implies $f(n)=O(h(n))$.

---

P.S. There is some typo in your question. For example, "$c\_1, c\_2\in\mathbb{N}$" should be "some $c\_1,\\,c\_2\in\Bbb{R}^+$" or "some $c\_1\>0,\\,c\_2\>0$". If you let $f(n)=n, g(n)=2n$, then there is no natural number $c\_1$ such that $c\_1g(n)\le f(n)$ for even one positive $n$.
> 1 votes

# Answer
From $f(n) \le c\_2 \cdot g(n) \< c\_2 \cdot c\_3 . h(n)$ you can infer that $f(n) \< c\_4 \cdot h(n)$ with $c\_4 = c\_2 \cdot c\_3$. Therefore $f(n) = o(h(n))$, and therefore also $f(n) = O(h(n))$, since this is a weaker statement (if $f(n) \< c\_4 \cdot h(n)$ is true, then certainly also $f(n) \le c\_4 \cdot h(n)$ is).

---

Also notice, that you should be a little more precise with your formulations. $f(n) = \Theta(g(n))$ means, that there exist some $c\_1, c\_2 \in \mathbb{N}$ with ... The inequality doesn't hold for every choice of $c\_1$ and $c\_2$.
> 0 votes

---
Tags: algorithms, algorithm-analysis
---


title: Looking for a problem provably not in P

text:
# Question
Title: Looking for a problem provably not in P
My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. Papadimitriou basically says that the proof is very similar to that of Cook-Levin theorem and do it yourself. Also, I wish to see the paper why Checkers is EXP-complete, but couldn't find a free version on the net.

Can you show me why a problem can be EXP-complete and *not in P provably*? How is the diagonalization encoded in the problem instances?

# Answer
> 6 votes
The time hierarchy theorem already does the diagonalization for you.

Let $X$ be any $\mathbf{EXP}$-complete problem. If $X\in\mathbf{P}$, then $\mathbf{EXP}=\mathbf{P}$, since we can solve any problem in $\mathbf{EXP}$ by using the polynomial-time reduction to $X$ followed by the polynomial-time algorithm for $X$. But $\mathbf{EXP}=\mathbf{P}$ contradicts the time hierarchy theorem, because that tells us that there are problems in $\mathbf{EXP}$ that are not in $\mathbf{P}$. Therefore, $X\notin\mathbf{P}$ for any $\mathbf{EXP}$-complete $X$.

Honestly, the proof that checkers is $\mathbf{EXP}$-complete will be long and not at all enlightening: the only thing that simulating Turing machines with checkers positions will teach you is that the craziest systems can support computation. It's much easier to see that the following problem is $\mathbf{EXP}$-complete. The input is the description of a Turing machine $M$, and an input $x$. You accept if $M(x)$ halts within $2^{|x|}$ steps and reject otherwise. Call the language of accepted strings $L$.

So, let $Y\in\mathbf{EXP}$ be a set of strings over, e.g., $\\{0,1\\}^\*$. It is decided by a Turing machine $M$ that runs in at most $2^{n^c}$ steps for some integer constant $c$, on inputs of length $n$. We define a new Turing machine $M'$ with input alphabet $\\{0,1,p\\}$ ("$p$" for "pad") that behaves as follows:

* if its input is of the form $z\\,p^{|z|^c-|z|}$ for some $z\in\\{0,1\\}^\*$, it simulates $M(z)$ and accepts or rejects as that machine does;
* otherwise, it rejects.

Note that $|z\\,p^{|z|^c-|z|}| = |z|^c$.

Now, the reduction of $Y$ to $L$ is as follows. Given a string $y\in\\{0,1\\}^\*$ for which we want to know whether $y\in Y$, we ask whether $(\langle M'\rangle, y\\,p^{|y|^c-|y|})\in L$. We can construct this query in polynomial time, since the description of $M'$ is some constant string, and we just need to write an easily computed polynomial number of $p$'s after $y$. And we have $(\langle M'\rangle, y\\,p^{|y|^c-|y|})\in L$ iff $M'$ accepts $y\\,p^{|y|^c-|y|}$ in at most $2^{|y\\,p^{|y|^c-|y|}|}=2^{|y|^c}$ steps, iff $M$ accepts $y$ in at most $2^{|y|^c}$ steps, iff $y\in Y$.

Similar techniques give you complete problems for any time or space complexity class.

---
Tags: reductions, complexity-classes
---


title: Asymptotic analysis of a summation

text:
# Question
Title: Asymptotic analysis of a summation
I was calculating the time complexity of one of the phases of my proposed algorithm, but unfortunately, I faced a problem about solving that and providing an understandable running-time. This phase of the algorithm indeed iterates a task $t$ times where $t$ is that iteration in which the algorithm achieves the desire result (optimal value). Each iteration $i$, where $0\leq i\leq t$, runs in $O\big((Y-iy)(\log(Y-iy)+D-id)\big)$ such that $y$ is the expected amount by which $Y$ decreases and $d$ is also the expected amount by which $D$ decrease at each iteration $i$. Therefore the total time complexity of this phase is as follows:

$$\sum\_{i=0}^t O\big((Y-iy)(\log(Y-iy)+D-id)\big)\\,.$$

Now I would like to find a nice solution for that. Can you help me approximate this in order to obtain a better solution? Any help will be appreciated. Thank you in advance.

# Answer
Assuming all the quantities are positive, just use $\log(Y-iy)\leq \log Y$, expand the brackets and use the standard identities for $\sum\_i i$ and $\sum\_i i^2$. The $\log$ term disappears anyway since, asymptotically, it's dominated by the terms polynomial in $i$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Space/Time Hierarchy Theorem - proving the language of the machine is in the larger space class
I am trying to understand the space and time Hierarchy theorems according to

> Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach

but the more general case.

What I don't understand is why the language decided by our custom machine is in the larger complexity class. For example, with the case of time complexity, the cost of simulating the input machine is $t\_1 \log t\_1$, so why is the language decided by it in $DTIME(t\_2)$ but not in $DTIME(t\_1 \log t\_1)$?

thanks

# Answer
> 1 votes
A rich man walks into a bar and says, "I can buy this beer because I am a millionaire." Eloo says, "The beer costs \\$5. I don't understand why this millionaire can buy it, but this guy with five dollars can't."

Remember that $\mathrm{DTIME}\[f(n)\]$ is the class of languages that can be decided by a deterministic Turing machine that uses **at most** $f(n)$ steps on any input of length $n$. So, since $t\_1\log t\_1\leq t\_2$, anything in $\mathrm{DTIME}\[t\_1\log t\_1\]$ *is* in $\mathrm{DTIME}\[t\_2\]$.

# Answer
> 0 votes
So after looking into it again I realized that if we give the machine any amount of additional time asymptotically (any time asymptotically larger than $t\_1\log t\_1$), then we can construct a language for it because it will accept the machine of the language and we can also add all the machines that reject their own description to that language too.

---
Tags: complexity-theory, time-complexity, space-complexity
---


# Question
Title: Determine whether two collections of items can be paired
Given collections `I` (items) and `S` (slots), where `I >= S`. And a pairing function that determines whether a slot can accept an item.

Is there an efficient way to find whether a "complete" pairing of items to slots exist, where "complete" means every slot is filled?

(More importantly for my use case... is there a way, other than trying every combination, to determine if no such pairing exists?)

# Answer
> 4 votes
Yes. You're just looking for a maximum matching in the bipartite graph where one side is the items, the other side is the slots and there's an edge between an item and each slot it's compatible with.

There are a number of efficient algorithms for this. The standard method taught to CS undergraduates is the augmenting paths algorithm of Hopcroft and Karp.

---
Tags: algorithms, matching, bipartite-matching
---


# Question
Title: Understanding Alpha Beta Pruning: Why do we ignore the values of a unsearched tree after the first leaf, can they not include acceptable values too?
So this is my question.

I am trying to understand this part of the book:

At d) why do we stop looking at the other nodes in that branch? There could be a acceptable value next to the 2? I am just trying to understand alpha beta pruning for a while.

# Answer
At $d)$, minimizer is comparing the $2$ he found with the currently best option for the maximizer higher in the tree (at node $A$, where maximizer will choose between $B$,$C$,...), which is $3$, at node $B$. He then knows that maximizer will not choose $C$.

The node $C$ **will** have value $2$ when minimizer sets it and **would** have value $2$ or less if minimizer explored it fully, so he doesn't need to waste his time searching other branches from $C$ if he already knows that maximizer will not choose anything lower than $3$.

I think what confuses you may be the following:
You are imagining a real-life gameplay scenario, but this is different in the sense that minimizer and maximizer **must** play their best move and **will** calculate it correctly.
So there is no way that minimizer could in this situation "fool" maximizer by setting the wrong value of $C$ (something higher than $3$) to force maximizer to choose it. If we assume that scenario a possibility, we must also implement the maximizer with "free-will" so he may not choose his best option but this is no longer an $\alpha$-$\beta$ pruning :)
> 1 votes

---
Tags: artificial-intelligence, search-algorithms
---


# Question
Title: How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression

```
 a(b*)c(d*)e

```

can be proved to be regular using pumping lemma. The string generated by this expression are of the form.

> abcde
>
> abbcdde...

We can not write these string in the form of $xy^iz$. We can only write it in the form $vx\_1^iyx\_2^jz$.

So, how can I prove using pumping lemma that the language generated by the expression is regular?

# Answer
The pumping lemma states a proprety of regular languages:

> If $L$ is a regular language then there exists an integer $p$ such that if $w \in L$ has length at least $p$ then it can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

Unfortunately, this property doesn't characterize regular languages. That is, there exist non-regular languages which also satisfy the property stated in the lemma. An example is $\\{a^i b^{j^2} : i,j \geq 0 \\} \cup \\{ b^k : k \geq 0 \\}$.

Your language satisfies the pumping lemma with $p = 4$. If $w \in ab^\*cd^\*e$ has length at least 4, then it must contain $b$s or $d$s. You can check that if it contains $b$s then you can take $y = b$, and if it contains no $b$s then you can take $y = d$.

As stated above, this doesn't prove that the language is regular. The simplest way to show that $ab^\*cd^\*e$ is regular is to use the fact that all languages given by regular expressions are regular. It is also not hard to construct a DFA that accepts your language.
> 16 votes

# Answer
You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) might have defined them as any of

* languages described by regular expressions;
* languages accepted by deterministic finite automata (DFAs);
* languages accepted by nondeterministic finite automata (NFAs).

If, additionally, you've proven that some or all of these definitions are equivalent, you can use any of the appropriate ones.

In this case, your language is defined by a regular expression. If that's your definition of regular languages, you're already done.

Our reference question has more information.
> 18 votes

# Answer
You already got your answer, this is just to make it clear that the problem you are facing is actually a logical one.

The pumping lemma is an implication: „If $L$ is regular then XYZ“. It states a *necessary* condition for a language to be regular (not a *sufficient* one). Note how the implication does not say anything about what happens if XYZ is true.

BUT you can use the contraposition of the implication, i.e. „if XYZ is not true“ to prove that a language is *not* regular (because we know that all regular languages *do* satisfy XYZ)

As already noted by the others you can show that $L$ is regular by showing that you can generate $L$ while adhering to whatever rules you have defined as being valid for regular languages (e.g. can be generated by a DFA, regular grammar, etc.). Note how OTOH you can‘t use this to show that some language is *not* regular, since you would need to show that no such DFA exists - but how can you know that it really doesn‘t exist and it is not simply your disability to find it? Well, here is where you can use the pumping lemma.
> 3 votes

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


# Question
Title: Are there infinite possibilities to the outcome of the P vs. NP question?
The P vs. NP poll provides 3 possibilities: equal, not equal, and independent. This is reasonable, because despite the law of the excluded middle you must supply a proof for your answer, which itself is insufficient. But then the statement "P vs. NP is independent" itself can be independent, with a proof. And this process can go on indefinitely. One of them must be provable, or did I miss something? Anyway the number of possibilities is infinite, instead of 3. Is this correct?

# Answer
This isn't really a question about P vs. NP - any other statement would do in its place. The point is that there are a couple different "philosophical contexts" being mixed up here, and depending on exactly how you ask the question each of $2$, $3$, or infinity are reasonable answers *(I'm not claiming that these are exclusive, but I think they frame the question well)*:

* **The Platonic**: If we adopt a certain measure of Platonism *(for P vs. NP, something like "the natural numbers exist objectively even if our understanding of them is limited")* then yes, every statement is either true or false. Provability from a given theory is a purely secondary matter, and the independence of a statement from (say) ZFC has no bearing on its truth.
* **The formalist**: If we don't want to make any philosophical commitments, the most we can ask is whether the statement is provable *in a given theory*. Once we fix a single theory of interest - say, ZFC - the formalist version of the question does indeed boil down to three possibilities: our statement is either provable in that theory, or disprovable in that theory, or independent of that theory. *(Or the theory is inconsistent, in which case the first two options hold simultaneously.)*

+ Wildness of the type you're asking about emerges when we ask the "broader" formalist question: **which theories is our statement provable in**? When asked this way we do indeed get a wild situation, since for any interesting statement there will be some theories which prove it and some theories which disprove it. *Note that this is really a more "stable" perspective than focusing on a single theory, but in practice mathematicians tend to prefer a single background theory so we can ignore foundational considerations which aren't really germane to the specific mathematics at hand.*

Of course this conflicts with the language we often use in actual practice. The "true/false/independent" trichotomy blurs the Platonic and formalist contexts by conflating a fixed theory - usually ZFC - with "truth." This is a common practice, but is at best raising the question of why we assign privileged status to ZFC specifically *(why not ZFC + an inaccessible? or ZF? or ZC? or ...)*. Ultimately it's just a linguistic convention: we recognize that in many situations, in order for our everyday mathematical language to be truly accurate we need to implicitly understand "true" as an abbreviation for "provable in ZFC."
> 5 votes

---
Tags: p-vs-np
---


# Question
Title: Is This A Solution for does P=NP problem?
My understanding had been badly lacking in just what complexity theory was in the context of computer science. I thought it was abstracted to all mathematical problems applicable outside the realm of computation. Truthfully, I doubt I understand it. But seeing as how this is here to stay, here's an idea for a P=NP proof that is hopefully less embarrassingly off. The heart of the question being can NP problems be both solved in polynomial time and verifiable in linear time.

Take P to mean all problems that are solvable in polynomial time, and verifiable in linear time. Take NP to mean all problems that are solvable in non-polynomial time, and verifiable in P.

Problems exist that have been solved in P and verified in Linear time. Problems exist that have been solved in NP and verified in P. There exist solutions to problems in NP that are considered P.

Alright here's where it gets weird. Problems in NP can be solved in P, if a solution is found rapidly enough to be considered P. Such a problem in NP would be considered verified in Linear time if a correct solution was found in P. That would mean that for some problems P=NP (call this getting lucky). Problems in NP are not all solved in P, which means they are not verified in Linear time. This means P=/=NP. P=NP iff all NP were solved in P and verified in Linear, which is not the case.

/shrug That's my best guess.

# Answer
> 5 votes
There a lot of assumptions here that fall to "common sense" without scrutiny, but that's the point of rigor; it's the scrutiny that leads intuition.

Anyway, a number of your statements are vague and unproven.

1. "By definition, everything in existence is in existence. This means nothing can't exist."

Whose definition? What are the consequences of this definition? We can't even prove that there's a set that contains all sets out there. Furthermore, how does this mean nothing cannot exist? If "nothing" is a word we use to describe the absence of objects, how does "nothing" not exist? Without harping too much on the metaphysics, these broad modes of reasoning and loosely connected ideas don't really say much about the problem but muddy the water with vague beliefs.

2. "Therefore the concept of not or non, can’t exist, as this implies non existence. This means that Non-polynomial time problems can’t exist."

The negation of something (its NOT) and its non-existence (being "non") are two different things. For some proposition A, I can describe its negation ~A and have little trouble convincing myself and peers of its existence. Furthermore, what is the relationship between negation to non-polynomial time?

3. "Existence can’t equal non-existence. Thus, P=/=NP. As a result, there is only P."

Where do you claim that existence cannot equal non-existence? I agree in broad, but I don't really see any steps leading up to it or its relevance to complexity classes.

In general, I think you have mixed up the negation of a proposition with the difference between complexity classes. We want to find out if the boundary between P and NP is arbitrary. If you want to prove that NP doesn't exist, then you might want to start by trying to prove that a general NP problem can be solved in P.

# Answer
> 3 votes
You also don't seem to know what NP is. NP is **not** non-polynomial time, but nondeterministic polynomial time, big difference, since there are complexity classes like EXP, which are proven to be non-polynomial time.

Edit: removed wrong part

# Answer
> 3 votes
This is not a proof of P != NP nor does it approach one.

Among other issues, we have very similar classes to P and NP where they are in fact equal. For example, we know that PSPACE = NPSPACE by Savitch's theorem https://en.wikipedia.org/wiki/Savitch%27s\_theorem but nothing in your suggested proof uses at all that one is distinguishing time from space.

You appear to be under a misconception that P and NP have to do with some sort of broad notion of "existence"- this is not the case. While the definition of NP does talk about the existence of specific types of proofs, that's not the same thing.

"However, there also needs to exist a reality where paradoxes are true because paradoxes are included in everything. Therefore, there are 3 realities. One where P=NP, one where P=/=NP, and one where both exist at once. The other can't exist because both p=np and p=/=np are false. Making true nothingness."

I'm not sure what you mean by "reality" here, but it sounds like it has little resemblance to anything connected to theoretical computer science. It is possible that P != NP is independent from the standard set of mathematical axioms of ZFC, in which case one could construct *models* where P != NP or where P= NP, but that's very different from what you appear to be talking about.

"By the way, this is also The Theory of Everything"

The Theory of Everything is an idea about physics. P != NP is an idea in math/theoretical computer science. By nature they cannot be the same thing. One is a description of our specific universe, and one is a proof about an abstract mathematical fact. If one thinks this is somehow the "Theory of Everything" then it is likely that one doesn't understand what we mean by a Theory of Everything or what we mean when we talk about a mathematical proof.

Speaking more broadly, let me give some general advice:

First, if you want to attack a problem, make sure you actually understand the problem in question. There are a lot of good introductions to theoretical computer science out there; my preferred book is Moore and Mertens, but others will have other texts; many people like Sipser "Introduction to the Theory of Computation."

Second, don't expect that you are going to solve some well known open problem and certainly don't expect that you are going to solve it in a paragraph. If you are wondering if you have single paragraph answer to any famous open problem that myriad very smart people have thought of, the answer is definitely no. In general, the vast majority of mathematicians and computer scientists don't go around solving the very biggest problems in their fields, and don't expect to do so. What we do spend time on is solving little, approachable problems, and we occasionally nibble away at the big ones, hoping to make enough progress that eventually someone will put everything together to solve the big ones. If you go into any of these areas hoping to solve the largest problems, you will almost certainly end up disappointed.

---
Tags: complexity-theory
---


# Question
Title: M is a Determinstic TM with one tape, c2 is c1 reachable, if it's reachable within finite positive time
$M=(Q,\sum,\Gamma, \delta, q\_{0}, q\_{accept}, q\_{reject})$ is a TM with one tape. let $c\_{1}, c\_{2}$ be two configurations of $M$.

A configuration is defined like this:

$uqv$ where $(q\in Q; u,v\in \Gamma^{\*} )$

we say that $c\_{1}$ is reachable from $c\_{2}$ in $M$, if when $M$ is in configuration $c\_{1}$ it can reach the configuration $c\_{2}$ in a finite number of steps that is greater than 0.

Is the following language TR (Turing Recognizable), is it Decidable?

$L=\\{\langle M, c \rangle \mid M\text{ is a TM; configuration }c\text{ is reachable from configuration }c\text{ in }M\\}$?

I know that the answer to this is no, $L$ is not Decidable. I just fail to see the logic behind that.

See I thought $L$ is Decidable because of the following justification:

$L$ is decided by the structure of $M$ it's self with no regards to whatever language $M$ accepts so it is intuitive.

Let's run $M$ non diterministically on any letter of it's alphabet until we get to cofiguration $d\ne c$ then again to reach another config. and so on until we get to configuration $c$ it's self after a threshold number of steps, let's say $N^{q}$ number of steps, where $N$ is the number of configurations in $M$ and $q$ is the number of letters in alphabet.

Kindly explain why language $L$ is TR and not Decidable.

Thank you in advance.

# Answer
Since no answer has been posted I will attempt the answer my self: Since Giacomo explained why $L$ is TR(I thank him for that) I won't talk about it.

I will prove $L$ is not decidable:

We do that by building a machine $K$ that will decide the halting problem $L\_{1}$ using $G$ the decider of $L$ that we assume exists.

$L\_{1}$={\< $R$, $w$ \> | $R$ is a TM; $w \in \Sigma^{\*} $; $R$ halts on $w$ }

Description of $K$:

Build TR $H$ that has a configuration $c$ as follows:

* "Configuration $c$": On input \<$R$, $w$ \> if $R$ halts on $w$ go to configuration $d$ which on any input goes back to configuration $c$.
* else go to configuration $e$ and loop forever.

Run $G$ on input \<$H$,$c$ \> if $G$ accepts, accept else reject.(if $H$ accepts $K$ accepts and vice-versa)

Giving \< $R$,$w$\> to $K$ as input, $K$ will decide if $R$ halts on $w$ if and only if (iff) $G$ decides if $c$ is reachable from $c$ in $H$.

But we know that the halting problem is not decidable in contradiction to what we have assumed in the first place, so $G$ cannot exist there for $L$ is not decidable.
> 1 votes

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


# Question
Title: Subgraph isomorphism on star multi-graphs with labelled edges
My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example, and two reformulations below. The second reformulation is equivalent to an unbalanced assignment problem with a binary cost matrix.

**Original Formulation**

I have two star multigraphs: A small *pattern*, and a large *target*. The graphs may have multiple edges between a single pair of nodes. The edges of each graph have labels from some small set of labels. I am looking for the most efficient algorithm to check if there exists a subgraph of the target which is isomorphic to the pattern.

**Example**

Consider the pattern

and the target

where edge colors represent labels. There is a subgraph of the target consisting of the nodes 1, 2, 3, and 5 (and some edges that I haven't given names) which is isomorphic to the pattern graph. Note that the subgraph need not be a node-induced subgraph, and is not in this case.

**Reformulation 1**

Enumerate the neighbors of the center of each graph: $1, 2, \dots n\_{\mathrm{pattern}}$ and $1, 2, \dots n\_{\mathrm{target}}$. Define $A\_{i,j}=1$ if node $i$ in the target has at least as many edges of each type to the target's center as node $j$ in the pattern has to the pattern's center. If the constraint is not met, then $A\_{i,j}=0$. The problem becomes: Given a binary matrix $\mathbf{A}$ with more rows than columns, does there exist a permutation of the rows such that the main diagonal is all ones?

**Reformulation 2**

You are given $n\_{\mathrm{target}}$ workers to perform $n\_{\mathrm{pattern}}$ tasks, where each worker is competent in only a subset of the tasks. Does there exist an assignment of workers to tasks such that each task has at least one competent worker assigned?

# Answer
> 1 votes
After you fix the star centers, your problem is simply bipartite matching.

---
Tags: algorithms, graphs, search-algorithms, constraint-satisfaction
---


title: Chomsky Hierarchy and P vs NP

text:
# Question
Title: Chomsky Hierarchy and P vs NP
I have read multiple questions here that involve this kind of subject but I haven't found any definite answer. In what class do regular languages belong? (P or NP or some regular are P and other NP), context-free languages? (same question) ,context-sensitive? and general languages? . I personally believe all regular languages belong in P class and the rest (more complex) languages of chomsky hierarchy are in the NP class. Can someone answer and provide some kind of proof for the answer? Thanks in advance.

# Answer
### Regular languages

Regular languages are in $\mathbf{P}$ because a deterministic finite automaton is a restricted deterministic Turing machine that runs in linear time.

### Context-free languages

In fact, any context-free language is in $\mathbf{P}$: Valiant showed in the 1970s that context-free grammars in Chomsky normal form can be parsed in time $O(n^3)$ \[1\]. $\mathbf{P}$ strictly includes the set of context-free languages, since $\\{a^nb^nc^nd^n\mid n\geq 0\\}$ is not context-free but is clearly in $\mathbf{P}$.

### Context-sensitive languages

Context-sensitive languages can be parsed in nondeterministic linear space \[2\]. We don't know the exact relationship between this class and $\mathbf{NP}$ but, since a linear space Turing machine can use exponential time, probably there are context-sensitive languages that aren't in $\mathbf{NP}$. However, showing this would be a major advance in complexity theory as it would imply that $\mathbf{NP}\neq\mathbf{PSPACE}$.

The problem of "Here's a context-sensitive grammar $G$ and a string $w$: is $w\in L(G)$" is $\mathbf{PSPACE}$-complete \[2\], so certainly every problem in $\mathbf{NP}$ can be reduced to the parsing problem for context-sensitive gramars. However, that's not the same thing as saying that every language in $\mathbf{NP}$ is defined by a context-sensitive grammar, since the $\mathbf{PSPACE}$-completeness result allows arbitrary polynomial-time computation in the reduction and also allows the grammar to depend on the instance. Hopefully, somebody can post a comment or answer clarifying this.

### Unrestricted grammars

Unrestricted grammars define all recursively-enumerable languages. This includes all of $\mathbf{NP}$ and includes undecidable languages such as the halting problem, which definitely aren't in $\mathbf{NP}$.

---

**References**

\[1\] L. G. Valiant, *General context-free recognition in less than cubic time*, *Journal of Computer and System Sciences* 10(2):308–315, 1974.

\[2\] Context-sensitive language, Wikipedia.
> 8 votes

---
Tags: complexity-theory, p-vs-np, chomsky-hierarchy
---


title: Definition of "overhead"

text:
# Question
Title: Definition of "overhead"
I am writing a paper on the invariance thesis introduced by Cees F. Slot and Peter van Emde Boas as;

> 'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

The paper I am writing is in Croatian where I cannot find a properly convenient word like "overhead". Also, I am unable to find a strict Computer Science definition for the term.

Specifically, I have $Time(M)$ as the cost of reducing the $\lambda$-term $M$ to its normal form and a Turing machine able to simulate this reduction in $O((Time(M))^4)$. Therefore, I would like to say "this TM can simulate $\lambda$-calculus with polynomial-time \[overhead\]" concisely as it is in English.

I would appreciate any suggestion in the form of literature references for the definition, advice on how to best define it myself or even synonyms of the word.

# Answer
> 1 votes
I doubt that “overhead” is a term. Here’s what we use in Russian papers:

1. оверхед — direct transliteration (for informal texts)
2. издержки — costs (of production)
3. Translations of “slowdown” (for time) and “blow-up” (for space).

---
Tags: complexity-theory, computation-models
---


# Question
Title: DFS timestamps, how important are they in pathfinding?
I am writing a work on pathfinding algorithms and DFS is a part of it. And the book Introduction to Algorithms and many another websites mention timestamps. And they say timestamps could be used for others algorithms using DFS, topological sorting and etc.

So for pathfinding these timestamps dont really matter?

Thank you for helping.

Here is the section from the book mentioning timestamps: Besides creating a depth-first forest, depth-first search also timestamps each vertex. Each vertex has two timestamps: the first timestamp :d records when is first discovered (and grayed), and the second timestamp :f records when the search finishes examining ’s adjacency list (and blackens )

# Answer
Correct. If you just want to check which nodes are reachable, or find any path from $s$ to $t$, you don't need the timestamps (the pre and post values).
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: (DROP) Data Reduction Algorithm - How it works?
I am studing a PHD framework which the propose is to reduce the dataset with the most representative samples for training a classifier. Maybe I am loosing something, but I could not undestand a specific part.

Basic this is the algoritm 1 proposed:

**Question 1**: line 7 says it will union 'edge (s,t)'. What it means? It means that Z'2 (output) will be a set of edges with s and t from different cluster-id's?

And I am asking it because the second algorithm in thesis is the following:

**I am not sure if I understood how it L list is generated because some edgs did not make sense by the figure below:**

**Question 2** Why 6 and 7 has the same element (triangles)? It not should be different, once the edges (from algorithm 1) are from different cluster-ids?

This is the link for thesis: http://repositorio.unicamp.br/handle/REPOSIP/275528?locale=en (page 21-22)

# Answer
> 1 votes
Algorithm 1 takes non-annotated data as input, so it is agnostic to the labels (shapes). In line 1, algorithm 1 computes clusters on the non-annotated data. The cluster assignments do not necessarily correspond exactly to the labels. The output of algorithm 1 will be a set of edges between data in different clusters, but the data need not have different labels. So the reason edges 6 and 7 can connect between triangles is because the triangles have been assigned to different clusters.

---
Tags: graphs, machine-learning, reinforcement-learning, clustering
---


# Question
Title: Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks
Lets just say I have two lists of the running time of tasks *A* and *B*. Formally, I would have:

```
A = {a_1, a_2, a_3 ... a_n}
B = {b_1, b_2, b_3 ... b_n}

```

I can only have one task from *A* running at any one time. All other tasks in *A* have to wait on that task to complete before they can be released. I can have any amount of tasks from *B* running at any one time, **however** I cannot run a task from *B* if its equivalent task from *A* has not finished. For example, I could not run `b_1` if `a_1` had not finished beforehand.

To put this in an analogy, say that I have some athletes who will perform a di(duo?)athlon: they will run laps on a running field then cycle for some distance. Only one athlete can be running laps on the field at any one time, and only after he or she has finished can he or she proceed to cycling. Any amount of athletes can be cycling at any one time. In this case, *A* would be the amount of time I know an athlete will take to run their laps around the field and *B* would be the amount of time I know it will take them to cycle the required distance.

I would like create an algorithm which devises a schedule for my tasks (or for my athletes) so that the total time it takes for all of them to complete their activities is kept to a minimum.

The basic jist is this: The time it takes for any individual athlete to complete their tasks is `running_time + cycling_time + waiting_time`. The running and cycling times I know, while the waiting time would be the sum of all running times of all athletes prior to the current one, i.e. For some athlete `a_i` the `waiting_time = a_1 + a_2 + a_3 + ... + a_(i-1)`. Intuitively, I would like the athletes with shorter running times and longer cycling times to go first since I want to maximize the amount of athletes cycling at any one time.

My question is: how would I go about doing this? How would I schedule my tasks (athletes)? Obviously, I could go about computing every single possibility and picking the best one, but that would result in some ludicrous `O(2^n)` algorithm. Subsequently, (it seems?) a greedy algorithm would be the best choice.

EDIT: A few days later.

The way (again, I believe) that seems to be the most optimal is this: Let `a_max = a_1 + a_2 + ... + a_n - a_i`. Informally, this is to say that `a_max` is the worst-case waiting time for a task/athlete `i`. Then, let `completion_time_for_i = a_max + b_i`. We compute `completion_time_for_i` for each task/athlete and order it in a descending fashion. That is to say, tasks/athletes with larger `completion_time_for_i` will be up a the top of the schedule, while tasks/athletes with lower `completion_time_for_i` will be lower down on the schedule.

The point is that `a_max` is larger the smaller `a_i` is and `completion_time_for_i` will be largest for tasks/athletes with the greatest difference between their running and biking times. Hence, we are doing what intuition suggests: putting the tasks/athletes with shorter running times and longer biking times first.

Of course, I cannot escape the math, can I? I'm not even entirely certain where to start my proof to show if this algorithm is "correct". I guess it would be something along the lines of: my schedule takes *x* time. The greedy algorithm is incorrect if there exists a *y* such that *y* \> *x*. However (assuming that my algorithm is correct) I cannot construct a schedule which takes *y* time and hence the proof by contradiction (as suggested in the link from @D.W.).

# Answer
> 1 votes
Nice exercise!

The usual strategy for designing greedy algorithms is to just brainstorm a bunch of different candidate strategies. You're going to sort by some quantity; try some ideas for what that quantity might be -- maybe it is sorted by $a\_i$, or by $b\_i$, or by $a\_i-b\_i$, or something; try to come up with as many possibilities that make sense. Then, for each candidate strategy, test whether it appears to be correct using the methods in How to prove greedy algorithm is correct.

Try that for a little while. If you're still stuck, here's an extra hint (don't look until you've tried the above):

> See if you can figure out which of the $n$ items must come *last*.

---
Tags: algorithms, algorithm-analysis, time-complexity, greedy-algorithms
---


# Question
Title: Proof that Turing machines and computers have same power
How do we prove that any logical circuit can be simulated by a Turing machine?

For example, we take a logical circuit $L$ that is made of gates *and*, *or*, and *not*. This circuit determines a problem, for example, whether the input is an even number. How can we prove that if a problem is decided by a logical circuit, there is a Turing machine that can decide the problem?

In other words, how do we prove that a CPU is equal in power to a Turing machine? We should not forget that a Turing machine has infinitely many cells.

# Answer
> 5 votes
Turing machines and Boolean circuits cannot really be compared, since Turing machines handle inputs of arbitrary length, whereas Boolean circuits only handle inputs of fixed length.

Furthermore, Turing machines and CPUs corresponds to two different computation models. Turing machines access their memory by moving a head across a tape. In contrast, a CPU accesses its memory via *random access*. The abstraction corresponding to CPUs is the random-access machine.

If we want to compare the power of Turing machines and circuits, we need to put them into equal footing. One way to do this is to consider a sequence of circuits $C\_0,C\_1,C\_2,\ldots$, one per input length. Such a sequence computes a language in the natural way: an input $x$ belongs to the language if $C\_{|x|}$ returns True when given $x$ as input. This circuit model is much more powerful than Turing machines – indeed, it can compute *any* language, whereas Turing machines can only compute decidable languages.

What went wrong? Let us consider your example, of circuits for parity. The circuits computing parity for different lengths of input are very similar to one another; they seem to be made from a "mold", a set of instructions which can be translated to a circuit of arbitrary length. In contrast, the circuit model considered in the preceding paragraph specifies no such relation between the different circuits. When we add this constraint – that the different circuits follow a "blueprint" – we do get a model equivalent to Turing machines. What exactly constitutes a blueprint is a bit technical (one option is to have the circuits generated by a Turing machine), but the intuitive idea should be clear.

Circuits also come up when trying to understand resource-bounded computation, such as the complexity class $\mathsf{P}$ of languages which can be decided in polynomial time. It is known that any such language can be translated to a "uniform" family of circuits *of polynomial size*. In this way, the fact that the language can be decided efficiently is reflected by the size of circuits that compute it.

# Answer
> 3 votes
If your circuit is of fixed-size, then a Turing Machine T exists to compute it. The reason is that the Turing Machine can simply contain a list with all the possible input/output pairs.

If your circuit is not of fixed size, then we distinguish two cases. Either the circuit can be computed by a TM, given the input size, or not. In the case the circuit can be computed by a TM, say T', then T can invoke T' to obtain the circuit encoding. Subsequently, T can evaluate the circuit on the input. In order to do so, T would topologically sort the circuit and obtain the output value of each gate until the output value of the output gate is obtained, which will be its output. In case there exists no TM T' to obtain the circuit given the size, then the language is uncomputable and T cannot exist. To see this, note that the circuit could encode the halting problem.

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


# Question
Title: Is DFA and Regular Expression equivalent?
The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that?

If Regular Expression cannot do that, does it mean that DFA and Regular Expression are not equivalent (in at least some cases)?

# Answer
According to Wikipedia:

> Given a finite alphabet $\Sigma$, the following constants are defined as regular expressions:
>
> * (empty set) $\emptyset$ denoting the set $\emptyset$.
> * ...

... a string that contains only an empty-set symbol is a regular expression, which represents the empty language.
> 4 votes

# Answer
Complementing xskxzr's answer, let me mention that if $L$ is a non-empty regular language, then $L$ has a regular expression not involving $\emptyset$; so we only need $\emptyset$ to accommodate the empty language.

This claim can be proved in many ways. One option is by induction on regular expressions. Let us prove the following claim by induction: if $r$ is a regular expression, then either $L\[r\] = \emptyset$, or $L\[r\] = L\[s\]$ for some $\emptyset$-free regular expression $s$.

We need to consider six cases:

1. $r = \emptyset$. In this case $L\[r\] = \emptyset$.
2. $r = \epsilon$. In this case $r$ is $\emptyset$-free.
3. $r = \sigma$, where $\sigma \in \Sigma$. In this case $r$ is $\emptyset$-free.
4. $r = s^\*$. If $L\[s\] = \emptyset$ then $L\[r\] = \\{ \epsilon \\} = L\[\epsilon\]$. Otherwise, we can assume that $s$ is $\emptyset$-free, and then $r$ is also $\emptyset$-free.
5. $r = st$. If $L\[s\] = \emptyset$ or $L\[t\] = \emptyset$ then $L\[r\] = \emptyset$. Otherwise, we can assume that $s,t$ are $\emptyset$-free, and then $r$ is also $\emptyset$-free.
6. $r = s + t$. If $L\[s\] = L\[t\] = \emptyset$ then $L\[r\] = \emptyset$. If $L\[s\] = \emptyset$ and $L\[t\] \neq \emptyset$, then $L\[r\] = L\[t\]$, and we can assume that $t$ is $\emptyset$-free. The case $L\[t\] = \emptyset$ and $L\[s\] \neq \emptyset$ is symmetric. Finally, if $L\[s\],L\[t\] \neq \emptyset$ then we can assume that $s,t$ are $\emptyset$-free, and then $r$ is also $\emptyset$-free.
> 0 votes

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


# Question
Title: How to create constraints for Mixed integer linear problem?
i am a beginner to `Discrete optimization` domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can use gas and electricity or electricity and hot water or hot water and gas for their operation. Each appliance has some set of tasks, each task use above mentioned energy carriers based on the requirement.

The question is, i want to create a constraint such that if the task of the appliance starts with electricity and hot water, it should end with using electricity and hot water. It should not alter the energy carrier to gas during the operation.

I have created some of the decision variables like this:

$x\_{t,i,j}$ indicates whether task j of appliance i at time slot k processed by electricity or not; 1 = task processed; 0 = not processed

$y\_{t,i,j}$ indicates whether task j of appliance i at time slot k processed by natural gas or not; 1 = task processed; 0 = not processed

$z\_{t,i,j}$ indicates whether task j of appliance i at time slot k processed by hot water or not; 1 = task processed; 0 = not processed

I tried with the following constraint it seems something missing.

$\sum\_{k=t}^{t+H\_{i,j}}$ $(x\_{t,i,j}+y\_{t,i,j}+z\_{t,i,j})$ $\geq$ $H\_{i,j} (x\_{t,i,j}+y\_{t,i,j}+z\_{t,i,j})$

Where `i` is index of appliance.

`t` is current time slot.

`j` is index of task.

$H\_{i,j}$ is run time of tasks.

# Answer
You have the constraint:

$\sum\_{k=t}^{t+H\_{i,j}}$ $(x\_{t,i,j}+y\_{t,i,j}+z\_{t,i,j})$ $\geq$ $H\_{i,j} (x\_{t,i,j}+y\_{t,i,j}+z\_{t,i,j})$

I presume your iteration variable is $t$. In that case this says that the amount of energy used in the task is at least the expected amount of energy based on its first slot multiplied by task length. This doesn't guarantee using correct type of energy etc.

Assuming you use all required types of energy in the first slot of the task and that you need to use exactly two of them, you should have the following:

1. Exactly two types of energy used in first slot:

$$x\_{t, i, j} + y\_{t, i, j} + z\_{t, i ,j} = 2$$

2. If you use some energy in first slot, you need to use it until the end of the task, so in each step variable indicating use of some energy type has the same value as in the first step of the task:

$$ \forall\_{t'=t}^{t + H\_{i,j}} x\_{t', i, j} = x\_{t, i, j} $$

Same goes for $y$ and $z$ variables.
> 0 votes

# Answer
I suggest you use the variable to represent when the task was *started*. For instance, $x^\*\_{t,i,j}$ indicates that task $j$ of appliance $i$ is started at time $t$, and the task is using electricity. For example if the task is running at times $t,t+1,\dots,t+9$, you'll have $x^\*\_{t,i,j}=1$ but $x^\*\_{t+1,i,j}=\dots=x^\*\_{t+9,i,j}=0$.
> 0 votes

---
Tags: optimization, linear-programming, integer-programming, constraint-programming
---


# Question
Title: Ordered set cover problem: is it NP-hard?
Given a set of elements $U=\\{1,2,\ldots,n\\}$ and a collection of $m$ sets $\\{S\_1,S\_2,\ldots,S\_m\\}$ whose union equals $U$. Each element $e$ of a set $S\_i$ has a weight $w\_i(e)$. The weight $w(S\_i)$ of the set $S\_i$ is defined as $w(S\_i):=\max\_{e\in S\_i}w\_i(e)$.

The problem is to choose an **ordered** collection of sets $O$ from $\\{S\_1,S\_2,\ldots,S\_m\\}$ whose union is $U$ and its **total weight** is minimum. **Here, if $O=\\{S\_1,S\_2,\ldots,S\_p\\}$, then we choose $S\_1$, then we choose $S\_2$, etc.** We define the *total weight* $W(O)$ as the sum of the weight of the sets covering new elements, i.e. $$W(O)=w(S\_1)+w(S\_2\backslash S\_1)+\ldots+w(S\_p\backslash\bigcup\_{i=1}^{p-1} S\_i),$$ since we choose $S\_1$ first, then all elements of $S\_1$ are new. At the time we choose, $S\_2$, the newly covered elements are $S\_2\backslash S\_1$, etc.

# Answer
> 3 votes
The decision version of your problem is NP-hard (and so, NP-complete), by reduction from SAT.

Let $\varphi$ be a SAT formula on variables $x\_1,\ldots,x\_n$ and clauses $C\_1,\ldots,C\_m$. The universe will be $\\{x\_1,\ldots,x\_n,C\_1,\ldots,C\_m\\}$. For every literal $x\_i$ or $\bar{x}\_i$, there will be a set $S\_i$ or $\bar{S}\_i$ consisting of $x\_i$ together with all clauses satisfied by the literal, in which all elements have unit weight. This instance has a solution of weight at most $n$ if and only if $\varphi$ is satisfiable.

Indeed, if $\varphi$ is satisfiable, then the sets corresponding to a satisfying assignment are a solution of weight $n$, in any order.

Going in the other direction, Suppose that $T\_1,\ldots,T\_r$ is a solution of weight at most $n$. Any solution must cover $x\_1,\ldots,x\_n$, so it must contain either $S\_i$ or $\bar{S}\_i$. If a solution contains both $S\_i$ and $\bar{S}\_i$, then the one which appears later must have zero cost, that is, its elements must all be covered by preceding sets; so the solution remains a solution even if we remove it. Therefore we can assume that exactly one of $S\_i,\bar{S}\_i$ appears. The corresponding truth assignment is easily seen to be a satisfying assignment of $\varphi$.

---
Tags: algorithms, np-hard
---


title: Removing arithmetic within recurrences

text:
# Question
Title: Removing arithmetic within recurrences
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.

Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$

Statement: we wish to prove that $T(n) \le 5 \ n \log n$ for $n \ge 0$

Base case, $n = 0$ and $T(0) \le 0$

$T(0) = 0$

$T(0) \le 0 \log 0$

Holds, since $0 \log 0 = 0$

Inductive step, for $n \> 0$

(Inductive Hypothesis is: $T(n) = 5 \ n \log n$)

$T(n) = T(\lceil n/5 \rceil + 36) + n \log n$

$\le 5 \\, (\lceil n/5 \rceil + 36) \log (\lceil n/5 \rceil + 36) + n \log n$ by Ind. Hyp.

$\le 5 \\, (n/5 + 36) \log (n/5 + 36) + n \log n$ by property of ceiling

$= (n + 180) \log ((n + 180)/5) + n \log n$ by algebra

This is the point where it gets hazy. According to the link, what I should do is say that for all $n \ge 180$, then

$\le (n + n) \log ((n + n)/5) + n \log n$

$= 2n \log (2n/5) + n \log n$

$= 2n \\, \[\log n + \log (2/5)\] + n \log n$

$= 2n \log n + 2n \log (2/5) + n \log n$

$= 3n \log n + kn$ where $k = \log (2/5) * 2$

$\le 5n \log n$

Does this complete the proof? Or am I in error? I still don't understand why I can just set $n \ge 180$ and therefore get rid of the irritating arithmetic within the log.

# Answer
> 2 votes
The link doesn't say what you say it does. I don't see the number 180 appearing anywhere on that link. And that link doesn't say the purpose is to prove $T(n) \le 5 n \log n$ for all $n \ge 0$; it says to prove that $T(n) = O(n \log n)$. Check the definition of big-O notation; it doesn't require proving $T(n) \le c n \log n$ for all $n \ge 0$; it suffices to prove it for all $n \ge 180$ (or for all $n \ge n\_0$ for any other constant $n\_0$ of your choice).

---
Tags: asymptotics, proof-techniques
---


# Question
Title: What is the use case of multi-type-parameters generic interface?
Previously, I ask a similar question, but the answer given only demonstrates the usage of multiple-type-parameters(MTP) **data structure**, but not MTP **generic interface**.

Based on my experience, generic interface is useful for generalizing algorithms. For example, the sorting algorithm can be defined as such:

```
// Java code

interface Comparable<T> {
    Boolean compareTo(T other)
}

void <T extends Comparable<T>> sort(List<T> elements) {
    // body
}

```

So, the code above demonstrated the usage of single-type-parameter generic interface.

However, I have not encountered any use case for multiple-type-parameter generic interface up until now.

Thus, I am hoping that some one could provide me some use cases regarding multiple-type-parameter interfaces.

Also, if possible, please explain how multiple-type-parameter could improve some situation.

*(For example, the Comparable interface allows the sort function to be generalized, so that one do not need to define multiple sort function for different types of element)*

P/S: I ask this question because I am considering whether to include MTP generic interface in my new programming language.

# Answer
A map, also known as a dictionary, is a datastructure that maps *keys* of type `K` to *values* of type `V`. It is naturally parameterized by two parameters, `K` and `V`. This is the case in the Java collections library, for instance, where you can find the interface `Map<K,V>`.

There are may other examples, of course. For instance, you could have a graph whose vertices are labeled with type `A` and edges labeled with type `B`. Then it would be natural to have a class `Graph<A,B>`.

**Supplemental:** The OP is still asking for examples where generics with several parameters are used. In order to prod the imagination, here are some:

1. Dijsktra's algorithm for finding shortest paths in a graph could be parametrized by `Graph<A, B extends Comparable>` so that it works on any graph whose edges are labeled by values that implement the `Comparable` interface. (Yes, `A` is not used in this example, but that is beside the point. It is *useful* to allow vertices of graphs to be labeled.)
2. An implementation of `Map<K, V>` using AVL trees would be a class `AVLMap<K extends Comparable, V>`. Such a class will contain generic implementations of algorithms for manipulation of AVL trees. Other variants are possible (red-black trees, splay trees, etc.), each leading to a whole family of algorithms.
3. A function which takes a `Map<K,V>` and determines whether a given map represents an injective function.
4. A function which takes a `Map<K,List<K>>` representing a graph by the adjacency lists and determines whether the graph is bipartite. Or counts the number of cycles. Or computes the chromatic number. This is an example where there is a *dependency* between the parameters of `Map`. If we did not have multi-parameter interfaces, then we could not even express dependencies between the parameters.
5. A function which takes a `Map<K, V>` and converts it to a `HasMap<K, V>`.
6. A function whic takes a `Map<K, V>` and computes the inverse map `Map<V, Set<K>>`.
> 2 votes

# Answer
The most typical usecase I've encountered is generic idea of container, parameterized by both the container type and contained type. F.e. you can describe generic type class of containers providing get/set/delete operations for arbitrary types providing hash() operation.

Even more complicated usecase is type+container+monad, involving concrete monad where all update operations on the container occur, but this is mainly interesting in the Haskell realm.
> 2 votes

---
Tags: type-theory
---


# Question
Title: Sample K representative frames within a video
I have an image-based processing module that takes photos for some computer vision processing. I have many videos, but I need to sample representative frames as its inputs, preferably those frames with higher attention.

What are some good and effective algorithms or approaches to take K sample frames in a video? Interesting feature is that usually camera doesn't move much in successive frames with higher attention. So basically we have more stable scenes when a person is focusing on something important. Is there any ways to take this into account for our sampling?

# Answer
The question misses a lot of detail, so I will try to make an educated guess.

I don't know of any specific algorithm for the task you are trying to achieve, but the first step towards your solution would be perhaps the computation of the average of the magnitude of the optical flow throughout the whole duration of a video. Why: you said that an interesting feature in your videos is the fact that the camera moves less while filming something interesting. Then, the magnitude of optical flow vectors will be expectedly smaller. If you plot the average magnitude of optical flow throughout time of the video, you could start to see parts where there is potentially something interesting here and there.

Edit: look-up at the algorithm used by Youtube for "smart" thumbnail selection. E.g. https://stackoverflow.com/questions/28263511/smart-video-thumbnail-generator-algorithm
> 3 votes

---
Tags: algorithms, computer-vision, image-processing, sampling, video
---


# Question
Title: In lieu of neural networks and deep learning, what are some approaches to computer vision?
So much software related to computer vision relies on AI and neural networks, I wonder some of the approaches which *don't* use those methods. How could some of the mainstays of computer vision (eg. recognition and identification) be achieved without "artificial" means?

I'm reading *Vision* by David Marr and it talks about the human visual system model and how it could be emulated algorithmically for computer vision. I know of salience mapping and edge detection algorithms which there's significant consensus that the brain processes visual information in a manner not too dissimilar to, but what other methods are there?

Consider something such as facial recognition: I have a headshot of hundreds of individuals, how could a system recognize if a new face was novel or previously recognized *without neural networks or deep learning*? My interest is in white-box approaches to computer vision rather than these black-box approaches.

# Answer
> 1 votes
Yes there are a number of computer vision algorithms that do not involve AI in the sense they do not 'learn'. In certain use cases these approaches can be more efficient than a neural net approach.

These algorithms work by extracting features (like histograms, edge detection, etc.) from an image, then using an algorithm to compare these features.

* K-Nearest-Neighbor is a generic classification algorithm that can be used to classify images. There is an open online class from Standford that describes this approach, then adds AI on top to improve it.
* SIFT (Scale-invarient feature transform) is a patented feature detection algorithm used in computer vision problems, like object or facial recognition.
* SURF, partly inspired by SIFT, is a very complex algorithm used to feature detection and object recognition/reconstruction.

# Answer
> 1 votes
I think you could use some type of probabilistic model to solve this issue. I might be completely wrong, though, as I do not know a lot about probabilistic models.

Some time ago, I made use of Markov chains to generate levels for a game called Mega Man, and I remember that the results were promising, so I looked up "Markov Chains and face recognition" and found the following paper:

http://www.anefian.com/research/nefian98\_face.pdf

It deals with the specific problem of face recognition.

Markov Chains also work with Optical Character Recognition, and though I know that comparing a letter to a face is a bit of a stretch, the following paper might give you some insight.

http://www.aclweb.org/anthology/N03-1018

I hope that helps!

# Answer
> 1 votes
In order to complement some answers here, here are other approaches related to Computer Vision without using neural networks:

* 3D reconstruction for achieving 3D models of imaged objects (although I am starting to see some PhD opportunities that try to make use of deep learning here)
* Text detection (and possible recognition) in natural imagery. (I am referring to the classical approaches, such as Maximally Stable Extremal Regions and/or Stroke Width Transform). Nevertheless, the classification performance in this context improved a lot by using deep learning techniques, as it can be seen in some Robust Reading competition results throughout the years.
* Machine learning and even direct correlation analysis techniques apart from neural networks are still widely used in detection of diseases in plants, for example.

---
Tags: computer-vision, human-computing, bio-inspired-computing
---


title: Interpreting camera matrix

text:
# Question
Title: Interpreting camera matrix
I'm having some trouble interpreting the camera matrix $K = \begin{bmatrix} f\_x & s & x\_0 \\ 0 & f\_y & y\_0 \\ 0 & 0 & 1 \end{bmatrix}$ after it multiplies some 3D vector.

Assume that $f\_x = f\_y = f$ and $s = 1$

$\begin{bmatrix} f & 1 & x\_0 \\ 0 & f & y\_0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} X \\ Y \\ Z \end{bmatrix} = \begin{bmatrix}Xf+Y+x\_0Z \\ Yf + y\_0Z \\ Z \end{bmatrix} \propto \begin{bmatrix} \frac{X}{Z}f + \frac{Y}{Z} + x\_0 \\ \frac{Y}{Z}f + y\_0 \\ 1\end{bmatrix}$

So the last vector is the imaged point in homogenous coordinates. However, I'm having trouble interpreting what each of the components are physically doing. An explanation would be much appreciated!

I should mention that I'm familiar with the constants, focal length, skew, and principle point. I just can't tell what they are doing in this configuration.

# Answer
> 1 votes
I will try to help you with this, even if incomplete.

Generally speaking (I don't know if you already know this or not), the camera matrix $K$ tells you how the pinhole camera projects each point in a 3D world, with some coordinates $(X,Y,Z)$ into an image-plane point, with coordinates $(x,y)$. A good reference is Wikipedia. Looking at the diagrams provided there, the 3D point has coordinates labelled $(X\_1,X\_2,X\_3)$, which can be the same ones as our $(X,Y,Z)$ here, and the projected 2D point has coordinates $(y\_1,y\_2)$, which map to our $(x,y)$ here.

Let's delve into specific cases:

* In the case the 3D point is $(0,0,Z)$, the point will be mapped to $(x\_0,y\_0)$, as the equation you provided shows. Why: in this case, the 3D point is along the line that is perpendicular to the image plane and which goes through the principal point of the camera, regardless of distance $Z$ to the camera.
* For some fixed $(X,Y)$ in the 3D world, let's increase $Z$ endlessly. What happens is that, the bigger the distance $Z$ to the camera, the nearer to the camera's principal point $(x\_0,y\_0)$ the projected point will be. As an example, imagine a road photographed by a camera, such as this one. See how the 3D points that form the surface of the road converge to the principal point of the camera when their distance to the camera increases. This relates to the fact "parallel lines intersect themselves at infinity".

Now that we presented some specific cases, let's go a little backward in terms of why this matrix makes sense in the first place. It has to do with simple trigonometry around similar triangles. Please look at the Wikipedia article where it shows the similar triangles diagram and the corresponding mathematical formulation; you'll see the resemblance with $f\frac{X}{Z}$ and $f\frac{Y}{Z}$ elements you provided.

Now, you provided a camera matrix with high skew ($s=1$). In a pinhole camera model, you should have $s=0$, which means no skew at all, and so kill that $\frac{Y}{Z}$ parcel you have at your first entry, which only confuses you further. Skew in a camera is typically due to digitization effects and is very close to zero, not $s=1$ as you provided.

For further knowledge about this topic, I highly recommend the book Computer Vision: Algorithms and Applications by Richard Szeliski available freely as PDF at the same link.

I just came across this good article that also thoroughly explores the pinhole camera model. It includes an interactive applet at its bottom.

I hope this helped you get a first understanding of how those entries make any sense.

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


title: Filling bins with pairs of balls

text:
# Question
Title: Filling bins with pairs of balls
A bin is called *full* if it contains at least $k$ balls. Our goal is to make as many bins as possible full.

In the simplest scenario, we are given $n$ balls and may arrange them arbitrarily. In that case, obviously the best we can do is pick $\lfloor n/k \rfloor$ bins arbitrarily and put $k$ balls in each one of them.

I am interested in the following scenario: we are given $n$ *pairs* of balls. We have to put the two balls of each pair in two different bins. Then, an adversary comes and removes one ball from each pair. What can we do to have the maximum possible number of full bins after the removal?

A simple strategy is: pick $\lfloor n/(2k-1) \rfloor$ pairs of bins. Fill each bin-pair with $2k-1$ ball-pairs (each bin contains $2k-1$ balls, one ball from each pair). Then, regardless of what our adversary removes, we have in each bin-pair at least one full bin.

Do we have a strategy that achieves a larger number of full bins (more than $\lfloor n/(2k-1) \rfloor$)?

# Answer
> **TL;DR -- No, there is no better strategy than the simple strategy.** Here is the main idea of the proof. When there are not enough balls, there will be a "ball path" from a $k$-full bin to a bin with at most $k-2$ balls. The adversary can pass a ball from that full bin to that less full bin along that path, which can be done repeatedly until the number of $k$-full bins is reduced.

---

## Reformulation in Graph theory

Suppose we are given a simple finite graph $G(V,E)$ with a function $w: E\to\Bbb Z\_{\ge 0}$. We say there are $w(e)$ balls in edge $e$. Let $E\_2$ be the (end-marked edge) set $\\{(e,v)| e\in E, v\in e\\}$. If $d:E\_2\to\Bbb Z\_{\ge 0}$ satisfies $w(e)=d(e,v\_1) + d(e,v\_2)$ for every edge $e=\\{v\_1,v\_2\\}$, we say that $d$ is $w$-distributing. Any $w$-distributing function $d$ induces a function, which we use the same symbol, $d:V\to\Bbb Z\_{\ge 0}$, $d(v) =\sum\_{v\in e}d(e,v)$. We say that $d(v)$ balls are in $v$. Given $k\in\Bbb Z\_{\gt0}$, let $F\_k(d)=\\#\\{v\in V|d(v)\ge k\\}$, the number of $k$-full vertices by $d$.

**(Erel-Apass Theorem) For any simple finite graph $G(V,E)$ and $w:E\to\Bbb Z\_{\ge0}$, we have $\sum\_{e\in E}w(e)\geq (2k-1) \min\_{w\text{-distributing }d}F\_k(d)$**

Imagine each vertex is a bin. For each edge $e=\\{v\_1,v\_2\\}$, $w(e)$ ball-pairs are put into $v\_1$ and $v\_2$, each of which getting $w(e)$ balls. Among these $w(e)$ ball-pairs, the adversary may take away $d(e,v\_2)$ balls from $v\_1$ and $d(e,v\_1)$ balls from $v\_2$. The end result is the same as if, given all empty bins initially, for each edge $e=\\{v\_1, v\_2\\}$, $w(e)$ balls are put into it and, then, $d(e,v\_1)$ and $d(e,v\_2)$ balls are distributed to $v\_1$ and $v\_2$ respectively by the adversary. Hence, **Erel-Apass theorem says that in order to ensure $t$ k-full bins after a smart adversary's removal, at least $(2k-1)t$ pairs of balls are needed.** In another word, an optimal strategy to have the maximum possible number of full bins left is indeed the "simple strategy", which repeatedly fills a different pair of bins with $2k-1$ ball-pairs until we do not have enough balls to repeat.

---

## Proof of the theorem

For the sake of contradiction, let $G(V,E)$ and $w$ be a counterexample whose number of vertices is the smallest among all counterexamples. That is, there is $w$-distributing $m$ such that $F\_k(m)$ is minimal among all $F\_k(d)$ of $w$-distributing function $d$. Furthermore, $$\sum\_{e\in E}w(e)\lt (2k-1)F\_k(m)$$

Let $V\_s=\\{v\in V | m(v)\le k-2\\}$. Let $V\_\ell=\\{v\in V|m(v)\geq k\\}$. So $F\_k(m)=\\#V\_\ell$.

**Claim one: $V\_s\neq\emptyset$.**
Proof of claim one. Suppose otherwise that $V\_s$ is empty. $$ \sum\_{v\in V}m(v)= (k-1)\\#V +\sum\_{v\in V}(m(v)-(k-1)) \ge (k-1)\\#V + \\#V\_\ell \gt (k-1)\\#V$$ Let us also reuse $w$ as a function from $V$ to $\Bbb Z\_{\ge 0}$ such that $w(v)=\sum\_{v\in e}w(e)$ for any $v\in V$. $$\begin{align} \sum\_{v\in V}w(v) &=\sum\_{v\in V}\sum\_{v\in e }w(e) =\sum\_{e\in E }\sum\_{v\in e}w(e) =\sum\_{e\in E}2w(e) =2\sum\_{e\in E}w(e)\\ &=2\sum\_{e\in E }\sum\_{v\in e}m(e,v) =2\sum\_{v\in V}\sum\_{v\in e }m(e,v) =2\sum\_{v\in V}m(v)\\ &\gt 2(k-1)\\#V \end{align}$$ So there must be a vertex $b$ such that $w(b)\ge 2k-1$.

Consider the induced setup $G'(V', E')$ and $w'$, where $V'=V\setminus\\{b\\}$, $G'(V', E')$ is the induced graph $G\[V'\]$ and where $w'=w|\_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d\_{d'}$ where $d\_{d'}$ is the same as $d'$ on $E'$ while $d\_{d'}(e, b)=w(e)$ for every edge $e$ adjacent to $b$. Note that $F\_k(d\_{d'})= F\_k(d') + 1$ since $d\_{d'}(b)=\sum\_{b\in e}d\_{d'}(e,b) = \sum\_{b\in e}w(e)=w(b)\ge 2k-1\ge k$. Then $$\begin{align}\sum\_{e\in E'}w'(e)&\le\sum\_{e\in E}w(e) - w(b)\\ &\lt (2k-1)F\_k(m) -(2k-1)\\ &=(2k-1) \left(\min\_{w\text{-distributing }d}F\_k(d) -1\right)\\ &\le (2k-1) \left(\min\_{w'\text{-distributing }d'}F\_k(d\_{d'})-1\right)\\ &\le (2k-1) \min\_{w'\text{-distributing }d'}F\_k(d') \end{align}$$ So, $G'(V', E')$ and $w'$ is a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot true by our assumption about $G(V,E)$ and $w$. So claim one is proved.

---

For any vertex $v$, define $v$ $d$-reachable from vertex $u$ if there is a path $u\_0= u, u\_1, u\_2, \cdots, u\_m, u\_{m+1}=v$, $m\ge0$ such that $d(\\{u\_i, u\_{i+1}\\}, u\_i)\>0$. Let $V\_r=V\_\ell\cup \\{v\in V|\exists u\in V\_\ell \text{ and } v\text{ is } m\text{-reachable from } u \\}$.

**Claim two: $V\_r = V$**
Proof of claim two: Suppose $V\_r\neq V$. For any vertex $v\in V\_r$ and $u\notin V\_r$, since we cannot reach $u$ from $v$, if $\\{v, u\\}$ is an edge, then $w(\\{v, u\\}, v) = 0.$ Consider the induced setup $G'(V', E')$ and $w'$, where $v'=V\_r$, $G'(V', E')$ is the induced graph $G\[V'\]$ and where $w'=w|\_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d\_{d'}$ where $d\_{d'}$ is the same as $d'$ on $E'$ and the same as $m$ on other edges. Note that $F\_k(d\_{d'})= F\_k(d')$ since all vertices with no less than $k$ balls inside are in $V\_\ell\subset V\_r$. Then $$\begin{align}\sum\_{e\in E'}w'(e)&\le\sum\_{e\in E}w(e)\\ &\lt (2k-1)F\_k(m)\\ &=(2k-1) \min\_{w\text{-distributing }d}F\_k(d)\\ &\le (2k-1) \min\_{w'\text{-distributing }d'}F\_k(d\_{d'})\\ &\le (2k-1) \min\_{w'\text{-distributing }d'}F\_k(d') \end{align}$$ So, $G'(V', E')$ and $w'$ would be a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot be true by our assumption about $G(V,E)$ and $w$. So claim two is proved.

---

Now let us prove the theorem.

Since $V\_r=V$ and $V\_s\neq\emptyset$, there is a path $u\_0= u, u\_1, u\_2, \cdots, u\_m, u\_{m+1}=v$, $m\ge0$ with $m(u)\gt k$, $m(v)\leq k-2$ and $d(\\{u\_i, u\_{i+1}\\}, u\_i)\>0$. Let us construct a new $w$-distributing function $r(m)$ from $m$ so that $$r(m)(e, u)= \begin{cases} m(\\{u\_i, u\_{i+1}\\}, u\_i) -1 & \text{ if } (e,u)=(\\{u\_i, u\_{i+1}\\},u\_i)\text { for some } 0\le i\le m\\ m(\\{u\_i, u\_{i+1}\\}, u\_{i+1}) +1 & \text{ if } (e,u)=(\\{u\_i, u\_{i+1}\\},u\_{i+1})\text { for some } 0\le i\le m\\ m(e,u) &\text{ otherwise } \end{cases}$$

$m$ and $r(m)$ agrees on all vertices except $v$ and $u$, $m(v)\lt r(m)(v)\le k-1$ and $r(m)(u)\lt m(u)$. We can apply this procedure on $r(m)$ to get $r^2(m)$. Repeating this $i$ time for some large enough $i$, we will obtain a $w$-distributing function $r^i(m)$ with $F\_k(r^i(m))=0$. However, we have assumed that $F\_k(m)\>0$ is the minimum among $F(d)$ of $w$-distributing function $d$. This contradiction shows that we have proved the Erel-Apass theorem.
> 6 votes

---
Tags: combinatorics, balls-and-bins
---


# Question
Title: Regular expressions with backreferences over unary alphabet
Setting:

* regular expressions with backreferences
* unary language (1-symbol alphabet)

Is the following problem decidable in this setting:

* Given a regular expression with backreferences, does it define a regular language?

For example, `(aa+)\1` defines a regular language, while `(aa+)\1+` doesn't. Can we decide which one is the case?

---

For concreteness, "regular expressions with backreferences" here refer to e.g. the following subset of the usual Perl-compatible regular expressions:

* `a` matches character `a` (the only character in the alphabet)
* `X*` matches 0 or more occurrences of `X`
* `X|Y` matches `X` or `Y`
* parentheses can be used for grouping and capturing
* `\1`. `\2`, etc. match the same string as the 1st, 2nd, etc. pair of parentheses

We can also use the normal shorthands e.g. `X+` = `XX*`.

# Answer
Evidence against the effective decidability of the problem is provided by the construction in the proof of Theorem 9 in my paper *On Practical Regular Expressions*: You could determine if there are finitely many Fermat primes.
> 4 votes

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


# Question
Title: How to generate a binary string so to minimize weighted bitwise distance?
I've got an array of weights, for example

```
[1, 0, 3, 5]

```

The distance between two strings is defined as a sum of weights for different bits, like this:

```
size_t distance(const std::string& str1, const std::string& str2, const std::vector<size_t>& weights) {
  size_t result = 0;
  for (size_t i = 0; i < str1.size(); ++i) {
    if (str1[i] != str2.at(i))
      result += weights.at(i);
  }
  return result;
}

```

and starting string for example

```
'1101'

```

I need to generate strings in the way that strings with lowest distance from the original one go first, like this:

```
'1001'  # changed bits: 2nd. Because it has lowest weight. Distance is 0
'0101'  # changed bits: 1st.                               Distance is 1
'0001'  # changed bits: 1st, 2nd.                          Distance is 1
'1011'  # changed bits: 2nd, 3rd.                          Distance is 3
'1111'  # changed bits: 3rd.                               Distance is 3
'0111'  # changed bits: 1st, 3rd.                          Distance is 4
'0011'  # changed bits: 1st, 2nd, 3rd.                     Distance is 4
'1100'  # changed bits: 4th.                               Distance is 5
'1000'  # changed bits: 2nd, 4th.                          Distance is 5
'0100'  # changed bits: 1st, 4th.                          Distance is 6
'0000'  # changed bits: 1st, 2nd, 4th.                     Distance is 6
'1110'  # changed bits: 3rd, 4th.                          Distance is 8
'1010'  # changed bits: 2nd, 3rd, 4th.                     Distance is 8
'0110'  # changed bits: 1st, 3nd, 4th.                     Distance is 9
'0010'  # changed bits: 1st, 2nd, 3rd, 4th.                Distance is 9

```

I don't need code, I need just an algorithm which gets string of length N, array of weights of the same length and i as input and generates i-th combination, without generating the whole list and sorting it.

# Answer
It is not possible to uniquely determine $i$-th combination because a function $f: \\{0,1\\}^\* \to \mathbb{R}$ assigning distance to a string is not generally injective., that is - there may be multiple strings that correspond to a specific distance $d \in \mathbb{R}$ (which you example actually presents).

Also, it is not possible to know in advance all the possible distances as to determine which strings could be in $i$-th position, without actually calculating all the distances. It would be like knowing the shortest route to some destination by examining just that route.

I would suggest a different approach (but it will not make you happy as I generally think there is no way to achieve this in its fullest without generating all combinations); creating an algorithm that takes as input not $i$, but the distance $d$ and returns strings that are $d$ distance from your base string (note that it is in fact irrelevant). You can then eliminate from further process the weights that are larger than $d$ (and even ones equal to $d$, with further care).

* If you want **all** strings $d$ distance away and remaining weights vector is not too long, you can generate all subsets (a power set) of weights array and checking which has the sum $d$, but considering your restrictions on the solution - you do not want that because it would generate all the binary strings in the process.
* If you need **just one** string on distance $d$, no matter which, you can implement some backtracking search/sum on the weights array to find a combination that sums to $d$. (You can then store ones you got and repeat this process ignoring ones you found already, if you still want all.)
* You can model your problem as finding a path of length $d$ in a fully connected directed graph where you graph has $N$ nodes and the weight of an edge going to node $i$ is $weights\[i\]$. Then you can maybe use some optimized graph path finding (heuristic) algorithms, but that seems like an overkill.

I am quite sure this problem is in NP.
> 1 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: How to test if my implementation of tree/graph data structures are correct?
I've recently implemented RB tree, B-Tree and vEB tree. I was wondering however if there's any rule of thumb for testing if my implementation are actually correct.

Is there any reference that can tell how to develop proper test cases for such data structures?

Besides from mathematical techniques maybe.

What about graph in general?

# Answer
Identify the representation invariants. Add assert statements to check that the representation invariant holds (sometimes called a repOK function). Use random testing to generate millions of test cases, and check that no assert ever fires.

Build a reference implementation of the abstract data type that implements all of the methods, but instead of using your data structure, implements the same semantics using some known-good data structure (e.g., a simple list or something). Use random testing to generate millions of test cases, and check that in every case your implementation produces the same results as the reference implementation.

This isn't perfect but it'll probably be pretty good.
> 2 votes

---
Tags: graphs, trees, software-testing, testing
---


title: Why does n! have the least time?

text:
# Question
Title: Why does n! have the least time?
I was reading the book Introduction to Algorithms, Chapter 1. When I saw this diagram, I got confused because $\lg n$ has the largest value of time while $n!$ has the least value of time. And that doesn't make sense to me - perhaps I misunderstood this?

# Answer
> 37 votes
The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.

i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.

One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.

For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).

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


title: A directed graph colored path problem?

text:
# Question
Title: A directed graph colored path problem?
**Given:** A rooted, directed, a-cyclic graph $G$. Let $r\_0$ be the root node and $t\_0$ be another target node. Each node in $G$ is assigned a non unique id/color ($ID\_i),\ 1\<i\<N$ for some integer N.

**Problem:** Is there a directed path from $r\_0$ to $t\_0$, such that for some $ID\_x$ there is no node in that path with $ID\_x$ as its $ID$. In other words, the nodes in the path do-not cover all the $IDs$.

**Comments:** Clearly the problem is in $NP$ since if we are given such a path we can easily verify it. I suspect the problem is also in $P$ and can be solved in polynomial time. But, I am struggling to find an algorithm for the same.

Can someone please help with this?

# Answer
> 2 votes
Simple approach: for each $1 \le i \le N$ (I assume that the $\<$ in the question are typos) run depth-first or breadth-first search ignoring nodes coloured $i$.

Slightly more advanced approach: use a matrix-based all-pairs reachability algorithm, but rather than record a Boolean `isReachable` or a numeric `shortestDistance` record a bitmap of which colours can be avoided.

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


# Question
Title: Searching and inserting in $O(n)$ when $n$ is the size of the key
**Edit:** The solution to my problem is called a trie ; according to Section 8.1 of Peter Brass book "Advanced Data Structures", for a given alphabet $A$ and a word $w$ of length $n$ on this alphabet, a trie can search $w$ in $O(n)$ and insert or delete $w$ in $O(|A| n)$. Since in my case $|A|=2$, all these operations are performed in $O(n)$. Hooray !

**Context :**

I am trying to put an upper bound on the worst case complexity of an algorithm. In that algorithm, I have an arbitrarily big positive integer $n$, and a map in which keys are sequences of bits of length $n$. My algorithm makes use of the INSERT and SEARCH operations in that map. So I am searching for a data structure with the least possible worst case complexity (with respect to $n$) for INSERT and SEARCH.

My first idea was : let's assume that the map is implemented with a red-black tree. Red-black trees perform SEARCH and INSERT in $O(\log m)$ (where $m$ is the number of nodes in the tree). In the context of my algorithm, there is at most $2^n$ different keys, so insert and search should run in $O(n)$.

**Problem :**

Binary trees usually assume that the keys are integers, which allows to compare two keys in $O(1)$. But since $n$ is not bounded, the length of my sequences can be greater than the encoding size of integers ; then it does not seem correct to just consider that my key can simply be treated as integers and compared in $O(1)$, right?

**Question:**

Do there exist data structures that would allow me to insert and search in $O(n)$ (worst case) with respect to the size $n$ of the key ?

**What I have for now:**

**1:** I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

**2:** I have come up with a very simple kind of tree that would perform INSERT and SEARCH in $O(n)$, and I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it). My solution goes like this :

* Keys are only stored in the leaves of the tree, and leaves are at distance $n$ from the root
* When searching or inserting, we recursively go down from the root ; on any given non-leaf node that is at distance $i$ from the root, we look at the $i$-th bit of our key : if it is 1 then go right, if it is 0 then go left.

I did not find any data structure based on this principle, but if it exists, that would be a good solution to my problem.

# Answer
> 3 votes
> I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it).

What you describe is called a trie. For practical implementation you might take more than one bit at each level (e.g. take two bits and give each node four children).

---

> 1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

There is potentially room for some subtlety here. If you record for each child node the bit index at which its key differs from the parent's, can you get it down to $O(n)$? I haven't thought through the answer myself, but it seems plausible that you'd essentially get a self-balancing trie-like structure, and might be an interesting exercise to attempt.

---

Finally, if you expect your map to be sparsely populated (i.e. to have much fewer than $2^n$ elements) it might be worth thinking about hashing.

---
Tags: complexity-theory, time-complexity, search-trees
---


# Question
Title: Cook completeness of a variant of Vertex Cover
Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$?

**Input**: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$

**Output**: **YES** if there exists a vertex cover $C'\subseteq V$ such that $|C'|=|C|-1$, **NO** otherwise

# Answer
First it is obvious that the above problem is in NP. I think there is even a Karp reduction from the well-known clique problem. It uses the well-known reductions from clique problem to independent set problem and from independent set problem to vertex cover problem.

The clique problem is as follows:

Given: a graph $G$ of size $n$, parameter $k$

Output: Yes iff there is a clique in $G$ of size $k$.

Now, first we add a clique of size $k-1$ in $G$. For sake of presentation, we denot the resulted graph by $G'$. Then, we create the corresponding complement of $G'$, denoted by $\hat{G}$. Denote $\hat{G}=(\hat{V},\hat{E})$ and let $V\_{clique} \subseteq \hat{V}$ be the set of vertices corresponding to the original clique of size $k-1$ in $G$. The reduction is a polynomial transformation. Note that $|\hat{V}|=n+k-1$

The graph $G$ contains a clique of size $k$ if and only if $G'$ contains a clique of size $k$, since adding a clique of size $k-1$ does not effects if $G$ has a clique of a larger size. Using the same arguments done in reduction from clique problem to the independent set problem and from independent set problem to vertex cover problem, we derive that $G$ contains a clique of size $k$ if and only $\hat{G}$ contains a vertex cover of size $|\hat{V}|-k=n-1$.

Using similar arguments, we derive that $V\_{clique}$ is an independent set in $\hat{G}$, and thus the set $\hat{V}\setminus V\_{clique}$ is a vertex cover in $\hat{G}$ of size $|\hat{V}|-(k-1)=n$.

Finally, let $L\_{clique}$ and $L\_{vertex}$ be the corresponding languages of the clique and the described vertex cover problems. Then, $(G,k) \in L\_{clique}$ iff $(\hat{G},\hat{V}\setminus V\_{clique}) \in L\_{vertex}$ (i.e., there exists a clique of size $k$ in $G$ iff there is a vertex cover of size $|\hat{V}\setminus V\_{clique}|=n-1$ in $\hat{G}$).
> 0 votes

---
Tags: np-complete, reductions, np-hard, np, decision-problem
---


# Question
Title: Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?
Several questions (, ) have been asked about this topic already but I am trying to be more specific.

In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is already on the stack is

```
    // It says w.index not w.lowlink; that is deliberate and from the original paper
    v.lowlink  := min(v.lowlink, w.index)

```

I understand that this rule is necessary to compute lowlink accordingly to its formal definition, which in Tarjan's paper is (emphasis is mine)

> LOWLINK(v) is the smallest vertex which is in the same component as v and is reachable by traversing zero or more tree arcs followed by *at most one* \[back edge\] or \[cross edge\].

What I do not understand is :

1. Would removing the emphasized restriction in the definition lead to a calculation with `v.lowlink := min(v.lowlink, w.lowlink)` ?
2. Would removing the emphasized restriction lead to incorrect detection of a graph's SCCs (**if so, I am looking for an example of such a graph**) ? If not, would this modification guarantee that in a given SCC, all nodes ultimately have the same lowlink value (again, if not, I am looking for a counterexample) ?

I am currently at the following point (which might be wrong !) :

Let v and w be as in the code (exploring v's successors, w already on stack). v is on the stack too, and so is r, the root of v and w's SCC (in Tarjan's sense) (it is a common ancestor of v and w in the spanning tree).

For the proposed modification of the algorithm to yield a bad result, one needs to have w.lowlink \< r.lowlink (this is the case where, by propagating the lowlink information back to r after finishing DFS, we will get an inconsistent value for r). For this to happen, w must have gotten its lowlink value from a vertex x discovered before r and belonging to a different SCC than r. But x needs to be in the stack when we were DFSing from w (if it were not the case, one would not have updated w.lowlink when reaching x because x is already discovered at that time). Since x is discovered before r, it is deeper in the stack than r, and thus it is still in the stack when we are DFSing from v. But then wouldn't all these nodes belong to the same SCC, rooted by x.lowlink ?

# Answer
For a given vertex, the only thing that matters in the algorithm is if there is an edge from the vertex or a child-vertex to a ancestor-vertex in the DFS exploration tree. In this case, we know that the vertex belongs to the same SCC as it's parent. In such a case, we are sure that the vertex itself or a child-vertex has a direct back edge to an ancestor of the vertex, and this ancestor has a lower index that the current vertex, so the `v.lowlink` will differ from `v.index`. We actually do not need to know the top-vertex of the SCC at this step.

So, using `v.lowlink := min(v.lowlink, w.lowlink)` instead of `v.lowlink := min(v.lowlink, w.index)` will lead to a correct algorithm too. The difference is that in this case, `v.lowlink` will not represent the vertex with the smallest id reachable from **v** nor the SCC top vertex, but just v if there is no such vertices, or any parent vertex that belongs to the same SCC (maybe the top-vertex), depending of DFS order. I think it's just lack in formal definition, and thus, wasn't used.

Let's see what appends when we use this alternative instruction. When we update `v.lowlink` because we have found a new back edge to a ancestor vertex, we will now set v.lowlink with the value of w.lowlink. But this vertex is an ancestor and is still in the stack: we may not have already explored all the child vertices of this ancestor and thus, w.lowlink can change in the future: this is why we dont's know exactly what will be the final value of v.lowlink because it depends of the DFS order. We can juste be sur that it will be w.index **or** a vertex with a lower index that belongs to the same SCC (so the algorithm will work as expected): the value of lowlink still differs for differents vertices of the same SCC.

The following example show how DFS order alters lowlink values in this alternative algorithm:  In this case, assuming we are exploring vertices in the order 0-1-2-3-4, when we consider the vertex 3, the vertex 4 has not been explored yet. The `lowlink` value of vertex 1 is so **1**, and vertices 2 and 3 will take the same value. But we will later find the back edge from 4 to 0, and set the `lowlink` value of vertices 4 and 1 at **0**. If we had explored vertex 4 prior to vertex 2, all vertices would have **0** as lowlink value.

And for the last question, yes, all this verteces belong to the same SCC, rooted by `x.lowlink` **or** an ancestor of the vertex with id `x.lowlink`
> 6 votes

---
Tags: graphs, graph-traversal, connected
---


# Question
Title: Finite list induction principle and the tail eliminator
In Dybjer's *Inductive Families* the author present a method to derive an eliminator/induction principle for every inductive family of types.

In particular for the type of finite lists, namely $$List' \colon (A \colon set) (n \colon N) set$$ we get the eliminator $$\begin{align\*} listrec' \colon &(A \colon set)\\ & (C \colon (a \colon N)(c \colon List'\_A n)set) \\ & (e\_1 \colon C(0,nil'\_A)\\ & (e\_2 \colon (b\_1 \colon N)(b\_2 \colon A)(u \colon List'\_A(b\_1))(v \colon C(b\_1,u))C(s(b\_1),cons'\_A(b\_1,b\_2,u)))\\ & (a \colon N) \\ & (c \colon List'\_A(a)) \\ & C(a,c)\ . \end{align\*}$$

From what I get from this eliminator we should be able to provide any possible operation using finite lists.

Now my question is

> how do we get the classical *destructor* $$tail \colon (A \colon set)(n \colon N)(List'\_A(s(n))) List'\_A n$$ that from any finite list gets its tail?

I am totally lost on how to approach this problem since the eliminator seems to be able to provide just function defined on the whole family $List'\_A(n)$ and not on the sub-family $List'\_A(s(n))$.

Thanks in advance.

# Answer
> I am totally lost on how to approach this problem since the eliminator seems to be able to provide just function defined on the whole family List′A(n) and not on the sub-family List′A(s(n)).

The typical trick in this situation is to pick a `C` such that you can pretend you are defining a function on the whole family when, in fact, you're only focusing on the sub-family you care about thanks to equality constraints.

Let me be more concrete:

If you pick `C(n, xs) = (m:N) -> n = s(m) -> List'_A(m)` then you can define a generalised `gtail` by using `listrec'`, and derive `tail` as a corollary.

```
gtail : (A:set) (n:N) (xs : List'_A(n)) -> C(n, xs)
gtail A = listrec' A C
          contradiction -- of type: (m:N) -> 0 = s(m) -> List'_A(m)
          (\ _ _ u _ -> u)

tail : (A:set) (n:N) -> List′A (s(n)) -> List′An
tail A n xs = gtailn A (s(n)) xs n refl

```
> 3 votes

# Answer
What follows is just a little modification of the idea proposed in the accepted answer, nevertheless I think it can be of interest to other readers.

Here's a way to build tail

We can consider the predicate $P \colon (A\colon set)(n \colon N)(l \colon List'\_A n)set$ defined (by recursion on natural numbers) as the only type family such that $$\begin{align\*} P(A,0,l)&= 1\\ P(A, s(n),l) &= List'\_A (n) \end{align\*}$$ where $1$ is the unit type with only term $()$.

If we let $$e\_1 = () \colon 1= P(A,0,nil')$$ and $$e\_2=\lambda n \colon N.\lambda x \colon A.\lambda xs \colon List'\_A n. \lambda p \colon P(A,n,xs). xs \colon (n \colon N)(x\colon A)(xs \colon List'\_A n)(p \colon P(A,n,xs))\underbrace{List'\_A(n)}\_{=P(A,s(n),cons'\_A(n,x,xs))}$$ we get $almostTail = (\lambda A \colon set) listrec'(A,P(A),e\_1,e\_2) \colon (A \colon set)(n \colon N)(l \colon List'\_A(n))P(A,n,l)$ which by the reduction principle is such that $$almostTail(A,s(n),cons'\_A(n,x,xs))=e\_2(n,x,xs,almostTail(A,n,xs))=xs\ .$$

So we get $$tail' \colon (A\colon set)(n\colon N)(l \colon List'\_A(s(n)))\underbrace{P(A,s(n),l)}\_{List'\_A(n)}$$ by letting $$tail'(A,n,l) = almostTile(A,s(n),l)\ .$$

**Note**: the only difference between gallais' example and mine is that instead of adding an hypothesis in the predicate to pass to $listrec'$ I have used a predicate with a *don't care value* for the case $n=0$.

In this case too we basically build a function defined on all the lists, with the desired behaviour in the case of interest (i.e. not empty lists), and then consider the specialized/restricted function for the sub-family of types we are interested in.
> 1 votes

---
Tags: dependent-types, inductive-datatypes
---


# Question
Title: Finding pairs of numbers in array whose reciprocals sum to 1
Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b \< 1$.

For example:

* Input: $2, 3, 1, 0.5, 3, 1.6$.
* Output: $(2,3), (3,2), (3,3), (3,1.6), (1.6,3)$.

We can compare each element with each other but it takes $O(n^2)$ complexity. How to improve that algorithm? Maybe use special structure? Maybe use sorting?

# Answer
Assume that $a$ is given. Then a valid $b$ has to satisfy (just rearrange the inequality) :

$$b \> \frac{a}{a - 1}$$

Notice, if the array is sorted, then you can find the number of valid $b$ using binary search, which gives $O(n \log n)$ to compute the number of all pairs.

Also notice, that if $a$ gets bigger, then $b$ is allowed to be smaller. So if you you iterate over $a$ in sorted order, and keep a pointer (to indicate the allowed elements for $b$), you don't need to use binary search and can compute the result in $O(n)$.
> 3 votes

# Answer
Assuming the numbers are integers \>= 1, the sum of two reciprocals is less than 1 unless one integer is 1, or both integers are two.

So assuming you have X array elements \> 2, Y array elements = 2, and Z array elements = 1, your solution will contain (X+Y) (X+Y+1)/2 - Y(Y+1)/2 = X(X+1)/2 + XY pairs of numbers.

If you represent the solution as pairs of numbers, then the time is at least as large as the size of the solution, which will be quadratic unless Z is very large.

It's in the nature of the problem that the solution is HUGE and therefore it takes a long time to produce the solution.

If your numbers are reals, you throw away anything \>= 1, split into number \<= 2 and numbers \> 2. All pairs of numbers \> 2 are solutions, the number of these pairs can be quadratic. Pairs of numbers \<= 2 are *not* solutions. What remains are pairs of one number \<= 2 and one number \> 2. Sort the smaller set, then for each member x of the larger set use binary search to find all elements y of the other set with y \> x / (x - 1). This works especially well if one set is small.

Of course you can avoid all the difficulties with reciprocals if you just replace each number x with 1/x.
> 0 votes

---
Tags: algorithms, complexity-theory, data-structures, optimization
---