# Question
Title: Showing that a property is semantic - Rice's theorem
I want to show that the language $$L= \left\\{ \left\langle M\right\rangle \mid\substack{\text{M is a TM and there exists a poly TM $M'$ such that}\\ \text{if M halts on input $w$, $M'$ halts on $w$ and answers the same} } \right\\} $$ is not decideable, using Rice's theorem.

I have a hard time understanding why this property is semantic. I obviously can't assume that $M \in R$ , so it might be that we have TMs $M\_{1},M\_{2}$ such that $L(M\_{1})=L(M\_{2})$, but $M\_{1}$ gets stuck on some input $z$, while $M\_{2}$ rejects it. Then, the property above (having a poly TM which identifies with $M$ on inputs which it halts on) might possibly apply for $M\_{1}$ but not for $M\_{2}$ (as $M\_{1}^{\prime}$ doesn't have to satisfy anything about $z$, while $M\_{2}^{\prime}$ must reject it). But according to the exercise I have to use Rice's theorem, so I am probably missing something and this property is semantic after all.

I saw this related question but it didn't really help.

# Answer
Informally speaking, a property is *semantic* if it only depends on the final "outcome" of running $M$ on a given input rather than on the workings of $M$. In order to formalize this, with each Turing machine $M$, associate a partial function $\Lambda$ from inputs $\Sigma^\*$ to pairs $\\{0,1\\} \times \Sigma^\*$, where the first element denotes whether the final state accepts and rejects, and the second element denotes the output of the machine (the contents of the tape). This is a partial function, since if $M$ doesn't halt on an input $x$, then $\Lambda(x)$ is undefined.

Suppose that $P$ is a nontrivial property of partial functions $\Lambda$ of that form. Nontriviality means that there exists some Turing machine $M\_+$ such that $\Lambda(M\_+) \in P$, and there exists another Turing machine $M\_-$ such that $\Lambda(M\_-) \notin P$.

If $P$ is decidable then consider the Turing machine $Q$ which on input $x$, determines whether $\Lambda(Q) \in P$ (this self-reference can be implemented using the recursion theorem), if so runs $M\_-$ on $x$, and otherwise runs $M\_+$ on $x$. By construction, if $\Lambda(Q) \in P$ then $\Lambda(Q) = \Lambda(M\_-) \notin P$, and if $\Lambda(Q) \notin P$ then $\Lambda(Q) = \Lambda(M\_+) \in P$. In both cases we obtain a contradiction.

Crucially, the identities $\Lambda(Q) = \Lambda(M\_\pm)$ implicitly rely on the fact that $\Lambda$ only captures semantic properties. The syntactic properties could well be different, since $Q$ isn't the same as $M\_\pm$, it just simulates those machines.
> 1 votes

---
Tags: turing-machines, computability, undecidability, rice-theorem
---


