# Question
Title: Why are programs executed in main memory?
Why are programs kept in main memory for execution? As per my understanding, we need a memory management scheme to manage several processes in the main memory. These things can be done in secondary memory as well (I think). Just to improve performance, we need main memory or there is something more to it?

# Answer
> 2 votes
They are not. On modern desktop/server OSes, the program generally mmapped (or equivalent) into virtual memory and the currently running parts are paged in as needed. However, the remainder of the program can sit on secondary storage and never be accessed.

The reason for the currently executing parts of memory being paged in as opposed to running directly from secondary storage is performance. In general, any read access to secondary storage tends to be cached in memory, either directly through virtual memory or indirectly through something like a disk cache. In fact, in the main memory there's an extensive cache hierarchy (typically 3 layers on x86 Intel / AMD processors) so even the idea that the program is store in "main" memory is mostly a convenient simplification, not a complete description of reality. What actually happens is that some parts of the program are paged into main memory (by the OS) and some parts of the the program from main memory is cached into the L3 cache (by the CPU) and some parts of that are cached into the L2 cache(by the CPU) and some parts of that are cached into the L1 instruction cache (by the CPU).

On embedded systems and more exotic architectures, deviations from this pattern definitely exist. Execute-in-place was already mentioned but another example is Harvard architecture processors, where instruction and data memory are completely separate and code runs from the instruction memory which isn't addressable as data. Small embedded microcontrollers like PIC and AVR are examples of such processors.

# Answer
> 1 votes
For every processor that I have seen in the last 30 years, code must be in a location that can be accessed by the memory-read hardware of the processor in order to be executed. Accessible to that hardware is RAM, ROM and variants, and the hardware could be designed to make things like flash memory accessible that way.

Typically, software is actually stored on a hard drive or flash drive, it is mapped to memory locations using virtual memory, so when the processor tries to read an instruction from main memory, and the code isn't there, an interrupt will interrupt that program execution, run code that reads the data from hard drive or flash drive and stores it somewhere in main memory, and then continues program execution.

---
Tags: operating-systems, memory-management
---


title: size of a variable

text:
# Question
Title: size of a variable
I'm a beginner. I would like to know if the size of a variable (and generally speaking of a storage space) is:

1. Its capacity (the amount of data that can be put in it).
2. The amount of data it contains

# Answer
Different programming languages have different ways of implementing the concept of a "variable". The "size" of a variable in a computer program will vary depending on a number of characteristics that determines how the target programming language implements variables, the type of the variable, and how the target hardware handles memory access.

The size of the memory area for a variable may include not only the memory for the data of the variable but also memory for variable memory management. In a programming language such as Java or C# that has garbage collection, variables have additional data that is associated with the variable indicating whether the variable is still in use or not. So the actual memory size used for these variables will be larger than what the data type implies because not only is there memory for the variable's data but also memory for managing the variable's life time.

**Programming language may matter**

Some programming languages are much more flexible about how variables are created and used. An example of such a flexible language is JavaScript which is quite extraordinary in what the language allows you to do with variable assignments. Php has a similar flexibility in that a variable can be assigned a text string value at one point and a numeric value at another point and it will do automatic conversions from text to numeric for you as well.

So with programming languages such as JavaScript and Php, the idea of a variable and the type of value of a variable (text or integer number or floating point number or whatever) is quite fluid.

In the C++ programming language an object created from a `class` may be larger than the individual variable members of the `class` would indicate even with padding considered (see below about padding in C which is also used in C++). This can come from the addition of a v-table or virtual method table that the compiler generates when a function with the `virtual` keyword is part of the class.

**Machine hardware may matter**

In the C programming language there is a variable type of `int` which is used to define or declare a variable as an integer value. The actual physical or memory size of an `int` variable can vary depending on the target hardware. With 16 bit hardware the size of an `int` may be 16 bits while on 32 bit hardware the size of an `int` may be 32 bits and on 64 bit hardware the size of an `int` may be 64 bits.

These variations also means that the range of values that an `int` variable may assume or have will vary between different types of hardware.

The C programming language has a way to allocate memory at run time using the `malloc()` function of the Standard Library. When you make a call to request a memory area, the memory area that is actually allocated will be larger than the size you specified. This additional, hidden memory is used to contain information about the block of memory that was allocated. In addition the memory area may include padding or extra memory the memory allocator adds to your request to make its job of managing memory easier.

Finally in some cases you may define a variable which the C compiler will eliminate. There are a number of reasons why an optimizing C compiler will eliminate a variable.

The most obvious is because the compiler sees that while the variable is defined, it is not actually used anywhere so the compiler eliminates the variable in order to save memory space.

A second case is when the variable is used in a temporary fashion so rather than allocating memory for the variable, the variable's value is instead stored in a hardware register because while the value of the variable is needed, an actual memory location is not.

A third case is when the variable is set with some value that does not change so the compiler eliminates the variable and uses the constant value in the places where the variable would have appeared.

**Memory padding by the C compiler**

The C compiler standard also allows for the use of memory padding for variables that are made up of other variables, the `struct`. A `struct` defines a new type of variable that is composed of other variable types. An example:

```
struct {
    int   iVal;
    char  chArray[15];
    long  lVal;
    char  chArray2[5];
} MyStruct;

```

On an Intel x86 32 bit machine the C compiler may allocate a memory area for a variable of this type that would be the size of an `int`, 32 bits, fifteen times the size of a `char`, 15 * 8 bits, the size of a `long`, 32 bits, and 5 times the size of a `char`, 5 * 8 bits. Or the C compiler may introduce padding in order to align the `long` variable `lVal` on a 32 bit or double word memory boundary. So instead of the size of the `struct` being 32 bits plus 15 * 8 bits plus 32 bits it is instead 32 bits plus 16 * 8 bits (padding introduced to align the beginning of the next variable on a 32 bit memory boundary) plus 32 bits plus 5 * 8 bits.

This memory boundary requirement will vary depending on the underlying machine hardware characteristics. Some hardware designs are more efficient at accessing memory when a memory address is on a particular memory size alignment. For other hardware designs it may not matter.

So the C compiler may see the above `struct` (again this depends on the hardware design and the C compiler as the C Standard does not have a specific requirement for memory alignment) as really looking like the following:

```
struct {
    int   iVal;
    char  chArray[15];
    char  chPadding[1];   // invisible padding added by compiler for memory alignment.
    long  lVal;
    char  chArray2[5];
} MyStruct;

```

If you have an array of this `MyStruct` variable type you might expect that the memory allocated for the array would be the number of elements of the array times the size of the individual array element.

However the C standard says that a `struct` must begin on a memory boundary that aligns with the most restrictive type's needs. So in this case a `long` needs or requires a double word alignment so each of the elements of the array must start on a double word alignment.

The result of this requirement is that padding is added to the end of each array element when the size of the array is calculated by the compiler.

So now the `struct` looks to the compiler like the following:

```
struct {
    int   iVal;
    char  chArray[15];
    char  chPadding[1];   // invisible padding added for memory alignment.
    long  lVal;
    char  chArray2[5];
    char  chPadding2[3];   // invisible padding added for memory alignment for array.
} MyStruct;

```
> 2 votes

---
Tags: terminology
---


# Question
Title: How does make/scons manage dependency graph and figure out which file need to be recompiled?
what I understand is that, the file dependency is organized as a graph. Make/scons check the timestamp of each file, when a source file's timestamp is newer than the output, it re-compile everything depend on this file.

What kind of algorithm does Make/scons use to travel the graph? what if there are circles?

I have been searching around on internet but somehow I cannot find a lot of insights.

Can someone explain to me how does make/scons work?

# Answer
I do not how SCons works in details so I will focus on Make. I am not sure anyone really knows what is the algorithm Make uses because it is so complicated and error-prone, it is loosely described in the manual . But at the high-level, Make takes as input rules as described in the manual of form $$target: dependencies$$ Furthermore, when running make one has to specify one or more targets to build (if you give no target, it builds "default"): `make target1 target2 ...` This essentially describes a graph and a set of nodes to be built. In terms of graph, one could say that Make performs a depth-first search1 from those to-be-built nodes, but this hides many details like PHONY/FORCE rules, intermediate files, secondary-expansions, the fact that a file can actually be built twice, parallel make and more features. Make considers dependency loops to be an error and will break them arbitrarily (and display a warning).

In fact, one could say that Make performs two different (but related) functions: building the dependency graph and rebuilding everything according to the graph. The difference between Make and other tools is that other tools mostly take as input a complete description of the graph. On the other hand, Make provides a whole range of tool to dynamically create the graph. This creates a lot of confusion because you can literally have a 5 lines Makefile that will generate a graph with thousands of nodes and runs all kinds of tools to figure out the dependencies. SCons, CMake and friends will usually let other tools do this work for them and focus on just rebuilding everything. Also Make's approach makes it somewhat inefficient because just building the graph may involve running some tools, and not just reading the Makefiles.

1The order in which Make builds file is completely unspecified, except for the fact that it is a topological order (and even that is not entirely true because Make may actually build some targets more than once)
> 1 votes

---
Tags: algorithms, graphs, compilers
---


# Question
Title: What is the time complexity of $\sum_{i=0}^{\frac{n}{k}} p_i\cdot 2^{ik}$ if $p$ is a binary number?
Let $p$ be a number represented in binary of length $n$. We'll divide $p$ into $\frac{n}{k}$ parts, each of length $k$ (let each part be $p\_i$, $0 \le i\le \frac{n}{k}$) where $k=\lg n$. Now we want to represent $p$ as a sum: $$ \sum\_{i=0}^{\frac{n}{k}} p\_i\cdot 2^{ik} \qquad(\*) $$

I know that multiplying a number in binary by $2^{ik}$ is the same as shifting $i$ bits to the left which should be an $\Theta(1)$ operation in real life but theoretically this could be a $\Theta(n)$ operation because we may have to shift up to $n$ bits to the left. So the sum above becomes $\Theta(n^2)$.

Is there a faster way to perform the sum operation $(\*)$?

# Answer
The running time to compute the sum is $O(n)$ bit operations. You just concatenate $p\_1,p\_2,\dots,p\_{n/k}$ and you've got your answer.
> 1 votes

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


# Question
Title: Proof of equivalence of L0 and language accepted by made up machine
I have a made up machine, which has the same definition as Turing machine, but the transition function and the step of computation of the machine. What would be the approach of the proof that the language accepted by this machine is (or is not) equal to L0 (recursively enumerable language)?

# Answer
> 0 votes
You need to show that any language that is accepted by a Turing machine is accepted by one of your machines. So, start with an arbitrary Turing machine $M$ and show that one of your machines can accept $L(M)$, e.g., by showing how to directly simulate the operation of $M$.

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


