# Question
Title: Determining whether the output of an algorithm is constant
Suppose I have an algorithm $A$ that is known to halt before $f(n)$ steps for some function $f: \mathbb N \rightarrow \mathbb N$, where $n$ is the size of the input, and output is always either zero or one. Is it a decidable problem to determine whether $A$ always outputs zero?

# Answer
It's not decidable. Given any program $P$, you can write a program $Q$ running in time (say) $O(n^2)$, which on input $n$ simulates $n$ steps of $P$, and returns 1 if $P$ halted. Then $P$ doesn't halt if and only if $Q$ always outputs 0.

This shows that your problem is $\Pi\_1$-hard (since the halting problem is $\Sigma\_1$-hard). It is also clearly in $\Pi\_1$, and so it is $\Pi\_1$-complete. (For the definition of $\Pi\_1$, check out the arithmetical hierarchy on Wikipedia.)
> 2 votes

---
Tags: undecidability
---


# Question
Title: How is type safety handled differently between reference and value types?
I'm trying to understand how type safety is preserved for value types and for reference types, specifically in languages with managed memory (such as C#). I understand that reference types (i.e. classes) have data allocated onto a managed heap, with a reference to that data allocated on the stack. Is there metadata about the type of the data passed around with the pointer? Is there a new 'pointer type' created along with the class itself?

I've been looking at this SO question and this blog post but neither discuss typing itself as it relates to these topics.

# Answer
> 2 votes
There usually is metadata about the runtime class of an object contained within the object itself, regardless of what language you're working in. This metadata is essential in languages like C# that have automatic memory management. In order to clean up an object that is no longer referred to by any other objects, you need to clean up all of its members too, which means deciphering exactly what class it is.

