What is inapproximability of NP-hard problems? Recently I have come across a paper which talks of "(1+ε)-inapproximability" and of "logarithmic approximation".

While I have a basic knowledge of computational complexity (I more or less know what it means to be in P, NP, NP-hard and so on), I tried to study some basic texts on approximability but I'm not sure I really get what this inapproximability is. Could you enlighten me on what the above expressions mean?

If you want to know the paper I was referring to, it was DasGupta & Desai. «On the complexity of Newmanʼs community finding approach for biological and social networks». Journal of Computer and System Sciences 79, n. 1 (2013): 50–67. The found inapproximability is a property of the modularity measure (the so-called Q) related to the Newman-Girvan algorithm for finding community structure in networks, a measure whose maximization has been proved NP-complete by Brandes, Delling, Gaertler, Gorke, Hoefer, Nikoloski, and Wagner in 2008. Thank you in advance.

Optimization problems come in two flavors: minimization and maximization. For definiteness, in this answer we consider minimization problems; for maximization problems the situation is completely analogous.

Generally speaking, when we say that a minimization problem $\Pi$ is $c$-hard to approximate, we mean the following:

  If there is a polynomial time approximation algorithm for $\Pi$ whose approximation ratio is better than $c$ then [something bad happens].

Usually the "something bad" is $\mathsf{P} = \mathsf{NP}$, but sometimes we can only prove that, say $\mathsf{NP} \subseteq \mathsf{DTime}(n^{\log \log n})$ (that is, SAT can be solved in time $O(n^{
\log \log n})$). Since we believe that the "something bad" is wrong, it follows that probably no polynomial time approximation algorithm for $\Pi$ has an approximation ratio better than $c$.

Why this form of result? If $\mathsf{P} = \mathsf{NP}$, then all NP optimization problems (that is, all optimization problems whose decision version is in NP) can be solved in polynomial time. Therefore in order to prove that a certain problem cannot be approximated well we need to make some complexity assumption such as $\mathsf{P} \neq \mathsf{NP}$.

The best one can hope for is to prove that is an NP-hard to approximate $\Pi$ better than $c$. What this means is that for each $\epsilon > 0$ there is a polynomial reduction $A$ from SAT to $\Pi$ with the following properties:

If the input formula $\varphi$ is satisfiable than the optimal value of $A(\varphi)$ is at most $x$, for some value $x$ which the reduction explicitly calculates (in polynomial time).
If $\varphi$ is not satisfiable than the optimal value of $A(\varphi)$ is more than $(c+\epsilon)x$.

In particular, any polynomial time $(c+\epsilon)$-approximation algorithm would be able to distinguish the two cases, and thus to solve SAT in polynomial time.

Technically, what we have described is known as a promise problem: decide whether an instance of $\Pi$ has value at most $x$ or more than $(c+\epsilon)x$; or stated differently, find the optimal value of an instance of $\Pi$ (or at least distinguish the two cases) under the promise that the optimal value is either at most $x$ or more than $(c+\epsilon)x$.

In some cases we are able to prove that a certain problem $\Pi$ is $c$-hard to approximate, and also show that a polynomial time $c$-approximation algorithm exists. In this case we say that the inapproximability threshold of $\Pi$ is $c$. For example, Håstad shows that the threshold of inapproximability for 3SAT is $7/8$.

Our definition above of $c$-inapproximability states that in polynomial time it is impossible to approximate a certain problem better than $c$, but allows an approximation ratio of $c$. Sometimes we also want to disallow an approximation ratio of $c$. The terminology doesn't reflect this fine point, and formal statements of theorems have to be consulted.

Finally, $(1+\epsilon)$-inapproximability means that (under some complexity assumptions) it is impossible (in polynomial time) to approximate the problem to within $1+\epsilon$ for some $\epsilon > 0$ (in terms of our notation above, the problem is $1$-hard to approximate). We also say that the problem is APX-hard.

Logarithmic inapproximability means that it is impossible to approximate the problem to within $O(\log n)$, where $n$ is some natural parameter inherent in the problem, usually the number of vertices in the input graph.


time efficient key value store for fast lookup Let's state a collection of key/values.

Key is an unsigned integer (0 - 2^32-1). Hense there are comparable.
Value is few bytes fixed size.

There are 4M items in the collection.
Keys are not evenly spread in the key space i.e there is no way to predict hole size between two consecutive keys.

This collection is created once and never modify after that, even if not prohibited.

The aim is to lookup a value by its key. But if key is not found then the previous one (as in integer natural order) must be returned.

I'm looking for a data-structure that can be mmap on disk which would be reasonably space efficient but most importantly very time efficient for
the lookup function.

There is no known pattern on how the keys are queried.

Make a table with 2^22 entries to lookup the highest 22 bits of the key. Each entry is responsible for one value on average (but may contain up to 1024).

Entry #i in the table, which is responsible for 0 to 1024 values with keys from 1024i to 1024i + 1023, contains the following: 1. The number of keys in that range. 2. If there are 0 keys, the value of the next lower available key. If there is 1 key, the lower 10 bit of the key in that range, and its value. If there are two or more keys, an index j into a second table.

In the second table, we store the lower 10 bit of the key, plus the value, for every key where there are two or more keys in the range from 1024i to 1024i + 1023. For values in the second table, we use binary search.


Input to make worst case on big O not possible? Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a function does it need to take into account what the meat of the code actually does? I have some code that would (in the worst case) iterate through a while loop n times, but when you consider what that code actually does, it would always make it so that the condition for the while loop becomes false on the next iteration.

Some people say that it doesn't matter what is actually happening within the code; just that if it has the ability to iterate n times (even though it's virtually impossible because of the body of the loop) then that would be the worst case vs. however many steps the code ACTUALLY runs.

If anyone has any insight it would be greatly appreciated! Thanks!

It matters what is actually happening in the code. The following pseudocode is O(1)

loop_factor = input()

for x between 0 and loop_factor():
    for y between 0 and loop_factor():
        terminate

However, it doesn't matter what is likely or reasonable to happen. If the body of your loop makes it "virtually" guaranteed that the loop will terminate next iteration, that means nothing; you need an actual hard proof that the loop will exit early for all input, no matter how absurd.

Essentially if you can rewrite your algorithm so that the loop clearly can't iterate n times without changing the meaning (i.e. replace the loop with just a few copies of the loop body in if statements, or something), then you are justified in saying that the loop isn't going to do n iterations. If you really need the loop to be there in the code as a loop that can iterate up to n times, then the big-oh complexity of the loop almost certainly does have to be n times the complexity of the loop body.


Finding the k-th smallest rational number efficiently Consider the following set:

$S := \left\{\frac{a}{b} \colon a \in \{1,\ldots,A\}, b \in \{1,\ldots,B\} \right\}$

$S$ is the set of all rational numbers that can be represented by two integers $a$ and $b$ that are bounded by $A \geq 1$ and $B \geq 1$. For the sake of simplicity, we can also think of $S$ as a multiset such that the number of elements in $S$ is given by $A \cdot B$.

Do you see any possibility how to find the $k$-th smallest number in $S$ in time $\mathcal{O}(\log (A \cdot B))$ ?

Clearly, the smallest number if given by $\frac{1}{B}$ and, as long as $B \geq 2$, the second smallest number is given by $\frac{1}{B-1}$. But then things are getting interesting...

It is perhaps more natural to consider the set $S$. Let us further consider the case $A = B = n$ and the set $S \cap [0,1] = \mathcal{F}_n$, the $n$th Farey sequence; if we know $|\mathcal{F}_n|$ and can solve the problem for $\mathcal{F}_n$ then we can also solve it for the entire $S$. The set $\mathcal{F}_n$ has size $\Theta(n^2)$.

The fastest algorithm known for finding order statistics (i.e., the $k$th smallest element) in $\mathcal{F}_n$, due to Patrășcu and Pawlewicz, runs in time $\tilde{O}(n^{2/3})$. This is much slower than the complexity you're interested in, $O(\log n)$.

It is possible that considering the multiset instead of the set makes the problem easier.


Algorithm to merge two incomplete lists of symbols (strings) into a complete one I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution.

Let's say we have two ordered lists of symbols (strings):

A = "foobarquuz123"
B = "foobar456quuz"

my goal is to have a way to merge the two incomplete lists into the following, completed with parts from both:

C = "foobar456quuz123"

As you can see there is no intrinsic "sorting value" associated to the symbols, only their position, which is just a relative measure. Moreover, the symbols might be also repeated in arbitrary points of the strings.

Maybe the algorithm I am looking for might have been used in bioinformatics, for example for DNA or protein sequence alignment, but I am no expert of this.

What would you recommend? Do you have some pointers to algorithms that may solve this problem? I think that someone should already have figured out a solution with upper-bound computational complexity $O(k(n+m))$ where $k$ is a constant and $n$ and $m$ are the lengths of the strings.

I would be very happy to get also suggestions for books that illustrate this and similar problems.

The problem is called shortest common supersequence. For an arbitrary number of strings it is NP-hard, but for two strings it can be solved efficiently:

First find the longest common subsequence of the two strings with dynamic programming, then insert the remaining characters.


How does an NFA use epsilon transitions? In the picture below, I'm trying to figure out what exactly this NFA is accepting.

What's confusing me is the $\epsilon$ jump at $q_0$.

If a $0$ is entered, does the system move to both $q_0$ and $q_1$ (the accept state)?
If a $1$ is entered, does the system move to both $q_1$ and $q_2$?
Does the system only move to $q_1$ (accept state), if no input is given (empty string)?

Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states, to simplify this to you:

If the string is $\epsilon$ then your automata ends both in $q_0$ and $q_1$

If your string is '0' it'll be again in $q_0$ and $q_1$

If your string is '1', it'll be only in $q_2$, because if you look from the point of $q_0$, you have a '1' transition to $q_2$, but you have also to look at case you're in $q_1$(if you were in $q_0$ you always were in $q_1$ also) then there is no '1' transition, so this alternative path just "dies".

Just by looking at these cases its easy to see that your automata accepts $\epsilon$, $0^*$, and going from $q_0$ to $q_1$, the only way to reach $q_2$ is $0^*11^*1$, so, this resumes your automata to $\epsilon$, $0^*$, $0^*11^*1$

Hope this helped you, if you have any further doubts, just ask!


Language Reduction for any Language Given two languages $L_1$ and $L_2$, give a language $L'$ that both $L_1$ and $L_2$ reduce to.

I'm not quite how to do this. I know the solution is fairly simple. I know I can somehow represent $L'$ in terms of $L_1$ and $L_2$. Then I need to create a computable function that maps $L_1$ to $L'$ and either use the same function, or create a separate function that maps $L_2$ to $L'$.