# Question
Title: Approximation factor of NP-complete problems
We talked about the following theorem in class but I am still having problems to understand it:

*For a NP-complete decision problem "Does a valid solution with a value $\leq K$ exist?" there is no approximation algorithm for the corresponding minimization problem with an approximation factor $\lt 1 + 1/K$*.

Why is this necessarily true? And where does that upper bound $1 + 1/K$ come from?

# Answer
The crucial assumption here is that the value is an integer.

If the value is an integer, then telling whether there is a valid solution with value $\le 10$ is as hard as telling whether there is a valid solution with value $\le 10.999$ (it's the question). Thus, you shouldn't expect a polynomial-time approximation algorithm with approximation factor $10.999/10$ or better -- if you had such an approximation algorithm, you could tell whether there was a valid solution with value $\le 10.999$, which would tell you whether there is a valid solution with value $\le 10$, which would let you solve the original problem, which would mean that you have found a polynomial-time algorithm for a NP-complete problem. That would be unexpected.
> 1 votes

---
Tags: approximation
---


# Question
Title: How to prevent the optimization algorithm from just shrinking the image?
I'm trying to optimize a set of patterns in an image, but unfortunately they only way I have of evaluating the images results in smaller versions of the pattern scoring much better than larger versions.

As a result, the optimization methods I've tried all just end up shrinking the pattern down until they run into aliasing issues, and start becoming erratic.

I've tried normalizing the images by resizing the patterns to all be the same size at each step, but the optimization algorithm quickly just adds 'decoy' pixels to the corners, defeating the normalization.

I've considered trying to do the optimization with a vectorized form, but evaluating a pattern requires it to be rasterized to a particular size anyway. Vectorizing the pattern also doesn't solve the problem with normalization and adding decoy geometry.

How can I prevent the optimization process from just scaling down the image?

# Answer
I doubt your question can be answered in any detail without knowing more about what you're trying to achieve with these patterns. The *general* answer to "my scoring function rewards something I don't want" is either to fix the scoring function or to add a penalty to counteract it, but I'm sure you were already aware of that.

Depending the optimization method you're using, you could possibly also try biasing your sample generation method away from local optima in the unwanted part of the parameter space, but that's generally only effective if there's some other, better local optimum available elsewhere for the process to converge to instead. If the unwanted local optimum is actually the *global* optimum for your scoring function, then any decent optimizer will sooner or later find its way there. If that's the case, you really do just need to find a way to fix your scoring.

Anyway, since you say in the comments that smaller patterns *are* objectively better in some sense, I assume they must also have some property that makes them objectively worse in some other way. You might want to think about what exactly that property is, and try to penalize *that*.
> 2 votes

---
Tags: optimization, image-processing
---


# Question
Title: What would a language look like in which precise GC was implementable as a library?
Suppose you have some programming language with manual memory management. What features does this language need to have in order to be able to implement precise garbage collection as a library, and not as a fundamental language construct?

By a precise GC I mean one where only pointers to the heap are traversed to ascertain which variables are or are not live.

Some additional considerations:

* C and C++ have the Boehm garbage collector, but I don't count this since it's not a precise GC. The Boehm collector assumes that anything on the stack that could be a pointer, based purely on memory alignment requirements, is a pointer. For example, any integer `k` such that `(k % 4) == 0` looks at a bit level like a pointer, since pointers must be 4-byte aligned.
* magpie transforms existing C code to use a precise garbage collector. The generated C code has a lot of stubs for garbage collection, i.e. stuff for registering any stack pointers into the heap with the collector. I don't count this because no one could ever be expected to write code that way; it's more of a compilation target for other languages.

I imagine that such a language would need to have:

1. Macros or some form of metaprogramming, for encapsulating all of the extra code needed to do things like register GC roots.
2. Some reflective mechanism that allows you to inspect structs or unions; you need to determine which members are pointers.
3. Some reflective mechanism that allows you to examine the stack frame layout. This sounds a lot harder than 2.

I hope this isn't too vague or opinion-based but I've been wondering about it for a while.

# Answer
> 1 votes
I believe that this is possible, or at least nearly possible, in a language like Rust, though perhaps not necessarily in the sense you are thinking.

Rust actually has a GC library, though I can't say how precise it is. But the idea is that, there's a specific type `Gc<T>` for garbage-collected pointers to values of type `T`. So the metaprogramming that you're talking about doesn't happen

What makes it possible for this to be precise is Rust's ownership system: because of affine linear typing, every location in memory has at most one pointer to it, unless it's declared using an `unsafe` block (which is used to implement things like the Garbage collector). So if you have a pointer that's not wrapped in a `Gc` type, it gets deallocated as soon as it goes out of scope. So it's not possible to consider something as a pointer that isn't: either it's wrapped in the `Gc` type, or it's singly-owned and automatically deallocated.

Every type has an implicit `drop` method that's called when it goes out of scope, that deallocates things it points to. This `drop` method is aware of what is and isn't a pointer, which also helps with precision.

The language is strongly, statically typed, and unless you specifically are in an `unsafe` block, you can't cast things to other types, so it can be statically known what type a given chunk of memory has.

This isn't a drop-in transformer that lets you treat Non-GC code as Garbage collected. The programmer specifically specifies what values are collected. But given that, I think it has the potential to meet your criteria.

# Answer
> 1 votes
I think it is possible to implement a garbage collector in C++ without changing the language itself. But in order to use the garbage collector, one must restrict the programmer from using arbitrary language constructs. In particular, all memory allocation requests must be done through the allocation APIs given by the garbage collector, and all the access must be done through references that is managed by the garbage collector.

---
Tags: memory-management, language-design, garbage-collection
---


# Question
Title: Computing overlap of intervals in an integer programming framework
Suppose I have 2 intervals C1 = \[x1, x2\] and C2 = \[y1, y2\], where x1,x2,y1,y2 are variables in an Integer program, I want to compute the overlap of C1 and C2. I am interested in a tight formulation for computing the overlap as an another variable with as few big M constraints as possible. Any references or formulations are deeply appreciated.

# Answer
> 4 votes
By overlap I understand its length (no its coordinates) since you didn't specify how to handle no overlap case.

First you need to know whether $x\_1\le y\_1$ which is just a comparison.

Next, you create new variables $l\_1, l\_2, r\_1, r\_2$ for which you know that $l\_1\le r\_1, l\_2 \ge l\_1, r\_2 \ge r\_1$

Now the answer is $\min(\max(l\_2 - r\_1, 0), r\_2 - r\_1))$

How you build these constraints it is up to you. You can use approaches similar to https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ and https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/

---
Tags: integer-programming, intervals
---


# Question
Title: How do I find depth and height of all nodes in a bounded semilattice?
I'm writing a program where I have a bounded semilattice (it has a root element at the top, all edges point downwards, and a node may have multiple parents). I need to precompute each node's depth (the max number of edges from the root node) and height (the max number of edges to any leaf). I have a naive implementation for just the heights where every node is compared to all it's descendants, so probably O(n^2). What is a faster algorithm that computes both height and depth?

# Answer
> 2 votes
If you do a topological sort and then traverse the nodes in reverse topologically sorted order, you can annotate each node with its height in linear time. Similarly, you can annotate each node with its depth in linear time by traversing in topologically sorted order. This achieves linear running time, which is significantly faster than the quadratic time approach you mention.

---
Tags: algorithms, graphs, lattices
---


# Question
Title: Deleting nodes from graph so that they can be separated by a straight line
I have 2 types of points in a 2D plane, type 'A' and type 'B'. How do I delete the minimum possible number of points so that remaining can be separated (on different sides) by a straight line.

I tried modeling this as a graph, where I have 2 types of nodes, and i delete nodes from it. But I can't formulate an algorithm.

How can I go about formulating an algorithm for this situation?

# Answer
Try the following (inefficient) approach. Assume there are $N$ points in total. Now with each of the $N$ points try to find a line segment that passes through it with the least number of mis-classifications (number of points that were not correctly separated) by the line segment. The important point to note here is that, you would not have more than $N-1$ such line segments to check for. At the end of the procedure simply choose the point and its best corresponding line segment. The overall complexity is $O(N^3)$ under ideal conditions. Some perturbation of point may be required in the process, if not ideal.

A slightly more efficient procedure is as follows, let the convex hull of the points in type 1 be $P\_1$ and those of type 2 be $P\_2$. Then I suspect, in the previous procedure, instead of computing the best line segment for every point, just do the procedure for those in $P\_1 \cap P\_2$.
> 3 votes

# Answer
There are loads of machine learning algorithms for determining an optimal line (linear regression, logistic regression, and so forth). These will find values for w1,w2,w3 based on some error metric. Then you can test whether all of the points are correctly classified. That is, whether all of the values in A satisfy the equation above and similarly for B

.

As you are only interested in whether such a line exists, you needed use existing techniques (though that probably would be simpler). Simply set up the following collection of equalities in terms of free variables w1,w2,w3

.

w1ai1+w2ai2≥w3 for each i=1,..,|A|, where A={(a11,a12),…,(a|A|1,a|A|2)}

.

w1bj1+w2bj2

.

If these constraints are consistent, then a line exists.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Does crossover take the parents or the offsprings? How to select parents with linear ranking?
I am building genetic algorithm for feature selection. But there are vague things to me.

1. For example, there are 100 individuals with crossover probability 0.8. Does it mean I take 80 parents (40 couples), or 80 offsprings?
2. I'm using linear ranking as the parent selection because of the fitness values are close to each other. How can I select the parents after I get the values of linear ranking?
3. Assume if the answer on number (1) is taking 80 parents. After I get parent's candidates, what will happen to the unused parents if those candidates are more than our requirement? And what will happen if those candidates are less than our requirement?
4. If we only take the best 80 individuals as parents, then what is the point of using linear ranking as parent selection?

Thanks before.

# Answer
> 2 votes
> For example, there are 100 individuals with crossover probability 0.8. Does it mean I take 80 parents (40 couples), or 80 offsprings?

`0.8` is the probability that crossover will occur at a particular mating.

The standard algorithm samples the population with replacement (the same parent may be selected more than once):

* you pick out 50 couples;
* crossover is performed for (about) 40 couples producing 80 new individuals (80% of the new generation is produced via crossover);
* (approximately) 10 couples are copied to the new population (here ignoring the mutation operator).

(this is a generational approach).

> I'm using linear ranking as the parent selection because of the fitness values are close to each other. How can I select the parents after I get the values of linear ranking?