Just how that metadata is stored is up to the individual language implementation. Some languages make classes themselves into objects, and the metadata will consist of a pointer to the class. For example, this approach is used in some Common Lisp implementations (for reasons that we don't need to get into).

Other languages are a little more subtle about it. For example, in many object-oriented languages, an object stores a reference to a *virtual function table* or vtable. The vtable is a struct consisting of pointers to all of the implementations of that class's methods; the language runtime is responsible for setting up all of the vtables. Every instance of a class will store a reference to the same copy of that class's vtable, so you can figure out what class an object belongs to by asking which vtable it points to. This is exactly how object-oriented programming was mimicked in plain old C (see this article) and how it works under the hood in C++.

These kinds of complications are necessary because of inheritance. If I have an object `x` and I know it's of class `A`, `x` could really be an instance of any subclass `B` of `A`, and the language runtime needs to ascertain what the real class is in order to do method dispatch or garbage collection properly. In C#, struct types don't have inheritance at all, unlike class types. So a struct might have no metadata -- if the type of `x` is `S` and `S` is a struct type, it can't possibly be anything else.

I hope this at least addresses your narrow question about metadata. As for the much broader issue of type safety, have a look at Pierce's Types and Programming Languages, especially the chapters on subtyping.

---
Tags: type-theory, typing
---


# Question
Title: The maximum number of nodes in a heap tree of degree d and depth k
The maximum number of nodes in a binary tree of depth k is defined by $2^{(k+1)}-1$, but the same rule doesn't appear to work for heap trees of different degrees.

Let's say I have the following tree of degree 3

```
   1
 / | \
2  3  4

```

Here the depth of the tree is 1. So according to the formula, it will be $3^{(1+1)}-1=8$. But we have 4 nodes here. I am really struggling to adapt the binary tree formula to trees of other degrees.

Any thoughts?

# Answer
> 1 votes
A complete $d$-ary tree of depth $k$ has $d^\ell$ on level $\ell$ (where $0 \leq \ell \leq k$), so its total number of nodes is $$ \sum\_{\ell=0}^k d^\ell = \frac{d^{k+1}-1}{d-1}. $$

---
Tags: trees, combinatorics, heaps
---


# Question
Title: What is a the fastest sorting algorithm for an array of integers?
I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are:

* Which is the fastest currently known sorting algorithm?
* Theoretically, is it possible that there are even faster ones? So, what's the least complexity for sorting?

# Answer
In general terms, there are the $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $O(n^2)$ but quite often $O(n\log n)$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $O(n\log n)$ algorithms, like merge-sort and heap-sort, which are also good general-purpose sorting algorithms; and the $O(n)$, or linear, sorting algorithms for lists of integers, such as radix, bucket and counting sorts, which may be suitable depending on the nature of the integers in your lists.

If the elements in your list are such that all you know about them is the total order relationship between them, then optimal sorting algorithms will have complexity $\Omega(n\log n)$. This is a fairly cool result and one for which you should be able to easily find details online. The linear sorting algorithms exploit further information about the structure of elements to be sorted, rather than just the total order relationship among elements.

Even more generally, optimality of a sorting algorithm depends intimately upon the assumptions you can make about the kind of lists you're going to be sorting (as well as the machine model on which the algorithm will run, which can make even otherwise poor sorting algorithms the best choice; consider bubble sort on machines with a tape for storage). The stronger your assumptions, the more corners your algorithm can cut. Under very weak assumptions about how efficiently you can determine "sortedness" of a list, the optimal worst-case complexity can even be $\Omega(n!)$.

This answer deals only with complexities. Actual running times of implementations of algorithms will depend on a large number of factors which are hard to account for in a single answer.
> 48 votes

# Answer
The answer, as is often the case for such questions, is "it depends". It depends upon things like (a) how large the integers are, (b) whether the input array contains integers in a random order or in a nearly-sorted order, (c) whether you need the sorting algorithm to be stable or not, as well as other factors, (d) whether the entire list of numbers fits in memory (in-memory sort vs external sort), and (e) the machine you run it on.

In practice, the sorting algorithm in your language's standard library will probably be pretty good (pretty close to optimal), if you need an in-memory sort. Therefore, in practice, just use whatever sort function is provided by the standard library, and measure running time. Only if you find that (i) sorting is a large fraction of the overall running time, and (ii) the running time is unacceptable, should you bother messing around with the sorting algorithm. If those two conditions *do* hold, then you can look at the specific aspects of your particular domain and experiment with other fast sorting algorithms.

But realistically, in practice, the sorting algorithm is rarely a major performance bottleneck.
> 18 votes

# Answer
Furthermore, answering your second question

> Theoretically, is it possible that there are even faster ones?
> So, what's the least complexity for sorting?

For general purpose sorting, the ***comparison-based sorting problem*** complexity is ***Ω(n log n)***. There are some algorithms that perform sorting in O(n), but they all rely on making assumptions about the input, and are not general purpose sorting algorithms.

Basically, complexity is given by the minimum number of comparisons needed for sorting the array (log n represents the maximum height of a binary decision tree built when comparing each element of the array).

You can find the formal proof for sorting complexity lower bound here:
> 12 votes

# Answer
The fastest integer sorting algorithm in terms of worst-case I have come across is the one by Andersson et al. It has a worst-case of $O(n\log\log n)$, which is of course faster than $O(n\log n)$.
> 3 votes

# Answer
For integer sorting, the best known result seems to be: $$O(n \sqrt{log{ log{n}}})$$ in expectation using a randomized algorithm (or $O(n \sqrt{log{ log{U}}})$ if given an upper bound $U$), via Han, Thorup.
> 3 votes

# Answer
I read through the other two answers at the time of writing this and I didn't think either one answered your question appropriately. Other answers considered extraneous ideas about random distributions and space complexity which are probably out of the scope for high school studies. So here is my take.

Given an array $A$ with $n$ integer elements, you need exactly $(n-1)$ comparisons between elements in order to check if $A$ is sorted (just start at the beginning of the array and check the next element against the last element). In fact, $(n-1)$ comparisons is the best case running time for any *sorting* algorithm. In other words, the running time lower boundary for any sorting algorithm is $\Omega(n)$. If you recall radix sort or bucket sort, you will notice that their running times are $O(n)$. Since all sorting algorithms are bound below by $\Omega(n)$, I would argue that both radix sort and bucket sort are the fastest algorithms for sorting an array of integers.

Additionally, if you are not familiar with what $\Omega(n)$ or $O(n)$: Both notations mean that the algorithm takes approximately $n$ operations to complete (could be $2n$ or $3n-5$, but not $1$ or $n^2$ operations).
> 1 votes

# Answer
If you only allow making decisions by means of comparison of the keys, it is well-known that at least $\log(n!)$ comparisons are required in the worst case, to identify the comparison at hand among all the possible ones. This is an unbreakable bound.

If you allow other operations than comparisons, the trivial bound $\Omega(n)$ holds (and can be reached in special cases), as you have to read all the keys. This is unbeatable.
> 0 votes

# Answer
As you don't mention any restrictions on hardware and given you're looking for "the fastest", I would say you should pick one of the parallel sorting algorithm based on available hardware and the kind of input you have.

In theory e.g. `quick_sort` is `O(n log n)`. With `p` processors, ideally this should come down to `O(n/p log n)` if we run it in parallel.

To quote Wikipedia: Time complexity of...

> Optimal parallel sorting is O(log n)

In practice, for massive input sizes it would be impossible to achieve `O(log n)` due to scalability issues.

Here is the pseudo code for Parallel merge sort. Implementation of `merge()` can be same as in normal merge sort:

```
// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid = ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

```

Also see:
> 0 votes

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


# Question
Title: How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$
Following is a theorem from Sanjeev Arora and Boaz Barak I am unable to prove :

> If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p\_2$.

The previous similar theorem was

> If $\textsf{NP} \subseteq \textsf{P/poly}$ then $\textsf{PH}=\Sigma\_2^p$.

The second theorem was easy to prove as $\textsf{NP}=\Sigma\_1^p$. But $\textsf{EXP}$ does not have such characteristic. How do I prove the first theorem. Any hints?

# Answer
> 6 votes
The more classical statement is that if $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \textsf{MA}$, due to Babai, Fortnow and Lund. Impagliazzo, Kabanets and Wigderson showed that $\textsf{NEXP} \subseteq \textsf{P/poly}$ iff $\textsf{NEXP} = \textsf{MA}$. See lecture notes of Bogdanov for proof sketches.

# Answer
> 5 votes
There is a more 'elementary' proof of the problem that doesn't involve the polynomial-encoding/self-correction ideas of BFL. The result appears in the original Karp-Lipton paper and is credited to Meyer. The way I think of it is like this:

Step 1: Show that EXP in P/poly implies EXP = PSPACE. Hints: Show that if M is an EXP-machine, the entries of the computation tableau of M(x) are computable from x in EXP. Conclude that they're computable in P/poly. Now in PSPACE, try all circuits, and check that all entries of the tableau are locally correct.

Step 2: Show that PSPACE in P/poly implies PSPACE = Sigma\_2. Hints: Similarly, the tableau-contents-function of a PSPACE machine is in PSPACE, hence in P/poly. Now in Sigma\_2, you can nondeterministically guess a circuit supposedly computing the tableau, and then conondeterministically verify its correctness.

Step 3: Combine Steps 2 and 3 together.

---
Tags: complexity-theory, nondeterminism
---


# Question
Title: Given a set of points, find all collinear subsets
### General problem

* Given a space $S$ which is $N$-dimensional, bounded, and quantized
* Given a set $P$ of unique points
* Find the set of collinear subsets of $P$, each containing at least 3 points
* One point can exist in multiple subsets

### Specific problem

I am creating a 4D, 5 by 5 by 5 by 5 tic tac toe game. Each dimension is bounded by $\left(0,4\right)$ and quantized by $1$. I have a set of points within that space. Each point is associated with a player (the number of players is not bounded), so that could be treated as an additional bounded, quantized dimension.

I need to find any and all combinations of 5 points (played by the same player) that are collinear.

### Question

What is an efficient way to do this?

# Answer
> 1 votes
Here is a simple algorithm. For each way to choose 2 points from $P$, find the line that goes through those two points and then find all other points from $P$ that are on the line. If this yields at least 3 points, output it. Continue until you've iterated over all possible ways to choose 2 different points rom $P$.

The running time will be at most cubic. In particular, suppose there are $m$ points in the set $P$. Then there are ${m \choose 2} = m(m-1)/2$ ways to choose two different points from $P$. Thus, you'll do $\Theta(m^2)$ iterations. Then you can find all other points on the line in at most $O(m)$ time, so the total running time is $O(m^3)$.

There are probably more efficient algorithms. However, this might probably suffice for your needs. Specifically, in your example, you'll have $m \le 5^4$. Also, each iteration can be done faster than $O(m)$ time: given two points $p,q \in P$, you only have to check at most 3 other cells in the tic-tac-toe space. So, in your situation, the running time is $\Theta(m^2)$, and $m^2 \approx 2^{18.6}$, so this should be pretty fast.

---
Tags: algorithms
---


title: Follow set confusion about inclusion

text:
# Question
Title: Follow set confusion about inclusion
The book I am learning about compilers from states that $M \to \alpha N \beta$ will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable.

This is a bit confusing because there can be other productions such as $M\to \gamma K \theta $. Logically, then, the set of symbols which can follow $M$ can also be the set of set of symbols that can follow $k$ if $\theta$ is nullable and can be different from $\mathrm{FOLLOW}(N)$.

As such both $\mathrm{FOLLOW}(N)$ and $\mathrm{FOLLOW}(K)$ should be included in $\mathrm{FOLLOW}(M)$. Shouldn't it be like this? What might be the reasons behind the statement in the book?

# Answer
> 1 votes
If the grammar includes $M \to \alpha N \beta$ and $\beta$ is nullable then anything which could follow $M$ could also follow $N$. In other words,

$FOLLOW(M) \subset FOLLOW(N)$

So we need to add everything in $FOLLOW(M)$ to $FOLLOW(N)$. It does not oblige us to alter $M$'s follow set.

If there is also $M \to \gamma K \theta$ with $\theta$ nullable, then similarly we have

$FOLLOW(M) \subset FOLLOW(K)$

so we also have to add everything in $FOLLOW(M)$ to $FOLLOW(K)$. That implies that the FOLLOW sets for $N$ and $K$ are not disjoint, but it really says nothing interesting about $M$'s FOLLOW set.

---
Tags: compilers, parsers
---


# Question
Title: Does MST exclude the edge belongs to the cycle of the graph?
For any simple, connected, undirected graph $G(V,E,w)$ with each carrying distinct positive edge weights, is it true that MST will contain all the edges which do not lie in any cycle of $G$?

I think MST can take any edge of irrespective of the fact whether it is an edge of cycle (like I simply use Kruskal's), Also I am unable to see Why the above statement should true. Can anyone tell how the statement is true?

# Answer
> 3 votes
I think you need to be more precise in your reading of the statement, though it could be better phrased. A different version is "if $e$ is an edge of $G$ and it is not in any cycle in $G$, it must be in any MST of $G$". This *doesn't* say that edges that are in cycles can't be in the MST, it just says that any edge that isn't in a cycle must be.

To see why this is true, imagine an edge that is not part of a cycle; it has two endpoints, both of which must be part of the MST (otherwise it wouldn't be spanning). So how do we get to those endpoints? If we don't use that edge, we can't reach one of the endpoints (if we could reach both, then the edge would be part of a cycle), thus that edge must be in the MST.

# Answer
> 1 votes
It is simply not true that "*MST can take any edge of irrespective of the fact whether it is an edge of cycle (like I simply use Kruskal's)*". Think of *Prim's Algorithm*. Every iteration divides the graph into two sets - $Set A$ always forms a single tree. Each step adds to $tree A$ a light edge that connects A to an isolated vertex in $Set B$ (i.e., set of vertices on which no edge of A is incident).

Now imagine a situation where a vertex of $Set B$ is reachable through only one edge i.e., it is not a part of a cycle. To include it in a spanning tree, that one edge becomes necessary. Hence, every edge not belonging to a cycle should be added, else the vertices incident on the other end (belonging to B) of that edge shall never be included into the spanning tree.

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Is there a concept of information that distinguishes between "computed" and "non-computed" information?
I always tend to think of information as follows: If we have an information set $I$, and it is possible to derive from $I$ another information set $X$, then $I$ really contained $X$ all along, and we haven't actually discovered "new information". We've merely found out something new about the information we already had.

But sometimes, deriving $X$ from $I$ is computationally very complex, so that it may take 1000 years to do it. In this case, any reasonable person in every day life, would say that we don't have the information $X$, even though we have $I$ and $X$ can theoretically be computed from $I$.

**My question is, is there a concept that captures this notion of not having a piece of information merely because it is hard to compute**? i.e. it could be something like: $I\_{405}^\*$ is the information set containing all information that can be generated by at most 405 computational steps from $I$. This is a somewhat vague definition, but I'm wondering if there is something more formal

# Answer
The distinction between information theoretic and computational knowledge is an issue which is fairly common in cryptography.

Consider for example the one-time-pad encryption, that given a message $m\in\\{0,1\\}^l$, encrypts it using a secret key $k$ (chosen uniformly at random) by $m\oplus k$. Clearly, one learns no information from seeing the encryption of one message (it is a uniformly distributed string), so you could say that you have information theoretic security, which should make you very happy. However, if you insist on such a strict notion of security, it turns out you cant encrypt messages who are longer than the key, and if you want to do that, you should settle for a weaker notion, which is security against bounded resources adversaries (see semantic security).

One example which seems to fit your question well is one way permutations. A function $f:\\{0,1\\}^\*\rightarrow \\{0,1\\}^\*$ is called a one-way permutation if for every $n\in\mathbb{N}$, $f|\_{\\{0,1\\}^n}$ is a permutation of $\\{0,1\\}^n$, and for some bounded resources adversaries, almost no knowledge of $x$ is exposed from $f(x)$. Since $f$ is a permutation, $f(x)$ completely determines $x$, but it is extremely hard to recover.

That said, I will strengthen Raphel's comment and say that there isn't a general definition for information (or what you call computational information), this is an issue which strongly depends on the context.
> 2 votes

---
Tags: complexity-theory, terminology
---


# Question
Title: Proving that a Turing machine decides a language in NP
Suppose a deterministic Turing machine T decides language L and L is in NP. Then must it be provable in ZF that T decides L?

# Answer
In general, ZF does not prove that $T$ decides $L$, unless ZF is inconsistent.

Take e.g. $L$ to be the language of words having even length (which is in P, hence in NP).

Consider the TM $T$ which on input $w$, crafts the first $|w|$ proofs in ZF. If any such proof proves a contradiction, accept. Otherwise, accept if and only if $|w|$ is even.

We note that $T$ decides $L$ if and only if ZF is consistent. So, if ZF can prove that $T$ decides $L$, it is proving its own consistency, hence by Godel's second incompleteness theorem ZF is inconsistent.
> 3 votes

---
Tags: complexity-theory, logic
---


# Question
Title: Computability of an expression of a function rather than a function itself?
Let's assume we're talking about real functions purely for clarity purposes, but my question is more general.

We say that a function $f$ is computable, if for a given $x$, a turing machine can output $y$ such that $f(x)=y$.

However, I'm wondering whether there is some concept of "computability for the expresssion of a function". For example, let's say I have some implicitly defined function $f$, and let's say that this function is equivalent to $g(x)=\sin(x)$, but we don't know this yet. **Then what we would want is to compute the fact that $f(x)=\sin (x)$**, but we don't necessarily need to compute that $f(0.45)=0.434965534...$

**Is there a concept that rigorously captures this idea of the *expression* of a function being computable, rather than the function itself being computable?** In other words, it may be that a function is incomputible, but that there is at least a finite number of computations we can do to derive that it has a certain closed form expression.

# Answer
> 1 votes
I assume that a closed form of a function is a finite expression involving function symbols from some fixed natural finite list together with some real\[1\] parameters. Since we know what it means to compute a real number, and since we know what it means to compute finite tuples of stuff we know how to compute with, we obtain in a direct way a notion of what it means to compute a closed form of a function.

Then in particular we can ask questions such as "given these parameters for the differential equation, can we compute a closed form of the solution".

Note however that all usual continuous functions are computable. Given a closed form of a function $f$ and some input $x \in \mathbb{R}$, we can compute $f(x)$. However, the problem "given a continuous function that has a closed form, find that closed form" is **not** computable.

So asking for closed forms is asking for more, not asking for less.

\[1\] If you don't like computing with real numbers, go for parameters from the algebraic closure of $\mathbb{Q}\[\pi,e\]$ instead.

---
Tags: computability
---


# Question
Title: Question about the difference between radix trees and patricia trees
I've already done some research on this topic, but it still isn't quite clear to me.

According to this post patricia trees are radix trees with $r = 2$. Every patricia tree I've seen so far is used to store alphanumeric symbols. Assuming that there are used 8 bits to represent one symbol, $r$ is the number of bits compared and the radix of a radix tree is $2^r$ shouldn't the radix of a patricia tree be $2^8 = 256$?

If you have a look at a PATRICIA Tree with the following inputs (in this order):

* smile
* smiled
* smiles

According to the linked post a Patricia tree should then look like this:

```

smile - - - smiled - - - smiles

```

But intuitively (by the alphanumeric representation) it should look like this

```
       d
      /
smile
      \
       s

```

# Answer
Quoting Wikipedia:

> PATRICIA trees are radix trees with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch.

According to Wikipedia, *Patricia* is just a "brand name" coined by Donald R. Morrison, standing for *Practical Algorithm To Retrieve Information Coded In Alphanumeric*.

Patricia trees thus accept their input in the form of binary strings. If the input is a word, then it is first encoded in binary.

As for the smile/smiled/smiles example, it is explained in the linked post – each of these words is encoded as a binary string, and this is what the Patricia tree sees. It is completely unaware of the semantic interpretation of the bitstring as an alphanumeric word.
> 1 votes

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


# Question
Title: Maximize the number of edges in subgraph
We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph made with vertex set $U$.

# Answer
> 3 votes
Your problem is known as *densest subgraph*. According to Wikipedia, there is a polynomial time algorithm based on flow networks, due to Goldberg. See Goldberg's technical report Finding a maximum density subgraph.

---
Tags: algorithms, graphs, linear-programming
---


title: hardware interrupts and context switch

text:
# Question
Title: hardware interrupts and context switch
I have recently studied about interrupts and context switch i have read that the hardware interrupts cause the interrupt service subroutine to execute for this i read mixed articles saying that there no need for a context switch to kernel mode and some say we need a context switch to kernel mode from user mode do we need a switch to kernel mode in case of hardware interrupts

# Answer
> 5 votes
I think the answer partially intersects that of Do system calls always means a context switch?: it depends on the exact definition of "context switch". On most CPUs, an interrupt is not serviced in user mode but rather in a more privileged mode (IRQ mode on ARM, on x86 the IDT can specify the ring level). This is necessary because simply clearing the interrupt or determining its source requires accessing hardware registers (which by definition user mode cannot in general). That being said, the OS does not need to run the entire ISR in a privilege mode. Typically in a microkernel, an IRQ will be added to a queue and processed by a (user space) driver.

So an interrupt implies a privilege switch, which implies some amount of context switching (saving registers for example) but not necessarily a full process switch, depending on the architecture and the kernel.

---
Tags: operating-systems
---


title: Existence of one and two state PDAs

text:
# Question
Title: Existence of one and two state PDAs
I came across following fact in Automata book by Hopcroft, Ullman:

> **Theorem 1:** For every PDA accepting by empty stack (PDAeS), there is an equivalent one state PDA accepting by empty stack.

I was wondering how this applies to:

1. PDA accepting by final state (PDAfS)
2. Deterministic PDA accepting by empty stack (DPDAeS)
3. Deterministic PDA accepting by final state (DPDAfS)

My understanding is, it applies equally to PDAfS, since I read in the book that both PDAfS and PDAeS are of equal power. Am I right? Also what about DPDAs?

Also I came across this post, which states:

> **Theorem 2:** All PDAs are equivalent to two state PDAs.

I want to know what all variants (PDAfS, PDAeS, DPDAeS, DPDAfS) it refers to by PDA? Reading the explanation given in the problem itself, my guess is that it is possible with PDAeS and DPDeS. Am I right?

**Added later**

I came across two more theorems in the book:

> **Theorem 3:** For every regular language L, there is DPDAfS, such that L = L(DPDAfS) **Theorem 4:** For every regular language L, there is one state PDAeS, such that L = L(PDAeS)

So in all above highlighted theorems (total four, two originally stated and two added later), I want to know to what they apply? PDAeS, PDAfS, DPDAeS, DPDAfS.

So let me enumerate problems explicitly:

(From theorem 1)

1. For every PDA, is there equivalent one state PDAfS?
2. For every DPDA, is there equivalent one state DPDAeS?
3. For every DPDA, is there equivalent one state DPDAfS?

(From theorem 2)

4. Is all PDAs are equivalent to some two state PDAeS?
5. Is all PDAs are equivalent to some two state PDAfS?

(From theorem 3)

6. ~~For every regular language L, is there DPDAeS, such that L = L(DPDAeS)?~~ (details in Update 1)

(From theorem 4)

7. For every regular language L, is there one state PDAfS, such that L = L(PDAfS)?

**Update 1**

Realized that the answer to 6th question is no. DPDAeS are not even capable of generating all regular languages. This leads to the possible next question:

8. Cant any DPDAeS generate any regular language?

**PS:**

* Sorry, if you didnt like how I am referring to PDAs with fS and eS suffixes (which mean "acceptance by final state" and "acceptance by empty state" respectively). But I find it very convenient.
* Sorry for asking absolutely too much on one post. But all those problems form a part of one big problem: how FAs, PDAeS, PDAfS, DPDAeS, DPDAfS and their variants (one state and two state) generate each other.

# Answer
> 5 votes
For final state acceptance one needs two states in general. The reason is simply that one needs to distinguish accepted and not-accepted strings. That is why single state PDAf are not a very useful concept. But if you have one, the prefix of every accepted string will itself be also accepted. These languages are prefix-closed.

If a deterministic automaton with empty stack acceptance indeed accepts a string, there is no longer string that can be accepted. The reason is that with empty stack in the classical model of Hopcroft&Ullman the automaton blocks, no steps are possible. Here determinism is important because nondeterministic automata just may have alternative computations on the same string. These languages are prefix-free.

Let me summarize.

The answer to question 1, question 3 and question 7 \[single state with final state acceptance\] is "no" as not every (D)PDA language is prefix closed, for example regular $(aa)^\*$, or in fact finite $\\{a,aa\\}$.

The answer to question 2 \[single state, deterministic, empty stack\] is "no", as not every DPDA language is prefix-free, examples as before.

The answer to question 4 and question 5 \[two states\] are "yes", see Yuval's answer. These results are 'classic'. Perhaps you want to know the deterministic version of these results?

For question 8 observe that DPDAe's can accept 'any' regular language when the end of the string is marked by a special symbol. This makes the language immediately prefix-free.

# Answer
> 4 votes
Every PDA is equivalent to a PDAeS with a *single* state. This is because every context-free grammar can be simulated by such a PDAeS (nice exercise). This PDAeS, in turn, is equivalent to a PDAfS with two states.

I'm not sure whether the same reduction works for DPDAs – perhaps.

---
Tags: automata, finite-automata, compilers, pushdown-automata
---


title: Finding subgraph problem

text:
# Question
Title: Finding subgraph problem
Is the following a familiar problem ? Given a graph $G = (V, E)$ and a capacity function $c:V \to \mathbb{N}$ find a spanning subgraph $H$ of $G$ such that $1 \leq deg\_H(v) \leq c(v)$ for every vertex $v \in V$.

I would like to know if this is an NP-hard problem so any pointer to a similar problem (NP-hard or not) will be very appreciated as well.

Thank you,

GIlad

# Answer
(This is edited after the conversation in the Comments below) This is similar to *degree-constrained subgraph problems*. That is one direction to search in.

You can drop your 'spanning' requirement since you enforce a minimum degree of 1, which means every vertex has to be included in order to satisfy your degree constraints. It feels like it should be polytime with a max flow solution.
> 2 votes

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


# Question
Title: Decide whether the Language is regular {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0}
how would you prove if this language is regular/irregular?

question given:

Decide for each of the following languages whether it is regular. If so, design a DFA/NFA for recognizing it, and if not, give a formal proof(based on the Pumping Lemma).

i) {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0 are three integers};

I have constructed a DFA which I believe proves the language is regular however, using the pumping lemma i.e. where the pumping length (p) = 4: aaaabbbbcccc, and say this is split into xyz where x = aa, y = aa and z = bbbbcccc then x(y^i)z where i = 2 -\> aaaaaabbbbcccc

satisfy the conditions of the pumping lemma:

1. for each i \>= 0, x(y^i)z ∈ A
2. |y| \> 0
3. |xy| \<= p

so:

1. when i = 2, x = aa, y = aa, z = bbbbcccc then A = aa aaaa bbbbcccc is satisfied
2. |y| = aa so |y| = 2 which satisfies the condition
3. x = aa + y = aa so |xy| = 4 which satisfies the condition

meaning the language is regular BUT if:

x = aaa, y = ab, z = bbbcccc

1. when i = 2, x = aaa, y = ab, z = bbbccc then A = aaa abab bbbccc which doesn't satisfy the condition as they're not in order (a then b then c) anymore.
2. |y| = ab so |y| = 2 which satisfies the condition.
3. x = aaa + y = ab so |xy| = 5 which doesn't satisfy the condition.

I could be using the Pumping Lemma completely wrong I'm confused as initially (and from my DFA) I assumed this language is regular as the number of a's doesn't depend on the number of b's and the number of c's doesn't depend on the number of b's or a's etc.

basically: I think I have proven that the language is regular with a DFA but irregular with the pumping lemma and don't know how to give a definitive answer.

# Answer
> 2 votes
You're using the lemma completely wrong. It states that

If language $L$ is regular, then there is $p$ such that for every string $s$ in $L$ where $|s|\>p$ there is a decomposition $xyz$ with $|y|\>0$ and $|xy|\le p$ for which $xy^i z \in L$ for all $i \ge 0$.

When you want to use it to prove language not to be regualr, you use contrapositive implication (making $\neg B \implies \neg A$ from $A \implies B$ ).

You get if for every $p$ there is a string $s$ with $|s| \> p$ where for every decomposition $xyz$ with $|y|\>0$ and $|xy| \le p$ there is a $i \ge 0$ such that $xy^i z \notin L$ then $L$ is not regular.

Now for your actual question, what you seemed to be doing is trying to prove the first implication, which would tell you nothing. It's important to note that the lemma is **implication** not **equivalence**, thus proving that a language has the pumping property does not mean it is regular. Conversely you cannot prove such languages to not be regular by pumping lemma.

If you wanted to prove that the language is not regular, you would need to make a string $s$ longer than $p$ for every $p$ from the language $L$ (for example by taking string $a^p b$ or $a^{p+1}$ or similar strings) and then you would have to make sure that there is an $i$ for all of the decompositions $xyz$ such that $xy^i z \notin L$. You can find many examples both on this site and on the Internet, but it is impossible here because the language is in fact regular.

To take your example more closely, if you wanted to prove the language to not be regular with the pumping lemma, your first mistake was chosing $p$, because you need to prove the statement for every $p$.

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


# Question
Title: Is there a set of NP-hard problems that are most commonly used for proving NP-hardness?
Are there any NP-hard problems that are considered kind of the standard for reductions? There's so many but it feels like some come up more often than others (for example Vertex Cover, Independent Set, 3-SAT, etc.). I'm sure people just pick whatever is most convenient, but where's the boundary between "more useful" and "too obscure" when choosing a problem to reduce from?

# Answer
> 2 votes
Most textbooks will have a set of 'core' NP-Complete problems from which all their examples and exercises would reduce from, which are probably the ones you list (3SAT, Vertex Cover, Independent Set, Clique, k-Coloring, Set Cover, Dominating Set, Hitting Set, Subset Sum, Knapsack.)

A bigger set of 'standard' problems would be Garey & Johnson's book. Beyond that, people look at hard restrictions of the standard problems (i.e. k-coloring for k=3, Exact Cover version of set cover, not-all-equal 3SAT, etc).

Beyond that, it gets fairly domain specific.

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


# Question
Title: When does strong duality fail in linear programming?
When does strong duality fail in linear programming? I have considered the case when both primal and dual solutions are infeasible, but then there are no optimal solutions at all.

# Answer
The strong duality theorem of linear programming states that (quoted from "Algorithms" by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, 2006) "***If*** a linear program has a bounded optimum, ***then*** so does its dual, and the two optimum values coincide." Hence, it never fails.
> 3 votes

# Answer
There is a very good exercise - 5.23 - in Boyd's book on Convex Optimization (the solution might also help).

They prove that strong duality holds for the following LP and its dual **provided at least one of the problems is feasible**. In other words, the only possible exception to strong duality occurs when $p^\*= \infty$ and $d^\* = − \infty$.

LP:

$\min c^Tx$

st $Ax=b$

DUAL:

$max −b^Tz$

st $ A^T z + c = 0$ and $ z \succeq0$
> 1 votes

---
Tags: linear-programming
---


# Question
Title: Do we know if there is an oracle $B$ so that $P^B \neq NP^B$ but $coNP^B=NP^B$?
We know there is $B$ with $P^B \neq NP^B$, and we know there is $C$ with $coNP^C=NP^C$, what happens if we want to mix?

# Answer
> 2 votes
Any oracle relative to which $\mathsf{NP=EXP}$ would do the trick. You can find a construction of such an oracle in Heller's paper. Clearly if $\mathsf{NP=EXP}$ then $\mathsf{NP=coNP=EXP}$ but $\mathsf{P\neq NP}$ by the time hierarchy theorem.

I don't know whether there are known oracle constructions who collapse the hierarchy to $\Sigma\_i$ and not to $\Sigma\_{i-1}$, but it's an interesting question (I would guess the answer is in the affirmative).

---
Tags: complexity-theory
---


# Question
Title: Intersection between regular language and context-free language
In general, context-free algorithm are not closed under intersection but the intersection between a regular language and a CF language is known to be context-free.

My question is: does exist an algorithm to compute intersection in these special cases?

Thanks.

# Answer
> 3 votes
Yes, there does.

The key is to represent your CFL as a pushdown automaton, and the regular language as a DFA. Then compute the product automaton of the CFL's states and the DFA's states, keeping the stack operations from the CFL.

In essence, what you're doing is running your pushdown machine, and keeping track of what state you would be in in the DFA if you were running it in parallel. Then, when you reach the end, you only accept if both machines would accept.

---
Tags: regular-languages, context-free
---


# Question
Title: Find maximum non contiguous subarray that respect a specific rule
Given these two arrays:

```
[5, 3, 4, 1, 2]

[1, 3, 2, 4, 5]

```

Find the maximum subsequence in both arrays that the index of the elements are in a crescent order:

Example: `[3, 4]` it's an answer because the indexes are in a crescent way in both arrays. (same as `[1, 2]`). Therefore, the subsequence the answer `[3, 4, 1]` is wrong, because the indexes are the crescent in the first array, but not on the second one.

The output of the program should be the length of the max non-contiguous subarray.

This is the code I wrote for solving this, but it only takes the first subarray, and I'm having difficulty to generate the other possibilities

```
vector<pair<int, double>> esq;
vector<pair<int, double>> dir;
// N is the size of esq and dir
// pair<int, double> where int is the key (show in the example array) and double is the value, used for sort previously.
int cont = 1;
for (int i = 0; i < N - 1; i++)
{
    int cont_aux = 1;
    pair<int, double> pivot = esq[i];
    auto it_dir = find_if(dir.begin(), dir.end(), [&pivot](const pair<int, double> &p) { return p.first == pivot.first; });
    int last_index = it_dir - dir.begin();

    for (int j = 0; j < N; j++)
    {
        pair<int, double> actual = esq[j];
        auto it = find_if(dir.begin(), dir.end(), [&actual](const pair<int, double> &p) { return p.first == actual.first; });
        int pos = it - dir.begin();

        if (pos >= last_index) {
            last_index = pos;
            cont_aux++;
        }
    }

    cont = max(cont, cont_aux);
}

cout << cont << endl;

```

# Answer
> 1 votes
I will move my comment to an answer, since you seemed to indicate that the comment solved your problem.

Your problem is normally called the Longest Common Subsequence problem. It does not require the common subsequence to be contiguous. It can be solved efficiently with dynamic programming, and it is an early example of dynamic programming in many textbooks.

There are many implementations of LCS available online. The wiki article on LCS I linked to in the above comment is a good place to start.

---
Tags: arrays, maximum-subarray, c++
---


# Question
Title: Problems for which there is no algorithm with smallest time complexity
Are there any problems where there is no smallest time complexity, so there is a big-$\mathcal{O}$ but no big-$\Theta$?

More formally, I am looking for any problem $p$ where

* for any algorithm that solves $p$ in time $f(n)$
* there provably exists another algorithm that solves $p$ in time $g(n)$
* where $g(n) = o(f(n))$.

An example would be a problem for which there exist algorithms of complexity $\mathcal{O}(n^k)$ for all $k \> 0$, but for which there is no algorithm of lower complexity, like $\mathcal{O}(1)$ or $\mathcal{O}(\log n)$.

# Answer
> 3 votes
The existence of such problems follows from the Blum speedup theorem. The theorem shows, for example, that there exists a problem such that for any algorithm solving it in time $T(n)$, there is another one solving it in time at most $\log T(n)$.

# Answer
> 1 votes
You might be interested in something similar to what you are describing (in terms of a hierarchy of algorithms of different runtimes that get closer and closer to some limiting runtime). *Polynomial time approximation schemes* (PTAS) have runtimes stated like $O(2^{1/\epsilon}n^2)$ or $O(n^{1/\epsilon})$ for any epsilon, and you are sort of free to pick your epsilon as a trade-off between the runtime or the accuracy to an approximate solution.

See http://www.win.tue.nl/~mdberg/Onderwijs/AdvAlg\_Material/Course%20Notes/lecture7.pdf for an intro to PTAS and an example showing a $O(n^3/\epsilon)$ PTAS for a solution to Knapsack which is at least $(1-\epsilon)\times OPT$

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


# Question
Title: strong reduction of $\lambda$-terms, useful?
As we know many programming languages and systems don't implement the strong reduction of $\lambda$-terms, instead they do weak reduction (no reduction under abstraction).

I recently experimented several tests on $\lambda$-terms. I applied strong reduction and call by value reduction on them.

1. strong reduction took longer time even the size of the term is moderate.
2. call by value reduction is very fast.

I believe if we ignore inefficiency, strong reduction is more useful than weak one. These are what I felt from my experiments. That makes me think about some questions. here I would like to share them with you.

1. programming languages or other systems do not implement the strong reduction because it is inefficient (takes more time)?
2. programming languages or other systems don not implement the strong reduction because it is difficult to do?
3. which one is the reason, or something also?

# Answer
> 2 votes
There are several possible answers to your question:

1) Strong reduction is not implemented because it is not that useful: why take the trouble to reduce a term with un-instantiated variables when you'll have to go back in later to do the reduction when the variables get values anyway? And if the variables never get instantiated, then you've wasted your time entirely! More generally, it's easier to compute with concrete values than symbolic ones.

2) Strong reduction *is* implemented, because it *is* useful. It's just that this is usually done **at compile time**: inlining and constant propagation is just that, a way to do strong reduction.