# Question
Title: Find a pushdown automaton for { x#y ∣ x ≠ y }
I was told to built a PDA that recognizes the following language:

$$L = \\{x\\#y \mid x,y \in \\{0,1\\}^{\ast} \wedge x \neq y\\}$$

My attempt is basically to push $x$ to the stack for every $1$ and $0$ read. And then pop them for the second half. If it finishes and the stack is still not empty, it will be accepted. Or if it hasn't finished reading but the stack is empty already it will also accept.

Am I approaching this correctly? I can easily do the CFG but I'm told that it's easier to do the PDA from scratch rather than converting it since it needs to be in CNF.

Any help appreciated

# Answer
Since you have a marker $\\#$ separating $x$ and $y$, the solution is rather easy. The PDA must first decide non-deterministically whether it will attempt to check that $|x|\neq|y|$ or whether $x$ and $y$ differ for their $i$-th symbol, i.e. whether $x\_i\neq y\_i$. This corresponds to two distinct sets of states.

The first case can be dealt with as you suggest.

In the second case, the automaton scans the input, and stores a symbol $a$ in its stack to keep count. At the $i$-th symbol, chosen non-deterministically, it decides to check whether that is the symbol rank for which $x\_i\neq y\_i$. So it memorizes the synbol $x\_i$ in its finite control (meaning that the states now used have a component indicating whether a $0$ or a $1$ was found). Then, the PDA scans the input without memorizing anything until it scans the symbol $\\#$. Then it start scanning the $y$ part, popping the stack for each symbol read. When the stack is empty, it is reading the symbol $y\_i$, and it can check whether it is different from $x\_i$ memorized in the finite control. If it is different, the PDA can accept the string, and does not even need to scan the rest.

If the end of the string is reached before the stack is empty, the automaton can accept too, though this can also be handled by the first case.
> 5 votes

# Answer
Your approach will work when $|x| \neq |y|$, but not for something like $1\\#0$, which should also be in the language.

For the case where $|x| = |y|$, we happen to already have an answer, which can be easily adapted to suit (there's a PDA there, but you can also convert the CFG to a PDA, or just take inspiration from the answers).

The only part left is deciding which case you're in. As the PDA can't read ahead and count, you have two options, try and both count and guess the incorrect character at once, or use nondeterminism to guess at the beginning which case the input falls into. Neither are particularly harder than the other, so it's more a matter of how comfortable you are with the idea of each.
> 3 votes

# Answer
I was told to built a PDA that recognizes the following language:

```
                 L={x#y ∣ x, y ∈ {0,1}* ∧ x≠y}

```

See, To approach this, we can have followiing Cases:

**Case 1**: Let length of 'X' is more than length of 'Y',i.e., |x| \> |y|, it should be accepted in our PDA.

**Case 2**: Let Length of 'X' is less than ;ength of 'Y', i.e., |X| \< |Y|. it should also be accepted in our PDA.

**Case 3**: Let Length of 'X' is exactly equal to length of 'Y',i.e., |X| = |Y|. It SHOULD NOT BE ACCEPTED in our PDA.

```
 So, to solve this, Let us append an end-marker to the language at the end, which is *"$"*. Therefore our language will be :

                  L$ = {x#y$ ∣ x,y ∈ {0,1}* ∧ x≠y}

```

Now, Our DPDA can be look like this:

```
i have used input alphabet (0,1) and Stack alphabet (A, B). Here "A" represents "0" and "B" represents "1".
 Final States are q3 and q8.
 Initial state is q0.

i hope you can find it correct!

```
> 0 votes

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


# Question
Title: Is there a minimal order of an uncomputable function that bounds all computable functions?
Busy Beaver is an uncomputable function that grows quicker than any computable function. That means there exist functions f such that for all computable functions g: g in O(f). There is an upper bound on the order of computable functions.

Here I asked whether there is a computable function bounding all computable functions (There isn't).

Is there, though, among uncomputable functions, a minimal order function h such that

$$ \forall g:g\ computable \implies g \in O(h) $$ $$ \forall f: (\forall g:g\ computable \implies g \in O(f)) \implies f \in \Omega(h)$$

# Answer
> 0 votes
Suppose that $h$ is such that $g = O(h)$ for all computable $g$. Let $H(n) = h(n)/n$. I claim that $H$ also satisfies $g = O(H)$ for all computable $g$. Otherwise, let $g$ be a computable function such that $g$ is not $O(H)$. In particular, there are infinitely many $n$ such that $g(n) \geq H(n)$, and so $n g(n) \geq h(n)$. Let $G(n) = n^2 g(n)$, which is computable. Since $G(n) \geq n h(n)$ for infinitely many $n$, it is not the case that $G = O(h)$, contradicting the assumption on $h$.

---
Tags: complexity-theory
---


# Question
Title: Do uncomputable functions exist that are of the order of a computable function?
Are there monotonically increasing uncomputable functions f that are bounded by computable functions?

$$ \exists f,g: f\ uncomputable\ \land f\ monotonically\ increasing\ \land\ g\ computable\ \land\ f \in O(g) $$

# Answer
> 0 votes
Yes. Let $L$ be any undecidable language (e.g. the halting problem), w.l.o.g. encoded over the alphabet $\\{0, 1\\}$ and such that all $x \in L$ start with $1$. Further, let $\leq\_\text{lex}$ denote the lexicographical order of strings over the alphabet $\\{0, 1\\}$ and let $\operatorname{bin}(n)$ denote the binary representation of a natural number $n$. Define $$f\_L(n) = |\\{x \in L \mid x \leq\_\text{lex} \operatorname{bin}(n) \\}|$$ and observe that $f\_L$ is monotonically increasing and satisfies $f\_L(n) \leq n$ (and thus $f\_L \in O(n)$). Finally, note that $L$ can be decided using an oracle for $f\_L$, and hence $f\_L$ is not computable.

---
Tags: complexity-theory
---


# Question
Title: MSAT and IMSAT problems (restricted versions of SAT)
I was reading about about NP-intermediate problems on Wikipedia and saw the IMSAT problem mentioned over there.

There is no Wikipedia page for that problem and they only cite this paper.

In the paper they define the MSAT problem as:

> Recall that the satisfiability problem (SAT) is to decide whether a set of propositional clauses $C = \\{C\_1, ... ,C\_m\\}$, where each $C\_i$ is a set of literals, on atoms $X = \\{x\_1, ... , x\_n \\}$ is satisfied by some truth assignment to $X$. Its restriction $MSAT$, where every clause of $C$ must be either positive or negative, i.e., must not contain any negative or positive literal, respectively, is still NP-hard.

But they don't reference any source that prove $MSAT$ is indeed NP-Hard. Can you please enlighten me?

Moreover, they later introduce the problem of IMSAT by:

> The first subcase of MSAT which we consider is made up of instances with the property that every pair of a positive clause and a negative clause resolves, i.e. there is an atoms which occurs unnegated in the positive and negated in the negative clause.

I don't understand why Wikipedia mentioned this problem as NP-intermediate, this term was never shown in the paper. I see they prove that co-IMSAT is TRANS-HYP-complete, but couldn'tunderstand if TRANS-HYP is NP-intermediate, and what does it say on IMSAT.

I got a mess here, and I couldn't find any other sources. Is MSAT NP-Hard? I would like to see a proof (or at least an idea for a proof) Is IMSAT NP-intermediate? A proof of that seems to be missing as well, or I totally didn't understand the paper.

And another a bit more general question about using NP-intermediate problems:

If I understand correctly, it is quiet impossible to prove something is in NP-intermediate, since the class is defined as problems that polynomial running time solution was not found for them, and they were not proven to be NP-Hard (though they are in NP). If I want to "lean" on IMSAT as NP-intermediate. how can I do that?

Lets say I have a reduction from IMSAT to my problem P, which means if P is solvable in polynomial time, IMSAT as well. What paper can I cite to show that IMSAT in NP-intermediate - which can convince people P is a hard problem (and it is fair to use approximate/probabilistic algorithm instead of trying to solve it)

# Answer
For your first question, I'll give an elementary proof for the $\mathsf{NP}$-hardness of $\mathrm{MSAT}$ by reduction from $\mathrm{SAT}$.

Let $\varphi$ be a propositional formula in CNF (i.e., a $\mathrm{SAT}$ instance) consisting of the clauses $C\_1, ..., C\_m$ and let $C\_i^+$ and $C\_i^-$ denote the set of positive and negative literals of the clause $C\_i$, respectively.

I illustrate the idea using an example: Suppose we have a clause $C = (x\_1 \vee x\_2 \vee \neg x\_3)$. The idea will be to introduce a new literal $c$ to split $C$ into $C^+ \cup \\{c\\}$ and $C^- \cup \\{\neg c\\}$ to obtain two new clauses which are either positive or negative. In this example, we get $(x\_1 \vee x\_2 \vee c) \wedge (\neg c \vee \neg x\_3)$, and it is not hard to see that this formula is indeed equivalent to $C$ itself: Any satisfying assignment of $C$ must satisfy at least one of our two new clauses, and by choosing the assignment to $c$ accordingly, we can satisfy both. Conversely, any assignment to $c$ can only satisfy one of the clauses and hence, a satisfying assignment to both clauses must, if restricted to the variables $x\_1, x\_2$ and $x\_3$, satisfy $C$.

By applying this construction to all clauses, we obtain a formula $\varphi'$ which is equivalent to $\varphi$ but only contains positive and negative clauses. Clearly, $\varphi'$ can be computed from $\varphi$ in polynomial time, and we conclude that $\mathrm{MSAT}$ is $\mathsf{NP}$-hard.

On the second question (and the ones following): We do not know *any* $\mathsf{NP}$-intermediate problems (that is why the section title in the linked Wiki article contains "might"). By Ladner's theorem, such problems exist if and only if $\mathsf P \neq \mathsf{NP}$, which is an open question. Hence, you probably won't find papers showing (unconditionally) that $\mathrm{IMSAT}$ is $\mathsf{NP}$-intermediate.

One can speculate that problems which have evaded the $\mathsf P$/$\mathsf{NP}$-completeness classification for a long time could be intermediate, but speculation it is. In some cases, like the Graph Isomorphism problem, better arguments than "it hasn't been resolved either way for a long time" can be made: Under common complexity-theoretic assumptions (specifically, a non-collapse of the polynomial hierarchy), graph isomorphism is not $\mathsf{NP}$-hard. On the other hand, much research has been invested into finding polynomial-time algorithms for GI, yielding to many such algorithms for special cases and a general quasi-polynomial-time algorithm recently developed by László Babai.

I am not aware of similar "evidence" for $\mathrm{IMSAT}$, though it is not my field of expertise -- maybe someone else can expand on that.
> 2 votes

---
Tags: complexity-theory, satisfiability
---


title: What does "Temporal extent" mean?

text:
# Question
Title: What does "Temporal extent" mean?
I am reading Long-term Temporal Convolutions for Action Recognition and under the **Section 3.1**, I read this:

> To investigate the impact of long-term temporal convolutions, we here study network inputs with different temporal extents.....

and then

> As illustrated in Figure 2, the temporal resolution in our 60f network corresponds to 60, 30, 15, 7 and 3 frames for each of the five convolutional layers. In comparison, the temporal resolution of the 16f network is reduced more drastically to 16, 8, 4, 2 and 1 frame at each convolutional layer. We believe that preserving the temporal resolution at higher convolutional layers should enable learning more complex temporal patterns. The space-time resolution for the outputs of the fifth convolutional layers is $3 \times 3 \times 1$ and $1 \times 1 \times 3$ for the 16f and 60f networks respectively. The two networks have a similar number of parameters in the *fc6* layer and the same number of parameters in all other layers. For a systematic study of networks with different input resolutions we also evaluate the effect of increased temporal resolution $t \in \\{20, 40, 60, 80, 100\\}$ and varying spatial resolution of $\\{58 \times 58, 71 \times 71\\}$ pixels.

How can we reduce temporal resolution of a ConvNet at each convolutional layer.

What does preserving the temporal resolutional mean and what does complex temporal resolution mean?

I've taken courses on Convolutional Neural Network and never heard of anything such as "temporal extent" or "temporal resolutions". Searching about them gives links to other research paper, which still use the term without describing its meaning.

Anyone, kindly put some light on it.

# Answer
> 2 votes
It's just the ordinary meaning of the words extent and resolution, only applied to time instead of space. You can think of space-time as a kind of a continuous block, instead of just thinking of time as something that ticks away.

E.g. if you imagine a graph where one axis is space, and another is time, then the spatial extent of something would the width of that thing on the space axis (that is, how much space it takes up). Spatial resolution is how tiny you can draw two distinct things on the graph before you can't tell them apart anymore. That's the technical definition - the smallest separation at which you can *resolve* two things of interest, although we tend to think of resolution as of the size of the image in pixels.

Similarly, a temporal extent is is the width of something on the time axis. How long it extends through time. So it can be a duration of something, or expressed in some other time-related unit - like how many frames it takes up. Temporal resolution is how small a separation in time can two tings have, before you can't tell that there is a separation between them (e.g., if two things happen rapidly at different times within the same frame, and all your data is at the frame level, you can't tell if the two things were separated or simultaneous, if their time spans overlap or not. So, a FPS rate gives you the temporal resolution (after you invert it to seconds per frame). If the neural network is doing something that bundles information from a number of consecutive frames together (maybe it processes them in blocks of several frames), as some information is discarded, the time-resolution might drop (for example, think of severe lag in videogames - one frame you were just walking, next frame it's game over and you have no idea what happened).

> what does complex temporal resolution mean?

The term "complex temporal resolution" is not mentioned anywhere in the text. It says:

> "We believe that preserving the temporal resolution at higher convolutional layers should enable learning more complex temporal patterns."

I'm paraphrasing based on a quick look of the paper, but basically, what they are saying is: they think that if they can preserve (after all the transformations or whatever they are doing) the original fidelity when it comes to distinguishing two moments in time (i.e., this capability doesn't get worse as information goes through the network), then their neural network would have a better chance of learning/recognizing things that happen over time (e.g. that someone is doing something in a video) - that are potentially more complicated than what was possible before (e.g. instead of just being able to recognize that someone is swimming, it could maybe recognize some more complex action).

# Answer
> 0 votes
Temporal extent is the same as duration. It is measured in units of time, like second. For example, 1 second is a duration or temporal extent.

---
Tags: machine-learning, neural-networks, research
---


title: Concentric convex hulls

text:
# Question
Title: Concentric convex hulls
Given N points in a 2D plane, if we start at a given point and start including points in a set ordered by their distance from the starting point. After including every point, we check if there is a convex hull possible, we move all these points to a visited set and continue. Every time we determine a convex hull, we only move the points to the visited set if the so constructed convex hull contains all the points from the visited set.
How can we do count such convex hulls in as efficient manner as possible?

# Answer
> 0 votes
It seems you are trying to perform onion peeling(convex layers) from the inside out, which is not possible. A convex hull of given points is a polygon that contains all given points either on itself or inside it. To solve the problem you have described you must generate a convex hull using an algorithm of choice. Now that you have the outer layer, for the inner layer, use the same algorithm and only supply the points inside the convex hull.

```
The pseudo code would be:
 for given dataset:
   generate a convex hull
   remove the points that make the convex hull from the dataset
   loop until the dataset has no points or more than 2(since a convex hull requires at least 3 points).

```

# Answer
> 0 votes
Because of the rule "we move all these points to a visited set and continue", your problem is degenerate. Because the hull of a single point is the point itself, which you eliminate and continue from an empty set. (Also works with the first two or first three points, always forming a convex polygon.)

---
Tags: computational-geometry, convex-hull
---


# Question
Title: What exactly does Turing Equivalence mean?
Assume I have a programming language $L$ with well-defined semantics. Showing Turing-completeness is straightforward: if I write a program using $L$ simulating the universal TM, I'm done. What I'm concerned about is another direction. How do we show that a program in $L$ can be simulated by TM when $L$ supports things like:

* File I/O (I guess this can be handled by considering the entire filesystem as the part of the tape?).
* Interactive user input (I guess we can treat it as non-interactive?).
* Interaction with external devices, e.g. display, network, etc. (I guess it can be handled by the file interface?).
* Assume that the semantics is non-deterministic (e.g. $L$ allows parallel execution). How to fit it into TM settings?
* Probably many other things I didn't think of...

I'm fine with a reference that covers this question. Note that I'm talking about the language itself, not about its implementations, and hence the Church-Turing thesis is not applicable: e.g. a Turing complete language which also has access to the Halting oracle is not Turing equivalent.

# Answer
> 3 votes
First of all you should separate the (math) specifications of $L$ and its "execution" from the input/output functions of $L$. If such input/output is crucial for $L$ then you're trying to prove the Turing equivalence of a "device running $L$" with a Turing machine (which is a little bit different).

For example if $L$ has a function "read random bit from device X", then it's probably easy to prove the equivalence of $L$ with a Turing machine; but the combo "$L$ \+ an actual Geiger counter" leads towards the "physical Church–Turing thesis".

You must first model all aspects of $L$ (I/O, user input, ...) in terms of reading/writing into tapes. And this can usually be done in a very simple way:

* file/io --\> tape
* output devices --\> tape
* interactive user input --\> special tape in which user input is pre-loaded
* parallelism --\> already a lot of work on it and its TM modelization
* non determinism --\> NTMs
* ...

---
Tags: programming-languages, turing-completeness
---


# Question
Title: Evolving artificial neural networks for solving NP problems
I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. They use genetic algorithms to "evolve" the weights of the axons.

So basically my idea is the following. If I was supposed to write a program that recognizes numbers I would not know how to start (I could have some vague idea but my point is: It is not trivial, nor easy.) but by using neural network I do not have to. By creating the right context in order for the neural network to evolve, my neural network will "find the correct algorithm". Down below I quoted a really interesting part of the article where they explain how each layer have different role in the process of image recognition.

> One of the challenges of neural networks is understanding what exactly goes on at each layer. We know that after training, each layer progressively extracts higher and higher-level features of the image, until the final layer essentially makes a decision on what the image shows. For example, the first layer maybe looks for edges or corners. Intermediate layers interpret the basic features to look for overall shapes or components, like a door or a leaf. The final few layers assemble those into complete interpretations—these neurons activate in response to very complex things such as entire buildings or trees.

So basically my question is the following: Couldn't we use genetic algorithms + neural networks in order to solve every NP problem? We just create the right evolutionary context and leave "nature" find a solution.

Inceptionism: Going Deeper into Neural Networks

EDIT: I know we can use Brute-Force or find a not-efficient solution in many cases. That is why I try to highlight **Evolving** artificial neural networks. As I said in a comment: Given sufficient time and an appropriate mutation rate we could find the optimal solution (Or at least that is what I think).

# Answer
No. This direction is unlikely to be useful, for two reasons:

1. Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist *any* polynomial-time algorithm to solve *any* NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the neural network will itself be a polynomial-time algorithm. It follows that if P $\ne$ NP, neural networks cannot efficiently solve any NP-complete problem.
2. Neural networks aren't "magic". They are a way of trying to find patterns. For some problems where there are strong enough patterns to be found, and the patterns can be learned from a reasonable number of examples, they might be effective. But they're not magic fairy dust. Just because you can set up a neural network doesn't mean that backpropagation will necessarily find a good way to solve your problem. It might be that there are no patterns to be found, that the patterns can only be discovered with an unfeasible number of examples, or that patterns exist but the neural network training procedure isn't able to find them.

Neural networks are just another form of machine learning. We could make the same remarks about SVMs or random forests or linear regression any other form of machine learning. Neural networks aren't some kind of magical silver bullet that solve all machine learning problems. They're about as effective as other machine learning methods, or for some kinds of problems, maybe a little bit more effective, but they're not magic.

Sometimes I run across people who have heard only a little bit about neural networks, and they walk away thinking that neural networks are the answer to everything -- maybe because they heard that "your brain uses neural networks too", or they saw some very cool application (voice recognition or something). But don't be fooled. Don't believe the hype. Neural networks are a useful technique, but they're not going to enable computers to solve NP-complete problems, or to beat the Turing test, take away all our jobs and replace humans with computers. Not anytime soon, anyway. That's just science fiction.
> 22 votes

# Answer
It seems other answers while informative/ helpful are not actually understanding your question exactly and are reading a little too much into it. You didn't ask if neural networks would *outperform* other methods, you only asked if they could be *applied* to NP complete problems. The answer is yes, with some success and this has been known for decades and there is a wide variety of research on this, and it continues. This has to do with the flexibility of machine learning. Note that even if they dont find exact or optimal solutions, the solutions they have may have other desirable properties. some example papers:
> 11 votes

# Answer
Neural networks do not actually solve NP-complete problems. What they **do** do is solve problems which are remarkably close to NP-complete problems.

One big feature of neural networks is that they are not obliged to find the "right" answer every time. They are allowed to be "wrong." For example, you might be solving a bin-packing problem, and come to a solution which is 1% off of the ideal solution and be totally content with that answer.

If you remove the requirement of being 100% right every time, other problem solving approaches work very well. For example, many route planning algorithms (a la Google Maps) have to be NP-complete, but it is quite trivial to find an algorithm which finds a path within 1% of the optimum 99.9% of the time. It's trying to pin down results in that last 0.1% of the cases which drive NP-complete efforts to be so mindnumbingly expensive.

As it happens, when we try to use NP-complete equations in real life, we don't often need the *actual* answer. We're often very comfortable with a "close" answer, though we often don't have a wording to explain what "close" metric we are using. These are the situations where a neural network can answer the actual question you wanted to ask, rather than having to actually solve the NP-complete problem you asked for instead.
> 4 votes

# Answer
Neural networks are known to be capable of universal function approximation, but this requires training them on the problem (optimization) which is a NP-complete problem in and of itself, which is why you have evolutionary training and SGD with backpropagation and so on.

So while they are not likely to solve NP-complete problems they can be trained to approximate to an arbitrary degree of accuracy a function that models the problem. Also even if you happen to solve an NP-complete problem optimally using a neural network you still have no way to prove that the solution it found is actually the global optimum without brute forcing the solution (this is of course not feasible for almost any practical use case of neural networks).

Your visualization is accurate in the sense that evolutionary algorithms (see how the neat algorithm prevents a single species from taking over the population with an initially highly performant structure by using shared fitness) are less apt than SGD and other machine learning techniques to be trapped in local optimums but they provide no proof that the solution they find is in fact the global optimum solution.
> 1 votes

# Answer
Even if P $\neq$ NP, that says nothing about average case complexity. That for any algorithm for solving a NP complete problem must have at least some instances where it takes more than polynomial time. However it is certainly possible that we find an AI that can solve sat in linear time for 80% of instances better then any conventional algorithm. I do not know enough about AI to give the likelihood of that
> 0 votes

# Answer
Given that neural nets are good at interpolation (but poor at extrapolation), for a given use case it suffices to solve a few billion large problems and feed them to a sufficiently large net. In some cases this would work.
> -1 votes

---
Tags: machine-learning, np, neural-networks, p-vs-np, genetic-algorithms
---


# Question
Title: Calculating number of inversions in array using AVL Finger Tree
**Problem**: Let $ A $ be an array of $ n $ different elements from an ordered interval.
Let $ I(A) $ be the number of inversions in array $A$, meaning, the number of pairs of indexes $ 0 \leq i \< j \<n $ for which it occurs that $ A\[i\] \> A\[j\] $. Notice that $ 0 \leq I(A) \leq {n \choose{} 2} $ and that $ I(A) = 0 $ if and only if $ A $ is sorted.
Prove that given array $A$, it is possible to calculate $ I(A) $ in time $ O(n \log n) $.

**Official answer to problem:** Put the elements one by one into an AVL Finger Tree with a pointer to minimal key in the tree. After each insertion calculate $ n - TreeRank(x) $ , where $ n $ is the current number of elements after insertion and $ x $ is the node we inserted. Return the sum of these numbers.

**Note**: $ TreeRank(x) $ = position of $ x $ in sorted order in $ A $ ( count starts from 1 and not 0 , for example if $ A = \[ 6, 5 ,8 \] $ and $ N\_b , N\_a $ are nodes whose keys are 6 and 5 respectively then $ TreeRank(N\_b) = 2 , TreeRank(N\_a) = 1 $ ).

**My question:** I don't understand why calculating $ n - TreeRank(x) $ each time we insert $ x $ and then summing this result, will end up giving me the total number of inversions as we put each element of the array into the tree. What's the reasoning behind this technique that it works? Can you please help to elucidate this?

Thanks in advance for any help!

# Answer
> 1 votes
I think there is something wrong with the definition of $TreeRank(x)$. Shouldn't it be define as the position of $x$ among the inserted items in the tree and not $A$ entirely? Otherwise, it will not work with your example.

If you use my definition, $n - TreeRank(x) $ means you are counting how many elements greater than $x$ was inserted before $x$ in the tree. That should give you the idea why you get the number of inversions.

You can compute the $TreeRank$ while you insert the element if you save the size of each subtree. Since you're using a balanced BST, the cost of computing $n - TreeRank(x) $ for each $x$ takes $O(\log n) $, hence $O(n \log n) $ in total.

---
Tags: data-structures, trees
---


# Question
Title: Calculate shortest cycle that contains node $s$
Let $ G(V, E, w)$ be a graph with no negative weights.

Describe an algorithm that returns the shortest cycle containing a node $ v $.

I came across this algorithm https://courses.engr.illinois.edu/cs374/sp2017/labs/solutions/lab10-sol.pdf

I can't convince myself it is true, because $ d(s,v)+w(s,v)$ might not be independent.

By that I mean that perhaps $w(s,v)$ is contained in $d(s,v)$.

An algorithm I came up with is as follows:

```
Result arr=[]
For x in N(v):  // N is neighbours of v
    remove(v,x) // remove the edge (v,x)
    T=Dijkstra_tree(x,G)
    if(v is in T):
        Add d(v,x)+w(v,x) to Result Arr// add the weight of the tree+ the removed edge to arr
return Min(Result arr)

```

This algorithm has a running time of $O(|V|)(|E|+|V|\log(|V|)$.

Because $v $ might have $|V|-1$ neighbours, and then we run Dijkstra every time on them.

The algorithm they presented has a much better complexity but I just can't convince myself it indeed works. My algorithm fixed that issue, but costs a lot of runtime.

# Answer
> 1 votes
To answer the question "why is the linked algorithm correct?", first of all notice that it works for *directed* graphs.

We want to show that the shortest cycle containing $s$ consists of a shortest path from $s$ to some vertex $v$ plus the edge $(v,s)$ such that $d(s,v) + w(v,s)$ is minimized.

Let $C = \langle s=v\_0, v\_1, \dots, v\_\ell, s\rangle$ be a cycle. Clearly, the length of $C$ is at least $d(s, v\_\ell) + w(v\_\ell, s)$. On the other hand, all shortest paths $\pi$ from $s$ to a vertex $v$ such that $(v,s)$ exist imply the existence of a cycle of length $d(s,v) + w(v,s)$ (notice, in particular, that any simple path from $s$ contains no edges entering $s$, hence $\pi$ does not already contain $(v,s)$).

# Answer
> 0 votes
In an undirected graph $G$, remove vertex $v$ and find the shortest path between all pairs of vertices in $N(v)$; i.e. Find $d(a,b):=$shortest path between $a,b\in N(v)$ in graph $G'=G-\\{v\\}$.

Result is $min\\{d(a,b)+w(a,v)+w(b,v)|a,b\in N(v)\\}$.

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


# Question
Title: Need help proving the following for every integer n larger or equal to 1
i need help proving the following : $$\sum\_{k=1}^{n}\frac{1}{(3k-1)(3k+2)}=\frac{n}{6n+4}$$ for every integer n larger or equal to 1

Can you help? Thanks

# Answer
> 0 votes
$$\sum\_{k=1}^{n}\frac{1}{(3k-1)(3k+2)}=\frac{1}{3}\sum\_{k=1}^{n}\[\frac{1}{3k-1}-\frac{1}{3k+2}\]= \frac{1}{3} \\{\[\frac{1}{2}+\frac{1}{5}+\frac{1}{8}+\frac{1}{11}+\frac{1}{14}.........+\frac{1}{3n-1}\]-\[\frac{1}{5}+\frac{1}{8}+\frac{1}{11}+\frac{1}{14}.........+\frac{1}{3n-1}+\frac{1}{3n+2}\]\\}=\frac{1}{3}\[\frac{1}{2}-\frac{1}{3n+2}\]=\frac{n}{6n+4}$$

---
Tags: discrete-mathematics
---


# Question
Title: How to Implement Static Dictionary Compression?
I am targeting a simple dictionary-coder compression algorithm that uses a static dictionary (code in an existing program, but I can supply my own dictionary). How can I write a compressor for such an algorithm? The first thought I had was to rank all strings in the data by the size reduction from making them dictionary entries, but then what? When some of those strings overlap, the amount of compression achieved depends on which mutually exclusive substitutions you make. How can I find the optimal dictionary and optimal set of substitutions?

The dictionary references are all the same size, by the way, so this isn't like Huffman encoding.

# Answer
The simplest approach is to use the known text as a "priming text". Conceptually, you run whatever compression algorithm you want on the concatenation of the priming text and the text you want to compress, compress it, but don't transmit the compressed priming text.

Exactly how you realise this idea depends on the compression method. For example, if it were a LZ77 method, you could pre-fill the sliding window with the priming text. For the coding stage, you could train an adaptive coder on the priming text, and then use that for the initial coding model.

For methods that are more like LZ78 or PPM/DMC, you could build an initial model/dictionary on the priming text, and go from there.
> 1 votes

---
Tags: data-compression
---


# Question
Title: Converting a Directed Acyclic Graph to a Directed Tree
I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ). My question is, is there a known way to convert such graph to a directed tree that has no loops. I know of the junction tree/ clique tree way, but this results in an undirected tree after moralization.

I am trying to decompose a DAG type graph to a more tree-like structure. For context the vertices in the graph represents sinks and sources so there can be multiple sources.

Edit: I should've been more clear. To be more concise, I was wondering if there was a way to convert a DAG to a polytree.

# Answer
If the undirected version $G'$ of the DAG $G=(V, E)$ is not connected, then there is no polytree that contains all vertices in $V$ and only a subset of the edges in $E$.

If $G'$ is connected, then you can compute any spanning tree $T$ of $G'$ and construct the poly-tree that contains all vertices in $V$ plus all the (directed) edges $(u,v) \in E$ such that the (undirected) edge $\\{u,v\\}$ is in $T$.
> 0 votes

---
Tags: graphs, dag, decomposition
---


# Question
Title: Why does adding an $ \epsilon $-transition to a DFA or NFA preserve the regularity of the language?
Does adding an $ \epsilon $-transition to a deterministic finite automata preserve the regularity of the language?

Don't we have one chance to scan the word? If we choose one direction, don't we miss the other one?

# Answer
> 0 votes
A language is regular if and only if there exists a NFA (equivalently a DFA) that recognizes it.

Adding an $\varepsilon$-transition to a NFA (DFAs are special types of NFAs) still results in a NFA, hence both the the language of the original NFA and the language of the modified NFA are regular.

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


# Question
Title: Lower bound for ϵ-tester with one-sided error for the "2-injective" property of functions
**An $\epsilon$-tester** given an input and a property, is defined as follows:
If the input holds the property then the tester should accept with probability at least $\frac 2 3$. Otherwise if the input is more than $\epsilon$ far from holding the property then the tester should reject with probability at least $\frac 2 3$. Meaning that if the input holds the property, with $f$ being less than $\epsilon$ far from not holding the property, the algorithm should accept with probability at least $\frac 2 3$. If we need to change at least ϵn values of $f$ in order to obtain a function satisfying the property then the algorithm should reject with probability at least $\frac 2 3$.

**A tester with one-sided error** is a tester, given an input, if the input holds the property then the tester accepts the input with probability 1.

**A 2-injective function** $f\colon \[2n\] \to \[n\]$ is a function such that for all $1 \leq k \leq n$ there exist $1 \leq i\<j \leq 2n$ such that $f(i) = f(j)=k$ and there is no other $l \neq i,j $ such that $ f(l)=k $. Here $\[m\]$ for $m\ge1$ is the set of first $m$ positive integers, $\\{1,2,\cdots, m\\}$.

We can check that $f$ has more than $\epsilon$ of the input that do not hold the property iff $$\frac{2\left|\\{k\in\[n\]: f^{-1}(k)=\emptyset\\}\right| + \left|\\{k\in\[n\]: |f^{-1}(k)|=1\\}\right|}{2n} \gt \epsilon$$

We need to show that there exists $\epsilon$, for which an $\epsilon$-tester with one-sided error of a function $f\colon \[2n\] \to \[n\]$ for the "2-injective" property, requires $\Omega(n^{2/3})$ queries.

Unfortunately, searching online for articles and scientific papers about the topic yielded nothing, and I haven't had any success in solving this question myself. I managed only to show it for injective functions but the proof is almost straight-forward and trivial.

I'm pretty new at the field of property-testing so any help would be highly appreciated!

# Answer
Here's a sketch, for $\epsilon=1/10$ or so.

Let $f$ be a $2$-injective function chosen uniformly at random, and let $\widetilde{f}$ be the perturbation of $f$ formed by choosing $Y\_1 \subseteq \[n\], |Y\_1| = n/10$ uniformly at random, then choosing $Y\_2 \subseteq \[n\]\setminus Y\_1, |Y\_2| = n/10$ uniformly at random, then choosing a bijection $\phi : Y\_2 \to Y\_1$ uniformly at random, then, for each $y\_2 \in Y\_2$, choosing $x\_{y\_2} \in f^{-1}(y\_2)$ uniformly at random, and setting $\widetilde{f}(x) := f(x)$ if $x$ is not in $\\{x\_{y\_2} : y\_2 \in Y\_2\\}$ and $\widetilde{f}(x) := \phi(y\_2)$ if $x = x\_{y\_2}$ for some $y\_2 \in Y\_2$.

We'll present the presented tester with either $f$ or $\widetilde{f}$, each chosen with probability $1/2$.

Since there's no relation amongst the points of $\[2n\]$ (i.e. they are all the essentially the same and learning the value of the function at one point tells you equally about the value of the function at the other points), the set of points that the presented tester queries is as good as a set of points chosen uniformly at random from $\[2n\]$.

If the number of queries is less than $n^{2/3}$, say $n^{2/3-\delta}$, and $\widetilde{f}$ is presented to the tester, then, for any given $y \in Y\_1$, the probability that you see $y$ outputted by three of the queried points is basically $n^{-1-3\delta}$, so union bounding over $Y\_1$ shows that it is very unlikely you learn that any point has preimage of size $3$. So (here is where some more arguments need to be added) the tester can't tell $f$ and $\widetilde{f}$ apart.
> 3 votes

---
Tags: algorithms, algorithm-analysis, lower-bounds, probabilistic-algorithms, property-testing
---


# Question
Title: Is there a Turing machine that packs a machine and its input into a single machine?
Let $U$ be the universal Turing machine. Is there a Turing machine $T$ taking two inputs such that $\forall m \forall n \exists q \\; T(m; n) = q \land U(q;0)=U(m;n)$?

It seems "obvious" that there is such a Turing machine, but if there is one, then the function $Q(n) = 1 + T(n;n)$ is not computable because it's the diagonal of $T$ plus one (it is not in the list of all computable function) so there is no TM that computes $Q$ so there can't be any TM $T$ either.

This is the same argument for non-computability of Halting Problem.

What am I missing?

# Answer
Irrespective of whatever notation is used by the OP, I will use the following notation: $T^k$ is the $k$-th Turing machine under an acceptable numbering of Turing machine, and $T^k(n)$ is the result of running the $k$-th Turing machine on onput $n$. The output is either undefined, if $T^k$ never terminates on input $n$, or is a number.

The function $Q(n) = 1 + T^n(n)$ is computable. What you are missing is the fact that in general Turing machines compute *partial* functions.

Let us see how your imagined diagonalization argument for $Q$ fails. We want to show, for every $k \in \mathbb{N}$, that the $k$-th Turing machine does not compute $Q$, i.e., that $Q \neq T^k$, by arguing that if $Q = T^k$ then $$T^k(k) = Q(k) = 1 + T^k(k).$$ Now this would be a contradiction if we knew that $T^k(k)$ is a natural number. But $T^k(k)$ may be undefined, in which case there is no contradiction because both sides of the equation are undefined. The diagonalization proof breaks down.
> 1 votes

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


# Question
Title: weighted graph separation algorithm proof
I have a graph G (G=(V,E)), where each edge has a non negative weight to it.

My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that start in S and end in V\S is lower than a given positive k.

My approach was to pick a random node in the graph, run a bfs on a masked version of G where only the edges that are larger than k remain, and then check if each component of the masked G may be such S in G, if none may apply than ill conclude that no such S exists.

I calculated that this algorithm will have a run time of O(E^2 +V)

Now im finding a hard time to prove this algorithm is correct, but at the same time in struggling to find an example where it is incorrect.

Maybe someone could help me prove this algorithm is correct.

# Answer
> 0 votes
Your algorithm is incorrect. Let $G$ be a cycle on $4$ vertices where edge weights alternate between $2$ and $4$ and consider $k=5$.

The graph obtained from $G$ by keeping all and only the edges with weight larger\* than $k$ contains no edges. Therefore the sets $S$ that you consider contain a single vertex.

Given any vertex, the sum of the weights of its incident edges is $6$. Therefore you conclude that the instance admits no solution. This is wrong since it is possible to choose $S$ so that the sum of edges crossing that cut is lower\* than $k$ (in particular it is $4$).

\*I have chosen the counterexample so that it holds even if any occurrence of "larger" and/or "lower" in the problem statement and in the proposed algorithm is optionally replaced with "at least" and "at most" (respectively).

---
Tags: graphs, optimization, weighted-graphs
---


# Question
Title: Reducing a mixed Boolean expression containing XOR of conjunctions
I know that XOR-SAT can be solved in polynomial time using arithmetic in $F\_2$ and Gaussian elimination.

I have a set of formula that is of the form

$$ G\_i := \oplus\_{j=0}^{i} \left ( a\_j \land b\_{i-j} \right ) $$

where $a\_k, b\_k$ are the variables and $\oplus$ denotes XOR and $\land$ denotes logical AND.

Is there any standard reduction I could apply to these formulae to solve them using XOR-SAT?

I need to solve the conjunction of $\land\_{i} G\_i$.

Edit: The $G\_i$ are known.

# Answer
> 2 votes
Your question is a bit hard to understand, so let me interpret it in the following way. You are interested in Boolean CSPs (that is, constraint satisfaction problems over Boolean variables) in which the constraints are of the form $$ \bigoplus\_{i=1}^n (a\_i \land b\_i) = 1, $$ where $a\_1,\ldots,a\_n,b\_1,\ldots,b\_n$ are arbitrary *variables* (rather than literals), which can possibly repeat. The value of $n$ can be any natural number.

According to Schaefer's theorem, if $S$ is a collection of Boolean predicates that $\mathit{CSP}(S)$ can be solved in polynomial time if one of the following is a polymorphism of all predicates in $S$:

* The constant 0 function.
* The constant 1 function.
* The binary AND function.
* The binary OR function.
* The ternary XOR function.
* The ternary majority function.

(Here binary means that the function has two inputs, and ternary means that it has three inputs.)

If none of these are polymorphisms of $S$, then $\mathit{CSP}(S)$ is NP-complete.

In your case, $S$ is an infinite collection of predicates $\\{ P\_n : n \in \mathbb{N} \\}$. Fortunately, using the theorem it is easy to check that $\mathit{CSP}(\\{P\_2\\})$ is already NP-complete, and so your problem is also NP-complete.

---
Tags: satisfiability
---


title: kth smallest element in n sorted arrays

text:
# Question
Title: kth smallest element in n sorted arrays
kth smallest in one sorted array, just take `O(1)` time

kth smallest in two sorted arrays, there is a binary search algorithm, take `O(log k)` time

kth smaleest in n sorted arrays, we can use min-heap, takes `O(k log n)`. However, when `n = 1 or 2`, it's essential brute-force linear scan which takes `O(k)`.

Is there more optimized algorithm for kth smallest in n sorted arrays which will keep optimized when `n = 2`?

# Answer
> 0 votes
I think something like this could work:

Given $n$ arrays $A\_1, …, A\_n$ and an integer $k$, finding the $k$-th smallest element of those arrays can be done by finding $n$ "cuts" in those arrays such that the total number of elements before cuts is equal to $k$. The $k$-th smallest element is then one of the elements just before cuts in one of the arrays.

In details, if the arrays are of lengths $N\_1, …, N\_n$, we need to find indices $i\_1, …, i\_n$ such that for all $1\leqslant j \leqslant n$, we have $0\leqslant i\_j\leqslant N\_j$, and $\sum\limits\_{j=1}^ni\_j = k$.

To ensure the cuts are well done, for $j\neq j'$, we also need $A\_j\[i\_{j}-1\] \leqslant A\_{j'}\[i\_{j'}\]$.

The $k$-th smallest element is then $\max\limits\_{j=1}^nA\_j\[i\_{j}-1\]$ (note that some of those may not exist if $i\_j=0$).

The idea of the algorithm is some kind of double *divide and conquer*. Details may be missing, but I think this works:

* if $n = 1$, find the cut in $\mathcal{O}(1)$ time;
* otherwise:
    + let $k\_1 = 0$ and $k\_2 = k$;
    + while $k\_2 \> k\_1 + 1$:
        - let $\ell = (k\_1 + k\_2) / 2$
        - find the cuts for the $\ell$-th smallest element $x$ in arrays $A\_1, …, A\_{\frac{n}2}$;
        - find the cuts for the $(k-\ell)$-th smallest element $y$ in arrays $A\_{\frac{n}2+1},…,A\_n$;
        - if the cuts are well done, return $\max(x, y)$;
        - otherwise, if $x \< y$, $k\_1$ becomes $\ell$;
        - otherwise, $k\_2$ becomes $\ell$

To check if cuts are well done, you need to check if $x \leqslant A\_{j'}\[i\_{j'}\]$ for $j'\in \\{\frac{n}2+1, …, n\\}$ and if $y\leqslant A\_{j'}\[i\_{j'}\]$ for $j'\in \\{1, …, \frac{n}2\\}$.

For the complexity, let $C(n)$ be the time complexity for the search of the $k$-th smallest element in $n$ sorted arrays. Given the previous algorithm, we get: $$C(n) = \log\_2 k (2C\left(\frac{n}2\right) + \mathcal{O}(n))$$

Using the master theorem, we get $C(n) = \mathcal{O}(n(\log\_2 k)^{\log\_2 n})$.

We get $C(1) =\mathcal{O}(1)$ and $C(2) = \mathcal{O}(\log\_2 k)$.

---
Tags: algorithms
---


# Question
Title: $O(n \log n)$ Algorithm for first Train Problem
On $n$ parallel rails there are $n$ trains with constant speeds $v\_1, ..., v\_n$. At time $0$ the trains are at positions $k\_1, ..., k\_n$. Find an $O(n \log n)$ algorithm that determines which trains are in the lead at least once.

My current approach is to create a 2-dimensional coordinate system, time as x-axis and position as y-axis both only for positive values. Then i add a linear equation for each train: $y = v\_i \cdot x + k\_i$.

Then my first idea was to take the train with the furthes starting position since it is in the leading position at time 0. Then calculate the first intersection with another train $v\_j$, then from this point calculate the first intersection of $v\_j$ with another train and so on. But this leads to a runtime of $O(n^2)$ which is not good enough.

I talked to some colleagues and we discussed the option of a divide-and-conquer approach but couldn´t find a solution.

# Answer
> 1 votes
**Hint 1:**

Your approach is good. The algorithm type you are looking for is called a "scan line" algorithm. The idea is that you move from left to right on your 2d model and at each intersection (an "event") update data structures.

**Hint 2:**

In your case the you maintain a ordered binary search tree of the trains (sorted by which train is currently ahead). You also maintain a priority queue of "events".

**Hint 3:**

Each event is struct which contains at what time it occurs and which two trains are gonna change position in the "leader board" (the BST). Since positions only change at an event, you use these to note which trains were ahead once. Since trains can only change places when they are next to each other you can generate events quite easily. Basically in the beginning you create an event for each pair of neighboring trains, and after every event you create new events for the trains that switched places and their new neighbors (in the leaderboard). Keep in mind that getting the lower and upper neighbors in a BST is $O(log(n))$ and extracting and placing elements in a priority queue is $O(log(n))$ as well.

This is very similar to the Bentley-Ottmann-Algo

---
Tags: algorithms, sorting, search-algorithms, efficiency, divide-and-conquer
---


# Question
Title: Dynamic Time Warping and Similarity Measures
I have a multidimensional time series on which I would like to perform some clustering. I have been looking at DTW as a distance metric since my series are not always aligned in time. The problem I have is that while the one to many mapping of points along two series allows for their alignment in the event they are the same signal but just shifted in time, it also means that time series with different frequencies are treated as being similar. In this case, a different frequencey should result in a larger distance metric. I can impose some locality constrains using different warping windows but that does not really help. Is there such a time series similarity measure that aligns series that are shifted in phase but treats differences in frequencies between series as being different?

EDIT:

In this case the time series corrsoponds to small molecule vibrational motion. Each of the dimensions in the time series corrosponds to a different bond length or angle and they are inherently coupled. Below are two example 1D cuts of the higher dimensional time series (prior to Z-normalisation).

.

So far I have just been playing with a single dimension (the first plot above), and the standard symmetric step used in DTW results in a measure that is not physical for my system, for example different frequency vibrations are treated as being similar. Let us take several of the smaller amplitude and higher frequencey signals from the first plot as an example,

Using the symmetric step, the series labelled 0 and 2 are predicted to have a much lower alignment cost than the others. Here several of the points in the first peak of the querry value is matched to many points in the lower frequency signal. By allowing many horizontal/ vertical steps in the construction of the warping path, one ignores differences in frequency.

I then looked at different step patterns, and by restricting the freedom for horizontal/ verticle steps through one of the Rabiner Juang type patterns, I achieve a more sensible result,

here you can see that the one to many mapping of the points in the querry to the lower frequency series no longer exists. It seems that using such a step pattern enforces the warping behaviour I want - basically it just shifts the two signals along eachother as to optimally align them. When testing it on other combinations of signals from the series I have, it ranks them as one would expect now. My only concern now is the treatment of the end points. Perhaps I can allow some horizontal and vertical steps but restrict the number of succesive steps.

Another problem is Z-normalisation. Currently I perform this once for the time series, not for each sequence, else the ampltiude of the series shift with respect to eachother? In this case the amplitude of the raw signal matters and should be treated differently. Perhaps DTW is not the measure I need, within this application to physics different frequencies and ampltidues in the time series corrospond to the molecular system having different energies and being in a different state and therefore they must be treated differently.

# Answer
Minor point, you say "looking at DTW as a distance metric " DTW is not a metric, it is just a measure.

The answer to your question "Is there such a time series similarity measure that aligns series that are shifted in phase but treats differences in frequencies between series as being different" is Yes.

You can use phase invariant distance (\[a\] page 3). If you need speed, you can compute this in just O(nlog(n)).

Having said that, I am not convinced this is what you need.

Can you show examples of the data? That way I could advise you.

At a minimum, I recommend you read \[a\] and https://www.cs.unm.edu/~mueen/DTW.pdf

\[a\] https://www.cs.ucr.edu/~eamonn/Complexity-Invariant%20Distance%20Measure.pdf
> 0 votes

---
Tags: algorithms, dynamic-programming, time-series-analysis
---


# Question
Title: Contradicting asymptotic analysis in recurrence equation?
I'm trying to solve the recurrence equation from CLRS ed 2. $$ T(n) = 2T(\sqrt{n}) + 1 $$ The question says the solution should be asymptotically tight, but at first I didn't read it and solved it with a substitution of variables and tried to find a big-O solution. $$ m = lg(n) \\ S(m) = T(2^m) \\ S(m) = 2S(m/2)+1 $$ After this, I guessed the solution to be O(lgn) and proved it; changing back the m's to be in the form of n I got T(n) to be O(lglgn).

However, this is not a tight bound and after changing my guess for S(m) from O(lgm) to Θ(m) it worked. The resulting analysis led me to T(n) being Θ(lgn).

Though this is the part that confuses me, how can a function be O(lglgn) yet Θ(lgn)? I can't seem to find my error.

# Answer
Set $n=2^{2^m}$. The recurrence turns to

$$T(2^{2^m})=2T(2^{2^{m-1}})+1$$

or

$$S(m)=2S(m-1)+1.$$

This is an ordinary linear recurrence. By inspection it has the particular solution $S\_p(m)=-1$, and the homogeneous part of the equation is solved by

$$S\_h(m)=C\\,2^m.$$

From this,

$$T(n)=S(m)=C\\,2^m-1=C\\,\log n-1.$$

---

**Check:**

$$C\\,\log n-1=2(C\log\sqrt n-1)+1=\frac22C\\,\log n-2+1.$$
> 1 votes

---
Tags: algorithm-analysis, asymptotics, recurrence-relation
---


# Question
Title: What is the relation between the amount of data transmitted and line distance?
I am wondering what is the relation between line distance and the amount of data transmitted on that line. I know only the basic of computer science. Let's say I want to calculate the time it takes for 100 GB to transfer over a line with the speed of 100MBps. If I just divide them, I will get 1000 seconds but in my online class, the lecturer said the time depends on the line distance. Since it is an introductory course, he doesn't explain anymore. So my question is, how is it relevant and why? I know the simple answer should be the resistance of the line increase as it got longer but does the resistance affect on the needed time significantly? How could I calculate the needed time with distance?

# Answer
> 1 votes
With the size of data and bandwidth given, you can only calculate the **transmission delay** and not the **propagation delay**(latency). The latter depends on the physical characteristics of the medium used for transfer of data.

# Answer
> 0 votes
Distance sets lower bounds on *latency*, the effect on *throughput* as opposed to *data rate* depends on *protocol*.
Raw error rate increases with distance.

# Answer
> 0 votes
You wrote

> I know the simple answer should be the resistance of the line increase as it got longer but does the resistance affect on the needed time significantly?

but this is not about the resistance of the line.

Consider again the statement

> the lecturer said the time depends on the line distance

So the question is how long it takes to transfer/communicate $X$ amount of data (100 Gbit, let's say) if the line speed is 100 MBit/s). You think it may be just 1000 s (amount of data divided by line speed).

But the point about the line distance is that it takes a finite amount of time for the transmission to go through the line. This is called *latency*. For example, if it takes 10 s to go through the line, then the answer is 1000+10s = 1010s.

Knowing both the data rate (line speed) and latency (line distance), allows you to answer the question of how long it takes.

# Answer
> 0 votes
100 Gigabyte at 100 Megabyte per second will always take 1,000 seconds. That's computer science (taking the expression generously).

But then there is physics. It is harder achieving a certain bitrate over a long distance. Usually when you send a signal through cables, you have a quality loss at the initial connector at the source, you have loss at the final connector at the destination, and you have a loss of signal for every meter of distance. At some point the total loss of signal quality is so high that you can't transmit your 100 Megabyte per second anymore.

You can use higher quality parts, better connectors, better (more expensive) cables. That lets you transmit at the same speed over a longer distance. You can avoid laying your cable close to power lines, or bending your cables - if you need to change direction of the cable by 90 degrees do it in a gentle curve. All these methods let you transmit 100 Mbyte per second over a longer distance.

If that's not enough, you have two choices: Reduce the bitrate, or reduce the distance. A 50 Megabyte per second bitrate will work over a longer distance. So the longer distance doesn't make the bitrate slower, what it does is it reduces the highest bitrate that works. And a shorter distance increases the highest bitrate that works.

If you need more distance, you can insert amplifiers into the cable that will refresh a low quality digital signal into a higher quality one.

(There is a very small range where your quality is just low enough to introduce errors, but still high enough to fix or detect the errors. If you detect the errors, you'll have to ask the other side to retransmit the data. So your rate of *useful* bytes transmitted per second goes down).

---
Tags: computer-networks
---


# Question
Title: What is a good model for predicting which item the user will select from a list?
I have a list of apps the user has installed, a history of all previously opened apps, and a series of characters that the user has input.

The user is shown a list of apps filtered taking into account the input, the specific function should be given, but the app the user wants must never be filtered out. The list of apps the user is shown is sorted by some ordering given, but order should not change for the N (N is given and small ~10) most probable apps if character is added to the input.

The objective is to predict the most probable apps the user wants opened, and sort them from most probable to least and not jarringly re-sort the apps the moment the user goes to click.

Is there a *correct* way to achieve this? How should I think a solution for this? Is there a model for the user?

# Answer
> 0 votes
If you don't want the character input to affect the list of most probable apps, don't use the character input to predict the list of suggested apps.

If you use the character input to predict a list of suggested apps, then changing the character input has the possibility to change the list of suggested apps.

Alternatively, calculate a list of suggested apps when you first start displaying the list, then don't re-calculate it -- save that list, and continue to use that same list for some period of time, regardless of what additional character input might be provided.

There is no way to say what is "correct", because you haven't given a clearly specified criteria of what counts as correct. There are just some approaches with different tradeoffs.

# Answer
> 0 votes
If I understand your question correctly, you are looking for a function $f(input, apphistory, task)$ that returns the set of matching apps where $input$ is a string the user has entered (eg: the command name), $apphistory$ is a frequency distribution of the previous app launches (for inferring the most frequently used apps) and $task$ is an additional filter criteria that is associated with apps.

```
SELECT
 app_name, historical_use_count
FROM apphistory
WHERE
 app_name like @input AND
 task = @task
ORDER BY historical_use_count desc

```

A query like the above would filter apps suitable for the task at hand and sort them by historical frequency of use. You could then have the app restrict to the Top N results from the query to display in the UI.

This of course assumes that you have already associated the tasks with the apps and have that already tagged to the app (eg: as a column in the apphistory)

---
Tags: sorting, user-interface
---


# Question
Title: Why is the file size smaller than what I calculated?
The question is the conversion from an animation to a video file with the following attributes:

Frame rate:24 fps

Resolution:320\*240 pixels

Color depth:24 bits

Length of video: 60s

Bit rate: 500kbps

I calculated that the file size should be 24*60*320*240*3=316MB (frame rate\* resolution\* colordepth / 3 * resolution), but the answer stated that the actual file size was just 500kbps\*60=3.5 MB due to file compression.I do not understand how this works.

# Answer
> 0 votes
500 kilo **bits** per second for 60 seconds. The information is compressed to fit within the bit rate in a possibly lossy format.

8 bits = 1 byte.

So its $500 / 8 \times 60$ kilobytes.

Thats 3750 kilobytes.

---
Tags: bit-manipulation
---


# Question
Title: How does nondeterminism affect the power of a machine?
For example, in finite-state machines (FSM), the main difference between a deterministic (DFA) and a non-deterministic machine (NFA) is that there are possibly more branches or outputs for each input, depending on how a machine the machine was built. In terms of computational power, are these two the same?

# Answer
**For finite state machines:**

Since the non-determinstic behaviour can be simulated via the deterministic version of the machine where new states are created for all possible combinations of simultaneous states of the non-determinstic one. There is no added computational power for reaching for the non-deterministic one. NFA and DFA are just as powerful as each other. However it can sometimes be more memory efficient to stick with the non-determinstic one, so you can avoid an explosion in the number of states.

**For pushdown automata:**

NPDA is more computationally powerful than DPDA.

**For Turing machines:**

Both deterministic and non-determinstic are equal is computational power.

One real world example for the Turing machine would be Windows 3.11. It can run multiple programs at once on a single CPU with a single thread. However if one program locked up, then all programs locked up.
> 3 votes

---
Tags: turing-machines, finite-automata, turing-completeness
---


title: DNA sequence and algebra

text:
# Question
Title: DNA sequence and algebra
DNA is made of a string of different proteins.There are 4 different proteins which make up the human DNA.We can represent each protein as a 2 bit sequence of '0' and '1'.However wouldnt it be much better if we had 4 available logic states('0','1','2','3') for every type of protein?How would a algebra having as a base 4 available logic states look like compared to boolean algebra?

# Answer
> 0 votes
DNA is a long-chain polymer. The monomers that comprise a DNA strand are referred to as "nucleotides".

A protein is a completely different polymer, the monomers of which are called amino acids. The "standard model" relationship between the two (which is a little more complex in practice) is that the "coding regions" of DNA encode sequences of amino acids, DNA is transcribed into RNA, and these RNA transcriptions get turned into proteins.

A nucleotide is comprised of a sugar molecule onto which there are two additional radicals: phosphate, which links the sugar molecules together into a chain, and one of four bases: adenosine, cytosine, guanine, and thymine (hereafter referred to A, C, G, and T).

In bioinformatics, we don't typically care about the difference between a "nucleotide" and a "base" and tend to use the terms interchangeably.

DNA is organised into a double helix structure. We can read each helix strand in a known order, typically 5' to 3'. The sugar molecule has a pentagonal structure, and the primes refer to where on that pentagon the phosphate molecules bond.

The other strand of the helix is (assuming no errors) the "reverse complement". The strand has the opposite order (using 5'-3' ordering), and each nucleotide is hydrogen-bonded with its complement: A is the complement of T, and C is the complement of G.

So, for example, to find the reverse complement of the sequence `ATTTG`, swap each nucleotide for its complement, and reverse the whole sequence, obtaining `CAAAT`.

A quirk of the Latin alphabet is that if you represent the four nucleotides in alphabetical order and assign a two-bit code to them, the complement of a nucleotide is its the logical "not".

```
00 A Adenosine
01 C Cytosine
10 G Guanine
11 T Thymine

```

The complement of a nucleotide isn't that useful on its own. The reason why it's important is that if you read a sequence of DNA, you could be reading from either strand of the double helix. You therefore need to consider the *reverse* complement of a sequence, not merely the complement of each base.

There are lots of situations where interpreting nucleotides as algebraic objects are useful, but which interpretation you pick depends on precisely what you're trying to do.

As a real example, I was once tasked with designing an error-correcting code for tagging DNA samples. The first approach I tried was to use a linear code, and that meant interpreting each nucleotide as an element of the finite field $GF(4)$. There might be other uses for that particular algebraic interpretation, but it's not obvious to me.

In summary, DNA doesn't have a "natural" algebraic structure, in the sense of an algebraic interpretation which corresponds to anything chemical or biological. If it's convenient to interpret DNA using some specific algebra to solve a problem that you're faced with, go for it. But it will likely be different depending on the specific problem.

# Answer
> 0 votes
IMO speaking of algebra here is irrelevant. No computation is ever made on the strings (be them bits or quaternary digits), no boolean operation, only comparisons for equality.

Furthermore, if you somehow encode the digits 0-3 or symbolic values like A T G C, the representation will most probably end-up as the binary numbers 00 01 10 11.

By the way, all computers in the world are binary, as this system is by far the most hardware-efficient. There had been attempts to build ternary computers, but they were abandoned. A quaternary computer is out of question.

Also notice that computer registers always have an even size (most of the time a power of 2), so that bits fit in pairs.

---
Tags: computer-algebra
---


# Question
Title: does local search's State-Flipping Algorithm always terminate?
I am looking at the state flipping algorithm, an algorithm that tries to find a stable configuration in a Hopfield network.

The algorithm simply flips the state of unsatisfied nodes as long as the the network has not reached a stable configuration.

Please check page 673, chapter "An Application of Local Search to Hopfield Neural Networks" of the textbook *Algorithm Design* by Jon Kleinberg and Éva Tardos.

Figure 12.4 depicts a network ending in a stable configuration, then in the following paragraph they say about the same network. "Indeed, in the earlier directed example, this process will simply cycle through the three nodes, flipping their states sequentially forever", which implies non termination, and in the following paragraph of the same page they prove termination!

In the slides (slide 18) by the same author, they say "Hopfield network search problem: Given a weighted graph, find a stable configuration if one exists...", but there is no known poly-time algorithm for the search problem"

I am totally lost... why do we say the search problem is not polynomially solvable even though we say that the state flipping algorithm always terminates in bounded time with a stable configuration?

# Answer
A Hopfield (neural) network is introduced as an **undirected** network satisfying some conditions in that book.

The book also introduces a **directed** Hopfield network exactly as a Hopfield network, except that "each edge is directed, and each node determines whether or not it is satisfied by looking only at edges for which it is the tail." Note that a directed Hopfield network is **NOT** a Hopfield network anymore.

The State-Flipping Algorithm can be applied to a Hopfield network as well as to a directed Hopfield network. That algorithm will not terminate for a certain directed Hopfield network with three nodes, although it always terminate for a Hopfield network. There is no contradiction here.

---

The State-flipping Algorithm "always terminates in bounded time with a stable configuration". However, this "bounded time" is proved to be polynomial in $n$ and $W$, not in $n$ and $\log W$. Here $n$ is the number of nodes and $W$, as a natural upper bound of $\Phi(S)$, is the total absolute weight of all edges.

For example, suppose there are $50$ nodes and the absolute maximum of the weights is $1657034118$. That textbook proves that algorithm will terminate in no more than $W$ flips, where $$W\le 50 \times 1657034118=82851705900.$$ $\log\_2 82851705900\approx37$. Had the algorithm been proven to terminate in no more than something like $37^3$ flips instead, that textbook could have stated the algorithm would terminate in time polynomial in $n$ and $\log W$. The point here is the big difference between $82851705900$ and $37^3$, that becomes more significant when the maximum of weights becomes bigger.

It is not a surprise that the textbook says "it turns out to be an open question to find an algorithm that constructs stable states in time polynomial in $n$ and $\log W$ (rather than $n$ and $W$)".

More generally, there is no known algorithm for this search problem in time that is polynomial in the size of input. That is why we say "there is no known poly-time algorithm for the search problem."
> 1 votes

---
Tags: algorithms, neural-networks, search-problem, local-search
---


# Question
Title: How does caching increases scalability in distributed file system?
There are clusters of LAN connected computer systems. California cluster has cached "viral video" at first stage, when client near California requested the file firstly.

Now, another client near California requests "viral video".

The benefit here is that there would be no network latency and subsequently no network traffic.

Since network latency\>file transmission and request time, this is beneficial.

**Network has 1 few user. So network is more scalable to 1 extra user.**

> How many users are using the network doesn't affect the response time for the client.

> How many nodes are there doesn't affect the response time for client.

I don't get how less network traffic is helping for scalability?

Text Book Explanation-:

# Answer
> 1 votes
> The benefit here is that there would be no network latency and subsequently no network traffic.

This is slightly incorrect, there would definitely be some network latency since within clusters we have separate machines connected by LAN, although the intra cluster latency would be very less compared to inter cluster latency.

> I don't get how less network traffic is helping for scalability?

Consider the scenario where a **client requests for a file not available at the cluster**, so the cluster then fetches the file from its location via the network. **If such requests increase in number, the inter cluster network traffic increases**, and the respective clients are waiting till the file is fetched and served. So your **throughput(no. of clients served per unit time) would drop as compared to when the file is cached at the clusters** in which case, there would be less network traffic. This would mean **you are able to scale to more users when the file is cached(low network traffic) as compared to when it is not cached(higher network traffic)**.

Of course both the scenarios occur together, **the initial requests aren't cached so the throughput is low, which increases as more requests are cached and users request for them (no. of users \> no. of files)**

> How many users are using the network doesn't affect the response time for the client.

This holds only up to a certain limit, **if the rate of incoming requests is \>\>\> rate at which they are served**, then its easy to see the bottleneck.

> How many users are using the network doesn't affect the response time for the client.

This is considering that the architecture within the cluster can efficiently serve the requests irrespective of the number of nodes, it sort of gives an upper bound of time taken to serve a request that is cached. **A request would arrive at one of the nodes. Assume a simple ring architecture, then in order to find which node has the copy of the requested file, the upper bound would be given by querying all nodes in the ring. As the number of nodes increase, this upper bound would increase, but it wouldn't effect the client as it is unaware of the internals of the DFS.**

---
Tags: distributed-systems, computer-networks
---


# Question
Title: Average number of comparison for 3 items
What is the average number of comparisons performed when sorting 3 items?

The question is based on the above picture.

# Answer
There are six possible orderings of three numbers. You can distinguish between six states with two 2-bit codes and four 3-bit codes; that is the lower bound if all orderings are equally likely. Average number of bits = 2 2/3rds.

Since you can’t have arbitrary tests but only comparisons between two items, you won’t be able to achieve the lower bound for larger numbers of items.
> 1 votes

# Answer
You haven't defined what you mean by *average*, so let me assume that the average is taken over all permutations of some fixed array consisting of three *distinct* numbers (the exact numbers don't matter, since the result will be the same).

Denote the number of comparisons performed on an array $A$ by $C(A)$. Then the average number of comparisons is $$ \frac{C(1,2,3) + C(1,3,2) + C(2,1,3) + C(2,3,1) + C(3,1,2) + C(3,2,1)}{6}. $$
> 1 votes

# Answer
> $$\frac{2\cdot 2+4\cdot 3}6.$$
> 1 votes

---
Tags: sorting, comparison
---


# Question
Title: Regular language superset with exactly exponential size
### Definitions

Define the *density* $\rho\_L$ of a language $L$ to be a function $\rho\_L : \mathbb{N} \rightarrow \mathbb{N}$ where $\rho\_L(n)$ is the number of words in $L$ of length $n$.

### Question

Let $L \subseteq \Sigma^\*$ be a regular language with density $\rho\_L(n) \leq b^n$ for some constant $b \in \mathbb{N}$ with $b \leq |\Sigma|$. Does there always exist another regular language $L' \subseteq \Sigma^\*$ such that $\rho\_{L'}(n) = b^n$ and $L \subseteq L'$?

### Easy Cases

* $b=0$: Trivial.
* $b=1$: In this case $L$ has at most 1 word of each length. We first make a new language $X$, which is $L$, but where every character is replaced with $x$. Then, $L'=(x^\* \setminus X) \cup L$ is a superset of $L$ with density function $\rho\_{L'}(n)=1^n=1$ as desired, and it is regular via closure properties of regular languages.
* $b=|\Sigma|$: Here $L' = \Sigma^\*$ always works.

So the first interesting case is $b=2, |\Sigma|=3$.

# Answer
The answer is "no". Let $L$ be an arbitrary regular language such that $\rho\_L(n) \leq b^n$ with $b \leq |\Sigma|$. Assume there exists such a regular language $L'$ with $L \subseteq L'$ and $\rho\_{L'}(n) = b^n$. Then, by closure properties of regular languages, the language $L' \setminus L$ is also regular, with density $\rho\_{L'\setminus L}(n) = b^n - \rho\_L(n)$. Then, as shown in "On the generating sequences of regular languages on $k$-symbols" by Beal and Perrin, 2003, this suffices to prove that $\rho\_L$ is the density of some other regular language $L''$ defined over a different alphabet of size $b$. But this implication is false: in the referenced paper, the authors give an example of a regular language $L$ satisfying $\rho\_L(n) \leq b^n$ such that there is no regular language with the same density defined over an alphabet of size $b$. So we have reached a contradiction, and the answer to the original question is "no".
> 2 votes

---
Tags: regular-languages
---


title: a halting turing machine

text:
# Question
Title: a halting turing machine
> Prove that there does not exist a universal Turing machine that takes a pair $\langle M, w\rangle$ as input, where M is a Turing machine and w is a string, and that always halts, accepts if $M$ accepts $w$, and rejects if $M$ reject w.

I think assuming the existence of such a machine H could allow one to decide the halting problem. Assume the existence of such a machine. Suppose $\langle M, w\rangle$ is given as input. Then let $M'$ be the machine resulting from swapping the accept and reject states of $M$. If $H$ accepts $\langle M,w\rangle$ and $\langle M', w\rangle$ or if $H$ rejects both inputs, then either $M$ accepts w in the first case or $M$ rejects w in the second case. However, it's possible that $H$ accepts $\langle M,w\rangle$ and rejects $\langle M', w\rangle$ or vice versa, in which case $M$ can either accept or reject w. I'm not sure how to deal with this issue.

# Answer
> 0 votes
Proof of concept referenced by Nathaniel tells that the idea for a contradiction resulting from assuming a decider $\text{halts}$ that decides the halting problem is to construct a Turing machine $g$ that "does the opposite of what $\text{halts}$ says $g$ should do, so $\text{halts}(g)$ can not return a truth value that is consistent with whether $g$ halts.

We can adapt that idea to the current situation.

For the sake of contradiction, assume there exists such a universal Turing machine $U$.

Construct Turing machine $F$, which on input $w$, checks if $w=\langle M\rangle$ for some Turing machine $M$.

* If not, $F$ accepts. (In fact, it is OK for $F$ to accept or loop here. It does not matter what is $F$'s behavior here.)
* Otherwise, simulates $U$ on $\langle M, \langle M\rangle\rangle$.
    + If the simulated $U$ accepts, $F$ rejects.
    + Otherwise, the simulated $U$ must reject since $U$ always halts. $F$ Accepts.

Now let us run $F$ on input $\langle F\rangle$. So, $F$ will simulate $U$ on $\langle F, \langle F\rangle\rangle$. There are two cases.

1. The simulated $U$ will accept and $F$ will reject.
2. The simulated $U$ will reject and $F$ will accept.

Let us check case 1, where $F$ will end up with rejecting $\langle F\rangle$. By the specification of $U$, the simulated $U$ should also reject, which means we are not in case 1.

Let us check case 2, where $F$ will end up with accepting $\langle F\rangle$. By the specification of $U$, the simulated $U$ should also accept, which means we are not in case 2.

Since neither case can happen, there must be no such Turing machine $F$. That means there is no such Turing machine $U$.

---
Tags: complexity-theory, turing-machines, undecidability, halting-problem
---


# Question
Title: Efficient algorithm for finding linear combination of piecewise functions
While porting an algorithm, I having a bit of a problem with finding an efficient algorithm for finding a linear combination of piecewise functions. The procedure is described in the Table 3 of the appendix of the SIRUS algorithm by Bénard et al. (https://proceedings.mlr.press/v130/benard21a.html).

The problem is defined as follows. Given the following rules

| rule number | if | then | else |
| --- | --- | --- | --- |
| 1 | MMAX \< 32000 | 61 | 408 |
| 2 | MMAX ≥ 32000 | 408 | 61 |
| 3 | MMIN \< 8000 | 62 | 386 |
| 4 | MMIN ≥ 8000 | 386 | 62 |
| 5 | CACH \< 64 | 56 | 334 |
| 6 | CACH ≥ 64 | 334 | 56 |
| 7 | MMAX ≥ 32000 & CACH ≥ 64 | 517 | 67 |
| 8 | CHMIN \< 8 | 50 | 312 |
| 9 | CHMIN ≥ 8 | 312 | 50 |
| 10 | MYCT \< 50 | 335 | 58 |
| 11 | MYCT ≥ 50 | 58 | 335 |
| 12 | MMAX ≥ 32000 & CACH \< 64 | 192 | 102 |
| 13 | MMAX \< 32000 & CHMIN ≥ 8 | 157 | 100 |
| 14\* | MMAX ≥ 32000 & CHMIN ≥ 12 | 554 | 73 |
| 15 | MMAX ≥ 32000 & CHMIN \< 12 | 252 | 96 |
| 16 | MMIN ≥ 8000 & CHMIN ≥ 12 | 586 | 76 |
| 17 | MMIN ≥ 8000 & CHMIN \< 12 | 236 | 94 |

Then, according to the authors of the paper, rule 12, 15 and 17 are linearly dependent on other rules. Specifically, for rule 12, there exist 3 real numbers, $\alpha\_1$, $\alpha\_5$, and $\alpha\_7$ such that for all $x \in \mathbb{R}^p$ (all datapoints; $p$ is the number of features in the dataset)

$$ g\_{12}(x) = \alpha\_1 g\_{1}(x) + \alpha\_5 g\_{5}(x) + \alpha\_7 g\_{7}(x) $$

where $g\_5(x)$ denotes the rule outcome of rule 5 for datapoint $x$. For example, if the datapoint $x$ satisfies `CACH < 64`, then the outcome is 56, and otherwise it is 334. That rule 15 and 17 are linearly dependent on other rules should follow from similar reasoning.

My question now is, what would be an efficient algorithm to find these linearly dependent rules? Further assumptions are that the number of rules is somewhere in between 1k to 100k and that the number of constraints is at most two, so `A` and `A & B` are possible but `A & B & C` is not.

Footnote by rule 14: There is a typo in the paper for rule 14 as I learned by the author of the paper via email. It should read `MMAX ≥ 32000` instead of `MMAX < 32000`. I've fixed it in the table here and verified that the table is now correct according to the algorithm described below.

# Answer
> 2 votes
Conceptually, I suggest an approach like this:

* For each rule $r$:

+ Check whether it is linearly dependent on the preceding rules. If it is, output the linear dependence and remove $r$ from the set of rules.

To help us do this, we can note that a rule whose condition is of the form `A && B` can only depend on rules that use some combination of `A`, `!A`, `B`, and/or `!B`, as well as certain other special combinations of rules indicated below.

First, find all sums of rules that are equivalent to a rule with a single clause. Every such sum must be a sum of two rules $g\_1,g\_2$, where $g\_1$ is "`A && B` then $c\_1$ else $c\_2$" and $g\_2$ is "`A && !B` then $c\_3$ else $c\_4$"; then the sum $(c\_4-c\_3) g\_1 + (c\_2-c\_1) g\_2$ will be equivalent to the derived rule "`A` then $c\_2 c\_4 - c\_1 c\_3$ else $2c\_2 c\_4 - c\_2 c\_3 - c\_1 c\_4$". Add these derived rules to the set of rules.

Second, find all sums of rules that are equivalent to a rule with no clauses. Every such sum must be a sum of two rules $g\_1,g\_2$ (possibly derived, possibly original), where $g\_1$ is "`A` then $c\_1$ else $c\_2$" and $g\_2$ is "`!A` then $c\_3$ else $c\_4$"; then the sum $(c\_3-c\_4) g\_1 + (c\_1-c\_2) g\_2$ is equivalent to the derived rule "`True` then $c\_1 c\_3 - c\_2 c\_4$". Add these derived rules to the set of rules. Actually, we only need one. (And assuming there is at least one, we only need one derived rule "`A` then .. else ..." per possible clause `A`.)

To check whether a rule $r$ is linearly dependent on the preceding rules, we only need to consider rules whose clauses are a subset of the clauses of $r$ and/or their negations. For instance, if $r$ is "`A && B` then ... else ...", we only need to consider rules (including both original ones that precede $r$, and derived rules) whose conditions are `A && B`, `A && !B`, `!A && B`, `!A && !B`, `A`, `!A`, `B`, `!B`, or `True`.

Now we need a way to tell whether $r$ is linearly dependent on those rules. We can do that with linear algebra. Let $x\_1,x\_2,x\_3,x\_4$ be four values for the variables, where $x\_1$ satisfies `A && B`, $x\_2$ satisfies `A && !B`, $x\_3$ satisfies `!A && B`, and $x\_4$ satisfies `!A && !B`. We can map each rule $g\_i$ to the 4-vector $v\_i=(g\_i(x\_1),g\_i(x\_2),g\_i(x\_3),g\_i(x\_4))$. Now rule $r$ is linearly dependent on those other rules iff its 4-vector is linearly dependent on the corresponding 4-vectors. That can in turn be tested using linear algebra, e.g., Gaussian elimination on a matrix whose rows are the 4-vectors for those other rules.

This should be very efficient, even for 100K rules.

---
Tags: algorithms, machine-learning, statistics
---


# Question
Title: Is IP a property of the device one uses or the router through which one connects to the internet?
Let's say I visit an IP Checker online, is the OP shown there my IP or the IP of my router? I can't seem to find a conclusive authoritative answer online.

# Answer
> 2 votes
It depends on how your network is configured.

Since you talk about a router, most domestic users have a public IPv4 assigned to their router and then a private subnetwork for all the home devices. The router is used as a gateway to the internet and it handles translating the private addresses to the public address through a mechanism called NAT. In this case you'd see the public IP assigned to your router.

The situation could be different for IPv6 addresses. For example your provider can assign a /64 IPv6 prefix to your router, which then advertises it to your network. Each device builds its own (public) IPv6 address by combining the prefix with a 64-bit device-specific suffix (for simplicity, think of it as the MAC address of the network interface card, although this is not always the case).

Keep in mind that these are just two examples. Only you can know how your network looks like.

---
Tags: ip
---


title: Combinatorics under constraints

text:
# Question
Title: Combinatorics under constraints
I have two sets of points in space with known positions:

$$A = \\{r\_1^{\alpha}, r\_2^{\alpha}, ..., r\_n^{\alpha}\\} \quad n \in \mathbb{N}, \quad r\_i^{\alpha} \in \mathbb{R^3}$$

$$B = \\{r\_1^{\beta}, r\_2^{\beta}, ..., r\_m^{\beta}\\} \quad m \in \mathbb{N}, \quad r\_i^{\beta} \in \mathbb{R^3}$$

$$m \< n$$

I want to pick $a$ points from $A$ and $b$ points from $B$ but I want to make sure that the distance between each points chosen is not lower than a given threshold $\lambda$.

If one want to knows the number of ways there are to pick $a$ points and $b$ points in both set simultaneously, this question can be answered by using basic combinatoric rules (Newton coefficients). But I am not sure how to mathematically translate the distance constraint.

I coded an algorithm that work ok for my specific problem, but I would like to know what kind of algorithm I could use to solve the general case of such problem?

# Answer
Unfortunately, if $\mathsf{P} \neq \mathsf{NP}$, there is no efficient algorithm that solves your problem.

An algorithm that is able to solve your problem could be used to solve (the decision version of) the maximum independent set problem on unit disk graphs, which is known to be $\mathsf{NP}$-hard. This holds even in the special case in which points are in $\mathbb{R}^2$, $m=0$, $\lambda=1$, and we only want to know whether the number of feasible choices is $0$ or more than $0$.

Indeed, to decide whether there exists an independent set of size $k$ you can consider the set $A$ containing the locations of the graph's vertices and choose $a=k$. If there is at least one way to pick $a$ points from $A$ such that their distance is at least $1$, there there is an independent set of size at least $k$ in the unit disk graph.
> 1 votes

---
Tags: trees, combinatorics
---


# Question
Title: Given the current knowledge about complexity class, what can we say?
I am a CS student. I am looking at some questions my professor made and I got stuck in this one.
"Which one of the following inclusions between complexity classes is coherent with the current knowledge? (even if not proved, yet)". The possible answers are:

* P $\subseteq$ EXP (Which I know it is true)
* NP $\subseteq$ EXP (Which I know it is also true)
* EXP $\subseteq$ P (Which is clearly false)
* EXP $\subseteq$ NP

Now, if I flag as correct answers only the two I know that are true, I obtain that my answer is partially correct. So in conclusion my question is: Given the current knowledge can we say that EXP $\subseteq$ NP or is this just a mistake of my professor?
Thank you for your answers!

# Answer
Notice that the question is not asking for inclusions that are known to be true, but instead just for those that **could conceivably** be true given the current knowledge. In other words you need to select both the relations that are already known to be true and the relations whose status is still unknown.

The inclusion $\mathsf{EXP} \subseteq \mathsf{NP}$ is not disproven since, from what we know so far, it could be the case that $\mathsf{EXP} = \mathsf{NP}$. Therefore the last option should also be marked.
> 4 votes

---
Tags: complexity-theory, time-complexity, np, complexity-classes
---


# Question
Title: Merge sort and quicksort recursion tree depth
**1)**
I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about 100 or 1000 elements? How do I determine recursion tree depth for them? Is there any pattern that I cannot see? What if someone would ask me for recursion tree depth for a string composed of one million elements?

**2)**
I need to determine the biggest and the smallest recursion tree depth for strings composed of 10, 100 and 1000 when using quicksort. So it's kind of similar but those could be any strings, so is there even constant number that defines the smallest and the biggest? How to count this?

**3)**
I need to provide a recursive dependency which value for the given $n$ is the number of recursion tree levels of recursive calls of merge sort for an $n$-element string.

# Answer
> 1 votes
1. There is a pattern, and it has to do with the fact that you are splitting the lists in half in each time. Keep in mind the runtime of mergesort is $O(n \cdot log(n))$, that should provide some hints as to where to go with this problem.
2. There isn't really a even constant unless you define the constant in terms of $n$. I wouldn't think about this problem in that way, instead I would consider the best and worst cases for quicksort, i.e what choice of pivot is the best / worst, and how does it affect the depth of the recursion tree?
3. This is very similar to the first problem, in fact, I believe if you figure out the first problem, then this one shouldn't be too hard to come up with. Once again, think about the fact that you are halving the size of the list each time. I'm not sure if you are familiar with recurrence relations, and if not that is something you will definitely want to take a look at.

Here is a good resources to look at:

The whole chapter will be a good read, but for your purposes, just the bits about mergesort and quicksort will suffice

http://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf

I have only given hints and general guidance because I think this is a good problem to think about and to test your understanding of general algorithm analysis, but if you need a stronger hint, feel free to comment.

# Answer
> 0 votes
**Hint:**

About MergeSort:

$$1000=500+500\\ 500 = 250+250\\ 250=125+125\\ 125=63+62\\ 63=32+31\\ 32=16+16\\ 16=8+8\\ 8=4+4\\ 4=2+2\\ 2=1+1$$

Do you understand the pattern ?

---
Tags: algorithms, recursion, quicksort, mergesort
---


# Question
Title: Myhill-Nerode equivalence under a function
Consider two finite languages, $L\_A$ and $L\_B$, potentially over different alphabets. Now since these languages are finite, there exist minimal acyclic deterministic finite-state automata to decide them. We are given that $L\_A$ is bigger than $L\_B$: $|L\_A| \> |L\_B|$.

We are given a function $f$ which maps elements of $L\_A$ to $L\_B$: $\ f{:}L\_A \rightarrow L\_B$. We also have the constraint that acceptance is preserved under $f$: $\ \ x \in L\_A$ iff $f(x) \in L\_B$, modeled below by formula $\eqref{eq1}$.

Here's the question: if two strings $u$ and $v$ map to the same Myhill-Nerode equivalence class in $B$ under $f$ \[modeled by formula $\eqref{eq2}$\], do they map to the same equivalence class in $A$ \[modeled by formula $\eqref{eq3}$\]? That is, if we are given formulas $\eqref{eq1}$ and $\eqref{eq2}$, can we conclude formula $\eqref{eq3}$?

$\forall x((x \in L\_A) \leftrightarrow (f(x) \in L\_B)) \tag{1} \label{eq1}$

$\forall z((f(uz) \in L\_B) \leftrightarrow (f(vz) \in L\_B)) \tag{2} \label{eq2}$

$\forall z((uz \in L\_A) \leftrightarrow (vz \in L\_A)) \tag{3} \label{eq3}$

Is there some existing result which subsumes what I'm trying to do here? It feels very similar to the closure property under homomorphisms. Or do we need to prove the result, for instance by two applications of formula $\eqref{eq1}$ to formula $\eqref{eq2}$ to yield theorem $\eqref{eq3}$?

# Answer
> 1 votes
Yes, (1) and (2) imply formula (3).

$\forall z$, $(uz \in L\_A) \leftrightarrow (f(uz)\in L\_B) \leftrightarrow (f(vz)\in L\_B) \leftrightarrow (vz\in L\_A)$.

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


# Question
Title: Question about epsilon and estimation Turing machines
i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple limit: $lim\_{n \rightarrow \infty} {3-\frac{7}{n}}$.

now i used $3 - \epsilon$ and i am trying to show that there can't be any $\epsilon\>0$ so that the estimation of the algorithm is $3-\epsilon$, because there exists a "bigger estimation" - and this is the part i am not sure about, what is the correct direction of the inequality? $3-\frac{7}{n} \> 3 - \epsilon$ or the opposite? i am trying to show that the estimation ration is close to 3.

i think that what i wrote is the correct way, but not sure. would appreciate knowing what is correct in this case. thanks.

# Answer
> 0 votes
A "bigger estimation" is expressed the inequation

$$3-\frac 7n\>3-\epsilon,$$

which is solved by

$$n\>\frac 7\epsilon.$$

# Answer
> -1 votes
Suppose there exists $k\>0$ such that $\lim\_{n\to\infty} \left(3-\frac7n\right)=3-k$.

By the definition of a limit, $$\lim\_{n\to\infty} f(n)=L\Leftrightarrow \forall\epsilon\>0,\exists N\>0,n\>N\implies |f(n)-L|\<\epsilon$$

Here, we need to check: $$\lim\_{n\to\infty} \left(3-\frac7n\right)=3-k\Leftrightarrow \forall\epsilon\>0,\exists N\>0,n\>N\implies \left|k-\frac7n\right|\<\epsilon$$

Now, disproving this just requires a suitable choice of $\epsilon$. Consider $\epsilon=\frac k2$. We have for all $n\>\frac{14}{k}$, $\left|k-\frac7n\right|\>\frac k2$. So, there does not exist any $N\>0$ satisfying the condition, and as a result, no such $k\>0$ can exist.

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