Just use the standard roulette wheel selection algorithm and, rather than weighting each candidate by its fitness score, use its rank.

> If we only take the best 80 individuals as parents, then what is the point of using linear ranking as parent selection?

It's not deterministic. An individual has a **probability** of getting selected as a parent (the probability is linked to the rank).

With rank selection the best individual is more likely to be chosen than the second one, but both have the same probabilities of being chosen whether the best had ten times the fitness of the second best, or only a slightly greater fitness.

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: Radix, merge, counting sort and when to use
Okay can't figure this out. I want to make sure I understand it.
There are n random keys each being float numbers with p decimal places. So, for example, 123.456,

343.645,

234.543,

863.238,

956.043,

etc.

For which values of p should you use counting sort, radix sort, and merge sort to make it the fastest. I know counting sort runs O(n+k), radix runs O(d(n+k)), and merge is O(n) in its best case. Also, I \*think when sorting with decimals you first multiply each by 1000 (in this case) to make them whole numbers, correct? Or is that wrong? Any and all help would be appreciated.

# Answer
> 2 votes
The idea seems wrong at its core. The missing parts are: what is the distribution and range of the data. How many items do you have? (You may not know this in advance, but it renders some algorithms useless).

The counting sort works well when the range is compact, it gives good memory requirements and the mere array traversal is not computationally expensive. In the case of floating-point numbers, when you multiply decimal part to make full integers the range may be huge, in that case $n$ may be small but $k$ is huge. Instead of multiplying them out the better idea is to round them and store only decimal part. This idea would not blow up the range and after counting you are left with small bins to sort. To give more or less answer to $p$ parameter, it really depends on scarcity of data and number, but say, if you really want to multiply them by $10^p$ in many cases for $p \ge 3$ it seems like bad idea.

The radix sort depends on $d$ which is the number of digits, here it doesn't matter where is the decimal point, but with bigger $p$ the $d$ is bigger, which kills the performance (unless bigger radix is used for decimal part only).

Merge sort, the natural variant, is $\mathcal O(n)$ but this property is not that important to choose, it effectively says that the algorithm terminates sorting early when it gets sorted data. The best case for sorting (when applicable by algorithm properties) must be $\Omega(n)$ to at least read the input and check whether consecutive numbers obey order. Merge sort runtime does not depend on $p$, as far it is some built-in type, unless the float is stored as the string, but this on its own may be problematic and performance killer. The access to decimal digits in case of some floating-point number requires conversion, which takes time or additional memory.

To choose sorting algorithm the first step is to match inherent properties with data, use (or add if you have to) properties like stability of sorting, understand what asymptotic notation mean, look at average case and test with your real data.

Why $n$ is important here? Because if it is small (10-20) Bubble sort is faster on average than other algorithms (short of counting sort with extremely tight range), because it has small hidden constant and for non-artificial data it does rarely encounter bad case. The situation gets more complicated when actual data is bigger, but in the case of smallish data, say 1000 – 20000 items, the hidden constant still matters.

For data in your format (3 digit decimals with $p$ decimal places) if you know distribution, it may be beneficial to use distribution sort or counting sort, rounding numbers beforehand. Back to your question, the decision to select one of given algorithms doesn't solely depend on $p$.

---
Tags: sorting, counting, radix-sort, mergesort
---


# Question
Title: in a graph G= (V,E), finding a clique of size |V|- d where d is some constant
Is the question above still NP? I've been stuck on this question for couple of days now... I know k-Clique problem is NP-complete generally, but the problem is k = |V|-d where d is some integer constant...My current guess is that for large |V|, `d << |V| => Finding all subsets of size k = (V choose V-d)` so this question is in P.

# Answer
> 1 votes
The brute force algorithm would check all vertex subsets of size $n-d$, where $|V|=n$. There are $$\binom{n}{n-d} = \binom{n}{d}=\frac{n(n-1)\dots (n-d+1)}{d!}$$ different subsets. This quantity is $\mathcal{O}(n^d)$ and since $d$ is constant this problem is in $P$.

You are asking

> Is the question above still NP?

Even though the problem is in $P$, this problem is still in $NP$ since $P \subseteq NP$, however, unlike $k$-clique problem this problem may not be NP-complete.

---
Tags: np-complete, np
---


# Question
Title: Group values up to a threshold and minimize groups
Given a threshold $t$ and a list of numbers $N$. $\forall n \in N: n \leq t$ Now group the numbers so that the sum of the numbers $s$ is lower or equal $t$. Minimize the amount of groups.

Example: $N={20,19,18,17,14,12,9,5,4}$ and $t = 40$

Possible Grouping: ${(20,19),(18,17,4),(14,12,9,5)}$ (Greedy)

Is greedy a strategy/algorithm, that will lead to the optimal solution? If not, are there other algorithms to solve this problem?

# Answer
> 1 votes
I just learned that this is the bin packing problem with goal of minimizing the bins. This problem is NP hard. So the greedy strategy wont guarantee an optimal solution.

---
Tags: algorithms, greedy-algorithms, packing
---


title: Machine error in computer arithmetic

text:
# Question
Title: Machine error in computer arithmetic
I'm wondering if if is possible to have a function $f$ such that there exists $x,y$ such that we have $f\_t(x) \> f\_t(y)$ where $f\_t$ denotes the true value of $f$ and $f\_a(x)\<f\_a(y)$ where $f\_a$ denotes the value of f as stored in a computer? (I am referring to floating point numbers and numerical analysis)

I am looking at programs that solve equations and so am concerned about if my programs will work in extreme cases. Things like if I have a function that is extremely close to $0$ in an absolute sense over the interval and I want to find the root. (In this case I think I can make an argument that if $f\_t(x) \geq 0$, then we must have that $f\_a(x) \geq 0$.) But if I'm looking for a maximum of a function that is almost constant, say $g$, then I don't think I know that $g\_t(x) \> g\_t(y)$ implies that $g\_a(x) \> g\_a(y)$. Is this correct?

Any other resources on this matter would be greatly appreciated.

# Answer
> 1 votes
Yes! Various languages and APIs often specify the precision you are guaranteed. If the underlying hardware doesn't offer that precision, they must emulate it with extra work. For instance, some machine instructions that compute transcendental function (sin, cos, exp, log, ...) only offer a limited accuracy. Library implementations that guarantee a certain accuracy must execute extra instructions to accomplish that by correcting the error and improving the approximation.

As a concrete example, consider the `native_sin` function in OpenCL. The error is "implementation defined." On the other hand, the regular `sin` function promises a certain accuracy and implementation of OpenCL must make that happen regardless of the extra work.

---
Tags: approximation, numerical-analysis, error-estimation
---


# Question
Title: Feedback Vertex Set with vertex partitions?
I've encountered this problem in a program analysis project I'm working on, where I've got a bunch of functions defined in terms of each other, and because I'm using SMT which doesn't support recursion, I'd like to define as many functions outright as possible, so that fewer are left to be solved by the SMT solver.

In terms of pure graph theory, my problem is this:

Given:

* A directed (possibly cyclic) graph $G=(V,E)$
* A partitioning of $V$ into disjoint subsets $V\_1, \ldots, V\_k$

I want to choose:

* $v\_i \in V\_i$ for each $1 \leq i \leq k$ that minimizes the feedback-vertex number of the subgraph of $G$ induced by $\\{v\_1,, \ldots v\_k \\}$

I'm fairly guessing the problem is $NP$-hard, because of its reliance on the Feedback Vertex Set problem. If we assume that our $V\_i$ sets are small, say with a maximum size $M$, then there are at most $M^k$ combinations to try.

I'm wondering:

* Has this problem (or anything similar) been studied before?
* Is this problem $NP$-hard, or does it fall into one of the subsets of feedback-vertex that is tractable (e.g. chordal graphs, convex-bipartite, etc.)
* Does anyone know of a way to reduce the Feedback Vertex Set problem to this? It's solvable in $O(1.7548^n)$ time, so if I can translate my problem into this one it's entirely possible it's solvable for small inputs. But for all I know, my problem is harder than Feedback-vertex.
* Are there any approximation algorithms that can be adapted to my variant of the problem, that are maybe not optimal, but would give near-optimal results quickly

# Answer
Your problem reduces *to* Feedback Vertex Set by turning every subset $V\_i$ into a clique, and creating one additional vertex $v\_i$ for each subset $V\_i$ that is adjacent to all vertices in $V\_i$. It might be easier to think in terms of the complement problem, Maximum Induced Forest.

Since $V\_i\cup \\{v\_i\\}$ is a clique, we can select at most two vertices from this set to be in our solution (to Maximum Induced Forest). We can assume $v\_i$ is always in the solution, since if less than two vertices of $V\_i$ are in the solution we can safely include $v\_i$, and if exactly two vertices of $V\_i$ are in the solution then $v\_i$ is not, but we can swap one of these two vertices (from $V\_i$) with $v\_i$.

A solution to Maximum Induced Forest thus selects at most one vertex from each set $V\_i$ such that the result is a acyclic, and these are exactly the vertices we should select in a solution to the original problem (from the sets $V\_i$ from which no vertices are selected, we can just arbitrarily select a vertex, and this vertex will be in our feedback vertex set). Conversely, it is easy to see how a solution to the original problem corresponds to a Maximum Induced Forest/Feedback Vertex Set in the graph created in this reduction.

This gives you a $O(1.7548^{n+k})$-time algorithm. If you allow parallel edges you can (instead of creating this additional vertex $v\_i$) double up the edges in every clique, which has the same effect (and may give a faster algorithm, if your algorithm for solving feedback vertex set allows for parallel edges).

The problem is $NP$-hard. We can reduce from Feedback Vertex Set. To decide whether a graph has a Feedback Vertex set of size at most $s$, we create $s$ cliques of size $n+1$. We can force that one vertex of this clique is always in the solution (by including it in a singleton set $V\_i$). We then create for each vertex $v$ in the original graph a set $V\_i$ that contains $v$, and one vertex from each of the $s$ cliques. In at most $s$ of these sets $V\_i$, we can select a vertex from each clique, but in the remaining $n-s$ sets we must select a vertex from the original graph. Therefore, we can find a solution to the original problem with feedback vertex set number $0$ if and only if the input graph had feedback vertex set number of at most $s$.
> 1 votes

---
Tags: graphs, optimization, np-complete, reference-request
---


# Question
Title: Why are forks in the Blockchain eventually resolved?
I'm reading Wattenhofer's *The Science of the Blockchain*. On page 87, he states the following thoerem:

> **Theorem 7.22.** Forks are eventually resolved and all nodes eventually agree on which is the longest blockchain. The system therefore guarantees eventual consistency.
>
> *Proof.* In order for the fork to continue to exist, pairs of blocks need to be found in close succession, extending distinct branches, otherwise the nodes on the shorter branch would switch to the longer one. **The probability of branches being extended almost simultaneously decreases exponentially with the length of the fork**, hence there will eventually be a time when only one branch is being extended, becoming the longest branch.

I don't quite understand why the probability decreases exponentially. I think it's quite probable that they happen at the same time, if not that the malicious block is faster and waits.

# Answer
> 7 votes
If we simplify and assume that each miner randomly guesses a hash (as opposed to being more systematic) and we discretize time, say into minutes, then each minute each miner is hoping to "roll" the right number. Let's say there are $N \> 1$ possible values only one of which is correct at each minute. Then, in a world with only two miners, each minute there is only a $\frac{1}{N^2}$ chance that both miners will roll the correct value. There's a $1-\frac{3}{N^2}$ chance that neither miner rolls the correct value. There is a $\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2}$ chance that both miners roll the correct value after exactly $k$ steps of both not rolling the correct value. The probability that they will both roll the correct value for the first time at the same time is then $$\sum\_{k=0}^\infty\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2} = \left(\frac{1}{1-\left(1-\frac{3}{N^2}\right)}\right)\frac{1}{N^2} = \frac{1}{3}$$

So the odds of them rolling the correct value at the same time $m$ times in a row is $\frac{1}{3^m}$. With more miners, birthday problem aspects enter, but that won't change the exponential nature. (In fact, I don't think the birthday problem really comes into play since each miner still needs to get the correct value not just a value that matches another miner's.)

I'm pretty sure this is the idea the author had in mind. As you say, though, a malicious miner (a selfish miner) can withhold announcing blocks until they notice someone else announcing them. To account for that, you could instead consider (in the two miner world again) what the probability is that the malicious miner finds a block before the honest miner. If the miners are comparable, then that's presumably something like $\frac{1}{2}$. However, things are further complicated by the fact that when the malicious miner *does* find the correct value first, then that miner also gets a head start on finding the correct value for the next block. Nevertheless, for comparable miners, there is still a good chance that the honest miner will find a block first despite the malicious miner's head start. This reasoning starts to get into the selfish mining aspect I referenced in the comments.

---
Tags: probability-theory, distributed-systems, blockchain
---


# Question
Title: How does the computational complexity of problems depend on the model specifics of a register machine?
On wikipedia page of register machines it says that all register machines defined appropriately are equivalent to Turing machines but that

> Computational speed is very dependent on the model specifics.

Does this mean that when we say a problem has complexity $O(n^2)$ or is a polynomial time problem, or something like that, this is assuming some specific model of computation? If so, how general is the statement that a problem is in $P$ or in $NP$ or anything like that?

# Answer
> 1 votes
The basic definitions of computational complexity are normally phrased in terms of plain Turing Machines, so one has to be careful about transferring results to different models. Naturally, if you can perform look-ups faster, any program that requires that functionality will also be faster (at least for that part).

However if the other model is not to extreme, then the gap in the precise running times falls below our normal threshold of caring. That is, most models of fairly general interest are polynomially equivalent to Turing Machines, so even though a register machine is in some sense faster than a Turing Machine, it's not so much faster that it breaks the definitions - it only speeds things up by a polynomial factor (i.e. an $O(n^{a})$ algorithm will only go down to a $O(n^{b})$ algorithm with $b \leq a$).

You can of course define models that are significantly faster than a Turing Machine (for a trivial example, a Turing Machine that can solve $\mathsf{Clique}$ in a single step), at this point, you can't feasibly replace "Turing Machine" in the definition of $\mathsf{P}$ or $\mathsf{NP}$ with the new model without changing things significantly (but models like this do have other uses).

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


# Question
Title: Church-Turing Thesis and computational power of neural networks
The Church-Turing thesis states that everything that can physically be computed, can be computed on a Turing Machine. The paper "Analog computation via neural networks" (Siegelmannn and Sontag, *Theoretical Computer Science*, 131:331–360, 1994; PDF) claims that a neural net of a certain form (the settings are presented in the paper) is more powerful. The authors say that, in exponential time, their model can recognize languages that are uncomputable in the Turing machine model.

Doesn't this contradict the Church-Turing thesis?

# Answer
No, it's still consistent with the Church-Turing thesis, their model comes equipped with genuine real numbers (as in arbitrary elements of $\mathbb{R}$), which pretty much immediately extends the power beyond that of a Turing Machine. In fact, the title of 1.2.2 is "The meaning of (non computable) real weight", where they discuss why their model is built to include non-computable components.