---
Tags: lambda-calculus, functional-programming
---


# Question
Title: Existence of Real-Time Multiprocessor Schedule
Does an algorithm exist to check for the existence of a Real-Time Multiprocessor Schedule for aperiodic hard tasks(all of which have the same Release time)?

Assumptions:

* The processors are Uniform parallel machines
* Job preemption is permitted
* Job migration is permitted
* Job parallelism is forbidden

EDIT: Let there be $n$ jobs $J = \\{j\_1, j\_2,\text{...}, j\_n\\}$ and $m$ no of processors $P = \\{p\_1, p\_2,\text{...}, p\_m\\}$. Each job $j\_i$ has a task time $t\_i$(amount of work it would take to complete it) and due time $d\_i$. Each processor has a constant speed $s\_i$(amount of work it does per unit time). Each task must be completed before its due time.

I am interested to know about an algorithm with can check feasibility of a schedule in polynomial time.

# Answer
> 2 votes
> Y. Cho and S. Sahni, Scheduling Independent tasks with due times on a uniform Processor System, Jr. of the ACM, 1980

Presents an algorithm to preemptively schedule **n** tasks(with due dates) on **m** uniform processors whenever a solution exists in $O(n\log{n} + mn)$ time.

Which is a stronger problem than I wanted to solve but still gives a polynomial algorithm, which answers my question.