Hint: Try $L=0L_1\cup1L_2$. Can you see how to map $L_1$ to $L$ and $L_2$ to $L$? You have to be slightly clever; you might want to use prefixes other than 0 and 1.


Linear Speedup and Amdahl's law I'm having trouble understanding and solving the problem.
Suppose we have a program which is composed of 3 portions A, B and C and that each portion takes $t_A$, $t_B$ and $t_C$ respectively to run on a single-core CPU.
Assume that $t_A$ < $t_B$ < $t_C$
Assume we parallelize only the portion C of the code and that we run the whole program on a cluster that has up to $N$ cores. The speedup we achieve is linear to the number of cores.
I have to plot the execution time vs the number of cores
What I don't understand is, how can you have a linear speedup ? I've tried playing around with Amdahl's formula to find a way to have a linear speedup to the number of cores. I might be mistaken, but I've realized that this is only possible if the speedup is equal to the number of cores (so I don't understand how you can achieve a linear speedup).
If you could explain this to me, that would be very helpful, thank you.

The phrase

The speedup we achieve is linear to the number of cores.

refers only to the C portion of the program. Therefore the running time on $N$ cores is
$$ t_A + t_B + \frac{t_C}{N}. $$
The speedup is
$$
\frac{t_A + t_B + t_C}{t_A + t_B + t_C/N} =
\frac{1}{\frac{t_A + t_B + t_C/N}{t_A+t_B+t_C}} =
\frac{1}{\frac{t_A+t_B}{t_A+t_B+t_C}+\frac{1}{N} \frac{t_C}{t_A+t_B+t_C}}.
$$
This is Amdahl's law.


Determine endpoint of a graph given as a list of nodes + direct successors and predecessors EDIT @20190313

I can rephrase my question a follows : I am given everyday a non weakly-connected directed graph by its so-called adjacency list representation -- nodes are stored as objects, and every node stores a list of adjacent nodes, its direct successors and predecessors. The graph is in fact highly non weakly-connected, in the sense that the number of its weakly-connected components is quite big. I must everyday find the weakly-connected components of the graph and determine sink nodes of every weakly-connected components, and know from one day to the next any new sink node for every weakly-connected components. (From one day to the next, only new sink nodes might be added, with their associated edges.)

I fix a type T once for all. (Concretely, T is a c# class, but that doesn't matter.) On T I have the notion of direct successor and direct predecessor. (Imagine the two notions modelled byt two T × T --> bool functions.) The notion is nice in the sense that t' is a direct successor of t if and only if t is a direct predecessor of t'. For an object t of type T I note d(t) the set (in the usual sense) of its direct predecessors and successors.

Each day I receive an xml containing the list of all (xml representations) of objects of type t, the representation of t "containing" d(t).

For an object t and an integer k>0 I note S(t,k) (resp. P(t,k)) the set of rank-k successors (resp. predecessors) of t, this set being recursively defined as S(t,1) (resp. P(t,1)) being the set of direct successors (resp. predecessors) of t, and S(t,k) (resp. P(t,k)) being the set of direct successors (resp. predecessors) of object from S(t,k-1) (resp. P(t,k-1)). Finally I note F(t,k) the union of S(t,k) and P(t,k), and G(t) the union of all F(t,k) for k>1.

G(t) as defined is only a set, but can be turned into a graph as follows : each object of G(t) is a node, and two nodes t,t' are connected by an arrow going from t to t' if t' is a direct successor of t. The graph G(t) is connected by contruction and I note B(G(t)) its end points : the objects x in G(t) that don't have any direct successor (i.e. such that S(x,1) is empty).

I note X the set of all objects from the xml, and G1,...,GN all graphs. They obviously partition X.

My task is the following : every day, for any object t from X, I have to be able to determine the set B(G(t)) as fast as possible and the graph G(t) as fast as possible. (I can imagine that the two tasks may not necessarily be related.) Of course, every day I can save all graphs and their endpoints, if that could help for the task the next day.

(From one day to the next the only changes that occur are new direct successors added to objects that are endpoints and deaths (meaning that we know that the dead object will never have direct successors anymore until its rebirth) and rebirth (meaning that the object can now start to have direct successors.)

What are my options here ?

It appears this is an instance of "incremental graph connectivity".  There are very efficient algorithms for this.

First, let's identify the weakly connected graph components and keep track of them as the graph changes.  In undirected graphs, it's easy to keep track of connected components as you add vertices and/or edges, using a union-find data structure.  In particular, each time you add a vertex, you use the MakeSet function to put it in a component of its own, and each time you add an edge, you use the Union function to merge the two associated components.  You can use this to keep track of the weakly connected components in your directed graph.

This can be done $O(\alpha(n))$ time per operation (i.e., per vertex or edge added).

Your "ends" are normally called "sink vertices".  You can keep track of the "ends" of each weakly connected component by associating a doubly linked list with each component; that list contains all of the sink vertices in that component.  Also, each sink vertex should have a pointer to the placed in the doubly-linked list where it appears.  When you merge two components, you can concatenate their lists in $O(1)$ time.  Also, when you add an edge, you check if this turns a sink vertex into a non-sink; if so, you follow the pointer from that vertex to find its place in the doubly-linked list, and remove it from the doubly linked list.  This too can be done in $O(1)$ time.  In all, this takes an additional $O(1)$ time per vertex or edge added, which is dominated by the cost of the union-find data structure.


Finding largest subset that matches moments I would like to find a algorithm that will do the following:

Given two sets $A, B \subseteq \mathbb{R}$, where $|B| > |A|$, find the largest subset $C \subseteq B$, such that:
$\qquad |\operatorname{mean}(A) - \operatorname{mean}(C) |< \delta$ and
$\qquad |\operatorname{std}(A) - \operatorname{std}(C) | < \epsilon$

I think this problem is NP-hard, but I would like a good approximation that does reasonably well. An even harder version of this is to find the larget subset $C$ that matches not just the moments, but the histogram of $A$ to some quality metric. If you have a solution, or can point to same papers that would great!
I am a neuroscientist, and this is for my research.

I tried formulating this as an integer linear program, but ran into problems, because the variance is not a linear function: it is quadratic.

Here was my attempt.

Introduce variables $x_b$ (one for each $b \in B$), such that $x_b=1$ if $b \in C$ and $x_b=0$ if $b \notin C$.  Thus, we have $|B|$ new zero-or-one variables.  We can force them to be zero or one by adding the constraints $0 \le x_b \le 1$ for each $b \in B$.

Next, we'll force the mean of $C$ to be in the accepted range.  Introduce a new unknown $\mu$ and add the constraint

$$\mu = (\sum_{b \in B} x_b b)/|B|.$$

This forces $\mu$ to be the mean of $C$.  Also, it is expressible in a linear equation, since everything except for $\mu$ and the $x$'s are constants.  Finally, add the two linear inequalities

$$\text{mean}(A)-\delta \le \mu \le \text{mean}(A)+\delta.$$

But it's not clear how to force the standard deviation of $C$ to be in the accepted range.  Let $\sigma = \text{std}(C)$, i.e., $\sigma$ denotes the standard deviation of $C$.  We could try to use the fact that

$$\sigma^2 =  \frac{1}{N} \sum_{c \in C} c^2 - \frac{1}{N^2} \left( \sum_{c \in C} c \right)^2,$$

but now when we substitute in with our definitions of $x_b$, we get something ugly:

$$\sigma^2 =  \frac{1}{N} \sum_{b \in B} b^2 x_b - \frac{1}{N^2} \left( \sum_{b \in B} b x_b \right)^2,$$

where the right-hand term has something quadratic.  Worse still, $N$ also depends upon the $x$'s, which takes this even further away from something linear:

$$S = \sum_{b \in B} x_b.$$

Alternatively, we could try to use the fact that

$$\sigma^2 = \frac{1}{N} \sum_{c \in C} (c - \mu)^2,$$

but when we substitute in, again we get something that's not linear:

$$\sigma^2 = \frac{1}{N} \sum_{b \in B} x_b (b - \mu)^2,$$

where the non-linearity comes from the fact that $N$ is itself a function of the $b$'s, as well as the fact that the right-hand side involves a product of two linear variables ($x_b$ and $\mu$).

We want

$$\text{std}(A) - \epsilon \le \sigma^2 \le \text{std}(A) + \epsilon.$$

Plugging in, we find that we need

$$(\text{std}(A) - \epsilon)N \le \sum_{b \in B} x_b (b - \mu)^2 \le (\text{std}(A) + \epsilon)N.$$

This is not linear, because $x_b (b - \mu)^2$ is not a linear function of $x_b,\mu$.

We could deal with the fact that $N$ is not a constant by enumerating all candidate values of $N$ and solving an ILP for each.  However, that still doesn't deal with the problem that $x_b (b - \mu)^2$ is non-linear.

So, I'm stuck.  I wasn't able to formulate this cleanly as an ILP.


Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm? The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation.

The author then argues that this is a $log(n)$ time algorithm (where $n$ is the number of nodes in the list) because the span of nodes covered by the "far" pointer doubles on every iteration of the innermost loop. What I don't understand is why the author doesn't seem to factor in the time required for the first two lines of code after the begin statement, where a processor is assigned to each node in the list. Assuming the input to the algorithm is just a pointer to the header node to the linked list, wouldn't the assignment of processors require traversing each node in the linked list and thus take time linear in $n$? After all, each node in the linked list may be stored in some highly non-contiguous locations in memory identifiable only by following the chain of pointers from predecessor nodes in the list one at a time.

It seems this paper, which serves as a foundation for subsequent work on list ranking parallel algorithms, handles the oversight of assigning processors by assuming that the input is just given as an array containing the linked list (not necessarily in the order of the nodes in the list). This assumption of contiguous memory storage is implicitly followed in later papers such as this one.


Merge sort: sorting and merging complexity $\Theta(n)$ So this is the Master theorem for Merge Sort:

$$ T(n) = 2T(n/2) + \Theta(n). $$

I am not able to understand why is the time complexity for sorting and merging $\Theta(n)$.

Is sorting $O(1)$ and merging $O(n)$?

Each iteration of merge sort consist of 2 phases:

Merge Sorting the first and the second half separately.
Merging the two halves.

So in your equation phase 1 is represented by $2T(n/2)$. This means that merge sort is called on the two halves. This is a recursive call, which is why $T$ is used here.

Phase 2 is represented by $\Theta(n)$. Merging two lists of length $a$ and length $b$ takes $\Theta(a+b)$. In our case the two lists are both of size $\frac{1}{2}n$, so we get a total of $\Theta(n)$.

In the end we get that $T(n) = $ step 1 + step 2, resulting in
$T(n) = 2T(n/2) + \Theta(n)$


Can I simplify log(n+1) before showing that it is in O(log n)? Had a question about the following:

$$\log (n+1) \in O(\log n)$$

Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold?

Simplifying the left-hand side is a good strategy. You aren't going to find a simpler expression that's equal to $\log(n+1)$, though. However, since you're only interested in proving that $\log(n+1)$ is “not too large”, it can be a good strategy to find an intermediate step that's larger than $\log(n+1)$ but still not too large. That is, try to find a function $f$ such that $\log(n+1) \le f(n)$ (for sufficiently large $n$), and $f(n) \in O(\log n)$.

(Easy exercise: prove that this is true — if you've found a such a function $f$ then $\log(n+1) \in O(\log n)$.)

So you can try to fill in the statement $\log(n+1) \le \ldots$ with something simpler on the right-hand side. “Simpler” meaning that in the end it'll be simpler to prove that this is in $O(\log n)$. So keep the definition of $O$ in mind: you'll need to prove that $f(n) \le C \log n$ for some $C \gt 0$.

This suggests trying to find $f$ of the form $C \log(n)$.

Hint:

   $x + 1 \le x + x$

Hint #2:

   You can say that again.

Of course this approach works for other functions and other bounds.

Exercise (open-ended): can you generalize this to $\Omega$? To $\Theta$? To $o$?


How to read typing rules? I started reading more and more language research papers. I find it very interesting and a good way to learn more about programming in general. However, there usually comes a section where I always struggle with (take for instance part three of this) since I lack the theoretical background in computer science: Type Rules.

Are there any good books or online resources available to get started in this area? Wikipedia is incredibly vague and doesn't really help a beginner.

In most type systems, the type rules work together to define judgements of the form:

$$\Gamma\vdash e:\tau$$

This states that in context $\Gamma$ the expression $e$ has type $\tau$.
 $\Gamma$ is a mapping of the free variables of $e$ to their types.

A type system will consist of a set of axioms and rules (a formal system of rules of inference, as Raphael points out).

An axiom is of the form

$$\dfrac{}{\Gamma \vdash e:\tau}$$

This states that the judgement $\Gamma \vdash e:\tau$ holds (always).

An example is

$$\dfrac{}{x:\tau\vdash x:\tau}$$

which states that under the assumption that the type of variable $x$ is $\tau$, then the
expression $x$ has type $\tau$.

Inference rules take facts that have already been determined and build larger facts from them. For instance the inference rule

$$\dfrac{\Gamma\vdash e_1:\tau\to\tau' \quad \Gamma\vdash e_2:\tau}{\Gamma\vdash e_1\ e_2:\tau'}$$

says that if I have a derivation of the fact $\Gamma\vdash e_1:\tau\to\tau'$ and a derivation of the fact $\Gamma\vdash e_2:\tau$, then I can obtain a derivation of the fact $\Gamma\vdash e_1\ e_2:\tau'$. In this case, this is the rule for typing function application.

There are two ways of reading this rule:

top-down - given two expressions (a function and another expression) and some constraints on their type, we can construct another expression (the application of the function to the expression) with the given type.
bottom-up - given an expression that is, in this case, the application of a function to some expression, the way this is typed is by first typing the two expressions, ensuring that their types satisfy some constraints, namely that the first is a function type and that the second has the argument type of the function.

Some inference rules also manipulate $\Gamma$ by adding new ingredients into it (view-ed bottom up). Here is the rule for $\lambda$-abstraction:

$$\dfrac{\Gamma x:\tau\vdash e:\tau'}{\Gamma\vdash \lambda x.e:\tau\to \tau'}$$

The inference rules are applied inductively based on the syntax of the expression being considered to form a derivation tree. At the leaves of the tree (at the top) will be axioms, and branches will be formed by applying inference rules. At the very bottom of the tree is the expression you are interested in typing.

For example, a derivation of the typing of expression $\lambda f.\lambda x.f\ x$ is

$$\dfrac{\dfrac{}{f:\tau\to\tau',x:\tau\vdash f:\tau\to\tau'} \qquad \dfrac{}{f:\tau\to\tau',x:\tau\vdash x:\tau}}
{\dfrac{f:\tau\to\tau',x:\tau\vdash f\ x:\tau'}{
\dfrac{f:\tau\to\tau'\vdash \lambda x.f\ x:\tau'}{\vdash \lambda f.\lambda x.f\ x:\tau'}}}$$
Two very good books for learning about type systems are:

Types and Programming Languages by Benjamin Pierce
Practical Foundations for Programming Languages by Robert Harper

Both books are very comprehensive, yet they start slowly, building a solid foundation.


Disabeling interrupts to solve critical section issue on multiprocessor system Assume I have a multicore system and a critical section.

I understand how disableling interrupts on a single core systems solves the critical section problem.

So assume I could disable interrupts on all cores atomically (Why is that not possible?).
Why would that solve the problem?

As I understand, there would still be n processes running at the same time that may interfere with each other. They just wont be stopped until interrupts are enabled again.

Can somebody explain why that would (according to my professor) work?

We are generally concerned about controlling concurrent access to kernel data structures.  User-level processes don't have access to kernel data structures, so they can't do any harm from user space.  The only risks are (1) if a user process does a syscall or causes a context switch to kernel mode, (2) if an interrupt arrives.  (1) could be guarded by explicitly checking for a lock, or by other methods.  (2) could be guarded by disabling interrupts, if you had a way to disable them on all cores.


LBA for $L = \{a^nb^{2n} \mid n\geq1 \}$ I want to construct a linear bounded automata for the language $L = \{a^nb^{2n} \mid n\geq1 \}$ . I know how LBA works but I don't have an idea how it can count the numbers of a's and check if the b's are 2 times more than a's. I would like to to hear some suggestions.

Repeatedly remove an $a$ from the beginning and a $bb$ from the end until the string becomes empty. If you cannot do it at any point, reject, otherwise, accept.


Clarification on an Hopcroft book DFA minimization example At page 156 there is an example on how to find the distinguishable states for the following automaton:

The following table shows the distinguishable states:

By applying the given definition for distinguishable states, it is not clear why E and G are considered distinguishable. For my understanding there is at least one string, "110" for example, that make them distinguishable, but one cannot test all the possible strings.
I'm sorry if my question sounds dumb but I'm a beginner for this topic.

It looks like you missed the paragraph for induction right before the Example 4.19 or figure 4.9 and the repetitive application of that induction.

INDUCTION: Let $p$ and $q$ be states such that for some input symbol $a,$ $\ r =\delta(p,a)$ and $s = \delta(q,a)$ are a pair of states known to be distinguishable. Then $\{p, q\}$ is a pair of distinguishable states.

That induction is all we employ to fill the table of state inequivalences besides the fact that every accepting state is distinguishable from every non-accepting state. (The fact holds because the empty string distinguishes them.) That is, we will never check strings that are more than one symbol long.
For example, to find whether $E$ and $G$ are distinguishable, we need to just check either $0$ or $1$ distinguishes them. Assuming $E$ and $F$ are distinguishable, since on input $1$, $E$ go to $F$, while $G$ goes to $E$, we know $E$ and $G$ are distinguishable.
You might ask, how do we know $E$ and $F$ are distinguishable? By the same procedure. "Since $\{C, H\}$ is distinguishable, and states $E$ and $F$ go to $H$ and $C$, respectively, on input $0$".
Note that we may not be able to determine whether $E$ and $G$ are distinguishable right from the start by this procedure. We will try the pair $\{E,G\}$ again and again together with other pairs until we cannot find more distinguishable pairs. Although we may have to check the same pair for many times, the number of times is bounded by the number of distinguishable pairs and each time we will check just 2 possible distinguishing strings, $0$ and $1$. We have avoided testing "all the possible strings", which are infinite.
You may want to look at another explanation of Hopcroft's algorithm such as this Wikipedia article or the excellent illustration at tutorialspoint.


How can I show mathematically the time complexity of this function is O(N)? int foo(N){
   if(N <= 1){
       return 0
   }else{
       return 1 + foo(N-1)
   }
}

I can tell that the time complexity of this program is O(N) but I am unsure on how to prove it mathematically? If I can get some hints I'd grealy appreciate it.

You can use induction on input.
For example, in your foo,
to show that foo(N) uses exactly N comparisons,
Base case: foo(1) uses 1 comparison
Induction hypothesis: foo(N) uses N comparisons
Step case: foo(N+1) does one comparison and then call foo(N), thus in total, does N+1 comparisons.
You can prove similar statement for addition or all operations, and then you can give a time complexity based on those number of operations.


Complex/Hybrid data structures- do people ever combine structures like graphs and hash tables together? I just built a LRU cache that combines a hash table and a double linked list. To me it was a brilliant idea to combine those two structures and use the strengths of each together, so it got me thinking, can people or do people combine hash tables with other more complex data structures like trees and graphs? Are there use cases and what would they be called? I don't see much written about these on the usual sites like Wikipedia.
Obviously the hash table gives constant lookup time (or nearly so allowing for collision resolution), and the tree or graph gives you ways and means of doing traversals.
I know you can hang a new tree's parent node from every single hash entry but I mean having one tree main tree or graph overlayed and interconnected with one main hash table

I am convinced that in many practical cases such hybrid data structures are key to effectiveness, so I like your question pretty much!
There are many examples, and I would like to detail one that makes a true difference both in practice and in theory.
First, a bit of context. There are two main data structures for representing graphs: adjacency lists, where we have the list of neighbors for each vertex; and adjacency matrices, where we have a double-entry array in which cell $i,j$ tells if there is an edge between vertices $i$ and $j$.
Let us consider a graph $G$ with $n$ vertices and $m$ edges. In practice, $m$ is generally much lower than its maximal value $\frac{n\cdot (n-1)}{2} \sim n^2$. This makes adjacency lists appealing, because they need only $O(m)$ space, whereas adjacency matrices need $O(n^2)$ space. However, one cannot query edge existence in constant time in an adjacency list representation, whereas one can do this in an adjacency matrix. This is why the two approaches coexist in the wide world of graph algorithms, with some relying on adjacency lists, and some on adjacency matrices.
In some cases, though, it is possible to take advantage of the best of the two worlds. This is particularly true when one considers large graphs with heterogeneous degrees. The degree of a vertex is its number of neighbors. Heterogeneous degrees mean that there are vertices with only few neighbors, as well as some with many many neighbors. In practice, there are often many nodes with low degree, as well as few nodes with very high degree (and some nodes with intermediate degrees). This leads to the following idea: represent low degree neighborhoods by adjacency lists, and then parsing them is fast (as they are small); and represent each high degree neighborhors by an array of size $n$. If one carefully chooses which degrees are considered small and which are considered large, then it is possible to have a compact graph representation that allows very fast edge existence queries.
I used this approach in triangle listing/counting algorithms (triangles are sets of three vertices all linked together):
Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs
In this case, one may formally show that the algorithmic complexity depends on the way vertices are divided into low and high degrees. The practical benefit is huge too.


Permutation on matrix to fill main diagonal with non-zero values I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled with non-zero values. My matrices represent a set of linear equations and there is no problem to use permutations between rows and columns of my matrix to get a zero-less diagonal.

I do know that the matrix is non-singular so such a permutation must exist (otherwise the determinant would be null), however I searched on the internet and wasn't able to find anything relevant.

Here is an example were 0 denotes an null value and 1 any non-zero value.
I numerated the rows, the permutation only changes the rows:

(row)    (matrix)        (matrix, blanks are zeros)

original:
01    1000011110000000    |1    1111       |
02    0100010001110000    | 1   1   111    |
03    0010001001001100    |  1   1  1  11  |
04    0001000100101010    |   1   1  1 1 1 |
05    0000100010010110    |    1   1  1 11 |
06    0000000000001110    |            111 |
07    0000000000110010    |          11  1 |
08    0000000001010100    |         1 1 1  |
09    0000000110000010    |       11     1 |
10    0000001010000100    |      1 1    1  |
11    0000010010010000    |     1  1  1    |
12    0001100000000010    |   11         1 |
13    0010100000000100    |  1 1        1  |
14    0100100000010000    | 1  1      1    |
15    1000100010000000    |1   1   1       |
16    1000000000000001    |1              1|

permutated:
01    1000011110000000    |1    1111       |
02    0100010001110000    | 1   1   111    |
03    0010001001001100    |  1   1  1  11  |
04    0001000100101010    |   1   1  1 1 1 |
05    0000100010010110    |    1   1  1 11 |
11    0000010010010000    |     1  1  1    |
10    0000001010000100    |      1 1    1  |
09    0000000110000010    |       11     1 |
15    1000100010000000    |1   1   1       |
08    0000000001010100    |         1 1 1  |
07    0000000000110010    |          11  1 |
14    0100100000010000    | 1  1      1    |
06    0000000000001110    |            111 |
13    0010100000000100    |  1 1        1  |
12    0001100000000010    |   11         1 |
16    1000000000000001    |1              1|

Is there a smart way to perform those row/column permutations in order to get a main diagonal without zeros ? I am almost certain that there is a way to express this problem as a path-finding problem (visit all the columns once and only if the current line of a column is a non-zero value) but wasn't very successful.

You can use bipartite matching for that.

Nodes corresponding to rows in one set, nodes corresponding to columns in the other set. A row has an edge to every column in which it has a 1. If the maximum matching has size n, every row is matched up with a corresponding column and the matching gives the order. The index of the column that a row is matched up with will be its new position.


How do you obtain transition relation of a PDA? I know how to figure out the start state, accepting state, input alphabet, and all that stuff. But how do you develop the transition relation of a PDA? For an FSM, (q0,a),q1) means if you start at q0 and get an a, you transition to q1. But what does (S,a,e),(S,a) mean? (S is start state and e is epsilon)

Here's a picture if that helps. I want to understand the circled part. I will be extremely appreciative of any help.

As you can see, $\Delta$ is a set of pairs that represent a transition function.
First element of the pair is a triple $(q, a, X)$, where $q$ is a state, $a$ is an input symbol (possibly empty string), and $X$ is the top stack symbol.

The other element of the pair describes the action of PDA when its configuration fits the above triple. This other element is again a pair $(p, \gamma)$, where $p$
is a new state and $\gamma$ is a sequence of symbols replacing $X$. If $\gamma = \epsilon$, then $X$ is just popped.

It might help to view $((q, a, X), (p, \gamma))$ as

$$(q, a, X) \rightarrow (p, \gamma)$$


Context-free grammar for $L = \{a^n : n\leq2^{20}\}$ I want to find a context-free grammar for $L = \{a^n : n\leq2^{20}\}$. There's one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the new strings. But I don't think there's such a thing in CFGs. Second approach was to produce the strings of the language top-down. Starting from the last string $a^{2^{20}}$ and removing an $a$ each time till epsilon but I don't think that's achievable either. Any ideas?

As Karolis mentions, one solution is
$$
S \to \epsilon | a | a^2 | a^3 | \cdots | a^{2^{20}}.
$$
However, we can do better:
$$
\begin{align*}
&A_{20} \to A_{19} A_{19} \\
&A_{19} \to A_{18} A_{18} \\
&A_{18} \to A_{17} A_{17} \\
&A_{17} \to A_{16} A_{16} \\
&A_{16} \to A_{15} A_{15} \\
&A_{15} \to A_{14} A_{14} \\
&A_{14} \to A_{13} A_{13} \\
&A_{13} \to A_{12} A_{12} \\
&A_{12} \to A_{11} A_{11} \\
&A_{11} \to A_{10} A_{10} \\
&A_{10} \to A_9 A_9 \\
&A_9 \to A_8 A_8 \\
&A_8 \to A_7 A_7 \\
&A_7 \to A_6 A_6 \\
&A_6 \to A_5 A_5 \\
&A_5 \to A_4 A_4 \\
&A_4 \to A_3 A_3 \\
&A_3 \to A_2 A_2 \\
&A_2 \to A_1 A_1 \\
&A_1 \to A_0 A_0 \\
&A_0 \to a | \epsilon
\end{align*}
$$
The start symbol is $A_{20}$. You can prove by induction that $A_k$ generates $\{ a^n : n \leq 2^k \}$. If you want an even shorter solution, you can try
$$
\begin{align*}
&A_{20} \to A_{18} A_{18} A_{18} A_{18} \\
&A_{18} \to A_{16} A_{16} A_{16} A_{16} \\
&A_{16} \to A_{14} A_{14} A_{14} A_{14} \\
&A_{14} \to A_{12} A_{12} A_{12} A_{12} \\
&A_{12} \to A_{10} A_{10} A_{10} A_{10} \\
&A_{10} \to A_8 A_8 A_8 A_8 \\
&A_8 \to A_6 A_6 A_6 A_6 \\
&A_6 \to A_4 A_4 A_4 A_4 \\
&A_4 \to A_2 A_2 A_2 A_2 \\
&A_2 \to \epsilon|a|aa|aaa|aaaa
\end{align*}
$$
Many more options are possible, see which one you like most.

Comments:

In terms of number of symbols, a grammar based on powers of 2 is the most efficient.
This approach seems (at first) to work only for powers of 2, but in fact you can use the binary representation to handle any upper bound (exercise).


Is there a combinator that introduces brackets to a combinatory logic expression using just B? Suppose I have the expression $abcdef$ and I want a combinator $X$ that does this:

$Xabcdef=a(bcd)(ef)$.

Is it possible to express $X$ using just the $B$ combinator, defined by

$Babc=a(bc)$?

Is this possible in general? That is, if I have a string of letters without brackets, is there always a combinator in terms of $B$ only that parenthesizes my expression in the way I want, leaving the order of the letters unchanged?

$X=B(BBB)(BB)$ answers the first question. Indeed,

$B(BBB)(BB)abcdef=BBB(BBa)bcdef=B(B(BBa))bcdef=B(BBa)(bc)def=BBa(bcd)ef=B(a(bcd))ef=a(bcd)(ef).$

For the second question, yes, this may be done in general. Here's a rough proof: if we have $Xabc\ldots xyz = (\textrm{expr})(yz)$, this becomes $Xabc\ldots xyz=B(\textrm{expr})yz$, so $Xabc\ldots x = B(\textrm{expr})$. If $(yz)$ is nested inside other brackets, like, for example, $Xabc\ldots xyz=(\textrm{expr})(x(yz))$, we get $Xabc\ldots xyz=B(\textrm{expr})x(yz)=B(B(\textrm{expr})x)yz$, and again we may then consider just $Xabc\ldots x=B(B(\textrm{expr})x)$. We may then do a further step: $Xabc\ldots x=B(B(\textrm{expr})wx)=BB(B(\textrm{expr}))x$, which means that $Xabc\ldots w=BB(B(\textrm{expr}))$. Continuing doing this, we end up with just $X$ on the left hand side and an expression involving (possibly bracketed) $B$'s on the right hand side.


In which environment we use NFA(Non Deterministic Finite Automata)? We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?

The NFA is simpler to construct and manipulate.

The equivalent DFA of a n-state NFA can have up to 2^n states in the worst case.

For these two reasons the NFA is the preferred state machine for most real implementations dealing with regular languages.

The non-determinism is dealt with using either backtracking or or simulating multiple states at the same time (this last one can be seen as constructing the states of the equivalent DFA on the fly).


Turing machine where the next step is determined by the state and the symbols up to the read/write head Given a modified type of turning machine where

$\delta = Q\times \Gamma^* \implies Q\times \Gamma \times \{L,R\}$

where the next step of the machine is determined by the current state and whatever written on the tape up to the current point.

For example: if the tape content is $a\_ab\_\$\$a$, and the head is on the left \$, then the next step is determined by the state and the word $a\_ab\_\$$.

How can I prove that unrecognized languages can be recognized with these types of machines?
Do those machines contradict the Church–Turing thesis?

Suppose we are given a language $L$ of words of finite length. We will construct machine $M_L$ that runs as the following.

$M_L$ starts at state $q_0$. On input $x$ of finite length that is put to the right of its head, $M_L$ will move right all the way to the end of input, keeping the input and state intact. (This might mean nothing if the input is empty.) When $M_L$ read the first blank symbol, what is written on the tape up to the current point exclusive is exactly the input $x$. (If current point should be included, let $M_L$ go back a cell.) It halts, changing state to

$q_1$, an accepting state if $x\in L$,
or $q_2$, a rejecting state otherwise.

It is clear that $M_L$ decides $L$.

Well, it is reasonable to say that that $M_L$ does not compute $L$ at all. $M_L$ just knows effectively each and every word in $L$ without any computation. When $L$ is infinite or even undecidable, we are not able to build or truly simulate such a machine within any bounded time by any known physical means and intelligence. Hence, we would not believe those imaginary machines contradict the Church–Turing thesis.

Exercise.  Given a modified type of turning machine where

$$\delta: Q\times \Gamma^* \to Q\times \Gamma \times \{L,R\}$$

where the next step of the machine is determined by the current state and the content of last $\lceil\log_2n\rceil$ cells that has been read by it, where $n$ is the number of steps the machine has run. Can some unrecognized languages be recognized with these types of machine?


Number of ways of tiling a 3*N board with 2*1 dominoes problem I came across this problem,
 Tiling with Dominoes
and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a doubt, why aren't we considering the below cases for the above problem?

In the solution only these cases are mentioned,

********   AA*******   AA******   A*******
******** = BB******* + B******* + A*******
********   CC*******   B*******   BB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)

But my question is there can be other case as well, like below, why aren't we adding them, because the problem asks for the number of possible cases-

********   AA*******   AA******   A*******   AB******   CC******
******** = BB******* + B******* + A******* + AB****** + AB******
********   CC*******   B*******   BB******   CC******   AB******
  f(n)   =  f(n-2)   +  g(n-1)  +  g(n-1)  +   f(n-2) +  f(n-2)

Why aren't we adding them? Thanks for your help.

These two cases are already counted in the recursive calls g(n-1).

A****
A****
BB***
g(n-1)

g(n-1) counts all possibilities to fill the empty space in this ^ form. One way would be to fill it out like the following image, so this case already gets counted and you don't need to add another recursive call.

AC***
AC***
BB***


Infinite Union operation of Formal Languages Is every formal language  not closed under infinite union operation ?
I know that Regual Languages are not closed under infinite union operation and I have counter-example for it but I don't have any counter-example for other languages. Intuitively , I think it should not be closed but intuition could be wrong also. So please clarify whether every language (like DCFLs,CFLs , Recursive , Recursively Enumerable)  is closed or not under infinite union operation.

Virtually every standard language class contains singleton languages, e.g. those languages containing exactly one word ($L_w = \{w\}$).

If a class containing every $L_w$ were closed under infinite union then it would contain any arbitrary infinite language $L$ since

$$
L = \bigcup_{w\in L} L_w
$$

More in general, we can write any language (finite or infinite) using an infinite union of singletons or empty languages.

$$
L = \bigcup_{w \in \Sigma^*} \{w\ |\ w\in L\}
$$

where $\{w\ |\ w\in L\}$ is $\{w\}$ when $w\in L$ and the empty language otherwise. (I wish set comprehensions had a standard notation for free and bound variables! Here, $w$ is free.)


I have a problem understanding a solution for number theory problem from SPOJ Problem statement can be found here or down below.

The solution which I'm trying to understand can be found here or down below.

Problem Statement.

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

Example
Input:
2
1 10
3 5

Output:
2
3
5
7

3
5

Solution

Concept: The idea behind solution here is to generate all the prime numbers that could be factors of numbers up to the maximum endpoint 1 billion. That square root happens to be around 32000. Using this array, do a bounded Sieve of Eratosthenes only in the range requested.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main() {
int primes[4000];
int numprimes = 0;

primes[numprimes++] = 2;
for (int i = 3; i <= 32000; i+=2) {
    bool isprime = true;
    int cap = sqrt(i)+1;
    for (int j = 0; j < numprimes; j++) {
        if (primes[j] >= cap) break;
        if (i % primes[j] == 0) {
            isprime = false;
            break;
        }
    }
    if (isprime) primes[numprimes++] = i;
}

int T,N,M;
scanf("%d",&T);

for (int t = 0; t < T; t++) {
    if (t) printf("\n");
    scanf("%d %d",&M,&N);
    if (M < 2) M = 2;

    int cap = sqrt(N) + 1;

    bool isprime[100001];
    memset(isprime,true,sizeof(isprime));

    for (int i = 0; i < numprimes; i++) {
        int p = primes[i];

        if(p >= cap) break;

        int start;

        if (p >= M) start = p*2;
        else start = M + ((p - M % p) % p);

        for (int j = start; j <= N; j += p) {
            isprime[j - M] = false;
        }
    }

    int start = (M % 2)?M:M+1;

    if (M == 2) {
        printf("2\n");
    }
    for (int i = start; i <= N; i+=2) {
        if (isprime[i-M]) printf("%d\n",i);
    }
}
return 0;
}

I know how Sieve of Eratosthenes works and I also ran this program using pen and paper. It works fine but I 'm not able to understand why it works and how do I prove that this program and the algorithm used in it are right?
I spent hours but could not prove.
Any help would be appreciated.

A number is prime if it has no non-trivial factors. In order to check whether a number $n$ is prime, it suffices to check that it has no factors in the range $2,\ldots,\sqrt{n}$. In order to find all primes in $[a,b]$, we go over all primes in $2,\ldots,\sqrt{b}$ (using a list prepared ahead of time), and for each such prime $p$, we mark off all multiples of $p$ in $[a,b]$. After going over all such primes, the unmarked numbers in $[a,b]$ are prime.

How do we mark off all multiples of $p$ in $[a,b]$? We mark off the first multiple $p \lceil a/p \rceil$ (computed in a funny way in the code), if it happens to fall inside the interval (but not if this multiple happens to be $p$ itself!), and then we mark off the remaining multiples, by jumping in steps of $p$ until we fall off the interval $[a,b]$.


What is wrong with this seeming contradiction with a paper about AND-compression of SAT? Got a simple construction seemingly contradicting a paper assuming plausible conjecture.

Since it is unlikely the conjecture to be false, what  is wrong with the argument?

From a paper

  An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x_1,\dots,x_t$ to a single SAT-instance $y$ of size $\text{poly}(\max_i |x_i|)$ such that $y$ is satisfiable if and only if all $x_i$ are satisfiable. ... Unless the unlikely complexity-theoretic
  collapse $\sf coNP \subseteq NP/poly$ occurs, there is no AND-compression for SAT.

Construction:

If $x_i$ are not in CNF, convert them to CNF possibly
adding new variables. This is polynomial.

In CNF one can encode AND gate $ C := A \land B $
and OR gate $ C := A \lor B $.

The AND and OR gates have the property that for all satisfying
assignments of their CNFs we have $C \iff (A \land B)$
and $C \iff (A \lor B)$.

Let the $j$-th clause in $x_i$ be $x_{i,j} = [y_1, \ldots, y_k]$
for literals $y_m$.

Using the OR gate and new variables, compute variable
$O_{i,j} := y_1 \lor y_2 \cdots \lor y_k$.

For all clauses in $x_i$ ($O_{i,j}$) and the AND gate compute variable
$V_i := O_{i,1} \land O_{i,2} \land \cdots \land O_{i,m}$.

By construction $x_i \iff V_i$.

For all $V_i$, using the AND gate compute $F := V_1 \land \cdots \land V_t$.

$F \iff x_1 \land \cdots \land x_t$.

So the final formula $y$ is the union of the CNFs for $O_{i,j}$,$V_i$,$F$,
and a unit clause $[F]$.

$|y|$ is linear in the number of all literals, $t$ is polynomial
in $\max |x_i|$, which makes $|y|$ polynomial in $\max |x_i|$.

This appears to contradict the claim in the paper,
unless the certain collapse happens.

  What is wrong with this argument that appears to contradict the claim in the paper?

Similar construction works for OR-compression, when
at least one $x_i$ must be satisfiable.

The newly introduced variable are uniquely determined
by the original variables.

OR gate in  CNF 3 := 1 \/ 2 : [[1 2 -3],[-1 3],[-2 3]]
AND gate in CNF 3 := 1 /\ 2 : [[-1 -2 3],[1 -3],[2 -3]]

The confusion arises from a misunderstanding of what being polynomial in the size of the largest instance means.  It does not mean that polynomial growth of the compressor's output is allowed as the number of instances ($t$) increases.  Rather it means the compressor's output is allowed to grow only as the maximum instance size grows, independent of $t$, and then only within a fixed polynomial of that value.

Your compressor concatenates the CNF instances, converts them to circuits, and then converts the circuits back to CNF.  Its output grows linearly with the number of instances ($t$) independent of the instance sizes and is therefore bound to exceed any polynomial function of the maximum instance size.  Because of this, indeed because it does not do any compression at all, your compressor does not cause any hierarchy collapse.

There also seems to be a misunderstanding as to what the AND-compressor function is supposed to do.  It does not have to output an instance that preserves all satisfying assignments for all the input instances, nor does there need to be a parsimonious counting reduction from the input instances to the output instance.  A conforming implementation could at the extreme output an empty instance if all the input instances are satisfiable and a single empty clause otherwise.

A more plausible AND-compressor might adapt standard data compression techniques such as the use of a dictionary.  A table of unsatisfiable subformulas could be precomputed and used to search against the input SAT instances.  A match would imply a forbidden variable assignment, which when instantiated as a learned clause might subsume (eliminate) several other clauses.

Another technique involves taking advantage the different sizes of the input instances.  If the input instances are of different sizes, the larger instances could be searched for subformulas equivalent to one of the smaller instances.  Such a match implies the existence of a variable assignment that could produce the subformula, and therefore the larger instance is satisfiable if the smaller instance is satisfiable.  If the smaller instance is unsatisfiable, the larger instance might still be satisfiable but it doesn't matter because compressor output should still produce an unsatisfiable formula.  So the output instance is effectively decoupled from the satisfiability of the larger instance and thus the larger instance no longer has to be represented in the output at all, eliminating a large number of clauses.

There are many other techniques.  The theorem in the paper suggests that efficiently achieving high levels of compression is unlikely given the implied partial collapse of the polynomial hierarchy.


Find Number of even subarrays $O(n)$ [explanation needed] So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must be even or even + even or odd + odd. However, I am not sure how this person manages to take into account the fact that these subarrays need to be contiguous and how just tracking the number of cumulative sums that are even/odd as you iterate through the array is good enough

Outlining his algorithm:

initialize sum, odds to 0 and evens to 1.
iterate through the array.

at each index i, do sum = (sum + A[i]) % 2

if sum is 0, increment evens, else increment odds

Lastly, return (evens * (evens - 1) / 2) + (odds * (odds - 1) / 2)

The algorithm works... I just have no idea how.

Let $S_i$ be the sum of the array upto index $i$. Then we can directly calculate the sum of any contiguous subarray $x_i, x_{i+1}, ..., x_{j}$ using the expression $S_j - S_{i-1}$. This subarray will have even sum only if  $S_{i-1}$ and $S_j$ are both even or both odd.

With this in mind, we can count how many even and odd $S_i$ we have and then calculate the number of possible pairs of $S_i$ and $S_j$ that yield an even number. So if we have $e$ even $S_i$ then there are $e \choose 2$ possible pairs. Each pair, corresponds to a different contiguous subarray.

$$
{e \choose 2} = \frac{e!}{(e-2)!2!} = \frac{e * (e-1)}{2}
$$

Same holds for the pair of odds.


An independent d-division I would love to have a direction for the following exercise (the material for this exercise is greedy algorithms):
Let $G = (V,E)$ an undirected graph whose vertices $V = \{v_1,\dots,v_n\}$ appear in this order on the real line (meaning forall $1 \leq i < j \leq n$, $v_i$ appears before $v_j$).
A $d$-divison of $G$'s vertices is a division into $d$ different intervals, meaning the choice of $d-1$ indices $1 \leq i_1 < i_2 < \dots < i_{d-1} < n$ which define the intervals:
$$ [v_1,\dots,v_{i_1}], [v_{i_1+1},\dots,v_{i_2}],\dots,[v_{i_{d-1}+1},\dots,v_n]. $$
A $d$-division is called independent if there are no two neighboring vertices in the same interval. Meaning, the division is independent if forall $0 \leq r < d$ and forall $i_r < j_1 < j_2 \leq i_{r+1}$ we have $\{v_{j_1},v_{j_2}\} \notin E$, where $i_0 = 0$ and $i_d = n$.
Offer an algorithm with time complexity $O(V+E)$ that finds an independent $d$-division of $G$ such that $d$ is minimal. Prove the correctness of the algorithm.
Notice: The division in this exercise is "continuous". For instance, if $v_1$ and $v_3$ are on the same interval, then $v_2$ is on the same interval with them. Also, there are no edges between any two vertices in the same interval. For instance, if the first interval in the division is $[v_1,v_2,v_3]$, then $\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_1\} \notin E$.
Thanks a lot,

Think about what happens when you manage to find the first interval, say it is $[v_1,...,v_k]$ for some $k$. Then what would you be able to say about the minimal division of $v_{k+1},...,v_n?$
Think also about how you could find the first interval. Starting from an empty interval and expanding it (how?) should do the trick.


Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it? I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ?
I don’t have specific topic that I care more about than others (like cryptography) ,Just CS.

Discrete mathematics, linear algebra, calculus, and probability are all used pretty much everywhere in computer science. Basically, discrete maths is the basis of everything, while linear algebra and calculus are used in specific areas of computer science, and there are various places you will see probability.
Probability is usually used to describe randomness in your algorithms, and therefore is used quite a lot. Basic knowledge of probability and expected value of random variables is usually enough.
Calculus is used mainly in optimization and machine learning problems (but you can still see it elsewhere).
Linear algebra, and specifically matrices from it are especially useful. You might not need the entire course for every application of it in computer science, but it will be very useful in machine learning.
I know there are other mathematical topics that can be useful for computer science, like  group theory, but I don't have experience with them to tell you what they are used for.
Also, there is no need to learn everything at once! You will start the math topics appear only in more advanced courses.


Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$ I have encountered two questions related to npda:

Construct an npda for $L_1 = \{a^{2n} b^n \mid n \geq 0\}$ as a language over $\Sigma = \{a,b,c\}$.
Construct an npda for $L_2 = \{w \in \{a, b, c\}^* \mid n_a(w) = 2n_b(w)\}$.

What is the difference between the above two languages?

The usual definition is that $n_a(w)$ refers to the number of $a$s in $w$.

Based on this definition, $L_1$ consists exactly of words that begin with an even number of $a$s followed by half as many $b$s (no $c$s are permitted). Therefore, you have $\varepsilon, aab, aaaabb, aaaaaabbb,... \in L_1$.

Whereas $L_2$ consists of words containing an even number of $a$s and half as many $b$s (in any order and with an arbitrary number of $c$ in between).

Thus every word in $L_1$ is also in $L_2$ (formally $L_1 \subseteq L_2$), but there are words in $L_2$ that are not in $L_1$:

For some $n \geq 0$, consider words of the form $b^n a^{2n}$. They are in $L_2$, because they contain an even number of $a$s and half as many $b$s, but if $n > 0$, then it does not match $a^{2n} b^n$, because the $a$s come after the $b$s. You have $\varepsilon, baa,bbaaa,bbbaaaaaa,... \in L_2$, but $baa,bbaaa,bbbaaaaaa \notin L_1$.
The same argument applies for $w = (aab)^n$. You have $\varepsilon, aab,aabaab,aabaabaab \in L_2$, but $aabaab,aabaabaab \notin L_1$.
A word can have an even number of $a$s and half as many $b$s and also contain $c$s. For example, $a^{2n} b^n c \in L_2$. But the words in $L_1$ by definition only contain $a$s and $b$s.


Is "Find a Steiner Tree of cost < K" NP-hard? Finding the minimum Steiner tree is well known NP-hard.
It seems obviois that asking "find a Steiner tree of cost < K" has to be NP hard, because I could solve the original problem by repetedly calling an algorithm that solves the second. But is this "repeteadly call"/loop a valid reduction? There seems to be something fishy with it, isn't it exponential in the number of bits of K (like the famous knapsack DP algorithm)?

Thanks

In fact, the optimization version of minimum Steiner tree isn't NP-hard, since only decision problems can be NP-hard. When we say that a minimization problem like minimum Steiner tree is NP-hard, what we mean is that the corresponding decision version is NP-hard. The decision version is just what you wrote: given an instance of minimum Steiner tree and a number $K$, to decide whether the minimum Steiner tree has cost at most $K$.


Complexity of an algorithm for bounding a region in 2D First I apologize if the title is unclear, but I didn't find anything better.

I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real numbers. For some points of the plane (or, equivalently, for some parameters of the differential equation) , the solution of the equation satisfies some condition and we denote such points of the plane with 1. This points make a simply-connected region in the plane, and I know that this region lies somewhere in $0<x<1.6, -.7<y<.3$ rectangle. My goal is to find this region.Remember that this region is on the real plane.($\mathbf R^2$)

My main question is this: I already know these two things about the wanted region:

The set of points on the plane that satisfy the conditions (the wanted region) , form a simply-connected region
This region lies somewhere in $0<x<1.6, -.7<y<.3$ rectangle

for example it may be something like this:

I want to use this two facts to find the region with less computations; i.e. instead of checking the condition on all points on the rectangle, actually , on a very high-resolution grid (this the first approach below), use an algorithm (below : Variant 2) that more quickly converges to the boundary (and so determines the region without inspecting all points).

(If you know a better approach ,I'll be happy to hear)

Variant 1 (the naive approach, noted above)

Divide each axis to identical steps (of length $\Delta$ ) and check the condition on each node to find the region.$\Delta$ must be as small as possible to find the region with an acceptable accuracy ($\Delta0.001$ suffices for my purpose) . (in the picture : nodes = intersections). This method needs a huge number of check operations , but can be used to find all kinds of regions; I mean if I didn't know that the wanted region is connected or it had sharp edges, etc. ,this method was the only way.

Variant 2

(It may be a famous method, but I haven't seen it before)

Because the region will be simply connected, it suffices to find its boundary .We use a recursive approach. We start from a grid (like the first step, but with much larger distance between nodes, say, $100\Delta$) and check the condition on this grid.For the next step, I assume the interval between two adjacent 1s is 1 everywhere and between two adjacent 0s is 0 everywhere. If two adjacent nodes gave different results (1 on one them and 0 on the other) , I put a point between them and check the condition on that point (red points in the picture) check this point. If it was 1, I put a new point between this point and the adjacent 0 and check that point; and if it was 0, I put a new point between this zero and adjacent 1 and check that point. I continue till I arrive at a distance of $\Delta$ between points.So I've found the boundary. (This method is like bisection method  for finding the roots of a function)

In the picture, the first iteration is shown.Black and yellow points are the points of the initial grid (that are distributed on the whole rectangle) and red points are those that are added after checking the initial grid nodes. Black points are points that are determined to satisfy the condition (are 1) and so are certainly inside the region. Yellow points are those that did not satisfy the condition and so are outside, and red points are those added in the 2nd iteration , between adjacent nodes with different results (between a 1 and a 0) ,according to the  above paragraph.

So , using this method I've found the region with the same accuracy as in the first method, and saved a lot of time too.

I want to know how much this method is faster. A qualitative answer that shows if it is better to implement this method , suffices. My problem is so computational intensive that I can't use the first approach.

This question is not well-posed.  You haven't told us what form you want the answer in, nor what you know about the region.  In the fully general case, this problem is not solvable in any finite amount of time: there are uncountably many possible regions, so you can't even describe all of them in finite space.

Perhaps what you want is an approximation to the region (or to its perimeter).  If so, you need to figure out how you want it to be described, and what approximation metric you are using.

A plausible approach is to find a bounding box, then sweep a vertical line from left to right.  If your region is convex, then given the vertical line $x=1$ (say), you can find all points on that line that lie within your region by using binary search (twice): the result will be that all points $(x,y)$ satisfying $x=1$, $f(1)\le y \le g(1)$ are in the region, for some values $f(1),g(1)$.  Now if you know that all of the points in your region lies satisfy $1 \le x \le 5$, you can iterate over values of $x$, from $1$ to $5$ by steps $\epsilon$, and find the values of $f(x)$ and $g(x)$ for each such $x$.  This gives you about $8/\epsilon$ points on the perimeter of the region.  Now, you could interpolate along these points somehow to get a plausible approximation to the shape of the region.

Whether this is good enough will depend upon your particular application and what you are trying to accomplish.  Since you haven't told us that, we can't evaluate whether this is an adequate solution for your needs.  (That, incidentally, is why the question is not well-posed.)


Context-free language and regular expressions I have the following context-free language:

S -> ASa | b
A -> aA | a

I don't understand why this is not regular. I first said that it's generated by the regular expression a+ba+. The following is regular however

S -> ASa | b
A -> aA | e

e stands for the empty string. I don't understand their differences.

The subtlety is that in the first case, the number of $a$'s before the unique $b$ must be at least the number of $a$ after, i.e. your language is $\{a^nba^m|n\geq m\}$, so it is not regular. This is because each $A$ produces at least one $a$.

In the second case however, this constraint disappears, and your language becomes indeed $b+a^*ba^+$ which is regular.


If NP is a subset of DTIME[n^O(log n)] then what happens? If $\mathsf{NP}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$ then what happens? Does it imply $\mathsf{NP}\neq \mathsf{EXP}$? Is there any other consequences such as $\mathsf{BPP}\neq \mathsf{EXP}$? Does it also give $\mathsf{PSPACE}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$?

If $\textbf{NP} \subseteq \textbf{DTIME}(n^{O(\log n)})$, then we get $\textbf{P}^\textbf{NP} \subseteq \textbf{P}^{\textbf{DTIME}(n^{O(\log n)})} = \textbf{DTIME}(n^{O (\log n)})$. Continuing this reasoning, the entire polynomial hierarchy $\textbf{PH}$ is contained in $\textbf{DTIME}(n^{O(\log n)})$. By the time hierarchy theorem, $\textbf{DTIME}(n^{O(\log n)})$ is a proper subset of $\textbf{EXP}$ (and even of $\textbf{E} = \textbf{DTIME}(2^{O(n)})$), so $\textbf{PH} \neq \textbf{EXP}$. In particular, we also get $\textbf{NP} \neq \textbf{EXP}$ and $\textbf{BPP} \neq \textbf{EXP}$ because both $\textbf{NP}$ and $\textbf{BPP}$ are in the polynomial hierarchy. For $\textbf{BPP}$ this is not that surprising since we already suspect it is contained in subexponential time.

What happens for $\textbf{PSPACE}$? Not much, as long as I'm aware of. We have $\textbf{PH} \subseteq \textbf{PP}$ and $\textbf{PH} \subseteq \textbf{P}^\textbf{#P}$ (by Toda's theorem), but I don't see any direct consequence for $\textbf{PP}$, let alone $\textbf{PSPACE}$.


Efficient insertion of deterministic acyclic finite state automaton (DAFSA) into a full-text search index? I have a problem where I can easily construct a set of deterministic acyclic finite state automata (DAFSA) and I need a full-text search index, e.g. a suffix tree/array, over all the words encoded by these automata.
Is there an efficient algorithm for this? By efficient I mean that the complexity must not depend on the on the total number of words encoded in the DAFSA which may get very large. Consider the following example:
(all edges are directed from left to right)

  a1 --- a2 ... a{n-1} --- an
 /   \ /               \ /   \
S     X                 X     T
 \   / \               / \   /
  b1 --- b2 ... b{n-1} --- bn

In this example there are $2^n$ distinct paths from S to T, e.i. if the nodes were labelled with characters it would be an DAFSA encoding $2^n$ words. Still, the number of vertices is just $2(n+1)$ and the number of edges $4n$.

There is (probably) no such algorithm. At least, for suffix tries it is not possible:
For every word encoded by the DAFSA there must be at least an end-of-word marker in the suffix tree. Thus, the construction takes at least $\Omega(N)$ where $N$ is the number of words encoded by the DAFSA.
This argument cannot be extended to any kind of search index because it may employ some kind of compression – like the DAFSA does.


Algorithm to solve Turing's "Halting problem" "Alan Turing proved in 1936 that a general algorithm to solve the
  halting problem for all possible program-input pairs cannot exist"

Can I find a general algorithm to solve the halting problem for some possible program input pairs?

Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?

Can I find a general algorithm to solve the halting problem for some possible program input pairs?

Yes, sure. For example you could write an algorithm that returns "Yes, it terminates" for any program which contains neither loops nor recursion and "No, it does not terminate" for any program that contains a while(true) loop that will definitely be reached and doesn't contain a break statement, and "Dunno" for everything else.

  Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?

Not if that language is Turing-complete, no.

However there are non-Turing complete languages like for example Coq, Agda or Microsoft Dafny for which the Halting Problem is decidable (and in fact is decided by their respective type systems, making them total languages (i.e. a program that might not terminate will not compile)).


Semantics of Regex with boundary matchers The regex /^(abc)$/ matches abc but why not abcdabc, abcdabc also begins with abc and ends with abc.

I am not sure about the semantics of this regex. Any explanation is welcome.

First of all, what we usually call Regex, for instance, in the context of programming languages, is not the same as pure regular expressions. That should not come as a surprise: all computational models have to be adapted to the real world to be made useful. In this case, besides being enriched by features that just enlarge the range of languages it can specify (such as numbered back references), Regex has other features that would require a completely different set of tools to be formalized properly.

What comes after ^ will not be matched to a prefix of the input string. What happens is that ^ is a reference to an event (as is $, they are called anchors). In abstract terms, you can think of the input of a Regex as continuous stream of symbols, unbounded, that is divided in units of limited size, separated from each other by a special symbol. Where should the matching process begin? This is where anchors come to the rescue.

In this context, ^ refers to the event of finding the special symbol, and forcing the Regex to match beginning with whatever comes right after, instead of $\unicode{x2013}$ for instance $\unicode{x2013}$ continuously trying to match a string starting with each symbol from the input, and backtracking to the next, in case of failure.

What the actual input unit is, pragmatically, depends on the context of application of the formalism. Usually we are talking about lines in a text file, separated by line break characters, or the successive contents of an input buffer.


Minimizing the total variation of a sequence of discrete choices My setup is something like this: I have a sequence of sets of integers $C_i (1\leq i\leq n)$, with $|C_i|$ relatively small - on the order of four or five items for all $i$.  I want to choose a sequence $x_i (1\leq i\leq n)$ with each $x_i\in C_i$ such that the total variation (either $\ell_1$ or $\ell_2$, i.e. $\sum_{i=1}^{n-1} |x_i-x_{i+1}|$ or  $\sum_{i=1}^{n-1} \left(x_i-x_{i+1}\right)^2$) is minimized.  While it seems like the choice for each $x_i$ is 'local', the problem is that choices can propagate and have non-local effects and so the problem seems inherently global in nature.

My primary concern is in a practical algorithm for the problem; right now I'm using annealing methods based on mutating short subsequences, and while they should be all right it seems like I ought to be able to do better.  But I'm also interested in the abstract complexity — my hunch would be that the standard query version ('is there a solution of total variation $\leq k$?') would be NP-complete via a reduction from some constraint problem like 3-SAT but I can't quite see the reduction.  Any pointers to previous study would be welcome — it seems like such a natural problem that I can't believe it hasn't been looked at before, but my searches so far haven't turned up anything quite like it.

Here is a dynamic program. Assume that $C_i = \{C_{i_1}, \ldots, C_{i_m}\}$ for all $i \in [n]$ for the sake of clarity; the following can be adapted to work if the $C_i$ have different cardinalities. Let $\operatorname{Cost}(i, j)$ be the minimum cost of a sequence over the first $i$ sets, ending with $C_{i_j}$. The following recursion describes $\operatorname{Cost}$:

$\qquad \displaystyle \begin{align}
  \operatorname{Cost}(1,j) &= 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad, 1\leq j \leq m \\
  \operatorname{Cost}(i,j) &= \min_{k = 1}^m \left(\operatorname{Cost}(i - 1, k) + \lvert C_{(i-1)_k} - C_{i_j} \rvert\right) \ , 2 \leq i \leq n, 1 \leq j \leq m.
\end{align}$

The overall minimum cost is $\min_{j = 1}^m \text{Cost}(n, j)$; the actual sequence of choices can be determined by examining the argmins along the way. The runtime is $O(nm)$.


How to find the Big-O for finding combinations of balanced parentheses? Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be:

def count_parenthesis(n, opened, closed):
  if closed == n:
    return 1

  num_pairs = 0

  if opened < n:
    num_pairs += _count_parenthesis(n, opened + 1, closed)

  if opened > closed:
    num_pairs += _count_parenthesis(n, opened, closed + 1)

  return num_pairs

Calling count_parentheses(3, 0, 0) results in the following call tree:

count_parenthesis(2, 0, 0)
  count_parenthesis(2, 1, 0)
    count_parenthesis(2, 1, 1)
      count_parenthesis(2, 2, 1)
        count_parenthesis(2, 2, 2)
  count_parenthesis(2, 2, 0)
    count_parenthesis(2, 2, 1)
      count_parenthesis(2, 2, 2)

How can the time and space complexity of this algorithm be determined?

There are a few areas which I'm unsure how to handle:

The variable that moves towards the base case (closed == n) does not get incremented every time.

Calls where a brace is opened (opened + 1) do not directly move towards the base case.

There isn't an obvious relationship (IMO) between n and the number of well-formed combinations:

n = 3, f(n) = 5
n = 4, f(n) = 14
n = 5, f(n) = 42
n = 6, f(n) = 132
n = 7, f(n) = 429
n = 8, f(n) = 1430

I'm unsure how a recurrence relation can be defined when the base-case is not 1 or 0, but n?
Should I approximate based on well-known runtime complexities? I.e. this looks like either exponential or factorial.

Note: I'm not looking for just an answer. I'd like to understand  the process finding the time/space complexity for this type of recursive algorithm.

Let us start by analyzing the recursion tree of your algorithm. The depth is $2n$. As for the number of nodes, at level $k$ you have all arrangements of $a$ left parentheses and $k-a$ right parentheses such that $a \leq n$ and in each prefix of the word, there are at least as many left parentheses as right parentheses.

Bertrand's formula states that for each $a$, the number of such arrangements is
$$
\frac{(a+1)-(k-a)}{k+1} \binom{k+1}{a+1} = \binom{k}{a} - \binom{k}{a+1}.
$$
Hence the number of nodes at level $k$ is
$$
\sum_{\lceil k/2 \rceil \leq a \leq \min(k,n)} \left[\binom{k}{a} - \binom{k}{a+1}\right] = \binom{k}{\lceil k/2 \rceil} - \binom{k}{\min(k,n)+1}.
$$
Summing this for $k$ from $0$ to $2n$, we obtain
$$
\sum_{k=0}^n \binom{k}{\lceil k/2 \rceil} + \sum_{k=n+1}^{2n} \left[\binom{k}{\lceil k/2 \rceil} - \binom{k}{n+1}\right].
$$
It follows from Stirling's approximation that this is $O(4^n/\sqrt{n})$, and conversely, just considering $k = 2n$ (corresponding to Catalan numbers), this is $\Omega(4^n/n^{1.5})$.

We are however not done, since the numbers involves are quite large — on the order of $n$ bits. Therefore arithmetic takes super-constant time. We still get a running time of $\tilde{O}(4^n)$.

Now for space complexity. The recursion tree is $n$ levels deep, and at each level we might be storing up to $n$ bits of information, giving an upper bound of $O(n^2)$ bits. This should be quite tight.


Are there any problems that reduce to the halting problem? I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where P is some other language, but is there an example of another language that reduces to $A_{TM}$ (i.e if we could decide $A_{TM}$ then we could decide that problem)

Trivially every computable problem is reducible to $A_{TM}$. On the other extreme, there are plenty of problems which are $A_{TM}$ "in disguise," which is to say that they are Turing-equivalent to $A_{TM}$ - for example, it's a standard exercise to show that $$\{\langle M\rangle: M\mbox{ halts on input $0$}\}$$ is Turing-equivalent to $A_{TM}$.

A more interesting situation arises when we ask about strict reducibility:

  Is there a problem $X$ such that $(i)$ $X$ is not computable, $(ii)$ $X$ reduces to $A_{TM}$, but $(iii)$ $A_{TM}$ does not reduce to $X$?

The answer to this question was shown to be yes by Kleene and Post, although interestingly no natural examples are known (and indeed it's generally believed that none exist). This led to a natural follow-up question ("Post's problem"):

  Is there a computably enumerable $X$ with the above properties?

This turned out to be much harder to solve, and wound up taking more than a decade; Friedberg and Muchnik independently introduced the priority argument to show that the answer is yes.

Today priority arguments - indeed, ones vastly more complicated than the original Friedberg/Muchnik theorem - are one of the main techniques in computability theory. They originally went by excitingly violent names: finite injury (Friedberg/Muchnik falls into this category), infinite injury (introduced by Sacks), and monstrous injury (introduced by Lachlan). While the first two terms are still in use, the third is not, and we categorize priority arguments more complicated than "basic infinite injury" according to the complexity of an associated set (the "true path"); in particular monstrous injury arguments are now called 0'''-arguments.


Find all neighbors at a certain distance, in 3 dimensions I have two algorithms which I would like to implement:

First, given a (very long) list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d>0$, find all $i$ such that $|\mathbf{r}_{i} - \mathbf{p}| < d$.

Currently, I sort the list over the $x$-coordinate, so that if $x_{i}$ is the $x$-coordinate of $\mathbf{r}_{i}$, then $x_{1} \le x_{2} \le \cdots \le x_{n}$. Then I use the condition $(x_{i}-\mathbf{p}_{x})^{2} > d^2 \implies |\mathbf{r}_{i} - \mathbf{p}|^2 > d^{2}$. This allows me to filter the list by binary search. This leaves me with a subset $\{\mathbf{r}_{i}\}_{i=j_{1}}^{i=j_{2}}$ of the original list where for all $i \in [j_{1}, j_{2}]$, $(x_{i}-\mathbf{p}_{x})^{2} <= d^2$. Then I have to bite the bullet and do an explicit test on each one of these to see if $|\mathbf{r}_{i} - \mathbf{p}| < d$.

This algorithm strikes me as weird and not optimal; is there a better way?

Next: A related problem: Given a list $\{\mathbf{r}_{i}\}_{i=1}^{n}\subset \mathbb{R}^{3}$ and a point $\mathbf{p} \in \mathbf{R}^{3}$, find $j \in [1,n]$ such that $d_{j}:=|\mathbf{r}_{j} - \mathbf{p}| = \min_{i} |\mathbf{r}_{i} - \mathbf{p}|$.  Is there an efficient algorithm to find $j$?

Finally, I should note that any one-time ``sorting'' expense is tolerable, since this operation is repeated many times.

I recommend using a k-d tree or an octree to store the list of points.  They support efficient nearest neighbor search.

If you need to update the list, look at R-trees, which allow your list to be dynamic: you can add or delete from the list and efficiently update the R-tree data structure.


What properties of a programming language make compilation impossible? Question:

"Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine code of a traditional CPU is not possible. What are these properties?"

Compilers: Principles and Practice by Parag H. Dave and Himanshu B. Dave (May 2, 2012)

The book gives no clue about the answer. I tried to find the answer on Concepts of Programming Languages (SEBESTA), but to no avail. Web searches were of little avail too. Do you have any clue?

The distinction between interpreted and compiled code is probably a
fiction, as underlined by Raphael's comment:

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

The fact is that code is always interpreted, by software, by hardware
or a combination of both, and the compiling process cannot tell which
it will be.

What you perceive as compilation is a translation process from one
language $S$ (for source) to another language $T$ (for target). And, the
interpreter for $S$ is usually different from the interpreter for $T$.

The compiled program is translated from one syntactic form $P_S$ to
another syntactic form $P_T$, such that, given the intended semantics
of the languages $S$ and $T$, $P_S$ and $P_T$ have the same
computational behavior, up to a few things that you are usually trying
to change, possibly to optimize, such as complexity or simple efficiency (time, space,
surface, energy consumption). I am trying not to talk of functional equivalence, as it would require precise definitions.

Some compilers have been actually used simply to reduce the size of
the code, not to "improve" execution. This was the case for language used in the Plato system (though they did not call it compiling).

You may consider your code fully compiled if, after the compiling
process, you no longer need the interpreter for $S$. At least, that is
the only way I can read your question, as an engineering rather than
theoretical question (since, theoretically, I can always rebuild the
interpreter).

One thing that may raise problem, afaik, is meta-circularity. That
is when a program will manipulate syntactic structures in its own source
language $S$, creating program fragment that are then intepreted as if
they had been part of the original program. Since you can produce
arbitrary program fragments in the language $S$ as the result of arbitrary computation manipulating meaningless syntactic fragments, I would guess you can
make it nearly impossible (from an engineering point of view) to
compile the program into the language $T$, so that it now generate
fragments of $T$. Hence the interpreter for $S$ will be needed, or at
least the compiler from $S$ to $T$ for on-the-fly compiling of
generated fragments in $S$ (see also this document).

But I am not sure how this can be formalized properly (and do not have
time right now for it). And impossible is a big word for an issue that is not formalized.

Futher remarks

Added after 36 hours. You may want to skip this very long sequel.

The many comments to this question show two views of the problem: a
theoretical view that see it as meaningless, and an engineering view
that is unfortunately not so easily formalized.

There are many ways to look at interpretation and compilation, and I
will try to sketch a few. I will attempt to be as informal as I can manage

The Tombstone Diagram

One of the early formalization (early 1960s to late 1990) is the T or
Tombstone diagrams. These diagrams presented in composable graphical
elements the implementation language of the interpreter or compiler,
the source language being interpreted or compiled, and the target
language in the case of compilers. More elaborate versions can add
attributes. These graphic representations can be seen as axioms,
inference rules, usable to mechanically derive processor generation
from a proof of their existence from the axioms, à la Curry-Howard
(though I am not sure that was done in the sixties :).

Partial evaluation

Another interesting view is the partial evaluation paradigm. I am
taking a simple view of programs as a kind of function implementation
that computes an answer given some input data. Then an interpreter
$I_S$ for the language $S$ is a program that take a program $p_S$
written in $S$ and data $d$ for that program, and computes the result
according to the semantics of $S$. Partial evaluation is a technique
for specializing a program of two arguments $a_1$ and $a_2$, when only
one argument, say $a_1$, is known. The intent is to have a faster
evaluation when you finally get the second argument $a_2$. It is
especially useful if $a_2$ changes more often than $a_1$ as the cost
of partial evaluation with $a_1$ can be amortized on all the
computations where only $a_2$ is changing.

This is a frequent situation in algorithm design (often the topic of
the first comment on SE-CS), when some more static part of the data is
pre-processed, so that the cost of the pre-processing can be amortized
on all applications of the algorithm with more variable parts of the
input data.

This is also the very situation of interpreters, as the first argument
is the program to be executed, and is usually executed many times with
different data (or has subparts executed many times with different
data). Hence it become a natural idea to specialize an interpreter for
faster evaluation of a given program by partially evaluating it on
this program as first argument.  This may be seen as a way of
compiling the program, and there has been significant
research work on compiling by partial evaluation of a interpreter on
its first (program) argument.

The Smn theorem

The nice point about the partial evaluation approach is that it does
take its roots in theory (though theory can be a liar), notably in
Kleene's Smn theorem.  I am trying here to give an intuitive
presentation of it, hoping it will not upset pure theoreticians.

Given a Gödel numbering $\varphi$ of recursive functions, you can
view $\varphi$ as your hardware, so that given the Gödel number $p$
(read object code) of a program $\varphi_p$ is the function defined
by $p$ (i.e. computed by the object code on your hardware).

In its simplest form, the theorem is stated in wikipedia as follows
(up to a small change in notation):

  Given a Gödel numbering $\varphi$ of recursive functions, there is a primitive recursive function $\sigma$ of two arguments with the following property: for every Gödel number $q$ of a partial computable function $f$ with two arguments, the expressions $\varphi_{\sigma(q,x)}(y)$ and $f(x,y)$ are defined for the same combinations of natural numbers $x$ and $y$, and their values are equal for any such combination. In other words, the following extensional equality of functions holds for every $x$:
      $\;\;\varphi_{\sigma(q,x)} \simeq \lambda y.\varphi_q(x,y).\,$

Now, taking $q$ as the interpreter $I_S$, $x$ as the source code of a
program $p_S$, and $y$ as the data $d$ for that program, we can write:
   $\;\;\varphi_{\sigma(I_S,p_S)} \simeq \lambda d.\varphi_{I_S}(p_S,d).\,$

$\varphi_{I_S}$ may be seen as the execution of the interpreter $I_S$
on the hardware, i.e., as a black-box ready to interpret programs
written in language $S$.

The function $\sigma$ may be seen as a function that specializes the
interpreter $I_S$ for the program $P_S$, as in partial evaluation.
Thus the Gödel number $\sigma(I_S,p_S)$ may be seen has object code that is
the compiled version of program $p_S$.

So the function $\;C_S = \lambda q_S.\sigma((I_S,q_S)$ may be seen as
a function that take as argument the source code of a program $q_S$
written in language $S$, and return the object code version for that
program. So $C_S$ is what is usually called a compiler.

Some conclusions

However, as I said: "theory can be a liar", or actually seem to be one. The problem is that we
know nothing of the function $\sigma$. There are actually many such
functions, and my guess is that the proof of the theorem may use a
very simple definition for it, which might be no better, from an
engineering point of view, than the solution proposed by Raphael: to
simply bundle the source code $q_S$ with the interpreter $I_S$. This
can always be done, so that we can say: compiling is always
possible.

Formalizing a more restrictive notion of what is a compiler would
require a more subtle theoretical approach. I do not know what may
have been done in that direction. The very real work done on partial
evaluation is more realistic from an engineering point of view. And
there are of course other techniques for writing compilers, including
extraction of programs from the proof of their specification, as
developed in the context of type-theory, based on the Curry-Howard
isomorphism (but I am getting outside my domain of competence).

My purpose here has been to show that Raphael's remark is not "crazy",
but a sane reminder that things are not obvious, and not even
simple. Saying that something is impossible is a strong statement
that does require precise definitions and a proof, if only to have a
precise understanding of how and why it is impossible. But building
a proper formalization to express such a proof may be quite difficult.

This said, even if a specific feature is not compilable, in the sense
understood by engineers, standard compiling techniques can always be
applied to parts of the programs that do not use such a feature, as is
remarked by Gilles' answer.

To follow on Gilles' key remarks that, depending on the language, some
thing may be done at compile-time, while other have to be done at
run-time, thus requiring specific code, we can see that the concept of
compilation is actually ill-defined, and is probably not definable in
any satisfactory way. Compilation is only an optimization process, as
I tried to show in the partial evaluation section, when I compared
it with static data preprocessing in some algorithms.

As a complex optimization process, the concept of compilation actually
belongs to a continuum. Depending on the characteristic of the
language, or of the program, some information may be available
statically and allow for better optimization. Others things have to be
postponed to run-time. When things get really bad, everything has to
be done at run-time at least for some parts of the program, and
bundling  source-code with the interpreter is all you can do. So this
bundling is just the low end of this compiling continuum. Much of the research on compilers is about finding ways to do statically what used to be done dynamically. Compile-time garbage collection seems a good example.

Note that saying that the compilation process should produce machine
code is no help. That is precisely what the bundling can do as the
interpreter is machine code (well, thing can get a bit more complex
with cross-compilation).


Is the DPLL algorithm complexity in terms of # of clauses or # of variables? I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?

In the papers I've read the time complexity of DPLL is expressed in terms of the number of variables in the CNF formula.  Using the number of clauses is inappropriate in general because it is known that random k-SAT instances go through an easy-hard-easy transition if you fix the number of variables and increase the number of clauses.  The solution space goes from underconstrained to overconstrained as the number of clauses increases with the hard instances clustering between those extremes.