There are in fact many models of computation that exceed the power of Turing Machines (q.v. Hypercomputation). The catch is that none of these are apparently able to be constructed in the real world (but maybe in the $\mathbb{R}$ world - sorry, couldn't resist).
> 47 votes

# Answer
To expand a little on Luke's answer, physically building a neural net to solve any language requires producing electronic components with infinitely precise resistances and so on. This isn't possible, in multiple ways:

1. You can't produce a resistor of exactly $\mathrm{2\\,\Omega}$.
2. Resistance changes with temperature and current flowing through the resistor will change its temperature.
3. Even supposing that you know an electronic engineer/sorcerer who can produce resistors to any exact value you choose and that don't change resistance with temperature, setting up your machine to decide an uncomputable language will require uncomputable resistance values. So there's no way you could actually tell your electronic engineer/sorcerer what resistance value you need.

So, although, in principle, these machines can decide any language, they don't violate Church–Turing because they can't be physically constructed.

You might want to engage in some rules-lawyering and claim that somebody could hand you one of these machines and say, "Hey, look, this machine just happens to have exactly the right resistance values to solve the halting problem!" However, they have no way of proving this claim, since they can't measure the components to infinite precision, so the best they can claim with justification is "I tested this on some finite set of inputs and it correctly decided the halting problem on those inputs." Well, any finite subset of the halting problem is already Turing-decidable so that's nothing exciting.
> 25 votes

---
Tags: computability, turing-machines, church-turing-thesis
---


# Question
Title: How memory remapping of physical address space that is above 4GB RAM works?
I have a query regarding the below information in http://duartes.org/gustavo/blog/post/motherboard-chipsets-memory-map/

*"In 64-bit mode it is possible to use physical addresses above the total RAM in the system to access the RAM regions that correspond to physical addresses stolen by motherboard devices. This is called reclaiming memory and it’s done with help from the chipset."*

Let's say if the RAM size is of 4GB. In 64-bit mode or with PAE enabled for 32-bit mode, if the address space above the total RAM 0x10000012C is assigned to some assorted device on the mother board, then how that assorted device can get hold of some memory region on RAM?

# Answer
> 0 votes
I am not entirely sure what your question is but I will try to answer. I think your confusion comes from the fact that some peripherals (typically PCI and APIC) use memory-mapped registers that "steal" memory from the physical address space (the famous 1GB hole described in the blog post). But those memory-mapped registers do not use RAM at all. They simply steal part of the address space and thus some physical addresses **that would normally refer to RAM** now serve another purpose. Now if you only have 4GB of RAM and the RAM is mapped at 0, a peripheral at 0x10000012C cannot create a hole in the RAM address space because the RAM is mapped from 0 to 0xffffffff. I attached a picture that hopefully makes this clearer.

In summary: when we say "memory-mapped register" what we really mean is "physical-address-space-mapped register", this has nothing to do with RAM.

Note, however, that any peripheral (memory-mapped or not), could **also** use some RAM, through DMA. But this is a totally different thing because by doing so it does not steal any physical address (and thus does not create a hole).

Finally note that all of this is simplified anyway because there isn't necessarily a unique physical address space in the system, each device may have a different view of the system. See  for a relatively clear explanation. Thus in the picture above, I am really referring to the CPU's physical address space.

: Not your parents’ physical address space, Gerber et al, PDF

---
Tags: computer-architecture, memory-management
---


title: Prove this language is non-regular

text:
# Question
Title: Prove this language is non-regular
I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated.

> *Prove using the Pumping Lemma that the following language is not regular.*
>
> *{0^n^3 |n ≥ 0 is an integer}*

From my understanding a language isn't regular if the power is linear. But I just cant get my head around using the Pumping Lemma to prove this even after reading other examples of Pumping Lemma.

I think most expressions require you to split them into seperate parts, but I just dont understand how this is possible for this expression.

---

# Answer
> 5 votes
Your language could be rewritten more clearly as:

$\\{ a^m \mid m \text{ is a perfect cube} \\}$

Now you'd have to find a word from this language, longer than the pumping length $p$, that can not be pumped. We choose as a candidate: $a^{p^3}$. We name our three substrings $x, y, z$, which must be of the form:
$x = a^i$
$y = a^j$
$z = a^{(p^3 - i - j)}$

The pumping lemma restricts $j$ to be greater than $0$ and $i + j \le p$. It's sufficient to show that there exists at least one integer $k \ge 0$, such that $xy^kz$ is not a valid word in the language. Because of our separation, we need to find a $k$ such that $p^3 + (k - 1)j$ is not a perfect cube.
Let's say $k = 2$, which gives us $p^3 + j$, strictly increasing with respect to $j$, having a maximum value of $p^3 + p$.
We also know that the smallest perfect cube larger than $p^3$ is $(p + 1)^3 = p^3 + 3p^2 + 3p + 1$.

Because $p^3 \lt (p^3 + p) \lt (p+1)^3, \forall p \gt 0$, our pumped string's length can't be a perfect cube (because it's strictly between two consecutive perfect cubes).

So the language contains at least one word longer than the pumping length that can't be pumped, which means the language isn't regular.

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


# Question
Title: Is a language containing set of binary numbers which are divisible by number N Regular?
Let N be any positive integer, then is following language regular for every $N$?

$L$ = { $B\_n : B\_n(modN) == 0$ } where $B\_n$ is binary representation of a number.

E.g, $L=\lbrace B\_n : B\_nmod31 == 0,B\_n \ is \ a \ binary \ number \rbrace$ is regular? Will the language be regular for any positive number in place of $31$.

# Answer
You can produce a finite automaton to recognize binary strings divisible by $N$ for any $N\>0$. Use $N+1$ states, $s$ (the start state) and $q\_i$, where being in state $q\_i$ corresponds to having seen input $B$ which is congruent to $i\bmod N$.

The transitions are then easy enough: in state $q\_i$ and seeing a $0$ input the machine would pass to state $q\_k$, where $k\equiv 2i\bmod N$, since appending a zero to a binary string doubles the number represented. Similarly $\delta(q\_i, 1)=q\_k$, where $k\equiv 2i+1\bmod N$.

The start state is there solely to avoid the question of what number the empty string represents, and obviously $q\_0$ is the final state.
> 2 votes

---
Tags: regular-languages
---


# Question
Title: Isn't NP problems always also co-NP problems?
I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every possible solution can be verified to be yes or no in polynomial time? If co-NP then is verifying no-instances isn't NP already doing that?

So simply put, if you can verifiy yes-instances can't you implicitly verifiy no-instances?

# Answer
> 3 votes
The definition you give in the quesition is very imprecise so it's understandable that you've misunderstood it. The formal definitions are given at our reference question on **NP**.

A decision problem is in **NP** if there's some polynomial $p$ and an ordinary, deterministic polynomial-time Turing machine $M$ such that:

* For every "yes" instance $x$, there is some $y$ with $|y|\leq p(|x|)$ such that $M$ accepts the string $x,y$;
* For every "no" instance $x$, $M$ rejects all strings $x,y$.

So, for example, 3-COLOURABILITY is in **NP**: the string $y$ is just a description of a $3$-colouring and $M$ accepts $x,y$ if $y$ is a valid $3$-colouring of the graph $x$ and rejects otherwise. The point is not that you can "verify 'yes' instances" but, rather, that every "yes" instance has a certificate $y$ that you can use to easily prove that it really is a "yes" instance.

But there's a significant asymmetry in the definition. If you give $M$ a "yes" input and a certificate $y$, then $M$ will say "I agree – that's a 'yes' instance." However, there's no input you can give it that will cause it to say "I agree – that's a 'no' instance." For any certificate you try, it will just say "That doesn't convince me it's a 'yes'." You could, of course, try all possible certificates. That would certainly prove that you had a "no" instance but there's a problem: there are exponentially many possible certificates to try, so trying all of them doesn't give you a polynomial-time algorithm.

# Answer
> -1 votes
No. As an intuitive argument, consider verifying primality. It is easy to show you that $8633$ is composite by $8633 = 89 \times 97$, whereas it is *not evident* that how this helps to develop a method to persuade you that some number is indeed a prime.

---
Tags: np, co-np
---


title: Does the A* algorithm visit every node?

text:
# Question
Title: Does the A* algorithm visit every node?
I have been taught that the A\* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, appear to show the algorithm stopping after finding the first path as the white blocks spreading out on the linked video do not cover the whole area before the path is highlighted, implying that not all nodes are visited.

Does the algorithm, therefore, not visit every node and instead stop after the first path is found? If so, is it not possible that a more optimum path could exist than the one found?

# Answer
It depends on how you implement your heuristic function. There are some properties that it must satisfy so that it will indeed return the optimal (shortest) path.

$A^\*$ differs from Dijkstra in the order that it chooses to expand partial paths. Recall that $A^\*$ expands a partial path to node $x$ if $f(x)$ is minimized over all nodes in the fringe. $$f(x) = g(x) + h(x)$$ where $g(x)$ is the actual distance to node $x$ and $h(x)$ is the *heuristic* estimate of the distance from $x$ to the goal node.

For $A^\*$ to choose an optimal (shortest) path $h(x)$ must satisfy:

* $h(x)$ is admissible, meaning it never *over*-estimates the actual minimal cost of reaching the goal.
* If you *do* use a closed set, meaning you never revisit nodes when they have already been visited (a tree search algorithm), then $h(x)$ must also be *monotonic* / consistent. This means for any pair of adjacent nodes $(x,y)$ we must have: $$h(x) \leq d(x,y) + h(y)$$ In other words, it is impossible to decrease $f(x)$ by extending the path to include a neighboring node.

Dijkstra's Algorithm is a case of $A^\*$ where $h(x) = 0$ and thus satisfies the listed properties and is therefore optimal.

Best-First Search is a case of $A^\*$ where $h(x)$ often overestimates the minimal cost (depending on implementation) and thus is not admissible and is therefore non-optimal.
> 2 votes

# Answer
It only flood-fills the graph if there is no path to the end-node.

What would be the point of including a heuristic if you were just going to visit every node anyways?
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis, search-algorithms, shortest-path
---


title: Computational Irreducibility

text:
# Question
Title: Computational Irreducibility
Define $Tape\_M(t, i)$ as the symbol in the $i$-th cell of the tape of Turing machine $M$ with empty input at step $t$.

> Does there exist a Turing machine $M$ such that *no* algorithm can compute $Tape\_M(t, i)$ within $o(t)$ (or $o(t/\log(t))$ ) time?

Actually, it is inspired by the celebrated *time hierarchy theorem*. I believe that it is true but I have trouble proving it. I think diagonalization may be a right direction (like what we do for time hierarchy theorem), but I am not certain how to diagonalize.

# Answer
I will assume that the alphabet is binary (not really important), and show that $Tape\_M(t,i)$ cannot be computed in $o(t/\log t)$ time for every $M$.

Consider a Turing machine $M$, which on the empty input, loops for all integers $i$ and does the following:

Simulate the $i$'th Turing machine $M\_i$ on the input $\left(g(i),i\right)$ for $\frac{g(i)}{\log g(i)}$ steps (the function $g$ will be determined later). If it produced output $r$, then write $\overline{r}$ in the $i$'th cell and never change that cell again (you can move forward on the tape and preform the next iterations on the rest of the tape).

Suppose for the purpose of contradiction that there exists a Turing machine $A$ which computes $Tape\_M(t,i)$ in $f(t)=o(t/\log t)$ time. Let $j$ be a large enough index of $A$, i.e. $M\_j=A$, such that for $t\ge j$ : $f(t)\<t/\log t$ (one can encode Turing machines in such a way that every machine has infinitely many representations, e.g. by allowing redundant zeros at the end). When $M$'s loop reaches $j$, it executes $Tape\_M(g(j),j)$, which according to our assumption, halts within $\frac{g(j)}{\log g(j)}$ steps with some symbol $r\in\\{0,1\\}$. $M$ then writes $\overline{r}$ in the $j$'th cell, and it is never changed again. Now suppose that up until the $j$'th iteration, $M$ used less than $g(j)$ time, then after $g(j)$ steps, $M$ has $\overline{r}$ written in the $j$'th cell, which contradicts the fact that $Tape\_M(g(j),j)=r$.

It remains to pick $g$ in such a way that until the $j$'th iteration, $M$ uses less than $g(j)$ time. The time required for $j$ iterations is $T\_j=\sum\limits\_{i=1}^j \frac{g(i)}{\log g(i)}\le j\frac{g(j)}{\log g(j)}$, assuming $\frac{g(i)}{\log g(i)}$ is monotonically non decreasing. Now, we want to pick $j$ such that $T\_j\le g(j)$, which is satisfied when $\frac{jg(j)}{\log g(j)}\le g(j)$, or equivalently $g(j)\ge 2^j$.
> 3 votes

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


# Question
Title: Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?
Recently I was reading again this propositions as types paper by Philip Wadler:

http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf

It gives an impression, that programs are proofs. So my first question was that why they are not enough for mathematical proofs then, for example in case of Riemann Hypothesis. Billions of zeros on critical line have been calculated in many many ways. I suppose they use some sophisticated algorithms or computer programs in that sense.

http://mathworld.wolfram.com/pdf/posters/Zeta.pdf

So, I was just stuck there. Why aren't these programs, or proofs in the system of Curry–Howard correspondence, enought?

# Answer
> 6 votes
The fact of the matter is, if a proof exists, then a Curry-Howard version of the program exists too. That doesn't mean that it's easy to find, though.

Undecidability still holds for Curry-Howard: if your types are advanced enough to capture logic, then there's no algorithm which takes in a type and outputs a program of that type, if it exists. Just like there's no algorithm that looks at a proposition and tells you if it's true or not.

> Billions of zeros on critical line have been calculated in many many ways.

Curry-Howard does *not* say that a program to compute zeroes can be turned into a proof of the Reimann hypothesis. It doesn't say that any program is a proof. What it says is, there is a dependently typed programming language where there's a type corresponding to the Reimann hypothesis, and a program with that type iff there's a proof of the Reimann hypothesis.

What this program would actually look like, if it's a proof, is a function that takes a number and a proof that that number is a zero of the Zeta function, and outputs a proof that that number is either a negative integer or has complex part 1/2. (Notice how the type of the input proof depends on the value of the given input, this is the "dependent" of dependent types).

# Answer
> 2 votes
The programs that you describe are very good at searching for zeroes *in an interval*; they can find all of the zeroes of the form $s+it$ between $t=0$ and $t=10^9$, say, and show that all these zeroes have $s=\frac12$. But that upper bound is critical, because it defines the search space. RH is the statement that *all* of the zeroes lie on the critical line, and no serial analysis of the zeroes within a given range will ever answer the question for all zeroes (so far as we know). What you're asking is exactly analogous to asking 'we've written programs to show that the Goldbach Conjecture is true for the first $n$ numbers, so why don't those programs constitute a proof that it's true for all numbers?'.

---
Tags: proof-techniques, first-order-logic, propositional-logic, mathematical-foundations, curry-howard
---


# Question
Title: Hint on median of two sorted lists, logarithmic time
I'm looking for a hint to help me think through/solve the problem of finding the median of two sorted lists/arrays in O(log(m+n)) time, where m,n are the sizes/lengths of each list, respectively.

I can immediately think of an obvious O(m+n) time algorithm using big-theta of m+n space, as follows: Merge the two lists into a new list in O(m+n) time. Find the middle element of that list in O(1) time (more particularly, if the merged list is even in length, take the mean of the floor of the element at index (m+n)/2, and the ceiling of the element at index (m+n)/2, otherwise the merged list length is odd and just use the element at (m+n)/2... potentially update logic for off-by-one depending on zero- or one-indexing).

But I don't immediately see how the median could be found in logarithmic time. Any hints would be appreciated!

# Answer
Let say you have the two sorted array arrange as follow, using uppercase letter to represent a sequence of numbers and a lowercase letter to represent a single number:

\[A,p,B\] and \[C,q,D\]

Now suppose p \> q, you know \[A, p\] and \[C\] \> \[q, D\], then what can you do with this fact?
> 3 votes

# Answer
Hint: Given any element, you can determine its relative position (in the sorted merged array) in time $O(\log m + \log n)$ using binary search. Use this primitive together with binary search to determine the median.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Model disjunction in a $\{0,1\}$ integer linear program
How can I model logical OR as an integer linear program?

$$(y\_3 + y\_4 + y\_5 + y\_6 = 2) \lor (y\_2 = 1)$$

where $y\_i \in \\{0, 1\\}$, $1$ = True and $0$ = False.

# Answer
Let's assume that all variables are Boolean (constrained to $\\{0,1\\}$). Here is how to encode the constraint "$x+y=1$ or $z=1$". Presumably you can extend this.

$$ \begin{align\*} &x+y+u-v = 1 \\ &z+w = 1 \\ &w+u+v \leq 1 \end{align\*} $$

If $x+y = 1$ then we take $u=v=0$ and $w=1-z$.

If $z = 1$ and $x+y = 0$ then we take $u=1$, $v=0$ and $w=0$.

If $z = 1$ and $x+y = 2$ then we take $u=0$, $v=1$ and $w=0$.

This shows that these equations are solvable when $x+y=1$ and when $z=1$.

Conversely, suppose that these equations are solvable, and so at most one of $w,u,v$ is non-zero. If $w = 0$ then $z = 1$. Otherwise, $u=v=0$ and so $x+y = 1$.
> 1 votes

# Answer
For simplicity let $Y = y\_3+y\_4+y\_5+y\_6 $. We can rewrite you requirement as $ ( (Y \geq 2) \land (Y \leq 2) ) \lor ((y\_2 \geq 1) \land (y\_2 \leq 1))$. Introduce a binary variable $z\_1$ to detect if $(Y \geq 2)$ using $M$ variables. Similarly introduce $z\_2$ to detect if $(Y \leq 2)$. Do the same for the other inequalities and call them say $z\_3, z\_4$. Now introduce binary variable $z\_5 = z\_1 \land z\_2$ (this can be done using Fortet's linearization without $M$ variables), similarly $z\_6 = z\_3 \land z\_4$. Lastly constrain $z\_5 + z\_6 \geq 1$.
> 0 votes

---
Tags: linear-programming, integer-programming, propositional-logic
---


# Question
Title: What is the relation between countability and recursive enumeration?
Does recursive enumeration implies countability? Does countability implies recursive enumeration?

I believe the first implication holds but not sure about the second. A good example would suffice.

# Answer
If a language is recursively enumerable then it is countable. However, there are languages that are countable but not recursively enumerable. For example, consider the $A\_{TM}$, the language of the Halting problem. This language is recursively enumerable while its complement $\Sigma^\*-A\_{TM}$ is not recursively enumerable, otherwise $A\_{TM}$ would be decidable. However, $\Sigma^\*-A\_{TM}$ is clearly countable since it is a subset of a countable set $\Sigma^\*$.

Hence one simple relation between countability and enumeration is that every r.e. set is countable, but the opposite is not always true.
> 3 votes

---
Tags: uncountability
---


# Question
Title: On $NP=\Sigma_2^P$ from non-deterministic time?
We know $NP=\bigcup\_{k\in\Bbb N}NTIME(n^k)$ and $\Sigma\_2^P=NP^{NP}$.

1. Does $\Sigma\_2^P\subseteq\bigcup\_{k\in\Bbb N}NTIME(n^k)$ also hold (we can do $O(n^k)$ queries to $NP$ oracle which runs in non-deterministic $O((n^k)^c)$ time which is non-deterministic $O(poly(n))$ time)?
2. Is there a reason we cannot conclude $NP=\Sigma\_2^P$ from this?

From this $NP=PH$ should hold.

# Answer
> 2 votes
Here is a simpler "proof" using the same ideas. I will show that NP=coNP. Indeed, suppose that $L \in \mathsf{coNP}$, and consider the machine which on input $x$, invokes the NP-oracle $\overline{L}$, and outputs the opposite value.

What goes wrong in this argument? Let us use the "witness" definition of NP: a language $L$ is in NP if there exist a polynomial $p$ and a polytime predicate $P$ such that $$ x \in L \Longleftrightarrow \exists |y| \leq p(|x|) \\, P(x,y). $$ Now suppose that $L$ is in coNP, that is, $$ x \in L \Longleftrightarrow \forall |y| \leq p(|x|) \\, \lnot P(x,y). $$ (We get this by applying the previous definition to $\overline{L}$.)

Our machine deciding $L$ nondeterministically accepts as input $x,y$ and outputs $\lnot P(x,y)$. However, this accepts a different language $L'$ given by $$ x \in L' \Longleftrightarrow \exists |y| \leq p(|x|) \\, \lnot P(x,y). $$ The difference is the quantification — existential instead of universal.

---

Informally, this shows that nondeterministic machines cannot simulate nondeterministic oracles. However, they can simulate deterministic oracles: $\mathsf{NP}^L = \mathsf{NP}$ for all polytime $L$. This is because an NP-machine can simulate the computation of $L$ on any given input directly. The same cannot be said about nondeterministic oracles.

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


title: Why does substitution terminate?

text:
# Question
Title: Why does substitution terminate?
I'm formalizing some properties of lambda calculus in Coq and I have some problems proving termination of substitution. My terms are defined as:

```
Inductive Term :=
  TVar: nat -> Term
| TAbs: nat -> Term -> Term
| TApp: Term -> Term -> Term.

```

and I have a way of generating fresh variables using a function

```
fresh: Term -> nat

```

satisfying:

```
Lemma fresh_is_fresh:
  forall t,
    ~ FV t (fresh t).

```

and similarly a function `fresh2: Term -> Term -> nat` for obtaining a fresh identifier wrt. two terms.

I now want to define a standard notion of capture avoiding substitution:

```
Fixpoint substitute (t1:Term) (t2:Term) (x:nat): Term :=
  match t1 with
  | TVar y =>
    if beq_nat x y then t2 else TVar y
  | TApp t11 t12 =>
    TApp (substitute t11 t2 x) (substitute t12 t2 x)
  | TAbs y t =>
    if beq_nat x y then
      TAbs x t
    else TAbs (fresh2 t t1) (substitute (substitute t (TVar y) (fresh2 t t1)) t2 x)
  end.

```

Obviously, Coq cannot see that this definition is terminating, so I need to provide a custom measure, so that the code is something like the following:

```
Program Fixpoint substitute (t1:Term) (t2:Term) (x:nat) {measure ???}: Term :=
  match t1 with
  | TVar y =>
    if beq_nat x y then t2 else TVar y
  | TApp t11 t12 =>
    TApp (substitute t11 t2 x) (substitute t12 t2 x)
  | TAbs y t =>
    if beq_nat x y then
      TAbs x t
    else TAbs (fresh2 t t1) (substitute (substitute t (TVar y) (fresh2 t t1)) t2 x)
  end.

```

Now my question is: What is the correct measure to use here? And how I do use it to prove the obligations which arise using this measure?

# Answer
> 2 votes
Derek Elkins' comment solved my problem! Here's the solution I came up with:

We create a seperate renaming function `rename: Term -> nat -> nat -> Term`, which assumes that the name to rename with is fresh. This makes it trivially terminating.

```
Fixpoint rename (t:Term) (x y : nat): Term :=
  match t with
  | TVar z =>
    if beq_nat y z then TVar x
    else TVar z
  | TApp t1 t2 =>
    TApp (rename t1 x y) (rename t2 x y)
  | TAbs z t =>
    if beq_nat y z then
      TAbs z t
    else
      TAbs z (rename t x y)
  end.

```

we then define a (somewhat arbitrary) measure of a term:

```
Fixpoint size (t:Term): nat :=
  match t with
    TVar _ => 1
  | TApp t1 t2 => size t1 + size t2
  | TAbs x t => 2 + size t
  end.

```

and we can easily prove that renaming preserves this measure:

```
Lemma rename_preserves_size:
  forall t x y,
    size t = size (rename t x y).

```

this lemma is used in the final case of substitition in order to prove that the term `rename t y' y` has the same size as `t` and thus the call `substitute (rename t y' y) t2 x` happens on a strictly smaller term.

Now *all* I need to prove that this is correct.

---
Tags: programming-languages, lambda-calculus, semantics, coq, termination
---


title: P-Completeness and Parallel Computation

text:
# Question
Title: P-Completeness and Parallel Computation
I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is unlikely to have an efficient parallel algorithms.

> What is the intuition behind this last statement?

# Answer
Any $P$-complete problem, is unlikely to have an efficient parallel algorithm. Why ?

The existence of $P$-complete problems is the most important clue that $(P ∩ POLYLOGSPACE) ≠ P$. The question then is, why is this conjecture relevant to parallel computing? Let's start with the resources used in a computation. For sequential computing: time and space; for parallel computing: time and hardware (number of processors). Is there a relation? Yes! Sequential space ↔ parallel time; Sequential time ↔ parallel hardware. The correspondence between sequential space and parallel time seems to be independent from the parallel computing model adopted; this leads to the following, so called *parallel computation thesis* which is unproven.

(Chandra and Stockmeyer) Every computation of a TM with space complexity $S(n)$ can be simulated in a parallel computing model in time $T(n) = O(S(n)^{O(1)})$ and every computation of a parallel computing model with time complexity $T’(n)$ can be simulated by a TM with space complexity $S’(n) = O(T’(n)^{O(1)})$.

The class of problems solvable sequentially in polynomial space is $PSPACE$ and the set of problems solvable in polynomial time is $P$.Since $PSPACE$ is thought to be a much larger class of problems than $P$, the thesis quantifies the effective improvement made possible by parallelism. A consequence of this thesis is that a PRAM can solve $NP$-complete problems in polynomial time… Unfortunately, no! The parallel computation thesis implies that we can actually deal with problems belonging to $PSPACE$… but this requires an exponential number of processors! A time-space trade-off is working: The exponential time on the sequential computing model is transformed into an exponential number of processors on the parallel computing model, whereas the polynomial space on the sequential computing model is transformed into a polynomial time on the parallel computing model.

This trade-off is easier to understand if we try to restrict both parallel time and parallel hardware: if the parallel computing model has a polynomial number of processors, then the class of problems solvable in parallel polynomial time is $P$. If we restrict the number of processors to a polynomial we can improve the performances of a sequential machine, but no more than a polynomial factor. Thus we can reduce the degree of the polynomial representing the time complexity, but we are not able using parallelism to reduce exponential costs to polynomial costs.

The problems solved in parallel with polynomial time complexity are those problems belonging to $P$. The polynomial constraint on the number of processors leads to a parallel computing model equivalent to TM. There are two important practical considerations: which polynomial number of processors is acceptable/affordable ? In practice, the polynomial number of processors is meant to be linear or close. Which subpolynomial time is achievable ? It turned out that almost all highly parallel feasible problems can achieve polylogarithmic parallel time. In parallel, a time complexity which is logarithmic in the input length represents an efficient parallel computation. A parallel algorithm is considered efficient if, given a polynomial number of processors, its time complexity is polylogarithmic.

Given a problem $R \in TIME\\\_SPACE\_{TM}(n^k, (log n)^h)$ where $k$ and $h$ are constants, the parallel computation thesis implies the existence of a parallel algorithm for $R$ with time complexity $O((log n)^{k’})$ where $k’$ is a constant. The comparison between sequential and parallel time allows classifying $R$ as a problem highly parallelizable (from a time perspective).

From the parallel computation thesis, it follows that $POLYLOGSPACE$ is the class of problems highly parallelizable. $POLYLOGSPACE$ does not contain problems complete with regard to log-space reductions; this implies $POLYLOGSPACE \neq P$. It seems that

1. $POLYLOGSPACE ⊄ P$
2. $P ⊄ POLYLOGSPACE$

$P ∩ POLYLOGSPACE$ contains the problems that can be solved in polynomial time using polylogarithmic space. $P$-complete problems probably belongs to $P - (P ∩ POLYLOGSPACE)$.

$NC$ (Nick’s class - so called in honour of Nicholas Pippenger, the first to identify and to characterize it in 1979) is the class of problems that can be solved in polylogarithmic time (i.e., with time complexity $O((log n)^k))$ with a polynomial number of processors (I.e., bounded by $O(f(n))$ for some polynomial function $f$ where $n$ is the problem size) The parallel computation thesis implies $NC ⊂ (P ∩ POLYLOGSPACE)$.

However, unfortunately by definition $NC$ also includes lots of problems which are *not* efficiently parallelizable. The most infamous example is *parallel binary search*. The trouble is that this problem has polylogarithmic time complexity even for $p$ = 1. Any sequential algorithm requiring at most logarithmic time in the worst case is in $NC$ regardless of its parallel feasibility!

Now, we can finally explain why $P$-complete problems are the hardest parallelizable problems. Given a $P$-complete problem $Q$, it is very unlikely the existence of an efficient parallel algorithm: if such a parallel algorithm would exist with time complexity $O((log n)^k)$, then the parallel computation thesis will imply the existence of a sequential algorithm with space complexity $O((log n)^{k’})$ for the same problem. Since $Q$ is a $P$-complete problem this in turn will imply that every problem in $P$ can be solved in poly-log space: $(P ∩ POLYLOGSPACE) = P$. As you already know, we instead believe that $(P ∩ POLYLOGSPACE) ⊂ P$, even though we are not yet able to prove this.

One final observation, about the polynomial processor requirement. Well, that is a theoretical statement. In practice: a processor requirement that grows faster than the problem size might not really be useful.
> 19 votes

# Answer
Because "efficient parallel" falls inside $\mathsf{NC}$ (“Nick's Class” of problems decidable in polylogarithmic time with a polynomial number of processors), and it is widely *believed* that $\mathsf{NC} \neq \mathsf{P}$. So any $\mathsf{P\text{-}complete}$ problem is not *believed* to have an efficient parallel algorithm (since that would imply that $\mathsf{P} = \mathsf{NC}$).

Of course all of this is up to conjecture that $\mathsf{NC} \neq \mathsf{P}$, as you know it is an open problem that $\mathsf{P}$ is not in the first level of $\mathsf{NC}$, i.e. we don't *know* if $\mathsf{NC^1} \neq \mathsf{P}$.

Even more, we don't even know if you cannot solve problems in $\mathsf{P}$ in $\mathsf{AC^0\[6\]}$, i.e. constant depth (=constant parallel time) boolean circuits with $\mod\_6$ gates.

For further information, take a look at the following book:

Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo, "Limits to Parallel Computation: P-Completeness Theory", 1995.
> 11 votes

# Answer
Kaveh's answer covers the usual definition of "parallelism", which is NC. The question of whether P $\<$ NC is one of the harder questions in complexity theory (and in some ways just as relevant as the P $\<$ NP question).

The intuition behind it is that some problems in P, like linear programming, or DFS order feel like they have a lot of dependencies that force a long "critical path" that can't be parallelized. This is not a proof any more than non-determinism seeming to be very powerful is, but this is the basic idea.

**Edit:** To clarify for the comments, the point of this answer is to say why (some) people don't think that P and NC are the same. Much as with P and NP, nobody knows how to prove whether the two are different, but there is something about the hard problems that makes (some) computer scientists think they are.

Another aside is that NC is "polylog time on polynomially many processors", which is asking for a very dramatic speedup but giving a lot of processors. Thus it might not fit a practical notion of parallelizable.

In particular, if you think that P $\<$ NP, then you will start looking at heuristics and approximation algorithms right away for NP-complete problems. On the other hand, even if you think that NC is smaller than P, you might be able to get non-trivial speedups from the kinds of parallelism available from today's computers.
> 7 votes

# Answer
Be very mindful of who takes "efficient parallel algorithms" to mean what, exactly.

The older answers explain the perspective of complexity theory. There, "efficient" usually means something vague like "runtime in $O(f(n))$ time with $O(g(n))$ processors". Note that the number of processors can depend on the input size!

In particular, the often named class NC is the

> set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.

This has *nothing* to do with whether there are parallel algorithms for these problems which are efficient in more practical terms¹:

* If you have an NC algorithm you get no information about how to solve the problem (efficiently) on any machine with a fixed number of processors.
* Just because there is no NC algorithm for a problem does not mean there isn't a "real" one; just because we can not break apart the problem into polynomially many very small pieces does not mean we can not break it into constantly many sufficiently smaller ones, as $n$ grows.

For instance, on constantly many processors with shared memory, CYK parsing can be done in parallel with asymptotically optimal speedup (see my master thesis, even though context-free parsing is P-complete.

Describing efficiency on machines with finitely many processors in a useful way requires more precise analysis than $O(\dots)$ since speed-up is bounded by a finite constant, the number of processors². You rarely find this in complexity theory. Therefore, if you want to learn about parallel algorithms that are of use in the real world, I would advise to look elsewhere.

---

1. Let $T\_p : \mathbb{N} \to \mathbb{R\_{\geq 0}}$ the runtime function of a parallel algorithm. You might want to call an algorithm "efficient" if $T\_1(n)/T\_p(n) \approx p$, or if $T\_1(n) \approx T(n)$ for $T$ the runtime function of a good sequential algorithm. I propose this in a more rigorous fashion in my master thesis, building from literature cited therein.
2. This is not always true; memory hierarchy and hardware may allow for larger speedup, at least sometimes. There will be another constant bound, though.
> 4 votes

# Answer
> Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?

That question was marked as duplicate this question, so let me just assume that it is really a duplicate, and provide one possible answer.

We know that NC != PSPACE, hence a proof that P=NC would also prove P != PSPACE. That may not sound like a big deal, but it is one consequence for computer science research.

Why do we know NC != PSPACE? Well, we know NCk ⊆ DSPACE(O(logk)), so we can just use the space hierarchy theorem.

---

In term of practical applications, the applications around linear (and convex) programming might be so seducing that custom parallel architectures together with compilers for translating linear programming formulations efficiently to that hardware could be developed and sold.
> 1 votes

---
Tags: complexity-theory, parallel-computing
---


# Question
Title: Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL
I'm trying to prove $L = \\{ w : w \neq w^R \\}$ over $\Sigma = \\{0,1\\}$ is CFL.

Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \\; T \to 0T|1T|\varepsilon$. Now I want to show that $\mathcal{L}(G) = L$.
One direction is fine, where given $w\in \mathcal{L}(G)$, it must've deduced using $S \to 1T0|0T1$, and therefore $w \neq w^R$.

But given $w \in L$, all I know is $w \neq w^R$. How can I prove $w\in \mathcal{L}(G)$?

# Answer
Use induction.

For instance:

* Define $\mathcal{L}\_i(G) = \\{ w \in \mathcal{L}(G) \mid |w| = i \\}$ for $i \in \\{ 0, 1, 2, \ldots \\}$.
* Prove that for all $w$ and $i \> 1$, $w \in \mathcal{L}\_i(G)$ if and only if $\exists x \in \Sigma, v \in \mathcal{L}\_{i-2}(G) : xvx = w$.
> 5 votes

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


title: Integer Programming Complexity

text:
# Question
Title: Integer Programming Complexity
I would like to seek help on the complexity of the following problem. Given positive integers $m$, $n$ and $D$, find all sequences $0 \lt a\_1 \lt a\_2 \lt \dots \lt a\_n$ are there such that:

1. each $a\_i\in\\{1, \dots, m\\}$
2. $\sum\_{i=1}^n a\_i = D$

I want to know the complexity with respect to $m$, $n$, $D$. To what extend of $m$, $n$, $D$ that is computationally feasible?

Thanks very much.

# Answer
This can be calculated using dynamic programming: for each $0 \leq T \leq D$ and $0 \leq \ell \leq n$, calculate $C(T,\ell)$, which is the number of solutions over $\\{1,\ldots,m\\}$ of $\sum\_{i=1}^\ell a\_i = T$. The base case is $C(0,0) = 1$ and $C(T,0) = 0$ if $T \> \ell$. For $\ell \> 0$, we have the formula $C(T,\ell) = \sum\_{S=\max(T-m,0)}^{T-1} C(S,\ell-1)$. The answer is $C(D,n)$. This algorithm runs in time $O(mnD)$.

Equivalently, you are looking for the coefficient of $x^T$ in the generating function $(x+\cdots+x^m)^n = x^n\left(\frac{1-x^m}{1-x}\right)^n$. This expression can be massaged to give an explicit formula involving a double summation with alternating signs.
> 1 votes

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


# Question
Title: Can a CD disk and the memory of a device have an infinite space storage?
I’m asking this because, I’m thinking that it is possible to make a CD or ps vita cd to have an infinite space storage so that new updates will come.

And, it is possible for the company Sony to make the new memory of ps vita to be infinite space storage?

Can anyone tell me if it is possible for a company to do that?

Out of curiosity.

Sorry if I have asked in a wrong site and for adding this tags, you can edit this post.

# Answer
> 2 votes
This is impossible.

Storing information requires physical space and there is a limit. This might seem somewhat obscured by the fact that we can store a lot of information in a small space, by the technological process which brought us smaller and smaller storage devices and by other factors which make the relationship between information and space less clear (e.g. a 700MB CD and a 50GB Blu-Ray disk have the same volume).

The limit on how much information can be stored is given by the Bekenstein bound:

$I \le \frac{2 \pi c R m}{\hbar ln2} $

$I$ is the information quantity that can be stored in a sphere with radius $R$ and mass $m$.

In short, you need an infinite amount of space to store an infinite amount of information, but a CD has a finite volume.

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


# Question
Title: Show that maximum disjoint set problem is NP Complete
I have been thinking on this problem but couldn't come up with a good reduction yet. First part of the proof, i.e L is being in NP, is okay. However, I cannot find a proper reduction from 3-CNF-SAT to MAXIMUM-DISJOINT-SET problem.

Edit 1: MDS definition MAXIMUM-DISJOINT-SET problem: We are given a collection S of sets. We would like to find the maximum number of disjoint sets in S. K sets are said to be disjoint sets if they have no element in common(Wikipedia description).

I have tried the following ideas so far:

1. Let each clause in 3-CNF form be a set with each literal being its element. Our decision problem is "is it possible to find at least k-many disjoint sets?
2. If we put each literal of a clause to a set and distinguish between a literal and its negation, it does not work since phi = $(x\_1 \lor x\_1 \lor x\_1)$ and $(\neg x\_1 \lor \neg x\_1 \lor \neg x\_1)$ is not satisfiable but it is considered as disjoint set.
3. If we negate back all negated literals, then the set phi = ($x\_1$ $\lor$ $x\_2$ $\lor$ $x\_3$) and $(\neg x\_1 \lor \neg x\_2 \lor \neg x\_3)$ is considered as non-disjoint although this function is satisfiable.

Any help is appreciated.

# Answer
Given MIS is NP-Complete, we can reduce MIS to MDS. Let $G = (V,E)$ the graph we have for MIS problem. For every vertex $v\_i \in V$, create a set $S\_i$ with edges of $v\_i$, however, be careful that write each edge element as $v\_iv\_j$ even if it is $v\_jv\_i$. Reduction is completed after creating the sets $S\_i$. There is an independent set in $G$ of size $m$ if, and only if, there are $m$ disjoint sets where sets are taken from independent set's vertices.

This reduction can be performed in polynomial time since we traverse each vertex $v$ and its edges. It can be performed in $O(V+E)$. Additionally, given a collection of sets, we can verify if they are disjoint and there are at least $k$ of them in polynomial time.

Consequently, MDS is NP-Complete
> 2 votes

---
Tags: complexity-theory, np-complete, 3-sat
---


# Question
Title: Comparison of two line segments along a ray
I have a point $q$, a ray $L$ (halfline which is cast from $q$) and two non-intersecting (intersection is only possible at endpoints) line segments $s\_1, s\_2$. I want to efficiently compute which of the two line segments along the ray $L$ is visible ("comes first").

I found the following description of a possible solution:

Why are at most five orientation predicates sufficient? I tried it on a few examples but can't convince myself fully.

# Answer
The best way to see this is to describe the algorithm more carefully:

Pick one of the segments, say $s\_1$. First, we test the orientation of the points $a\_2,b\_2$ w.r.t. $s\_1$. If both lie on the same side of $s\_1$, we test the orientation of $q$ w.r.t. $s\_1$. Then, we have two cases:

1. $q$ lies on the same side as $a\_2,b\_2$. This means $s\_1$ is further away, as your figure shows.
2. $q$ lies on the other side as $a\_2,b\_2$. This means $s\_2$ is further away, which can also be seen from the figure, with a little imagination.

If $a\_2$ and $b\_2$ do *not* lie on the same side w.r.t. $s\_1$, note that, since $s\_1$ doesn't intersect $s\_2$, it follows that $a\_1,b\_1$ are on the same side w.r.t. $s\_2$!

So, we now only need to test whether $q$ lies on the same side as $a\_1$, w.r.t. $s\_2$: If it does, $s\_2$ is further. If it doesn't, $s\_1$ is further.

So, we have exhausted all possibilities and determined which segment is further using only *four* orientation tests! (In the first case, we test $a\_2,b\_2,q$ w.r.t. $s\_1$ and in the second $a\_2,b\_2$ w.r.t. $s\_1$ and $q,a\_1$ w.r.t. $s\_2$) So, we were able to improve upon the given $5$ in the description, by postponing the testing of $q$, such that $q$ only has to be compared to one segment and not $2$.

---

(Note that in the given configuration, if we assume $q$ isn't collinear with any of the segments, no points are on the linear extension of the segment, which means they are always on exactly one side.)
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph?
I've read many literature papers, but I still cannot understand their exact formalization definitions. Is their any difference among them or is there any relationship among them?

# Answer
I've only ever heard of directed and undirected graphs, whose definitions can be found in Wikipedia. Rudimentary search reveals the following interpretations of unidirectional and bidirectional graphs; it is possible that these terms also have different interpretations:

* A *unidirectional graph* is another name for an undirected graph.
* A *bidirectional graph* is a directed graph obtained from an undirected graph by replacing each edge $\\{x,y\\}$ by a pair of edges $(x,y),(y,x)$.
> 3 votes

# Answer
Well I'll try giving simple definitions, let's hope you get the idea with that:

**Directed graphs:** Are basically those graphs that have edges with directional arrows marked on them. They show which direction to move between the two vertices they connect.

**Undirected graphs:** Are just the opposite of directed graphs, as in the edges do not have any associated directional arrows with them.

**Unidirectional Graph:** Is a graph with edges which are directed only in one direction, like in the case of a directed graph.

**Bidirectional Graph:** Is a graph in which each edge is given an independent orientation (or direction, or arrow) at each end. Thus, there are three kinds of bidirected edges: those where the arrows point outward, towards the vertices, at both ends; those where both arrows point inward, away from the vertices; and those in which one arrow points away from its vertex and towards the opposite end, while the other arrow points in the same direction as the first, away from the opposite end and towards its own vertex.
> 1 votes

---
Tags: graphs, mathematical-analysis
---


# Question
Title: Are all context-sensitive languages decidable?
I was going through the Wikipedia definition of *context-sensitive language* and I found this:

> Each category of languages is a proper subset of the category directly above it. Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.

I could see that linear-bounded automaton is directly below decider in the article's ordering. If this is the case, then that means every computation on a LBA will halt at some point (since every LBA would be a decider). But I feel that there may be some computation which can run on a LBA at the same time never to halt. For example we can write a computation on LBA which would

1. read the first symbol on the tape and move right;
2. read the next symbol and move back left.

This (useless) computation (which is obviously a LB computation) would run indefinitely oscillating left and right and never halt and hence cannot be a decider. Where am I thinking wrong?

# Answer
> 9 votes
First, all context-sensitive languages are decidable, since they can be accepted by a LBA (as you said), and a Turing machine is more powerful than a LBA.

However, you were asking about something else. Can there be LBA that cycles? The answer is yes. You gave an example. However, you can modify every LBA $M$ to a Turing machine $M'$ that accepts the same language but never cycles. To see this, observe, that you can simulate $M$ on $M'$ and keep track of all configurations the LBA has attained so far. If there is one configuration that shows up twice, you detected a cycle. In this case you stop rejecting. The important thing here is that the LBA uses on linear space, and hence the number of its configurations is bounded.

# Answer
> 0 votes
I suggest you take a look at this book: Introduction to Languages and the Theory of Computation by John E Martin

page 283: **There are still open questions concerning context-sensitive languages, such as whether or not every CSL can be accepted by a deterministic LBA.**

---
Tags: formal-grammars, turing-machines, undecidability, context-sensitive
---


# Question
Title: Is this a standard representation of a 'space' character?
I recently came across a handwritten note with directions to push a string of text into a database. There was a strange character in the string I've never seen before, **a lower case 'b' with a forward slash through it:**

I asked the author about it and he said it was an old-school way of representing a space.

My question is whether or not this was a standard/widely used representation of a space character and if so, whether or not it's still commonly used.

# Answer
> 4 votes
The symbol ␢ has a unicode representation: 2422-unicode-blank-symbol.

It is an old typographic symbol for specifying explicit blanks in code. As Wikipedia states:

> This was used in the early years of computer programming when writing on coding forms. Keypunch operators immediately recognized the symbol as an 'explicit space'.

ps. I also learned this symbol as Turing tape blank. I will check an old book later. Nowadays I would use B or if I am feeling adventurous ␣ 'open box' (U+2423) $\text{\textvisiblespace}$.

---
Tags: strings, notation
---


# Question
Title: King of the North: Placing bannermen surrounding castle
I was trying to solve the King of the North problem in Kattis. Basically, the problem is, the king has a castle to protect. To do this, he wants to place bannermen across the open areas surrounding the castle (some parts are closed thanks to natural barriers).

A more detailed description of the problem: Given a grid of $R$ rows and $C$ columns, where one square contains our castle and some contain walls. We can place bannermen, who can blockade a square. Each open square has a different amount of bannermen required to form a blockade, which is given. Our task is to determine the minimum amount of bannermen that have to be fielded such that the castle is unreachable from the edge of the grid. (walls and blockaded squares are impassable)

*Please go through the attached link for an even more detailed (and colourful) description of the problem.*

My idea to solve this:

> 1. Go to each outermost corner of the map. From each of these points, do a A\* search. This will give the shortest path from the point to the castle.
> 2. For each such point on the shortest path, try to see which ones are 'critical' - meaning placing bannermen on those points will force the enemy to take a longer path.
> 3. Among all such critical points, see which ones need lesser bannermen.

Anyone has a better idea?

I do not like my approach, particularly because it involves heuristics, and I am not sure whether it is correct.

# Answer
This appears to be a max-flow/min-cut problem. Consider the directed graph $G$ with all non-hill/wall squares as vertices and edges between the neighbouring non-hill/wall cells in the map.

As the weights in the problem are on the vertices, but we need them as capacities on the edges, replace each vertex $u$ by the pair of vertices $u\_{in}$, $u\_{out}$ such that $c(u\_{in},u\_{out}) = w(u)$ and all incoming edges of $u$ are connected to $u\_{in}$ and all outgoing edges of $u$ are connected to $u\_{out}$. Give the capacity $+\infty$ to all other edges (so we cannot 'cut' those edges).

Call our castle the sink and connect all borders of the map to a source. Note that the edges can be bidirectional, except for those connected to the source or sink.

Now, the minimum amount of bannermen to required to protect the castle is equal to the minimum value over edges in our graph $G$ we need to remove such that the sink (our castle) cannot be reached from the source (the outside of the map). This is precisely the minimum cut on this graph $G$. So, we can compute the number of men required in $O((R+C)^3)$ using the Edmonds-Karp algorithm, where $R,C$ is the amount of rows and columns in our map. Given that $R,C\leq 300$, this approach is likely fast enough to solve the problem within the time limit.

---

Your approach looks a lot like an heuristic approach to the min-cut problem. I don't see any reason that this would be always be correct in this case, so that approach would likely fail, as you suspect.
> 7 votes

---
Tags: computational-geometry
---