---
Tags: algorithms, operating-systems, scheduling, process-scheduling
---


# Question
Title: Solve Time Complexity problem using Time Hierarchy
I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use Time Hierarchy.

I need to show that the following are either equal, on inclusive of one another...

TIME($2^{n^2}$) and TIME($n^3 \times 2^n$)

My intuition tells me that...

TIME($n^3 \times 2^n$) $\subset$ TIME($2^{n^2}$)

Can someone explain how I can prove this using the rules of Time Hierarchy?

# Answer
Your intuition that $ \text{TIME}(n^3 \times 2^n) \subsetneq \text{TIME}(2^{n^2})$ is correct.

It is easy to see that $2^{n^2}$ is time-constructible. Given $n$, you can compute $n^2$ in $\log^2 n$ time, then write 100...00 with $n^2$ zeros, in time $O(n^2)$.

The Time-Hierarchy Theorem states that, for such time-constructible $f(n)$,

$$ \text{TIME}(o(\frac{f(n)}{\log f(n)})) \subsetneq \text{TIME}(f(n))$$

It is clear that $ n^3 \times 2^n \in o(\frac{2^{n^2}}{\log 2^{n^2}}) = o(\frac{2^{n^2}}{n^2}) $.

Therefore, $ \text{TIME}(n^3 \times 2^n) \subseteq \text{TIME}(o(\frac{2^{n^2}}{\log 2^{n^2}})) \subsetneq \text{TIME}(2^{n^2})$.
> 0 votes

---
Tags: complexity-theory, time-complexity, polynomial-time, p-vs-np
---


# Question
Title: Compute the union of two sets between two endpoints minimizing communication complexity
I have two endpoints, $a$ and $b$, that can communicate through a channel. $a$ is storing a set of fixed-length strings $A = \\{a\_1, \ldots, a\_{N\_A}\\}$, and $b$ is storing another set of fixed-length strings $B = \\{b\_1, \ldots, b\_{N\_B}\\}$, with in general $A \cap B \neq \emptyset$.

Now, I would like to run a procedure that, using the communication channel between $a$ and $b$, results in both $a$ and $b$ storing $A \cup B$.

Both $a$ and $b$ can run an arbitrary amount of precomputation (e.g., sorting their sets, indexing them, organizing their elements in a tree...) but I would like the procedure to be as efficient as possible in terms of communication complexity.

The case I am most interested in is the one where $N\_A \simeq N\_B \simeq N$ with $N$ large and $|(A \setminus B) \cup (B \setminus A)| \ll N$. In that case, it seems to me like having the endpoints send their whole sets to each other should be an highly inefficient solution.

# Answer
> 3 votes
You can do this with $O(K \log N)$ bits of communication on average, where $K$ is the size of $|(A\setminus B) \cup (B\setminus A)|$, assuming you are willing to use a non-interactive protocol and are willing to accept a randomized protocol.

Let $H(\cdot)$ denote a randomized hash function. Do binary search on $i$ to find the smallest $i$ such that $H(a\_1,\dots,a\_i) \ne H(b\_1,\dots,b\_i)$, i.e., (ignoring hash collisions) such that $a\_i \ne b\_i$. Then you know that $a\_1=b\_1$, ..., $a\_{i-1}=b\_{i-1}$ and $a\_i \ne b\_i$. Thus $a$ can send $a\_i$ to $B$. You can use a $O(\log N)$-bit hash function and the probability of a hash collision can be made exponentially small. This takes $O(\log N)$ iterations of binary search, and in each iteration of binary search you send a $O(\log N)$-bit hash, so in all you send $O((\log N)^2)$ bits of information. At the end we have sent one of the $K$ elements from $A$ to $B$. Now you can repeat on the remaining elements (after discarding $a\_1,\dots,a\_i$ from both $a$ and $b$'s sets). You repeat at most $K$ times, so this gives a protocol that requires sending $O(K (\log N)^2)$ bits.

You can reduce this to $O(K \log N)$ bits by using a shorter hash. First do binary search using a 1-bit hash, to find the smallest $i$ such that $H(a\_1,\dots,a\_i)\_1 \ne H(b\_1,\dots,b\_i)\_1$, where $H(\cdot)\_b$ denotes the first $b$ bits of the hash $H(\cdot)$. This takes $O(\log N)$ iterations. Then, by using backtracking, you can find the smallest $i$ such that $H(a\_1,\dots,a\_i)\_2 \ne H(b\_1,\dots,b\_i)\_2$ , using on average $O(1)$ iterations. Then find the smallest $i$ such that $H(a\_1,\dots,a\_i)\_4 \ne H(b\_1,\dots,b\_i)\_4$, and so on, in each stage doubling the length of the hash. Each stage uses on average $O(1)$ iterations. If you sum the series of the number of bits sent, it sums to $O(\log N)$.

Thus, we get an improved protocol that requires sending $O(K \log N)$ bits on average. It does require interaction between $a$ and $b$ to enable the binary search, and it is randomized.

I don't know whether there is a non-interactive protocol with similar complexity, or whether the protocol can be derandomized to achieve $O(K \log N)$ bits in the worst case rather than in the average case (or rather than an exponentially small probability of sending more than $O(K \log N)$ bits).

---
Tags: sets, communication-protocols, communication-complexity
---


# Question
Title: Applying graph "adjustment" algorithms to Elo rating system
I'm trying to address what I *perceive* to be a potential shortcoming in the Elo Rating System (predominantly used by the international Chess community to rate + rank players). I have a two-player game in mind (not Chess) that is played all over the world, and I'd like to start rating/ranking its players using Elo, but and am toying with the idea of adding what I might consider to be an "enhancement" to basic Elo.

So with Elo your **performance rating** is relative and is directly influenced by the people you've previously beaten or lost to, and what their respective performance ratings were at the time you played them.

The problem is, the game I am interested in applying Elo to is largely played in isolated "pockets" all over the world, with very little (if ever, any) crossover between these pockets. Meaning there might be a "pocket" of, say, 5,000 players in Australia that only ever play each other. And there might also be an equally-isolated group of players in, say, Greenland that also only ever play one another. Only *extremely* rarely would an Australian play a Greenlander.

So what I'm wondering here is that since Elo is relative to the players you've won/lost to, that you might end up with, say, the champion (ranked 1st) Australian with an Elo rating of, say, 1845. And the leading Greenlander might have an Elo of, say, 1820. So on paper they look like they are pretty much equals.

**Except let's pretend that they're not -- not even close!** Let's say the quality of play in Australia is *far* superior to the average quality of play in Greenland. And if the leading Australian + Greenlander ever played each other, the Australian would mop the floor with the Greenlander (*BTW I'm American; nothing for/against Australia or Greenland here! Just using these as arbitrary examples!*). In this case, it might be that if this Greenland champion were to move to Australia and start consistently playing against Australians, his Elo rating might eventually settle to, say, 1330.

**Here's the fundamental problem I'm seeing with Elo:**

* The Greenland champion has an Elo rating of 1845, and the 2nd ranked Greenlander has a rating of 1805
* The Greenland champion will almost *always* beat the 2nd place player every time (8 out of 10 times, etc.)
* But now, the Greenland champion spends a summer in Australia and consistently loses, driving his Elo rating down to 1330
* The 2nd ranked Greenlander still has a rating of 1805 even though he is inferior to a player who is now rated at 1330, all because he stayed home in the safety of Greenland

Basic/current Elo does not account for the existence of these "isolated pockets" of players and doesn't allow for the auto-correction of them on the rare occasions when "cross-pollination"/cross-over does occur (that is: when a member of one pocket plays a member of another pocket). Current Elo is hinged upon the notion that *eventually* all players will play each other (across all groups/pockets) and will trend towards their true score. But in my game (and I'm sure many others), this is simply not true. Most players will spend their entire lives only ever playing the same group of opponents, and I'd like to find a way to augment Elo or apply an additional adjustment algorithm to Elo that truly keeps everyone's rating true to their current ability.

Essentially I'm wondering if there's a way for ratings to "ripple throughout a pocket/isolated group" anytime this cross-pollination does occur.

I guess in my mind I was thinking about a graph algorithm that represents the play history of the entire game. Each node in the graph represents a unique player. Every edge on the graph represents a distinct game (hence the same two nodes can have multiple edges between them if the same 2 players have played each other multiple times). Then, every time a new game is played, some type of adjustment ripples out over the entire graph. So in my example above, after the Greenland champion loses his first match to the first Australian, his rating goes down...but so does the rating for every other player in the isolated "Greenland pocket", etc. So as the Greenland champion's rating converges at 1330 (the more Australians he plays) all the other Greenlander's ratings go down at the same/appropriate rate as well.

**Are there any known/obvious solutions to this type of problem?**

# Answer
Good insight. There are other ranking algorithms that don't have this problem. The Bradley-Terry-Luce model is probably the easiest to understand. It is based on a principled statistical model for the likelihood that A will beat B, in terms of the difference between their ratings. It then applies maximum-likelihood statistical inference methods to infer the ratings of each player. This takes care of the issue you mentioned and ensures cross-pollination will occur.

So why do people use Elo instead of Bradley-Terry-Luce? Well, Elo is simpler. It can be implemented by hand, by looking up in a table to see how many Elo points you have gained or lost, based solely on the results of a single match. In comparison, statistical inference in the Bradley-Terry-Luce model requires a non-trivial inference algorithm that works on all the data, and so can only be done with the aid of a computer.

See also, e.g., https://stats.stackexchange.com/q/30976/2921, https://stats.stackexchange.com/q/6379/2921, https://stats.stackexchange.com/questions/tagged/rating, and https://stats.stackexchange.com/questions/tagged/ranking for more on our sister site, Statistics.SE.
> 1 votes

# Answer
For a graph-theoretic solution, it sounds like you want an algorithm like PageRank: https://en.wikipedia.org/wiki/PageRank

or the Hubs and Authorities algorithm (HITS): https://en.wikipedia.org/wiki/HITS\_algorithm

These algorithms score nodes (individuals) based on the scores of the nodes that it beat and who beat it.

Your problem here will probably want to weigh the edges in some way to reflect the timestamp of each edge. The most recent results should count more than older edges.
> -1 votes

---
Tags: graphs, statistics
---


# Question
Title: Is everything that is turing computable an element of NPSPACE?
So, if there is something that is turing computable, I know it is in NP (is that right?).

If M is computable, does it mean M is in NP?

M computable IFF in NP (is that true)?

And does all computable machines exist under NPSPACE?

# Answer
> 4 votes
> So, if there is something that is turing computable, I know it is in NP (is that right?).

No!!! The time hierarchy theorem says that, for example, there are problems in $\mathrm{NEXP} = \mathrm{NTime}\[2^{\mathrm{poly}(n)}\]$ that aren't in $\mathrm{NP}$. And that there are problems in $\mathrm{2NEXP} = \mathrm{NTime}\[2^{2^{\mathrm{poly}(n)}}\]$ that aren't in $\mathrm{NEXP}$. And so on, ad infinitum. In particular, this means that any $\mathrm{NEXP}$-complete problem is decidable but not in $\mathrm{NP}$.

To put it another way, there's no function $f$ such that every decidable problem can be solved in time (or space) $f(n)$, deterministically or nondeterministically.

In particular, there are perfectly reasonable decidable problems that aren't in $\mathrm{NP}$. For example, suppose you want to work with a graph on $n$ vertices. The graph is really large, so you can't store it. But, if I give you two vertices, it's easy for you to compute whether or not there's an edge between them (e.g., you can do that in deterministic polynomial time). Any problem that's $\mathrm{NP}$-complete when you're just given the full adjacency matrix as the input becomes $\mathrm{NEXP}$-complete when the graph is encoded in this way.

---
Tags: np
---


# Question
Title: Pumping lemma to show a language is not context free
I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start from?

I have to show that the following languages are not context-free

> > L = { w | w = 0a  1 b  2 ab  where a, b are \>= 1 }

and another question that goes like this:

> > L = { w | w = x11x21...1xk where k \>=0 and each xi is ∈ {0}*, and xi ≠ xj whenever i ≠ j

How would I tackle this problem? I understand pumping lemma in general but for these questions I can't seem to apply it.

# Answer
> 0 votes
First language: $0^{p}1^{p}2^{p^2}$ - If we make $0$ or $1$ longer, $2$ must get longer too to satisfy the condition of the language. Because of $|vwx|\le p$ $v$ cannot contain $0$ when $x$ contains $2$. Also if either $v$ or $x$ contained two different symbols, we know that it would break the language (there would be a sequence of e.g. $0^{i}1^{k}2^{l}1^{m}2^{n}$ with $l,m \> 0$).
The last possibility is when $v$ is of form $1^k$ and $x$ of form $2^{l}$. We will prove by contradiction that this is impossible too. We would need such $k, l\>0$ that the next equation holds for all $i \ge 0$ $$p(p+i\cdot k) = p^{2}\cdot i \cdot l \\ p^{2} + p\cdot i \cdot k = p^2 \cdot i \cdot l \\ l = \frac { p^2 + p \cdot i \cdot k }{p^2 \cdot i} \\ l = \frac {1}{i} + \frac {k}{p} $$ From $|vwx|\le p$ and $k,l\>0$ we know that $k\<p$. Similary $\frac{k}{p}\<1$ and $\frac{1}{i} \< 1$ for $i \> 1$. From those and the fact that $l$ is natural number, the only possible value of $l$ is $1$. That would mean $$p^{2} + p\cdot i \cdot k = p^2 \cdot i \\ k = \frac{p \cdot i - p}{i} \\ k = p - \frac{p}{i}$$

There are two problems with this: first it would hold only when $i$ divides $p$ and $k$ would be dependant on $i$ but has to be a constant. Thus we have proved this is impossible too and the lemma is complete.

---

For the second language, I believe it is pretty difficult example I and I would advise you to first try some easier languages, if you have just started using the lemma.

You can chose for any $p$ a string $0^{0}10^{1}10^{2}1...10^{p-1}10^{p}$ and then you have to enumerate all the possibilities and prove they don't hold for some $i$.

* Either $x$ or $v$ contains two (or more) $1$'s - then it also contains $10^m1$ so with $i\>1$ the pumped string will contain two $x\_m$'s so it will not be from $L$.
* Both $x$ and $v$ contain no $1$'s - with $i=0$ the substrings $x\_m$ and $x\_n$ containing $x$ and $v$ respectively will get shorter. Since the original string $s$ contained all shorter strings $x\_k$ at least one of them will colide with some shorter string.
* Either $x$ or $v$ contain only $1$. - If that substring is pumped, the new string will contain $...11... = ...1x\_{0}1...$, but the original string started with $1... = x\_{0}1...$, thus we have a collision.
* Either $x$ or $v$ are of form $0^{n}10^{m}$ with either $n$ or $m$ greater than $0$. With $i=3$ we get $...0^{n}10^{n+m}10^{n+m}10^{m}...$ where we immediately see a collision.

I hope I did not forget some special case.

---
Tags: automata, context-free, pumping-lemma, pushdown-automata
---


title: Meaning of the Time Hierarchy Theorem

text:
# Question
Title: Meaning of the Time Hierarchy Theorem
Given two positive integers $c\_1$ and $c\_2$ such that $c\_1 \< c\_2$, it's easy to prove that $n^{c\_1}$ is $\mathcal{O}(n^{c\_2})$ while $n^{c\_2}$ is not $\mathcal{O}(n^{c\_1})$. In general, for any functions $f(n)$ and $g(n)$ it is possible to determine which one (or both) is true, $f \in \mathcal{O}(g)$ or $g \in \mathcal{O}(f)$ using only definition of big-O notation. Thus it is not hard to see that TIME($n^{c\_1}) \subsetneq$ TIME($n^{c\_2})$ without using the Time Hierarchy theorem.

So, what is the meaning of the Time Hierarchy theorem and how and where can I use it?

# Answer
> 2 votes
You miss the meaning of the Time Hierarchy theorem, or perhaps of the classes TIME($n^k$) that you show.

It is indeed obvious that $O(n^k) \subsetneq O(n^{k+1})$, for instance. It is also clear that the set of Turing machines that run in time $O(n^k)$ is a strict subset of those that run in $O(n^{k+1})$.

However, it is not immediately obvious that the set of *problems* that *can be solved* by TMs in time $O(n^k)$ (i.e., the class TIME($n^k$)) is a strict subset of TIME($n^{k+1})$. For this much stronger statement, you need the Time Hierarchy Theorem. That is, you need to argue that there exists some problem that can be solved in time $n^{k+1}$ but not in time $n^k$. (Of course, this is just a special case of applying the theorem to polynomial running times.)

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


# Question
Title: Precomputation for partial products in monoids
Suppose I have a sequence of elements $a\_1,\ldots,a\_n$ in a group and I want to compute, for varying $1\leq i\leq j\leq n$, the product $b\_{i,j}:=\Pi\_{i\leq k\leq j}a\_k$. Then I can do a precomputation of all $b\_{1,j}$ and later determine each needed $b\_{i,j}$ as $(b\_{1,i-1})^{-1}b\_{1,j}$.

The cost is $O(n)$ group operations and $O(n)$ additional time for the precomputation, and $O(1)$ operations and $O(1)$ additional time for each access. Clearly optimal. So far so good.

Now what if I don't have inverses (that is I have a monoid instead of a group)? The best I can come up with is a binary-tree like precomputed data structure. The cost of access would increase to $O(\log n)$. Can that be improved?

# Answer
> 2 votes
As you say, with $O(n)$ precomputation you can arrange that each access takes $O(\log n)$ time. You build a binary tree over the elements, and annotate each internal node with the product of the leaves under it. This takes $O(n)$ precomputation and $O(n)$ storage.

If you are willing to do more precomputation, you can reduce the access time. In particular, with $O(n \log n)$ precomputation and $O(n \log n)$ storage, you can arrange that each access runs in $O(1)$ time. The idea is outlined below.

---

Notationally, we will let $b\_{i,j}$ denote the product $a\_i a\_{i+1} \cdots a\_j$, as you define in your question.

First, precompute the products $b\_{i,n/2-1}$ for $i=1,2,\dots,n/2-1$ and the products $b\_{n/2,j}$ for $j=n/2,\dots,n-1,n$. This can be done with a $O(n)$ precomputation. This will let you compute any product $b\_{i,j}$ in $O(1)$ time if we have $i \< n/2 \le n/2$, i.e., if the range $\[i,j\]$ spans the midpoint.

We still need a way to handle ranges that don't span the midpoint. We'll handle that recursively. Basically, take the sequence $a\_1,\dots,a\_{n/2-1}$ and recursively build a data structure for it (e.g., find its midpoint $a\_{n/4}$, etc.). Also, recursively build a data structure for $a\_{n/2},\dots,a\_n$. This will let us compute all products $b\_{i,j}$ where $j\<n/2$ or $i\ge n/2$, i.e., where the range $\[i,j\]$ doesn't span the midpoint. This covers all the cases.

How much time does the precomputation take? If $T(n)$ denotes the time for the entire precomputation, it satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n),$$

which solves to $T(n) = O(n \log n)$. Similarly, we can see that the amount of storage needed is also $O(n \log n)$. Finally, this data structure will let you compute any product $b\_{i,j}$ in $O(1)$ time.

(I'll let you figure out how to compute $b\_{i,j}$ from this data structure in $O(1)$ time. It can be done with some clever bit-shifting tricks. It may help to think about the data structure in terms of the big-endian binary representation of the indices. For each index $i$, we compute $b\_{i,i'}$ where $i,i'$ share a common prefix and then $i'$ is all ones after the common prefix; and we compute $b\_{j',j}$ where $j',j$ share a common prefix and then $j'$ is all zeros after the common prefix. Given $i,j$, we can find the longest common prefix of $i,j$, then express as the product $b\_{i,j} = b\_{i,i'} b\_{j',j}$, look up the values of $b\_{i,i'}$ and $b\_{j',j}$, and compute the product. All of these can be done in $O(1)$ time by placing the precomputed values in an array in the correct order.)

---
Tags: algorithms, data-structures
---


# Question
Title: Find the first integer with exactly $n$ divisors
For given positive integer $n$ find the first number $x$ with exactly $n$ divisors. For simplicity of the problem we can assume that $x$ will always fit in integer size and $n \leq 1000$.

**Example**

If $n=4, x = 6, \text{ divisors of 6 are } \\{1, 2, 3, 6\\}\\n=6, x=12, \text{divisors of 12 are } \\{1,2,3,4,6,12\\}$

I was thinking because the number should have at most 1000 divisors we should brute force them in some way, but I cannot think how it could be done.

# Answer
Some observations: If p is a prime, then $p^{n-1}$ has exactly n divisors. And if for example p, q, r are different primes, then $p^{n-1} q^{m-1} r^{j-1}$ has exactly n * m * j divisors.

And that's the only way we can find numbers with exactly n divisors: We write n as a product n = n1 * n2 * n3 ..., then find primes p1, p2, p3 and so on, and the product $p1^{n1-1} p2^{n2-1} p3^{n3-1} ...$ has exactly n divisors.

If we sort so that n1 ≥ n2 ≥ n3, then a product that is not in the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ can be made smaller while having the same number of divisors by using the primes 2, 3, 5 in that order. For example, if we start with $2^3 5^2$ then $2^3 3^2$ has the same number of divisors, but is smaller. Likewise, $3^3 2^2$ can be replaced with $2^3 3^2$ with the same number of divisors, bit smaller.

So the smallest number with n divisors has the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ with n1 ≥ n2 ≥ n3 ... and n = n1 * n2 * n3 ...

Now a number like n = 1000, or n = $10^{1000}$, can be written as a product in many ways, so you need to reduce the number of possibilities. You can use an algorithm where you try all possible exponents for 2 that could lead to the smallest number with n divisors, then all possible exponents for 3, and so on.

Let n = p1 * p2 * p3 ... * pk, with primes p1 ≥ p2 ≥ p3 ≥ ... ≥ pk. Whenever we choose an exponent, that exponent is either p - 1 where p is the largest prime not used so far, or it is of the form ab - 1 where b is the smallest prime factor of ab, and ab is greater than that largest prime. (That's quite obvious, right? It's a prime or composite minus 1, and since the exponents are in descending order, its the largest prime minus 1, or greater than that).

n was the product of k primes. Let P be the k-th prime. If an exponent is of the form ab-1, then P is not a factor of the number. And if we have a factor $p^{ab-1}$, then replacing this with $p^{a-1} P^{b-1}$ gives a number with the same number of factors, but smaller unless $p^a \< P$.

This *hugely* reduces the number of choices. Take n = $2^{1000}$ which is the product of 2,000 primes. The k-th prime is very roughly P ≈ 20,000.

We saw that the smallest number with n divisors can only have a factor $p^{ab-1}$ if $p^a \< P$. We have $2^{15}≥P ≈ 20,000$, $3^{10} ≥ P$, $5^7≥P$, $7^6≥P$, $11^5≥$, and $13^4≥P$, so a ≤ 14 when p = 2, a ≤ 9 when p = 3, a ≤ 6 when P = 5, a ≤ 5 when P = 7, a ≤ 4 when P = 11, and a ≤ 3 when p ≥ 13. And we must have ab ≥ 5, b is the smallest prime factor of ab, and ab must only have prime factors 2 and 5.

As a result, the only composite exponents minus 1 that are possible in the smallest number with $10^{1000}$ divisors are: $2^{4\*2-1}$, $2^{5\*2 - 1}$, $2^{5\*5 - 1}$, $2^{8\*2-1}$, $2^{10\*2 - 1}$, $3^{4\*2-1}$, $3^{5\*2 - 1}$, $3^{5\*5 - 1}$, $3^{8\*2-1}$, $5^{4\*2-1}$, $5^{5\*2-1}$, $5^{5\*5-1}$, $7^{4\*2-1}$, $7^{5\*2-1}$, $7^{5\*5-1}$, and $11^{4\*2-1}$. This is followed by a huge number of factors $p^{5-1}$, finishing with a huge number of factors $p^{2-1}$.

Since the exponents have to be in non-decreasing order, there is only a small number of cases to try, even for a huge number like $n = 10^{1000}$.

PS. In your trivial examples, n = 4 = 2 * 2, the solution was $2^{2-1} 3^{2-1} = 6$, and with n = 6 = 3 * 2, the solution was $2^{3-1} 3^{2-1} = 12$.

PS. Assume you have a more moderately sized n, let's say an n that is the product of 10 primes, making P = 10th prime = 29. We have $2^5\<29$, $3^3\<29$, $5^2\<29$, but $7^2 \> 29$. Therefore the only possible factors with an exponent that is not a prime -1 are: $2^{4-1}$, $2^{9-1}$, $2^{6-1}$, $2^{8-1}$, $2^{10-1}$, $2^{25-1}$, $3^{4-1}$, $3^{9-1}$, $3^{6-1}$, and $5^{4-1}$.
> 3 votes

# Answer
This is how you can precompute $A\[n\]$s for each $n\<1000$.

```
precompute()
  set A[1..1000] = 0
  count = 1
  x=1
  while(count <= 1000)
   m = count_divisors_of(x)
   if (A[m] == 0)
     A[m] = x
     count = count + 1
   end
   x = x + 1
  end
end

```

This procedure must terminate since for any $n$, $2^{n-1}$ has exactly $n$ divisors: $1, 2, 4,\dots 2^{n-1}$. However, I do not know how long time it may take to compute all $A\[i\]$s. You can optimize the procedure `count_divisors_of`. Also, the tables in this article list all of the divisors of the numbers $1$ to $1000$.
> 0 votes

---
Tags: number-theory
---


title: Unary Turing-unrecognizable language

text:
# Question
Title: Unary Turing-unrecognizable language
One of my final exam questions asked me to give a Turing-unrecognizable language over an unary alphabet, which I wasn't able to complete, but I ended using the Busy Beaver function (BB(k)) which is known to be something intractable or uncomputable so that I constructed the language as a set of strings 1^BB(k) for natural number k=1,2,... It intuitively feels like it's Turing unrecognizable but how can I prove it(if this is true)?

# Answer
Suppose that you have an algorithm $f$ that decides $L=\\{1^{BB(k)}\mid k \in \mathbb N\\}\subseteq \\{1^n\mid n\in \mathbb N\\}$. Then you can build the following algorithm that computes $BB$:

```
// input k
n = 0
values_of_bb = []
while length(values_of_bb) < k
  if f(1^n) == 1
    values_of_bb.push(n)
    n = n + 1
return values_of_bb[k]

```

This will be true for all strictly increasing functions from $\mathbb N$ to $\mathbb N$: if the image is decidable, then the function is computable. You just have to enumerate potential values in increasing order and put them in a list (still in increasing order), and then the $k^\text{th}$ value is simply the $k^\text{th}$ element of this list.
> 0 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: Decidability of whether a language described by Turing machine is regular
I am trying to prove decidability of problem whether language described by Turing machine is regular. My idea is that I can simulate finite automaton with a subset of Turing machine instructions, namely ones that check for symbol and then move right. If the language is not regular, then simulated FA will eventually come across a string that it cannot process, and give it a FALSE. On the other hand, if the language is regular, FA will successfully accept every string. The problem is that the language has infinite number of strings, and the simulated FA will be checking then forever and never giving affirmative answer. That would make said problem undecidable. Is my reasoning here correct? And if it is, can it be considered a valid proof, or do I need to prove it some other way?

EDIT: The exact wording of the exercise translated as best as I can: You're given a problem of whether language of given Turing machine is regular. Decide whether this problem is decidable and whether is partially decidable. Formally prove your argument.

# Answer
> 6 votes
This language/problem is neither decidable nor partially decidable (r.e). You can use Rice's theorem to prove it. The following proves that the language is not decidable.

"$L$ *is regular*" is a nontrivial property of recursively enumerable languages since there are regular and non-regular languages which are r.e. For example, $L\_1 = \\{0^{2n} \mid n \> 0\\}$ is regular, while $L\_2 = \\{0^n1^n \mid n \> 0\\}$ is not regular, but both are r.e. Hence, by Rice's theorem the language $\\{\langle M \rangle \mid L(M) \text{ is regular } \\}$ is not decidable.

In order to prove that this language is not r.e. you could use Rice's theorem for recursively enumerable index sets.

# Answer
> 0 votes
Your reasoning as is does not exactly show it is undecidable, since you need to show that *all* Turing machines fail to solve it. Since a set being regular is a non-trivial property, you can use Rice's Theorem to prove the problem is undecidable.

We can make an explicit machine construction to prove that the Halting problem starting with empty input is reducible to your problem. Let $M\_{NR}$ be a machine which accepts a non-regular set, such as $\\{a^nb^n \mid n \geq 1\\}$. The construction takes a Turing machine $M$ as input, and constructs a new machine $M'$ which does the following:

* Given input $x$, first simulate $M$ on empty input.
* If and when $M$ halts, simulate $M\_{NR}$ on input $x$. Output the answer that $M\_{NR}$ gives.

Here, we see that if $M$ halts on empty input, $M'$ always makes it to the second step, and so $M'$ accepts precisely the language of $M\_{NR}$, which is not regular. If $M$ does not half on empty input, $M'$ never makes it to the second step, and so $M'$ accepts the empty set, which is regular. Therefore, $L(M')$ is regular if and only if $M$ does not halt on the empty set. This completes the reduction, such that if your problem were decidable, the halting problem with empty input would be too. But the latter is undecidable, so your problem is necessarily undecidable.

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


# Question
Title: Finding whether the language is CFL or regular
$L = (0^i 1)^n$ where i=1,2,3,4...n and n\>=0

For eg :- 00010001 doesn't belong to the language as n=2 but i=3 at the beginning.

001001001 belongs to L as n=3 and i=2 in all cases.

I know the above language is not regular for sure as value of 'i' depends on value of 'n' and it requires comparison. So DFA not possible.

Now I am not sure to which class of language does the above language belong because to check number of zeroes or 'i', we need value of 'n' which can be found out only after reading the entire string.

Can someone please help?

# Answer
Suppose there exists a CFG whose language is $L$, and let $k$ be the pumping length. Consider the string $(0^k1)^k \in L$. Then, by pumping lemma, there exists a decomposition $(0^k1)^k = uvwxy$ where $|vwx| \leq k$, $vx \neq \varepsilon$, and for each $i \geq 0$, $uv^iwx^iy \in L$. Since $|vx| \leq |vwx| \leq k$, there are four types of values of $vx$: either $vx \in 0^+$, $vx \in 0^+1$, $vx \in 10^+$, or $vx \in 0^+10^+$. Try showing that in each of these cases, pumping $vx$ gives a string not in $L$, thus giving a contradiction and demonstrating that $L$ is not context-free.
> 2 votes

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


# Question
Title: Prove or disprove: Complement of language $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free
> Prove or disprove: Complement of language $L=\left\\{baba^2ba^3b...ba^{n-1}ba^nb \\, | \\, n \geq 1\right\\}$ is context-free.

I'm not quite sure how this is done. I would first try to find out whether $L=\left\\{baba^2ba^3b...ba^{n-1}ba^nb \\, | \\, n \geq 1\right\\}$ itself is context-free.

The language creates words $x$ of length $|x|= n+1+\frac{n(n-1)}{2}= \frac{n(n+1)}{2}$

So $L$ is not context-free. But I was looking for the complement of $L$, i.e. $\bar{L}$, the language.

Is it possible to argue that $\bar{L}$ is context-free because $L$ is not?

Or how would you show it better?

# Answer
> 1 votes
No, reasoning with the complement will not work as context-free languages are not closed under complement.

Consider an alternative description of $L$: it consists of all strings $ba^{a\_1}ba^{a\_2} \dots ba^{a\_n}b$ such that (1) $a\_1 =1$ and (2) for all $1\le k\<n$, $a\_{k+1} = a\_k+1$.

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


title: Traveling Salesman Solution

text:
# Question
Title: Traveling Salesman Solution
This problem has been heavily studied, and at last may have a potential solution. The concept I have come up with was made entirely on my own, but is close to some other theories that will be referenced.

The intended purpose for posting here is to have more experienced software developers review my theory. Should it prove to hold up, my ultimate goal is to publish an academic paper covering it.

## The Theory

My first step was to think about the problem differently. The classic TSP (Traveling Salesman Problem) is stated along these lines:

> A traveling salesman wants to sell his product in a set of given cities, and wants to travel along the shortest path between them all, returning to the city he started at. Each city is visited only one time. How is the length of this path found?

The problem is defined as the shortest route that starts and ends at the same point, which is essentially the shortest *circuit* for the whole graph, making the start aribtrary. In other words, no matter where you start on the graph, there will only be one "shortest path." The question then becomes:

> What is the shortest circuit for the given graph, visiting each point only once?

To calculate this, I thought of how to make the graph more "understandable" for a computer, and the easiest way is just to make the whole graph into one line. Thinking abstractly, we take all of the points in the graph and arrange them into one straight line along the y-axis, creating a path with the shortest distance between each point. This produces the shortest line possible. To make a circuit, we just get the distance from the last point in the line to the first, and add it back onto the total distance of the line. None of the point values are actually changed, just rearranged using abstract thought. Now for constructing this line.

Working in the first quadrant, it turns out you can just iterate over the x and y axis adding the points closest to y=0 in order from the bottom, and you'll just get the right path. If you have negative y values, then the starting y becomes the most negative value. This process will build the shortest line. Again, since the start is aribtrary, the first point encountered can be the start. Due to the nature of this line, all of the points must be sorted by order of least to greatest x and y. This doesn't change their values; all points are put in an order that's easy to calculate. Because the distance formula is used, any calculations done in the third quadrant are brought up to the first, and any done in the fourth are brought up to the second (by order of magnitude), which is also *conveniently* friendly to a number line.

Now this works very well for any random scatter plot of data, but what happens if y-values between two or more points are shared? How is this calculated? We'll call these kinds of points "collisions," and calculating them is challenging. When a collision is encountered, we have to decide whether it goes before or after the first point that shared the same y-value but wasn't a collision, which we'll call a "source." We also have to choose whether it goes directly before or after the source, or somewhere farther down the path in either direction.

I've tried many variations on a solution, and how I solve it right now is as follows. If the graph contains any collisions, check to see if the collision matches a source. If the collision has a shorter distance (a.k.a the most optimal choice) compared to the source's neighbor (the next point in the graph disregarding collisions) then set the collision as the neighbor and remove it from a collision cache. After the shortest path is computed, if any collisions are leftover, find the best place to put them into the graph. My initial intuition was to throw all leftover collisions onto the end of the line, which is right a suprising amount of the time.

After some research, my solution most closely resembles the *Nearest Neighbor Algorithm* by Rosenkratz, Stearns and Lewis, detailed on page 242 of this paper. The fact that people have thought along these lines in the past gave me reassurance that I was on an accurate path.

A proof to reflect the algorithm is a work in progress.

## Results

Currently my implementation works for the following cases:

* a single point (length 0)
* simple to complex polygons
* lines (simple to complex functions implied)
* scatter plots (implied from polygons)

Every possible path would have to be either one or a mixture of these.

Here is the asymptotic analysis for the whole program.

The code has been posted to CodeReview for review.

### GitHub

# Answer
First, it's important to recognize the gravity of what you are proposing. If correct, your algorithm is worth $1 Million USD. Secondly, many *many* people have tried and failed to solve this problem. So it's important to approach this with the assumption that you are wrong, and to exhaustively try to disprove yourself.

The next step is to prove two things:

1. Your program is correct
2. Your program does indeed run in polynomial time.

I suspect the problem lies with (1), but you state your complexities for (2) without explaining any reasoning behind them, so there may be a problem there.

If you are serious about this, or about tackling large problems in CS theory in general, I would highly advise that you learn how to use and encode your algorithm in a proof assistant, such as Coq or Agda. Such systems will not allow you to make mistakes in your proof, so if you manage to prove your algorithm correct, then there will be a high degree of confidence in your result. And if your algorithm is incorrect, then the errors or pain points should reveal themselves quickly.

Finally, it's important to realize that P vs. NP is entirely about proofs: the question is, are these two mathematical sets equal? There are plenty of algorithms that approximate solutions to NP-hard problems, and many that are polynomial in common cases, but exponential in the worst case (like SAT solvers). So experimental results will not be enough here.
> 11 votes

---
Tags: algorithms, traveling-salesman
---


# Question
Title: How would I design an NFA that recognises the language of all strings that don't end in a certain sequence?
How would I design an NFA that accepts all strings don't end in a certain sequence over the alphabet {0,1}. Designing a DFA that does the job is fairly straight forward, but I can't find out how to make my Automata Non-Deterministic.

# Answer
> 3 votes
Any DFA is also already a NFA, so you've already answered your question.

# Answer
> 1 votes
Actually "non-deterministic automaton" is a horrible name. It better be "(finite) automaton" which has a subclass of "deterministic" automata. I do not think people are really interested in the construction of an automaton that is on purpose non-deterministic.

---
Tags: automata
---


# Question
Title: What do we benefit from using ternary search trees rather than binary search trees?
Ternary search trees are very common in the text editing area. They could be used to implement Auto complete feature, spell checking, Partial-Match searching, Near-Neighbor Searching & many many other options.
The reason behind them being famous is their space efficiency compared to tries (Although tries are faster) & their flexibility (Compared to Hashtables).
Ternary search trees have three pointers in their data node : `lokid` the left kid, `hikid` the right kid & `midkid` the middle kid.
The thing that I'm missing is why do we need the middle kid ? What is the particularity of this pointer ? In which things it would be better to have that pointer rather than not having it at all ?
I was drawing some trees & i think we can realize the same thing using only 2 pointers (A binary search tree) with insertions going to the left kid if current character in the string to insert is equal or less than the character on the current node and insertions going to the right the other way around.

The following picture shows a binary tree generated from inserting words: KARIM, KARAS, SARAS.

The insertion algorithm of the above tree could be something similar to the following pseudo code :

```
insert(root, word){

    if(!root) {
        root = new node()
        root->char = *(word++)
    }

    if(*word > root->char)
        insert(root->right, word)

    else {
        if(*word == root->char)
            insert(root->left, word++)
        else
            insert(root->left, word)

    }
}

```

What could possibly be wrong with the above conception ? Am i missing something about the ternary trees which makes them superior to binary trees ?

# Answer
> 2 votes
I'd challenge you to write the code which queries your data structure. For example, how could you determine that "SARAS" is in your tree, but "KSARAS" is not?

The problem with your data structure is that we cannot tell the difference between searching and selecting a letter. This is what the middle child of the ternary tree is used for: when you've found the letter you're looking for, you step to its middle child.

Here's what a ternary tree for your set of words might look like. I've marked word ends with `*`.

```
    K
    | \
    A  S
    |  |
    R  A
    |  |
    I  R
  / |  |
 A  M* A
 |     |
 S*    S*

```

Querying for "SARAS", for example, would look like this:

* \[Looking for "SARAS", at node K\] S \> K, so go right.
* \[Looking for "SARAS", at node S\] S = S, so go down and advance to next character.
* \[Looking for "ARAS", at node A\] A = A, so go down and advance to next character.
* etc... (eventually returns true)

Querying for "KSARAS", however, would look like this:

* \[Looking for "KSARAS", at node K\] K = K, so go down and advance to next character.
* \[Looking for "SARAS", at node A\] S \> A, so go right.
* \[Looking for "SARAS", fell off tree\] return false.

---
Tags: data-structures, binary-trees, search-trees
---


# Question
Title: Can Haskell ensure a Functor (or other typeclasses) satisfies its law?
It seems that Functor definitions in Haskell can be accepted if the type is correct.
This code compiles, but it doesn't satisfy the functor law:

```
data Bst a = NIL | Node a (Bst a) (Bst a) deriving (Eq, Ord, Show)

instance Functor Bst where
  fmap _ NIL = NIL
  fmap f (Node v left right) = Node (f v) (fmap f right) (fmap f right)

```

Is is possible for Haskell to check if the functor definition satisfies the functor law?
If Haskell cannot, can Agda/Idris do this?

# Answer
So, while this question seems Haskell specific at first glance, I think it touches on enough aspects of modern Programming Languages theory and research that there's a good CS-general answer here.

As DW says, it's impossible to automatically verify that an implementation satisfies the Functor laws, by Rice's theorem.

However, strongly-typed languages give you several methods for proving properties of programs, so there are several approaches that work:

* Refinement Types. These are a lightweight form of dependent types, where you can refine a type by a predicate that values of that type must satisfy. This lets you model things like the type of non-zero integers. These are implemented in LiquidHaskell, and there's an upcoming accepted paper where they extend techniques like this to verify typeclass laws. This is implemented as a checker on top of Haskell, so you can write normal Haskell code and get all the inference you normally would, but you add annotations that get checked using SMT.
* Pseudo-dependent types. Haskell has GADTs, data-kinds, type families, and multi-parameter typeclasses, all of which let you reason about properties of types. The trick is that these tools can't do much to reason about values, so you end up "promoting" your functions to the type level (i.e. writing your functions as type families aka functions on types) and proving about them. With these, you get some inference, but not quite as much as you do when writing normal functions.

In the long run, Dependent Types are coming to Haskell, but probably not in as full a way as you see in Idris or Agda.
* Full dependent types. This is what Agda and Idris and Coq get you, and often in those languages, writing proofs that your instances satisfy typeclass laws is required. Types can depend on values, functions can return types, everything is merge. You have the full power of higher-order logic here, so if you can prove it, almost always you can prove it in these systems.

The tradeoff is that the inference in the languages is limited: you need to annotate nearly every function definition with its type, and in general, these languages add a degree of complexity above what Haskell has. And, all the proofs are explicit: you have to write the proof yourself that your programs fulfill your laws. Tactics can help to automate this process, but it ends up generally being rather tedious.
> 5 votes

# Answer
By Rice's theorem, this is undecidable in general.
> 2 votes

# Answer
It's possible with this: https://blog.jle.im/entry/verified-instances-in-haskell.html.

We need several extensions and the Singleton library.
And your functor become like this:

```
{-# LANGUAGE MagicHash, RankNTypes, PolyKinds, GADTs, DataKinds,
         FlexibleContexts, FlexibleInstances,
         TypeFamilies, TypeOperators, TypeFamilyDependencies,
         UndecidableInstances, TypeInType, ConstraintKinds,
         ScopedTypeVariables, TypeApplications, AllowAmbiguousTypes,
         PatternSynonyms, ViewPatterns #-}
class Functor f where
    type Fmap a b (g :: a ~> b) (x :: f a) :: f b

    sFmap
        :: Sing (g            :: a ~> b)
        -> Sing (x            :: f a   )
        -> Sing (Fmap a b g x :: f b   )

    -- | fmap id x == x
    fmapId
        :: Sing (x :: f a)
        -> Fmap a a IdSym0 x :~: x

    -- | fmap f (fmap g x) = fmap (f . g) x
    fmapCompose
        :: Sing (g :: b ~> c)
        -> Sing (h :: a ~> b)
        -> Sing (x :: f a   )
        -> Fmap b c g (Fmap a b h x) :~: Fmap a c (((:.$) @@ g) @@ h) x

```

From: https://www.zhihu.com/question/65775009/answer/263094330
> 1 votes

---
Tags: haskell
---


title: What are some constant time operations?

text:
# Question
Title: What are some constant time operations?
I know that some operations are definitely constant time, such as accessing an item in a list, however there are other operations that are assumed constant time sometimes, but non-constant other times, such as multiplication.

So if we were to deal with very, *very* large operations, which operations would be truly constant time, or at least polynomial for exponentially large data

# Answer
To answer this question properly, one needs two things: a model of computation and a notion of (time) complexity. Especially when talking about sub-linear complexity, the influence of the model of computation is extremely important. Starting from linear-time (and especially when dealing with polynomial time), it becomes mostly irrelevant and people avoid mentioning it. Consider addition for example:

* **Turing machine1** with **classical time complexity**: addition takes linear time on the size of the input because the machine has to read the inputs and that takes linear time.
* **Straight-line program(SLP)** counting number of instructions: addition is in constant time because there is an instruction for that.
* **Boolean circuit** with depth complexity: addition takes logarithmic time in the size of the input (using an optimized adder).

In fact Turing machines are not a very accurate model of current computers because they cannot do random accesses2 and very little can be done in constant time. This why counter machines and RAM models are more accurate, but also come with their drawbacks. Models such as SLP where addition is a constant time operation are known to be unrealistic because they can produce numbers of exponential size in the number of instructions.

When dealing with numbers, it is common to refer to "bit-complexity" and what it really means is a model that deals with bits and has random access memory. In this kind of model, addition can be done in linear time and multiplication in $O(n\log n \log\log n)$ where $n$ is the number of bits. Wikipedia has a page listing other operations.

1I am going to ignore the possible variations on the number of tapes, in this example we can consider that the two numbers are on different tapes and we have a dedicated output tape.

2Though one can argue that current computers are really only finite automata because they are finite, but this is not necessarily a useful point of view; or that computers really have logarithmic time random access in the size of the memory.
> 1 votes

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