# Question
Title: What is a dichotomy? Whether 2-SAT itself is a dichotomy of SAT?
Recently, I am reading papers about *dichotomy*. I do not understant what condition can be called as a *dichotomy*? What is the meaning of "a question is either in **P** or in **NP**-*complete*"? (assume **P** $\neq$ **NP**)

For example, I've known the Schaefer's dichotomy theorem, in which a dichotomy about "whether a class of SAT is in **P**" is given. In this theorem, the dichotomy contains six conditions, one of them is "2-SAT".

So my question is that, whether "2-SAT" itself can be called as a *dichotomy* or a trivial *dichotomy*, because 2-SAT is in **P** but 3-SAT is **NP**-*complete*? In another words, I wonder that "if a special class of an **NP**-*complete* problem is in **P**, then this class is a dichotomy? or a trivial dichotomy?"

# Answer
> 13 votes
A (coarse) *dichotomy theorem* states that in a certain class of problems, each problem is either in P or NP-hard. For example, Schaefer's dichotomy theorem concerns the class of problems of the form $\mathrm{SAT}(S)$. Here $S$ is a collection of Boolean relations, and $\mathrm{SAT}(S)$ is the problem of deciding satisfiability of propositions which are conjunctions of relations from $S$. This is best explained by an example. The problem 2SAT is $\mathrm{SAT}(S\_2)$ with $S\_2$ consisting of the following three predicates: $$ (x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y. $$ That is, each instance of 2SAT is a conjunctions of clauses of one of these three forms, where you can substitute any variables you want for $x,y$. As another example, HORNSAT is $\mathrm{SAT}(S\_H)$ where $S\_H$ is the following infinite collection: $$\begin{gather\*} x \mapsto x, \quad x \mapsto \lnot x, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y, \\ (x,y,z) \mapsto x \lor \lnot y \lor \lnot z, \quad (x,y,z) \mapsto \lnot x \lor \lnot y \lor \lnot z, \\ (x,y,z,w) \mapsto x \lor \lnot y \lor \lnot z \lor \lnot w, \quad (x,y,z,w) \mapsto \lnot x \lor \lnot y \lor \lnot z \lor \lnot w, \ldots \end{gather\*}$$ Schaefer's dichotomy theorem states that for each *finite* $S$, the problem $\mathrm{SAT}(S)$ is either in P or it is NP-complete (this is a *dichotomy* since there are only two possibilities). For example, 2SAT and $k$-HORNSAT are in P for every $k$, while 3SAT is NP-complete. This is surprising since if we believe that P$\neq$NP then Ladner's theorem shows that there are intermediate problems - problems which are neither in P nor NP-complete. Schaefer's theorem shows that these problems cannot be of the form $\mathrm{SAT}(S)$.

A more refined version of Schaefer's theorem states that $\mathrm{SAT}(S)$ is either in co-NLOGTIME, L-complete, NL-complete, $\oplus$L-complete, P-complete or NP-complete. In the past few years, countless generalizations of Schaefer's theorem have been proven or conjectured, including results about counting solutions and approximating the maximum number of satisfiable clauses, as well as results over non-Boolean domains. The main conjecture is the Feder-Vardi *dichotomy conjecture* which states that Schaefer's theorem holds for relations on an arbitrary finite-sized domains. For the status of Schaefer's original theorem in the case where $S$ is infinite, see this question.

# Answer
> 5 votes
The word "dichotomy" comes from the Greek *dichotomia* meaning divided, or split in two. Thus, a dichotomy is any statement of the form, "Everything is either A or B but not both." The classic example is, "You're either with us or against us." Schaeffer's dichotomy for Boolean CSP (which he calls "Generalized Satisfiability") is another example: for every finite set of Boolean relations, the corresponding satisfiability problem is either is either in P or is NP-complete (but not both, assuming that P$\neq$NP). Kuratowski's theorem is also a dichotomy: every graph is either planar of contains $K\_5$ or $K\_{3,3}$ as a (topological) minor.

Notice that a dichotomy isn't the end of the story and it might be possible to produce a more detailed classification. You might be completely with us or only slightly against us. Some of the polynomial-time cases of Schaeffer's theorem are easier than others (Allender, Bauland, Immerman, Schnoor, Voller, "The Complexity of Satisfiability Problems: Refining Schaeffer's Theorem". *Journal of Computer and System Sciences*, 75:245-254, 2009.)

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


title: Is Co-NP closed under taking subset?

text:
# Question
Title: Is Co-NP closed under taking subset?
I have a question on my homework causing some confusion.

> If L is a strict subset of L', and L' is a member of Co-NP, is L a member of Co-NP? True of False

Now I understand what belonging to Co-NP. Essentially means instead of deciding a yes instance we're deciding a no instance of the decidable problem. I'm stuck on interpreting L' and what it is.

My guess at this point is that L is a member of Co-NP since it's a subset of L' which we're given is in Co-NP.

# Answer
> 3 votes
For a language $L' \in \mathsf{coNP}$, there are certificates for all NO instances, which is to say inputs $x \notin L'$, which could be efficiently verified and used as proof that $x \notin L$. Suppose that $L \subset L'$: the fact that there are certificates for all NO instances $x \notin L'$ isn't enough to allow us to determine decisively if $x \notin L$, because we could have an input $x \in L' \smallsetminus L$.

Thus, the certificates for $L'$ are not sufficient to provide certificates for $L$, and we ***cannot*** conclude that $L \in \mathsf{coNP}$. Indeed, as @G.Bach indicates in the comments, there are examples where $L' \in \mathsf{coNP}$ and $L$ is not even a decideable language. Modifying his example, consider $$ L' = \Bigl\\{ x \in \\{0,1\\}^\ast \\;\Big|\\; |x| \text{ is prime} \Bigr\\}$$ which has certificates for NO instances simply by giving a non-trivial factor for $|x|$ on any input $x \notin L'$. Then $L' \in \mathsf{coNP}$, and indeed $L' \in \mathsf P$: not only because the AKS algorithm puts primality testing in $\mathsf P$, but because (the input being expressed in unary) even trial division would represent an efficient algorithm. However, the language $$ L = \left\\{ x \in L' \\;\left| \begin{array}{c} x \text{ encodes a Turing machine} \\ \text{and an input on which it halts,} \\ \text{padded with 0s} \end{array} \right\\}\right.$$ using whichever encoding of Turing machines that you like will not even be a decideable language in general, and so it will definitely not be in $\mathsf{coNP}$.

---
Tags: complexity-theory, closure-properties, np
---


# Question
Title: How can a Turing machine run another machine for an infinite amount of strings?
The proof in my textbook, that $E\_{TM}$ can be decided by oracle machine $O^{A\_{TM}}$, uses a Turing machine $P$ such that for an input $w$:

* $P$ runs the Turing machine $M$ on all strings of $\Sigma^\*$
* If $M$ accepts the string, $P$ accepts

$O^{A\_{TM}}$ then asks the oracle if $\<P,w\> \in A\_{TM}$

I can't seem to understand why $P$ can run $M$ for all strings of $\Sigma^\*$ because this is an infinite amount of strings. I do, however, understand that $P$ actually never has to run and is purely constructed to ask the oracle if it accepts.

# Answer
> 3 votes
The technique is knows as *dovetailing*. The machine $P$ keeps a two-dimensional tape and uses the following algorithm:

1. Run $M$ on the first string for one step.
2. Run $M$ on the first two strings for one step.
3. Run $M$ on the first three strings for one step.
4. ...

(We imagine that all possible strings are arranged in some arbitrary computable order, say $\Lambda,0,1,00,01,10,11,000,\ldots$.)

Each simulation of $M$ runs on its own "row" of the two-dimensional tape of $P$, which also stores the location of the head and the current state. (A two-dimensional tape can be simulated by a one-dimensional tape.)

If $M$ ever halts on one of the strings, then $P$ halts. Therefore $P$ halts iff $M$ halts on *some* input.

---
Tags: turing-machines, strings
---


# Question
Title: Parallelising random reads seems to work well — why?
Consider the following very simple computer program:

```
for i = 1 to n:
    y[i] = x[p[i]]

```

Here $x$ and $y$ are $n$-element arrays of bytes, and $p$ is an $n$-element array of words. Here $n$ is large, e.g., $n = 2^{31}$ (so that only a negligible fraction of the data fits in any kind of cache memory).

Assume that $p$ consists of **random numbers**, uniformly distributed between $1$ and $n$.

From the perspective of modern hardware, this should mean the following:

* reading $p\[i\]$ is cheap (sequential read)
* reading $x\[p\[i\]\]$ is very expensive (random reads; almost all reads are cache misses; we will have to fetch each individual byte from the main memory)
* writing $y\[i\]$ is cheap (sequential write).

And this is indeed what I am observing. The program is very slow in comparison with a program that does only sequential reads and writes. Great.

Now comes the question: **how well does this program parallelise** on modern multi-core platforms?

---

My hypothesis was that this program does not parallelise well. After all, the bottleneck is the main memory. A single core is already wasting most of its time just waiting for some data from the main memory.

However, this was *not* what I observed when I started experimenting with some algorithms where the bottleneck was this kind of operation!

I simply replaced the naive for-loop with an OpenMP parallel for-loop (in essence, it will just split the range $\[1,n\]$ to smaller parts and run these parts on different CPU cores in parallel).

On low-end computers, speedups were indeed minor. But on higher-end platforms I was surprised that I was getting excellent near-linear speedups. Some concrete examples (the exact timings may be a bit off, there is a lot of random variation; these were just quick experiments):

* 2 x 4-core Xeon (in total 8 cores): factor 5-8 speedups in comparison to single-threaded version.
* 2 x 6-core Xeon (in total 12 cores): factor 8-14 speedups in comparison to single-threaded version.

Now this was totally unexpected. Questions:

1. Precisely **why does this kind of program parallelise so well**? What happens in the hardware? (My current guess is something along these lines: the random reads from different thread are "pipelined" and the average rate of getting answers to these is much higher than in the case of a single thread.)
2. Is it **necessary to use multiple threads and multiple cores** to obtain any speedups? If some kind of pipelining indeed takes place in the interface between the main memory and the CPU, couldn't a single-threaded application let the main memory know that it will soon need $x\[p\[i\]\]$, $x\[p\[i+1\]\]$, ... and the computer could start fetching the relevant cache lines from the main memory? If this is possible in principle, how do I achieve it in practice?
3. What is the right **theoretical model** that we could use to analyse this kind of programs (and make *correct* predictions of the performance)?

---

**Edit:** There is now some source code and benchmark results available here: https://github.com/suomela/parallel-random-read

Some examples of ballpark figures ($n = 2^{32}$):

* approx. 42 ns per iteration (random read) with a single thread
* approx. 5 ns per iteration (random read) with 12 cores.

# Answer
> 9 votes
Forget for a moment all of the issues related to the access to main memory and level 3 cache. From a parallel perspective, ignoring these issues, the program parallelize perfectly when using $p$ processors (or cores), owing to the fact that, once you partition the work to be done through domain decomposition, each core must process either $\left\lfloor {\frac{n}{p}} \right\rfloor$ or $\left\lceil {\frac{n}{p}} \right\rceil$ elements and there is no communication and/or synchronization overhead since there is no functional dependence among the processors. Therefore, ignoring memory issues you expect a speedup equal to $p$.

Now, let's take into account the memory issues. The super-linear speedup you actually observed on your high-end Xeon based node is justified as follows.

A parallel system might exhibit such behaviour if its memory is hierarchical and if access time increases (in discrete steps) with the memory used by the program. In this case the effective computation speed could be slower on a serial processor than on a parallel computer using similar processors. This is because a sequential algorithm using $n$ bytes of memory will use only $n/p$ bytes on each processor of a $p$ processor parallel system, while cache and virtual memory effects could instead reduce the serial processor’s effective computation rate.

For $n = 2^{31}$ bytes, we need 2048 Mbytes of memory. But, when using 12 cores as in your last example, every core needs to deal with only 2048/12 Mbytes of data, which is about 170 Mbytes. High-end Xeon processors are equipped with a cache level 3 whose size ranges from 15 to 30 Mbytes of size. Clearly, with this huge cache size the cache hit ratio is high, and this explains the good or even super-linear speedup-observed.

Regarding your second question, current architectures already prefetch data by evicting cache lines and replacing them as required to exploit temporal and spacial locality of data. But this will not be enough for a single core processing 2048 Mbytes of data. If you restrict $n$ to about 170 Mbytes, then you should see on a single core more or less the same performances, since you are now running under (more or less, not exactly) the same conditions.

Finally, besides QSM (Queueing Shared Memory), I am not aware of any other theoretical parallel model taking into account at the same level the contention for access to shared memory (in your case, when using OpenMP the main memory is shared among the cores, and the cache is always shared as well among the cores). Anyway, even though the model is interesting, it did not obtain great success.

# Answer
> 5 votes
I decided to try out \__builtin\_prefetch() myself. I'm posting it here as answer in case others want to test it on their machines. The results are close to what Jukka describes: About a 20% decrease in running time when prefetching 20 elements ahead versus prefetching 0 elements ahead.

Results:

```
prefetch =   0, time = 1.58000
prefetch =   1, time = 1.47000
prefetch =   2, time = 1.39000
prefetch =   3, time = 1.34000
prefetch =   4, time = 1.31000
prefetch =   5, time = 1.30000
prefetch =   6, time = 1.27000
prefetch =   7, time = 1.28000
prefetch =   8, time = 1.26000
prefetch =   9, time = 1.27000
prefetch =  10, time = 1.27000
prefetch =  11, time = 1.27000
prefetch =  12, time = 1.30000
prefetch =  13, time = 1.29000
prefetch =  14, time = 1.30000
prefetch =  15, time = 1.28000
prefetch =  16, time = 1.24000
prefetch =  17, time = 1.28000
prefetch =  18, time = 1.29000
prefetch =  19, time = 1.25000
prefetch =  20, time = 1.24000
prefetch =  19, time = 1.26000
prefetch =  18, time = 1.27000
prefetch =  17, time = 1.26000
prefetch =  16, time = 1.27000
prefetch =  15, time = 1.28000
prefetch =  14, time = 1.29000
prefetch =  13, time = 1.26000
prefetch =  12, time = 1.28000
prefetch =  11, time = 1.30000
prefetch =  10, time = 1.31000
prefetch =   9, time = 1.27000
prefetch =   8, time = 1.32000
prefetch =   7, time = 1.31000
prefetch =   6, time = 1.30000
prefetch =   5, time = 1.27000
prefetch =   4, time = 1.33000
prefetch =   3, time = 1.38000
prefetch =   2, time = 1.41000
prefetch =   1, time = 1.41000
prefetch =   0, time = 1.59000

```

Code:

```
#include <stdlib.h>
#include <time.h>
#include <stdio.h>

void cracker(int *y, int *x, int *p, int n, int pf) {
    int i;
    int saved = pf;  /* let compiler optimize address computations */

    for (i = 0; i < n; i++) {
        __builtin_prefetch(&x[p[i+saved]]);
        y[i] += x[p[i]];
    }
}

int main(void) {
    int n = 50000000;
    int *x, *y, *p, i, pf, k;
    clock_t start, stop;
    double elapsed;

    /* set up arrays */
    x = malloc(sizeof(int)*n);
    y = malloc(sizeof(int)*n);
    p = malloc(sizeof(int)*n);
    for (i = 0; i < n; i++)
        p[i] = rand()%n;

    /* warm-up exercise */
    cracker(y, x, p, n, pf);

    k = 20;
    for (pf = 0; pf < k; pf++) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }
    for (pf = k; pf >= 0; pf--) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }

    return 0;
}

```

# Answer
> 4 votes
1. DDR3 access is indeed pipelined. http://www.eng.utah.edu/~cs7810/pres/dram-cs7810-protocolx2.pdf slides 20 and 24 show what happens in the memory bus during pipelined read operations.
2. (partially wrong, see below) Multiple threads are not necessary if the CPU architecture supports cache prefetch. Modern x86 and ARM as well as many other architectures have an explicit prefetch instruction. Many additionally attempt to detect patterns in memory accesses and do the prefetching automatically. The software support is compiler-specific, for example GCC and Clang have \__builtin\_prefech() intrinsic for explicit prefetching.

Intel-style hyperthreading seems to work very well for programs that spend most of their time waiting for cache misses. In my experience, in computation intensive workload the speedup goes very little above the number of physical cores.

EDIT: I was wrong in point 2. It seems that while prefetching can optimize memory access for single core, the combined memory bandwidth of multiple cores is greater than bandwidth of single core. How much greater, depends on the CPU.

The hardware prefetcher and other optimizations together make benchmarking very tricky. It is possible to construct cases where explicit prefetching has a very visible or non-existent effect on performance, this benchmark being one of the latter.

---
Tags: parallel-computing, cpu-cache, memory-hardware
---


title: Is radix sort a greedy algorithm?

text:
# Question
Title: Is radix sort a greedy algorithm?
I was thinking of radix sort, and at a sudden thought that it uses de facto the paradigm of dynamic programming, but I soon changed my mind to greedy algorithm. Is it really a greedy algorithm?

# Answer
Personally, I would not call it a greedy algorithm. I'm not sure that's a useful way to think about it.

A greedy algorithm optimizes some global objective function by making small choices, where at each step we make a locally optimal choice (among all the choices at each step, we choose the one that best improves our objective function). In a greedy algorithm, the objective function monotonically increases at each step of the algorithm. I don't see any sense in which radix sort has this form.

This becomes clearest if we look at the version of radix sort that starts by sorting on the least significant digit, then the next-least significant digit, etc. Here the objective function does not monotonically increase. The first step can take you further away from being sorted, but then later steps bring you back.

For instance, consider the list $\[0101, 0010, 0001\]$. Let's look at what happens if we apply radix sort to this list. The first pass will transform this to $\[0010, 0101, 0001\]$: it got further away from being sorted. After the second pass, we get $\[0101, 0001, 0010\]$, then after the third pass we get $\[0001, 0010, 0101\]$: it is finally sorted. So, we started out being close to sorted, then we got farther away from being sorted, then we got closer -- not exactly the characteristic of a greedy algorithm.

For an even better example, consider the list $\[0001, 0010, 0101\]$. Let's look at what happens if we apply radix sort to this list, even though it happens to already be sorted. The first pass will transform this to $\[0010, 0001, 0101\]$. I don't care what your global objective function is; this has certainly made the global objective function worse, because it changed the list from being completely-sorted to being not-sorted. So, this shows that radix sort doesn't seem to be a greedy algorithm (at least if you start by sorting on the least significant bit).

There's an alternative version of radix sort where we sort first by sorting on the most significant digit, then the next-most significant digit, etc. This does feel closer to a greedy algorithm, though I'm not sure that viewpoint is really useful in any practical way.

It is definitely not a dynamic programming algorithm.

I'm not sure that trying to classify it in this way is useful or helpful. I don't think it'll help you, e.g., understand how greedy algorithms work, or help you design better greedy algorithms in the future in other settings. I'd suggest you think about radix sort on its own terms: it just is what it is.
> 5 votes

---
Tags: algorithms, terminology, sorting
---


# Question
Title: Hashing a Specific Range Of a Character Array
I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my array remains the same throughout the process of hashing, I only am changing the range. To deal with this, I have to make an entire copy of the array everytime I process a query, and then compute the hash from the above function.

I am using Arrays.copyOfRange to create a copy everytime I process a query. I need to avoid this. So I was thinking of devising a hashing scheme of my own. This scheme should be such that I whould get a unique hash for each array range. Hashes should be same if all characters in the range are same.

Any Help on how to proceed with the making of such a hash function will be appreciated.

# Answer
> 1 votes
Use a rolling hash function, such as the Rabin-Karp hash. This allows you to compute hashes of any subrange of $A$ very efficiently, e.g., in $O(1)$ time, assuming you use some extra memory to keep track of all of the intermediate states of the rolling hash.

---

If $A\[0..n-1\]$ is your array, a rolling hash defines the hash of the entire array using a recurrence like this:

$$x\_i = f(x\_{i-1}, A\[i\])$$

where $x\_{-1}$ is some fixed constant and $f$ is some function. Now here's what you can do. You can store the $x$ values in an array $X\[0..n-1\]$ (where $X\[i\]=x\_i$). This will allow you to compute the hash of any prefix of $A$.

If you want to be able to compute the hash of any consecutive range of $A$, choose the function $f$ carefully to be reversible.

---

A simple instantiation: let $X\[-1\] = 0$ (for some constant $c$) and

$$X\[i+1\] = \alpha \cdot X\[i\] + A\[i\] \bmod 2^{32},$$

where $\alpha$ is some 32-bit constant (you'll want it to be odd). Preprocess the array $A$ once to compute the array $X\[0..n-1\]$.

Now, the hash of $A\[i..j-1\]$ can be very efficiently computed: it is the following:

$$X\[j-1\] - \alpha^{j-i} X\[i-1\] \bmod 2^{32}.$$

Notice that $\alpha^{j-i} \bmod 2^{32}$ can be computed efficiently using fast exponentiation algorithms, i.e., repeated squaring modulo $2^{32}$. Thus, assuming you've stored the array $X$ alongside the array $A$, a hash of any range of $A$ can be done in $O(1)$ time.

---

If you want something even simpler and easier to implement, set $\alpha$ to 1. Then the hash of $A\[i..j-1\]$ just becomes $A\[i\]+ A\[i+1\]+ \cdots + A\[j-1\]$, and $X\[i\]$ stores $A\[0\] + A\[1\] + \cdots + A\[i\]$, so the hash of $A\[i..j-1\]$ is just $X\[j\]-X\[i\]$.
However, the quality of this hash degrades and you might see an increase in hash collisions.

# Answer
> 0 votes
```
int hash = 0;
for (int i = range_start; i < range_end; i++)
    hash = hash*31 + your_array[i];

```

---
Tags: data-structures, arrays, hash, hash-tables
---


# Question
Title: Reducing from a Turing machine that recognizes is regular to the halting problem
I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present.

This is the reduction they give:

PROOF We let R be a TM that decides REGULARTM and construct TM S to decide ATM . Then S works in the following manner.

S = “On input $M$, $w$ , where M is a TM and w is a string:

1. Construct the following TM $M\_{2}$ .

$M\_{2}$ = “On input x:

1. If x has the form $0^{n} 1^{n}$ , accept .
    2. If x does not have this form, run M on input w and accept if M accepts w.”
2. Run R on input $M\_{2}$ .
3. If R accepts, accept ; if R rejects, reject .”

So, we start with a machine that decides whether a language of a TM is regular. And we want to use that to decide if a TM halts on a given input.

My question: What if $w$ does have the form $0^{n} 1^{n}$? Well, $M\_{2}$ accepts that string just cause of the form. But we never actually run $M$ on $w$. So how can we say that it will accept or reject it? We have no idea what it does because we never ran it on $w$.

# Answer
Here's the key: work out what $L(M\_2)$ is.

Notice that $M\_2$ takes a string $x$ as input, so we are trying to identify which strings $x$ will cause $M\_2$ to accept.

There are two cases:

* Case 1: If $M$ accepts on input $w$. Then $L(M\_2)=\Sigma^\*$.

In other words, in this case, it doesn't matter what $x$ is. $M\_2$ will always accept on input $x$. If $x$ has the form $0^n 1^n$, then $M\_2$ accepts (in step 1). If $x$ does not have the form $0^n 1^n$, then $M\_2$ also accepts (in step 2). $M\_2$ accepts either way; it accepts on every possible input.
* Case 2: If $M$ does not accept on input $w$. Then $L(M\_2) = \\{0^n 1^n : n \in \mathbb{N}\\}$.

Let's look at why this is. If $x$ has the form $0^n 1^n$, then $M\_2$ accepts in step 1. If $x$ does not have the form $0^n 1^n$, then $M\_2$ runs step 2 and doesn't accept (since $M$ doesn't accept on input $w$).

So, $L(M\_2)$ is one of two possibilities: it is either $\Sigma^\*$ (everything) or $\\{0^n 1^n : n \in \mathbb{N}\\}$. Which of those two possibilities it is will depend upon $M$ and on $w$ (and in particular on whether $M$ accepts on $w$). Remember that implicitly $M\_2$ is dependent upon $M$ and $w$: it's got them hard-coded into its code.

Moreover, $\Sigma^\*$ is regular, but $\\{0^n 1^n : n \in \mathbb{N}\\}$ is not regular. So if we have a way to tell whether the language of a TM is regular or not, we have a way to tell whether $L(M\_2)$ is $\Sigma^\*$ or $\\{0^n 1^n : n \in \mathbb{N}\\}$ -- which in turn means we have a way to distinguish Case 1 from Case 2, or in other words, we have a way to tell whether $M$ accepts on input $w$ or not.

That means, if we have a way to tell whether the language of a TM is regular or not, we have a way to solve the halting problem. (It's not the *same* TM; it's a related TM. The way we tell whether $M$ accepts on $w$ is not by analyzing whether the language of $M$ is regular; we construct some new TM that is related to $M$ and $w$ in a crazy way, and then test whether the language of that new TM is regular or not.)

---

It's important to remember that $w$ is not an input to $M\_2$. Instead, $w$ is just a constant that is hard-coded into the source code of $M\_2$. It would be like hard-coding the value of pi as 3.1415927 in your code, except here the hardcoded constant is going to be whatever $w$ is. Each different $w$ corresponds to a different $M\_2$.

P.S. I'll also repeat a crucial point from Karolis Juodelė: "Strings are not regular, languages are."
> 4 votes

---
Tags: computability, turing-machines, reductions, undecidability
---


title: Proving SSum is NP-Complete?

text:
# Question
Title: Proving SSum is NP-Complete?
SSUM is the same as the Subset Sum Problem with the only additional requirement is all the numbers must be unique in the subset.

To prove it's NP complete, the verifier is quite easy to construct being the same as one for the Subset Sum except you add the additional requirement of making sure all numbers are unique.

With the reduction, I assume you can use the same reduction as before from 3SAT, I'm just figuring out a way when evaluating that reduction, to determine if two or more numbers are the same. I'm using the 3SAT reduction in Sipser with the table of columns and rows. If one needs any more information I would be happy to provide.

# Answer
> 5 votes
One way to show that SSUM is NP-hard is by reduction from SUBSET-SUM. The idea is to replace each number $n\_i$ by two numbers $Mn\_i + \epsilon\_i$ and $\epsilon\_i$, where $M$ is a "large" integer and $\epsilon\_i$ is a "small" integer. By varying $\epsilon\_i$ you ensure that all numbers are different. You set your target at $MT+\delta$, where $T$ is the original target and $\delta = \sum\_i \epsilon\_i$. Further details left to you.

---
Tags: np-complete, reductions, 3-sat
---


# Question
Title: Complexity classes that are closed under subtraction
Are NP or P closed under subtraction? Im having a hard time deciding whether they are or aren't. *Question was edited*

**Original question**: Im having some hard time figuring out what languages are closed under subtraction. Say you have 2 languages A, B ∈ NP. Is A\B ∈ NP? what about P?

**Commenters**: My original question was extremely not accurate so i rephrased :)

Thanks!

# Answer
> 1 votes
$A \setminus B$ is defined as $\\{x | x \in A ~ and ~ not ~ x \in B \\}$. If you know the complexity of checking $x \in A$ and $x \in B$, what does that tell you about the complexitty of $x \in A \setminus B$? Can you see the algorithm for checking it?

---
Tags: complexity-theory, closure-properties, np
---


# Question
Title: Reducing from Hamiltonian Cycle to Subgraph Isomorphism
I am reading Subgraph isomorphism problem

I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article.

Can someone help me explain what is happening in more laymen terms?

# Answer
> 8 votes
In $\mathrm{Subgraph\\,\\,Isomorphism}$, you're given two graphs $G$ and $H$, and the question is whether you can delete some vertices and edges from $G$ to get $H$ (i.e. $H$ is a subgraph of $G$). The reduction from $\mathrm{Hamiltonian\\,\\,Cycle}$ to $\mathrm{Subgraph\\,\\,Isomorphism}$ is really just rephrasing what it means for a graph to have a Hamiltonian cycle.

A Hamiltonian cycle in a graph is a cycle that includes every vertex, so if we ignore the other edges in the graph, we can think of the Hamiltonian cycle as a subgraph of the original graph with the properties that it contains all the vertices, only some of the edges, and those edges make a cycle. That is, a Hamiltonian cycle in an $n$-vertex is isomorphic to the graph $C\_{n}$.

So if we start with $G$ and we can find a subgraph that's isomorphic to $C\_{|V(G)|}$, $G$ must be Hamiltonian. This is the same as solving the $\mathrm{Subgraph\\,\\,Isomorphism}$ problem where $H=C\_{|V(G)|}$.

---
Tags: algorithms, graphs, np-complete
---


title: Question on SAT reduction

text:
# Question
Title: Question on SAT reduction
Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard.

I know how to show that the complement of Two-Solutions-SAT is in NP, it's relatively easy to create a nondeterministic polynomial time TM that decides it.

My problem comes with reducing from SAT to the complement of Two-Solutions-SAT. I understand how to reduce from SAT to 3SAT, but in the case of 3SAT you will always have CNF's with 3 variables. With the complement of Two-Solutions-SAT, you have to somehow reduce to the case where you have 0 or 1 or \>= 3 distinct satisfying assignments, and I'm not sure how to go about reducing to that.

Thanks

# Answer
> 2 votes
Hint: For a formula $\varphi$, let $\\#(\varphi)$ be the number of satisfying assignments of $\varphi$. Come up with a polytime transformation $T$ so that $\\#(T(\varphi)) = \\#(\varphi) + 2$.

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


title: Is $O(N+M)$ exponential or polynomial?

text:
# Question
Title: Is $O(N+M)$ exponential or polynomial?
So In a review section, our professor asked:

Given integers $N$ and $M$

Is $O(N+M)$ exponential or polynomial.

It's exponential, but I just don't see how that is. I would have thought it's linear.

# Answer
> 8 votes
Exponential or polynomial **in what**? As stated, it's clearly polynomial in $M$ and $N$.

The complexity of algorithms is given in terms of the length of the input. If an algorithm receives $M$ and $N$ as input, written in binary, then $M+N = O(2^\ell)$, where $\ell$ is the length of the input in bits.

You should ask your professor for clarification. S/he knows what s/he actually said and what the context was; we're just guessing.

# Answer
> 3 votes
There must have been some miscommunication. It's not exponential, unless there is some additional context that we're missing. (e.g., if $M=2^N$, then $N+M=O(2^N)$ is exponential in $N$)

---
Tags: landau-notation
---


# Question
Title: Complexity of calculating a single model versus all models of a propositional formula with a SAT solver
I have little background with SAT sovers and theoretical computer science.

How can I describe the complexity of calculating all models of a propositional formula versus just the usual SAT problem of finding just one model?

I am writing a paper, in an area where finding a single of a model of a type of propositional formula is considered "easy", but for my reasearch I need to calculated all models. (I am using Picosat that can calculate all models of a logic formula.) Is there a way to describe how "hard" or "complex" finding all models is compared to finding a single model?

# Answer
> 2 votes
The worst-case complexity of finding all models of a SAT formula over $n$ variables is roughly $\Theta(2^n)$. (For instance, consider a formula where all assignments satisfy the assignment; then there are $2^n$ satisfying assignments, so just listing all satisfying assignments takes $\Omega(2^n)$ time.)

Nonetheless, this number probably isn't very useful in practice. In practice, the running time to find all models depends heavily on the formula and on the number of models. Standard methods for worst-case complexity don't offer a good way to summarize the time to do this, as the running time practice varies heavily.

So, for your paper, I wouldn't place much stock on this complexity figure. I just don't think it is very illuminating.

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


# Question
Title: How to approach NFA design questions intuitively?
I did see a lot of nice and informative questions, articles on inter-net and on StackOverflow itself, of-course. But I found all the questions or articles following a specific rule or a pattern to explain the topic. I mean, when a question was asked on NFA, DFA or Regular Expression, a solution was presented to the question abiding by the theorems / rules of these topics (Theory of Computation).

But what I feel is that, as most of the questions on DFA/NFA are of the type "Design an NFA...." or "design a DFA..." , I feel that developing/Designing DFA/NFA must be an ART.

And where there is ART I feel there is an intuition. If these problems involve "DESIGNING" something ,then everyone must have their own way (of-course not going out-of-the-way of theorems or rules as such) of solving or attacking these problems. One should have developed a thinking process (over the years of practise) to solve these problems.

So I would like all the experts over this Site to share their knowledge (preferably in simple words) how they think over the problems (simple ones) of these topics.

I would like to elaborate the question with a simple example.

> Let F be the language of all strings over {0,1} that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes F .

Or maybe this:

> Design an NFA to find a 4-state NFA for the complement of F.

These questions are from the Sipser's book and I have also found the solutions for them myself.

I just want to know , how one can develop an intuition for solving the problems?

# Answer
> 2 votes
There is one sentence in your question that is worth answering:

> I just want to know , how one can develop an intuition for solving the problems?

Same thing everybody does, be is musicians, crafts men or scientists: exercise. There is no shortcut.

You can certainly use the growing database of questions we have here. There is little use in repeating techniques here as they more often than not depend on the concrete example.

For regular languages in particular, you can devise *any* formal representation of the language as long as the model is equivalent to regular languages. There typically are (computable) methods to transform such representations (e.g. regular expression) to finite automata.

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


# Question
Title: Data structure to use for a consumable message queue where it's safe for messages to overwrite one another
I have a queue of messages representing filesystem operations that need to be processed in order. A message may succeed or fail when it's sent. A change message, for example, is generated when a user creates or saves a file.

* Delete Foo.txt message sent
* Delete Bar.txt message sent
* Change Baz.txt message sent
* Change Foo.txt message sent

In the most common case, I pop the top item from the queue and send it off for processing, which succeeds.

But suppose this happens:

* Delete Foo.txt message attempted (FAIL)
* Delete Bar.txt message attempted (OK)
* Change Baz.txt message attempted (OK)
* Change Foo.txt message attempted (OK)

What should I do in this case?

I want to move on and process the next item in the queue, but it's not that simple. In this case, "Delete Foo.txt" *must* be processed before "Create Foo.txt", otherwise we're deleting Foo.txt from the search index (see "more details" below), even though it exists.

One approach I had considered: a key-value store, where the document path is the key, and the Message is the value. In the context of a filesystem, the only operation that matters is the most recent, so overwriting the Message associated with a file if it hasn't been sent might work.

What kind of data structure and algorithm is right for this situation? I don't want to reinvent the wheel.

A few more details:

* New items are constantly arrive in the queue, from multiple producer threads
* The messages are consumed from the collection by a single consumer
* A message is a serialized object, sent to a RabbitMQ broker
* This queue exists in case the RabbitMQ broker goes down or a Publisher Confirm fails
* Messages are consumed from the endpoint by a different service which performs various actions to keep a search index incrementally up to date
* C#, if it matters

**Update 1:**

*Big picture*

I am sending messages *about* filesystem operations that have occurred. These messages are used to keep a search index (elasticsearch) up to date. A few minutes behind is perfectly acceptable. If a user makes three saves in rapid succession, I don't need search index updates for the first two saves. (If it happens, that's fine, but it's not required.)

CRUD operations are done by users working with their files on a busy network share. Each write operation triggers a message that has to be sent to a persistent work queue (the RabbitMQ broker). An example message might contain data that boils down to "File F has been deleted" or "File Y has been changed". (No file contents are contained therein.)

(These messages are consumed by another component downstream that performs an action based on the contents of the message, which is outside the scope of this question.)

Because messages represent filesystem actions that were performed in a sequence by users they either:

* Have to be sent in order so they can be processed in order OR
* The message associated with the most recent write operation on File F should overwrite any queued message associated with File F that hasn't been sent yet

In my example above (second unordered list), it's safe for the message representing "Change Foo.txt" to overwrite a failed "Delete Foo.txt", because the Change message was triggered after the Delete message. (The time where Foo.txt didn't exist isn't important.) Hence my thought of a using key-value store of as a holding area in case of a Message send failure.

# Answer
> 1 votes
Sorry, you have to tell us more. We can't tell you what you should do in case of a failure; that will depend upon the application semantics and the type of a failure.

In general, in the event of a failure of an attempted operation, there are several options:

* Retry the operation later.
* Treat the failure as permanent.

If you decide you want to retry it later, then the implications of this for other operations depends on the dependencies between operations and the desired semantics. If operations A and B commute (performing A first then B has the same effect as B then A), and if you try A and it fails, then often you can perform B immediately and then retry A. If operations A and B don't commute, and you try A first and it fails, then performing B immediately and then retrying A will have different semantics, which might or might not be acceptable depending upon what guarantees you are trying to provide.

Related topics: ACID, database transactions.

---

Example: Suppose you have a one-level filesystem (with no directories), and the intended semantics are that operations on one file can be performed in an arbitrary order compared to operations on another file (but operations on a single file are performed in the order they were requested).

Then operations A and B commute if they are performed on different files, and they don't commute if they're performed on the same file. Thus, conceptually you can maintain one queue per file. When you receive a request to perform operation $O$ on file $F$, append $O$ to the queue for $F$. Whenever you are free to perform an operation, pick an arbitrary file whose queue is non-empty and try the operation at the head of the queue. If the operation succeeds, then you can pop it from the queue. If it fails and you want to retry it later, then you have to leave it at the head of the queue to be retried later.

Such a data structure can be implemented with a hash table of queues. The hash table is keyed on the filename; it yields a queue. It's easy to implement all the necessary behaviors using this data structure.

---

I am assuming that there are only two possible outcomes of an attempted operation: success (the operation is performed in full), or failure (and there is no effect: this is the same as a no-op). If it is possible that an operation can fail partway through without rolling back its effects, so it has a partial effect, then you've got much bigger problems.

---
Tags: data-structures
---


title: Euclidean Algorithm in Coq

text:
# Question
Title: Euclidean Algorithm in Coq
## Question

> How do I write more intuitive proofs of the two following results in Coq?

```
Theorem Course_of_values_ind:
        InductiveRel N less

  Theorem DivRem: (forall d n:N,
      (Sigma N (fun q => (Sigma N (fun s =>
         and  (I N n (add (mul (succ d) q) s)) (less s (succ d))))))).

```

## Background

I recognize all of these results are already built into Coq, and so it is possible to provide much easier proofs than what I am asking for. This is something I have managed to do on my own; simply using the Coq library for this particular task. Even though this is much more concise (and thus arguably more elegant), I find don't find it very instructive.**Luke Mathieson** provided a good example of this when he gave an alternative proof in Coq of trichonomy for natural numbers:

```
(*
  The following is just to show what can be done with some of the tactics
  The omega tactic implements a Pressburger arithmetic solver, so anything
  with natural numbers, plus, multiplication by constants, and basic logic
  can just be solved. Not very interesting for practicing Coq, but cool to
  know.
*)

Require Import Omega.

Example trich' : forall (n m : nat),
  n < m \/ n = m \/ m < n.
Proof.
  intros.
  omega.
Qed

```

Notice that the actual proof of the theorem in Coq does not reveal how the proof would look like informally. Thus, my hope is that someone may be kind enough to give a more, shall we say "intuitive", proof of the Euclidean division algorithm in Coq. The proof I have in mind will uses structural induction, which rests on the validity of the following lemma:

> **Lemma**: *$(\mathbb{N},\<)$ is well founded. (Course\_of\_values\_ind)*

As this is so critical to the proof of the Euclidean division algorithm I decided to prove it.

**Proof**:

Suppose that $P(x)$ set $(x:N$) is a progressive predicate (definition is given below the proof of the Euclidean division algorithm) on $N$. Define \begin{equation} Q(x)=\_{def}(\forall y:N)(y\<x \subset P(y)) \tag{\*}\end{equation}

It is enough to prove $(\forall x:N)Q(x)$, as then for any $x:N$ we have $x\<S(x)$ and so $P(x)$. $Q(0)$ follows by Peano's forth axiom. The inductive step $(\forall x N)(Q(x) \subset Q(S(x)))$ follows by theorem A (see Theorem Proofs in Coq) combined with Peano 1a and 1b (see Code-file).

> For all natural numbers $n$ and $m$ if $n\>0$, if $m\>0$ then there are natural numbers $q$ and $r$ such that $n=qm+r$ and $r\<m$.

One may formalize this as:

> \begin{equation}(\forall n:\mathbb{N})(\forall k:\mathbb{N})(\exists q:\mathbb{N})(\exists r:\mathbb{N})(n=\_{\mathbb{N}}q\cdot S(k)+r \land r\<S(k) \end{equation}

where $m:=S(k)$. Now, an informal proof of the so-called Eucliean theorem can be given as:

Proof:

Let $k$ be an arbitrary natural number, define $m:=S(k)$ and then proceed by strong induction on $n$ (this is justified by lemma). Suppose $n$ is a natural number and for every $l \<n$ there are natural numbers $q$ and $r$ such that $l=mq+r$ and $r \<m$. We now have two cases:

1. $n\<m$. Let $q=0$ and $r=n$, Then clearly $n=qm+r$ and $r\<m$.
2. $n \geq m$ Let $l=n-m\<n$ and observe that since $n \geq m$, $l$ is a natural number. By the inductive hypothesis one may now choose $q'$ and $r'$ such that $l=q'm+r'$ and $r'\<m$. But, this means we have $n-m=q'm+r'$, so $n=q'm+r'+m=m(q'+1)+r'$. So, if we let $q=q'+1$ and $r=r'$, then we have $n=qm+r$ and $r\<m$.

# Definitions of the terms I use in my informal proofs

```
      Definition Progressive
           (A:Set)(R: A -> A -> Set)(P:A -> Set):=
        (forall x:A,
         (forall y:A, R y x -> P y) -> P x).

        Definition InductiveRel
        (A:Set)(R: A -> A -> Set):=
        (forall P:A->Set, Progressive A R P ->
        forall x:A, P x).

        Theorem Course_of_values_ind:
        InductiveRel N less
    Definition Decidable (A B:Set)(R: A -> B -> Set):Set :=
    forall x:A, forall y:B, or (R x y) (not (R x y)).

    Definition and (A B:Set) := prod A B.
    Definition and_el_left (A B: Set)(p: and A B)
    := fst p.
    Definition and_el_right (A B: Set)(p: and A B)
    := snd p.
(* Euclidean Division *)

Theorem DivRem: (forall d n:N,
  (Sigma N (fun q => (Sigma N (fun s =>
     and  (I N n (add (mul (succ d) q) s)) (less s (succ d))))))).

```

## Code-file

This code was generously provided by **cody** (again see Theorem Proofs in Coq). It is my intent to add the results presented above to this code as soon as they are all complete.

```
(* Inductive Sigma (A:Set)(B:A -> Set) :Set := Spair: forall a:A, forall b : B a,Sigma A B. *)

(* Definition E (A:Set)(B:A -> Set) (C: Sigma A B -> Set) (c: Sigma A B)  *)
(*   (d: (forall x:A, forall y:B x, C (Spair A B x y))): C c := *)
(*   match c as c0 return (C c0) with  *)
(*     | Spair a b => d a b  *)
(*   end. *)

Print sigT.

(* Binary sum type *)

(* Inductive sum' (A B:Set):Set := inl': A -> sum' A B | inr': B -> sum' A B. *)

(* Print sum'_rect. *)

(* Definition D (A B : Set)(C: sum' A B -> Set) (c: sum' A B)  *)
(*   (d: (forall x:A, C (inl' A B x))) (e: (forall y:B, C (inr' A B y))): C c := *)
(*   match c as c0 return C c0 with  *)
(*     | inl' x => d x  *)
(*     | inr' y => e y  *)
(*   end. *)

Print sum.

(* Three useful finite sets *)

(* Inductive N_0: Set :=. *)

(* Definition R_0 (C:N_0 -> Set) (c: N_0): C c :=  *)
(*   match c as c0 return (C c0) with end. *)

Print False.

(* Inductive N_1: Set :=  *)
(*   zero_1 : N_1. *)

(* Definition R_1 (C:N_1 -> Set) (c: N_1) (d_zero: C zero_1): C c :=  *)
(*   match c as c0 return (C c0) with  *)
(*     | zero_1 => d_zero  *)
(*   end. *)

Print unit.

(* Inductive N_2: Set :=  *)
(*  | zero_2 : N_2  *)
(*  | one_2 : N_2. *)

(* Definition R_2 (C:N_2 -> Set) (c: N_2) (d_zero: C zero_2) (d_one: C one_2): C c :=  *)
(*   match c as c0 return (C c0) with  *)
(*     | zero_2 => d_zero  *)
(*     | one_2 => d_one  *)
(*   end. *)

Print bool.

(* Natural numbers *)

(* Inductive N:Set :=  *)
(* |zero: N  *)
(* | succ : N -> N. *)

(* Print N. *)

(* Print N_rect. *)

(* Definition R (C:N -> Set) (d: C zero) (e: (forall x:N, C x -> C (succ x))): (forall n:N, C n) :=  *)
(*   fix F (n: N): C n :=  *)
(*   match n as n0 return (C n0) with  *)
(*     | zero => d  *)
(*     | succ n0 => e n0 (F n0)  *)
(*   end. *)

Print nat.

(* Boolean to truth-value converter *)

(* Definition Tr (c:N_2) : Set :=  *)
(*   match c as c0 with  *)
(*     | zero_2 => N_0  *)
(*     | one_2 => N_1  *)
(*   end. *)

Definition Tr (b : bool) : Type := if b then unit else False.

(* Identity type *)

(* Inductive I {A: Type}(x: A) : A -> Type :=  *)
(*   r : I x x. *)

(* Print I_rect. *)

(* Hint Resolve r.  *)

Print identity.

Notation "x ~ y" := (identity x y)(at level 60).

Notation "#":=(identity_refl)(at level 10).

Definition J
  (A : Type)
  (C: (forall x y : A, forall e : x ~ y, Type))
  (d: (forall x:A, C x x (# x))) :
  (forall (a : A)(b : A)(e : a ~ b),  C a b e) :=
    fun a b e =>
      match e in _ ~ b with
        | # => d a
      end.

Check J.

(* functions are extensional wrt identity types *)

Definition id_ext {A B: Type} {x y : A} (f: A -> B):
  (x ~ y -> (f x) ~ (f y))
  := fun p =>
    match p with
      # => # (f x)
    end.

(* addition *)

(* Definition add (m n:N) : N := R (fun z=> N) m (fun x y => succ y) n. *)

Print plus.

(* multiplication *)

(* Definition mul (m n:N) : N := R (fun z=> N) zero (fun x y => add y m) n. *)

Print mult.

(* Axioms of Peano verified *)

Require Import Arith.

Theorem P1a: (forall x: nat, (0 + x) ~ x).
Proof.
  simpl; auto.
Defined.

Theorem P1b: forall x y: nat, ((S x) + y) ~ (S (x + y)).
Proof.
  simpl; auto.
Defined.

Theorem P2a: (forall x: nat, (0 * x) ~ 0).
Proof.
  simpl; auto.
Defined.

Theorem P2b: forall x y: nat, ((S x) * y) ~ (y + (x * y)).
Proof.
  simpl; auto.
Defined.

(* Definition pd (n: N): N := R (fun _=> N) zero (fun x y=> x) n. *)

Print pred.

Theorem P3: (forall x y: nat, (S x) ~ (S y) -> x ~ y).
Proof.
 intros x y p.
 apply (id_ext pred p).
Defined.

(* Definition not (A:Set): Set:= (A -> N_0). *)

Print notT.

Definition isnonzero (n: nat): bool:= if n then false else true.

Eval compute in isnonzero 1.
Eval compute in isnonzero 0.

Notation "x !~ y":= (notT (x ~ y))(at level 60).

Definition false_if_succ (n : nat) : Type := if n then unit else False.

Hint Resolve tt.

Theorem P4 : (forall x: nat, (S x) !~ 0).
Proof.
  intro x.
  intro.
  assert (false_if_succ (S x)).
  rewrite H.
  simpl; auto.
  simpl in X; auto.
Qed.

Theorem P5 (P:nat -> Type): P 0 -> (forall x:nat, P x -> P (S x)) -> (forall x:nat, P x).
Proof.
  intros; induction x; auto.
Defined.

(* I(A,-,-) is an equivalence relation *)

(*All these are in the std library *)

Lemma Ireflexive (A:Set): (forall x:A, x ~ x).
Proof.
  auto.
Defined.

Lemma Isymmetric (A:Set): (forall x y:A, x ~ y -> y ~ x).
Proof.
  auto.
Defined.

Lemma Itransitive (A:Set): (forall x y z:A, x ~ y -> y ~ z -> x ~ z).
Proof.
  intros x y z e1 e2.
  rewrite e1; auto.
Defined.

Lemma S_cong : (forall m n:nat, m ~ n -> (S m) ~ (S n)).
Proof.
  intros m n e; rewrite e; auto.
Defined.

Lemma zeroadd: (forall n:nat, (n + 0) ~ n).
Proof.
  induction n; simpl; auto.
  rewrite IHn; auto.
Defined.

Hint Rewrite zeroadd.

Lemma Sadd: (forall m n:nat, (m + (S n)) ~ (S (m + n))).
Proof.
  induction m; intro n; auto.
  simpl; rewrite IHm; auto.
Defined.

Hint Rewrite Sadd.

Lemma commutative_add: (forall m n:nat, (m + n) ~ (n + m)).
Proof.
  induction m; intro n.
  rewrite zeroadd; auto.
  simpl; rewrite IHm.
  rewrite Sadd; auto.
Defined.

Lemma associative_add: (forall m n k:nat, ((m + n) + k) ~ (m + (n + k))).
Proof.
  induction m; auto.
  intros n k; simpl.
  rewrite IHm; auto.
Defined.

Print sum.

Open Scope type_scope.

(* Definition or (A B : Set):= (A + B). *)

Definition less (m n: nat) := { z : nat & S (z + m) ~ n}.

Notation "m < n" := (less m n)(at level 70).

Lemma less_lem : forall n m : nat, n < (S m) -> (n < m) + (n ~ m).
Proof.
  intros n m leq.
  elim leq.
  induction x; simpl; intro e.
  right.
  apply P3; auto.
  left.
  exists x.
  apply P3; auto.
Defined.

Theorem nattrichotomy: forall n m:nat, (n < m) + (n ~ m) + (m < n).
Proof.
  induction n; induction m; simpl.
  left; right; auto.
  left; left.
  exists m; rewrite zeroadd; auto.
  right; exists n; rewrite zeroadd; auto.
  destruct IHm as [ leq | gt ].
  destruct leq as [lt | eq].
  left; left; destruct lt.
  exists (S x).
  simpl; rewrite i; auto.
  left; left; exists 0.
  rewrite eq; simpl; auto.
  generalize (less_lem _ _ gt); intro less_eq.
  destruct less_eq as [less| eq].
  right.
  destruct less.
  exists x.
  rewrite Sadd; rewrite<- i; auto.
  left;right; rewrite eq; auto.
Defined.

```

# Answer
> 2 votes
I have a few suggestions. Here is the updated version. As you can see I run out of steam at the end (I'll finish up when I get the time).

Again several suggestions:

1. cs.stackexchange usually doesn't answer specific questions about coq developments which, by definition, usually aren't a huge help to others. You'd be much more welcome on the coq-club mailing list (and the answers would be by people more expert than I).
2. Use the built-in equality! The equality you are using is excruciatingly hard to work with as many tactics (replace, auto with arith, ring, omega) won't do anything with it.
3. I suggest you start with a less ambitious project. While simple on paper, proving Euclidian division from scratch isn't feasible in Coq if you're still struggling with elementary things about \< or addition. Here even with the `omega` tactic, things are far from trivial for a beginner. It's a slow road at first...
4. Try to procure or borrow Coq'Art which is the (very) extended version of Coq In a Hurry.
5. My code is terrible. I should have developed high-level tactics and hint databases to make the proofs simpler (mimicking `auto with arith`). I'll do it if I find the time.

---
Tags: proof-techniques, automated-theorem-proving, proof-assistants, mathematical-programming, coq
---


title: Finding valid permutation using a graph

text:
# Question
Title: Finding valid permutation using a graph
Let $A$ be a set of integers: $A=\left \\{ x\_1, x\_2...x\_n \mid 10\<x\_i\<100\right \\}$

A *valid permutation* $x\_{i\_1}x\_{i\_2}...x\_{i\_n}$ is a permutation that holds the following property:

For every adjacent numbers $x\_{i\_j}x\_{i\_{j+1}}$, the unit's digit of $x\_{i\_j}$ is equal to the ten's digit of $x\_{i\_{j+1}}$.

For example, if $A=\left\\{ 24,87,48,12 \right \\}$ then $12-24-48-87$ is a valid permutation, whereas if $A=\left\\{ 46,83,58 \right \\}$, there is no valid permutation of $A$.

Now, given such a set $A$, I need to find an algorithm that prints a valid permutation if such exist, otherwise, it returns that there is no valid permutation of $A$.

I need to solve it using a graph, with a reasonable complexity, and I've been instructed to use some of the Eulerian path's properties, so it might play some role in getting the solution to that problem.

This is what I have in mind so far:

Setting a directed graph $G=(V,E)$ with: $V=\left\\{ x\_1, x\_2...x\_n\right \\}$, and $E$ will contain all the arcs $(x\_{i\_j}, x\_{i\_{j+1}})$ s.t. $x\_{i\_j} x\_{i\_{j+1}}$ is valid (i.e the unit's digit of $x\_{i\_j}$ is equal to the ten's digit of $x\_{i\_{j+1}}$).

Now, if a valid permutation of $A$ exist, there is a path in $G$ that travel through every vertex only once.

There are two things that troubles me with this thought. First of all, it has nothing to do with Eulerian path, or Eulerian graph, or Eulerian anything, which makes me believe I'm way off target here. Second, the complexity of such algorithm is a nightmare: creating $G$ alone is $O(|V|^2)$, but that's nothing compared to finding **some** path in $G$ that traverse through **all** vertices only once, considering that I can't determine at which vertex to start the search.

Does anyone have an idea on how to approach this problem? Are there any observations I fail to see? Maybe searching the graph differently, or maybe even setting the graph in some other configuration?

# Answer
Suppose $A$ is the input set.

Let $A=\left\\{d\_{11}d\_{21},d\_{12}d\_{22},...,d\_{1n}d\_{2n}\right\\}$ s.t. for every $d\_{1i}d\_{2i}\in A$: $d\_{1i}$ is the ten's digit, and $d\_{2i}$ is the unit's digit.

Construct a directed graph $G=(V,E)$ s.t: $$V=\left \\{1\leq x\leq 9 \mid \exists d\_{1i}d\_{2i}\in D,x=d\_{1i}\vee x=d\_{2i} \right\\}$$ $$E=\left \\{(u,v)\in V\times V \mid \exists d\_{1i}d\_{2i}\in D,u=d\_{1i}\wedge v=d\_{2i} \right\\}$$ Now, the constructed graph has an Eulerian path\circle in it iff $A$ has a valid permutation.

Moreover, I'll write some of the observations I made, that help finding the Eulerian path: if the given set $A$ has a "cyclic" valid permutation (a valid permutation $x\_1x\_2...x\_n$ where $x\_jx\_{j+1}...x\_nx\_1...x\_{j-1}$ is also valid, for every $1\leq j\leq n$), then for every $v\in V$: $\deg^+(v)=\deg^-(v)\neq 0$ (meaning in-degree equals out-degree), and finally the search for the Eulerian path can start at any arbitrary vertex in V.

On the other hand, if $A$ has a valid permutation that isn't cyclic, then there exist $v\in V$ s.t. $\deg^+(v)=deg^-(v)+1$, and there exist $u\in V$ s.t. $\deg^-(u)=\deg^+(u)+1$, and for every other $w\in V$: $\deg^+(w)=\deg^-(w)\neq 0$, **and** consequencly, the search for the Eulerian path **must** start at $v$ in this case (and should end at $u$).

In any other case (where neither of these two conditions are met), $G$ does not have an Eulerian path\circle in it, therefore there is no valid permutation of $A$.
> 2 votes

# Answer
Hint: Let the vertices be the digits $0,\ldots,9$, and let the given integers be the *edges*.
> 3 votes

---
Tags: graphs, eulerian-paths
---


# Question
Title: Decomposing an Algorithm into Local Transformations/Perturbations
Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/perturbation in a confined neighborhood of the data while fixing the rest?

One benefit of this "breakdown" is improved conceptual understanding, and it also facilitates induction proofs (possibly based on invariants that are preserved by each step). Does this "decomposition" have a name in algorithm design? The idea might be similar to Divide and Conquer.

One might say that every individual step in an algorithm, like deleting an edge or labeling a vertex of a graph, is small enough to be considered "local", but I'm talking more about the "decomposition" in a higher-level description, like how truncating a polyhedron is local but sorting a list is not (even though at the lowest level, comparisons, insertions and deletions are local).

**Examples of decomposing into local transformations**

* Augustin Cauchy's proof of his Rigidity Theorem relied on his "Arm Lemma" that opened up a convex planar chain by sequentially opening at each vertex. Although his proof was found to be wrong, he decomposed the opening algorithm into a series of "local opening moves", and he tried to prove that each local move preserved convexity of the chain. By induction, convexity would still hold after iterating over all vertices.
* The *pivot algorithm* for self-avoiding walks (SAW) transforms a SAW into another by rotating or reflecting part of the original SAW. Markov Chain Monte Carlo can employ this transformation as a transition between SAW states to sample the space of SAWs.
* As an application of the above, one technique of protein folding prediction is to force an amino acid chain into several known protein structures, choose the one with the lowest energy (due to intermolecular forces), then let the chosen structure "relax" into a configuation with lower energy. Relaxation involves the prescription of a few "local moves", where small parts of the chain can "wriggle around" (e.g. subchains pivoting around their ends), and random wriggles are allowed for a period of time to let the chain "stabilize". Modelling the chain as an SAW allows pivots to be used as a "wriggle".

# Answer
there are several ways to measure this "local vs global" decomposition dichotomy of problems which does show up in a wide variety of CS contexts.

* how many local minima there are versus a global minimum for optimization problems. if there are many local minima it is harder to find the global minimum. roughly this is also a measure of how effective greedy algorithms are on that problem.
* algorithmic speedup due to parallelism. this metric is sensitive to both the problem and the algorithm chosen. for example the problem may not be very "decomposable", or a problem may be decomposable but it is not solved with a most efficient algorithm. for more decomposable problems, algorithmic speedup is nearly linear in increasing processors. for less decomposable problems, it is more an asymptotic sub-linear relationship.
* communication overhead of parallel processing. the decomposability is known as "granularity". for problems that are not as granular, there is more communication required between separate parallel threads or processors. problems with very "fine" granularity ie not requiring much or any communication between processors are called embarrassingly parallel.
* NC is the class of efficiently parallelizable algorithms. NC=?P is an open question. ie in short are all P-time algorithm efficiently parallelizable, or not?

one paper that does attempt to study these concepts more formally/systematically within the context of parallel computing is Landscape of parallel computing, the view from Berkeley. see eg "7+ dwarves" for the basic algorithmic patterns that seem to appear in practice and commentary on their decomposability wrt parallelism.

another influential researcher recently looking into the inherent limits/ceilings/gains of parallelism in CPU design (ie multicore) which relates to the general decomposability of everyday running code is Esmaeilzadeh.
> -1 votes

# Answer
The transformation that you are talking about is the very definition of Algorithm.

> An algorithm is an effective method expressed as a finite list of well-defined instructions(Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987).) for calculating a function.

I don't think that there is a place for local or global definitions, but steps. Once you been able to create a well defined steps of your algorithm, not only that it will be easier to understand/implement it but also to improve it, by looking at each step individually.
> -2 votes

---
Tags: algorithms, terminology, reference-request, algorithm-design
---


# Question
Title: Decidability of Turing Machines with input of fixed length
I'm learning about undecidability, and found this question:

```
Is this language decidable, make a proof:
    L = { M : machine M halts for every input of length not exceeding 100 }

```

Update: This is translated from an exam paper some years ago, and I'm quite sure it means that machine M should halt for every input with length from 0 to 100, and that it is no constraints on the tape size.

Update2: The solution given below, and hence the origin of this post, is for an variant of this question with fixed number of steps and input. Sorry for the confusion.

I came to the conclusion that this is an undecidable language.

My logic is as follows: Lets say for the sake of contradiction that it is possible to construct a machine $M\_R$, that takes as input an arbitrary input $(M,x)$, and reduces this to $M'$. $M'$ has the property so that $(M,x) \in M\_{HALT}$ iff $M' \in L$, this means that $M$ halts on all $x$ of input with maximum length of 100.

Then run $M$ on $x$, if it halts then accept.

And shows that $M\_R$ decides the halting problem, and in hence a contradiction and proves that his is not decidable.

But in the solution it is written that this question is decidable:

> You can simulate $M$ on all inputs of length 100 or less (you can generate such input in a loop and use the universal Turing machine to simulate M on x), it is only $|\Sigma|^{100}$ possible inputs of length 100, that is finite.

# Answer
> 2 votes
@jmite correctly points out that the statement is written in such a way that the language is obviously undecidable. Even with 0 cells of input, as long as the machine is able to use an *unbounded* amount of work tape, the language will be undecidable. This is a completely basic fact about the Halting set.

@Michael should check to see whether the problem states that the machine only has 100 cells of *input*, or of total *tape* to work with. Did you transcribe the problem correctly?

Given the suggested official answer (which is not very good, may I know where this problem came from?), I think the problem *meant* to say that the *total* amount of tape available is 100 cells. In which case, the answer is as follows.

The language is decidable. Let us suppose the tape alphabet consists of three symbols, $0$, $1$ and blank.

Given a Turing machine $M$ with $n$ states, there are at most $$n \times 3^{100} \times 100$$ configurations of the machine, the head and the tape: the machine can be in any one of $n$ states, each of the 100 cell tapes may contain one of three symbols, and the head may be in 100 different positions. To determine whether $M$ halts, we simulate step by step for at most $n \times 3^{100} \times 100 + 1$ steps. If the simulation halts, then $M$ halts, otherwise $M$ will have repeated the same configuration twice and therefore loop forever. We may even detect the repeated configuration if we wish.

Let me address the other two answers:

1. @jmite: you missed the fact that we may halt the simulation after a finite number of steps because there are only finitely many possible configurations of the machine, the tape and the state.
2. @Patrick87: it is true that the number 100 can be replaced with any other number. So, for any machine $M$ and any number $n$ we can decided whether $M$ will halt on a tape of length $n$. This however does not allow us to deduce anything about $M$ halting on an infinite tape because $M$ could run forever by using up unbounded amounts of tape. There will be no $n$ such that $M$ uses only $n$ cells, so knowing what it does on $n$ cells won't be helpful.

# Answer
> 1 votes
I believe the given solution is wrong.

The problem is, for an arbitrary machine $M$, it is undecidable if any word $w\in L(M)$. This comes easily from Rice's theorem.

So their technique of "try all words of length less than 100" doesn't work, because there is no guarantee that you will halt when trying those words.

Perhaps they're confusing R and RE? The problem is, in fact, recursively enumerable: since you only need to try a finite number of inputs, you will always halt if the test machine halts for every input of length less than 100. But there is no guarantee that you will halt if it doesn't halt for some input of length less than 100.

# Answer
> 1 votes
Yeah, their answer is wrong. If it were right, you could solve the halting problem. You can tell this since (a) all strings have some finite length and (b) the number 100 was pulled out of thin air, and their argument works the same way for any finite number. If you could just simulate a TM on an input to tell if it halts on the input, the halting problem would be decidable, since all TMs can be simulated.

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


title: help regarding combinatorics

text:
# Question
Title: help regarding combinatorics
I want to know if there is any good book or material that fully explains and fully covers all combinatorics.I even did not find even Kenneth H.Rousan for this.So can anyone tell me any Discrete Mathematics book or any material to fully explain Combinatorics even to advance level.that provide classification to combinatorics problems(most important).

# Answer
> 2 votes
You say in a comment:

> I am interested in combination problems that contain-distribution of distinct/indistinct objects to distinct/indistinct people,also with type of partition not defined,unordered partition etc advanced level problems

It doesn't sound to me like you want a book that covers all of combinatorics. Combinatorics is a vast subject, which includes enumerative combinatorics, probabilistic combinatorics, extremal combinatorics, graph theory, and several other subdisciplines. It sounds to me like you are interested in a subarea of *enumerative combinatorics*.

Richard Stanley's two-volume series on enumerative combinatorics is quite good, and I suspect it contains the material you want.

# Answer
> 0 votes
The following book might be what you are looking for:

**Handbook of combinatorics**. Vol. 1 and 2. Edited by *R. L. Graham, M. Grötschel and L. Lovász*, Elsevier Science B.V., Amsterdam; MIT Press, Cambridge, MA, 1995. Vol. I: cii+1018 pp.; Vol. II: pp. i--cii and 1019--2198. ISBN: 0-444-88002-X

---
Tags: combinatorics, discrete-mathematics
---


# Question
Title: Doesn't post-order traversal require subtrees to be evaluated separately?
Consider this tree:

If I traverse it using post-order, I'd start at *B* (as it is the leftmost leaf) and that's where my misunderstanding begins. I know *B* is the first and *A* will be the last node in post order, as the rule is left-right-root. One of my university professors said the correct answer for the post-order traversal of a tree similar to the one above would be ***B*, *C*, *D*, *E*, *A***, but in my understanding, it should be ***B*, *D*, *E*, *C*, *A***.

Am I getting it wrong? Shouldn't I evaluate *(C,D),(C,E)* as a subtree and then go back to the parent tree?

# Answer
You are right. You finish each sub-tree before printing that sub-tree's root node. The correct order is B, D, E, C, A
> 0 votes

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


title: numerical integral vs counting roots

text:
# Question
Title: numerical integral vs counting roots
I have a problem that can be viewed in two different ways:

1. Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$.
2. Count (just count) the roots of an $n$-dimensional function (not a polynomial).

Solving just one of them is sufficient for solving the original problem. I know that simple algorithms for numerical integration would take $O(L^n)$, taking linear time per dimension. But I am not sure if there an asymptotically faster algorithms for (1).

For (2), I am aware of algorithms that can find roots (Newton and Bisection), but I am not sure about the best algorithms just for counting how many roots are in a non-polynomial $n$-dimensional function.

What are the best algorithms for (2)? Are they better than the fastest of (1)?

# Answer
Consider using Monte Carlo method for computing quadrature. It is good choice when you need not so precise approximation and dimension of the domain is large.

You definitely should provide more details.
> 1 votes

# Answer
If you view the evaluation of your function at tensor-product quadrature points in the cube, then the resulting box of numbers forms a tensor. If there is some low rank underlying structure to this tensor, you could use some of the new tensor-train approximation techniques to approximate the tensor while evaluating the tensor at many fewer quadrature points. See the work of Ivan Osledets on tensor trains, in particular TT-cross which is based off the skeleton matrix decomposition for the different matricizations of the tensor.

http://www.mat.uniroma2.it/~tvmsscho/papers/Tyrtyshnikov5.pdf
> 0 votes

---
Tags: algorithms, numerical-analysis, counting
---


# Question
Title: Is there always a Big Oh complexity strictly between any two others?
I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if one can always find complexities between any other two.

Specifically, for any functions f and g with O(f) ⊂ O(g) does there always exist an h such that O(f) ⊂ O(h) ⊂ O(g)?

This isn't homework or anything. I'm just curious if anyone knows.

# Answer
> 10 votes
Yes: take a function in the middle, for some suitable definition of middle. You have a wide choice.

If $O(f) \subset O(g)$ (where the inclusion is strict), then $g \in O(g) \setminus O(f)$ (because if $g \in O(f)$ and $f \in O(g)$ then $\Theta(f) = \Theta(g)$). Take the geometric mean: let $h = \sqrt{f \cdot g}$ (since we're talking about complexity here, I assume the functions are positive).

Then $f \in O(h)$ and $h \in O(g)$ (if this is not immediately obvious, prove it using the definition of $O$), i.e. $O(f) \subseteq O(h) \subseteq O(g)$. If $O(f) = O(h)$ then $g = f \in O(f)$, which is not the case since we assumed $g \notin O(f)$. It remains to prove that $O(h) \ne O(g)$, and we'll have $O(f) \subset O(h) \subset (g)$.

If $O(h) = O(g)$ then $g \in O(h)$, i.e. there exists $A$ and $C \gt 0$ such that $\forall x \ge A, g(x) \le C \\, h(x) = C \sqrt{f(x) g(x)}$. Then $g(x) \le C^2 f(x)$ (take the square and divide by $g(x)$; again, I assume positive functions), thus $g \in O(f)$, which goes against our initial assumption. The hypothesis $O(h) = O(g)$ leads to a contradiction, which concludes the proof.

# Answer
> -3 votes
this seems to be true for "well defined" functions or possible "space/time constructible" however there are known to be so-called (by some) "pathological functions" found by Blum in eg Blums Gap theorem for which it is not the case. so it seems similar to the concept of eg differentiation in calculus which works for "most well behaved functions" but which "pathological exceptions" have been found. there does not seem to be much systematic/further study so far of these "pathological exceptions" in complexity theory.

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


# Question
Title: Can I construct a Turing machine that accepts only its own encoding?
Is the set $S$ = $\lbrace M \mid M \text{ is a Turing machine and }L(M)=\lbrace \langle M\rangle\rbrace\rbrace$ empty?

In other words is there a Turing machine $M$ that only accepts its own encoding? What about a Turing machine that rejects only its own encoding?

# Answer
The answer is yes.

See Kleene's second recursion theorem: for any partial recursive function $Q(x,y)$ there is an index $p$ such that $\varphi\_p \simeq \lambda y.Q(p,y)$.

Suppose that $M$ is a Turing machine that on input $\langle x,y \rangle$ accepts if and only if $x=y$; then, by the above theorem, exists $M'$ such that $M'(\langle y \rangle) = M(\langle M' , y \rangle)$ and we have $L(M') = \\{ \langle M' \rangle \\}$.

P.S. you can find a very clear proof of the recursion theorem in Chapter 6 of the M. Sipser's book "Introduction to the theory of computation".
> 7 votes

# Answer
Yes. For the trivial reason that we can choose the coding to have the property we want. (Note that there is no unique way of coding.) For example, let $\langle - \rangle$ be any coding function for Turing machines and let $M\_0$ be some Turing machine with $L(M\_0) = \\{0\\}$. Now, let $$\langle M\rangle' = \begin{cases} 0 & \text{ if } M=M\_0 \\ \langle M \rangle+1 &\text{ if } \langle M\rangle \< \langle M\_0\rangle \\ \langle M \rangle &\text{ otherwise.} \end{cases} $$

We have $L(M\_0) = \\{\langle M\_0\rangle'\\}$, as required.
> 3 votes

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


# Question
Title: Reduce variant of Vertex Cover to original decision-version Vertex cover problem
Consider the following variation (let us call it Q) on the Vertex Cover problem: Given a Graph G and a number K, we are asked if there is a k-cover of G so that it is the minimum cover. My question is: How may one prove that Q can be reduced to the general Vertex Cover problem? And, more generally, what is the approach to solve such a reduction, from "is there a k..." to "is k the minimum/maximum?"? I have a hunch on the methodology but am not sure and would appreciate a wiser opinion than that of myself on the subject.

My hunch is the following: First of all, we take into consideration the following fact: if there is a k-1 cover of G, then we will surely have a k cover of G, just by adding a random node to the k-1 cover ( the cover property holds if we add nodes ). Thus, We can reformulate Q this way: Is there a k-cover of G, so that there is no (k-1)-cover of the graph? From this reformulation it is clear that an instance of Q reduces to 2 instances of the original decision version of the Vertex Cover.

# Answer
> 3 votes
Your reduction works. A more efficient version would be to use binary search to find the optimal value through a series of queries "Is there a vertex covers of size $k$?"

However, note that this is a polynomial-time Turing reduction (also known as a Cook reduction): you're solving the vertex cover optimization problem by making multiple queries to an oracle for the decision version. On the other hand, NP-completeness is defined in terms of polynomial-time many-one reductions (a.k.a. Karp reductions): here, you're only allowed to make one to the decision version. I'm not aware of a many-one reduction between these two problems.

Cook reductions have the advantage that they correspond more closely to the idea of "If I have an efficient algorithm for problem A and a reduction from B to A, I have an efficient algorithm for B, too. On the other hand, Karp reductions allow for finer-grained distinctions in complexity theory. For example, there are Cook reductions between NP-complete problems and coNP-complete problems but a Karp reduction between an NP-complete problem and a coNP-complete problem would prove that NP=coNP.

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


# Question
Title: Understanding Return Oriented Programming on Harvard Architecture
I'm currently reading this paper: *Code injection attacks on Harvard-architecture devices* (ACM) (pdf)

I understand the basics of what the attack is trying to do, but one thing really bothers me. If Harvard Architecture is supposed to have a strict separation of code and data, how is the initial buffer overflow allowing the attacker to rewrite return addresses on the stack? Since the architecture only allows data to be read into instruction memory via the SPM instruction--one that is specially reserved--I just don't get where the ability to rewrite the ret pointers is coming from. I feel like I'm missing something obvious.

# Answer
I believe the architecture you're interested in - the AVR - is actually a *modified* Harvard architecture, whereby instruction memory can be accessed by instructions as if it were data. (I haven't used the AVR in a while, so I don't recall if you can execute instructions out of RAM.)

The ARM Cortex M processors (perhaps others) are similar. There aren't too many pure Harvard architectures in new designs these days.

By the way (since you tagged your question with "atmega"), there is a **good paper by Francillon and Castelluccia (PDF from ACM Proceedings)** regarding code injection attacks on (modified) Harvard architecture devices, including the AVR.
> 3 votes

# Answer
Yes, the program can write to the return address on the stack. The CALL instruction has to be able to do it, and other instructions can too. The stack is just part of the data segment, so any instruction that operates on data potentially has the ability to overwrite the return address. There's nothing in the architecture that prevents it.
> 1 votes

---
Tags: security
---


# Question
Title: Detecting a subsequence that's an arithmetic progression, in a sorted sequence
I have following problem: I have a sorted sequence of $N$ integers (assume they are monotonically increasing). I want to check whether there is any subsequence of length $\ge N/4$, such that consecutive elements of the subsequence all differ by the same value.

For example, in the sequence \[3,4,5,8,12\] there are two such subsequences: \[3,4,5\] (the difference is 1) and \[4,8,12\] (the difference is 4). Thus, the length of longest such subsequence is 3 for this example. Since $3 \ge 5/4$, the answer is yes, there is a subsequence of length $\ge N/4$ with the desired property.

In my real-life situation, the sequence is of length $N\approx 10^6$, and the elements are all 9-digit numbers. Is there an efficient algorithm to solve this problem?

---

My naive approach was to create Cartesian product with absolute differences between numbers:

$$ \left( \begin{array}{ccccc} 0 & 1 & 2 & 5 & 9 \\ 1 & 0 & 1 & 4 & 8 \\ 2 & 1 & 0 & 3 & 7 \\ 5 & 4 & 3 & 0 & 4 \\ 9 & 8 & 7 & 4 & 0 \end{array} \right) $$

And then focus on top-right part and compute number of occurrences of each difference, so:

$$ ||\text{diff-by-1}|| = 2 =\> \text{3 numbers diff by 1}\\ ||\text{diff-by-4}|| = 2 =\> \text{3 numbers diff by 4} $$

This is very simple and very ineffective. It requires lot of comparisons and does not scale (at all): its running time is $\Theta(N^2)$. In my real life scenario my sequence is ~10^6 long, so this is too slow.

To give you wider picture as maybe there is much better (probabilistic) approach to this problem: after largest sub-sequence is found I want to compute simple ratio:

$$ r:=\frac{\text{largest sub-sequence length}}{\text{sequence length}} $$

and if $r$ is greater then some fixed value I want to raise alarm (or do whatever I have to do ;-)).

Thanks for any help, references, pointers, etc.

BTW: here are things that I was/am looking at:

**Update**: was thinking a little bit more about it and started from the end, so instead of computing all differences between numbers (top-right corner of the matrix) I can derive small $k$ value from "fixed value" I mentioned at the end of original question. For instance if I am going to raise the alarm when 25% of all numbers are in some sequence I need to focus on small "triangles" in matrix and number of computations required is smaller (much smaller). When I add some sampling then it should be simple enough to implement at scale.

**Update 2** \- Implemented @D.W. algorithm, sample run below:

```
    11:51:06 ~$ time nodejs progression.js
    L: 694000000,694000002,694000006,694000007,694000009,694000010,
        694000013,694000015,694000018,694000019,694000021,694000022,694000023,
    694000026,694000028,694000030,694000034,694000036,694000038,694000040,
    694000043,694000045,694000046,694000048,694000051,694000053,694000055,
    694000057,694000060,694000061,694000063,694000067,694000069,694000072,
    694000074,694000076,694000077,694000079,694000080,694000082,694000083,
    694000084,694000086,694000090,694000091,694000093,694000095,694000099,
    694000102,694000103,694000105,694000108,694000109,694000113,694000116,
    694000118,694000122,694000125,694000128,694000131,694000134,694000137,
    694000141,694000143,694000145,694000148,694000152,694000153,694000154,
    694000157,694000160,694000162,694000163,694000166,694000170,694000173,
    694000174,694000177,694000179,694000180,694000181,694000184,694000185,
    694000187,694000189,694000193,694000194,694000198,694000200,694000203,
    694000207,694000211,694000215,694000219,694000222,694000226,694000228,
    694000232,694000235,694000236
    N: 100
    P: 0.1
    L: 10 (min)
    D: 26 (max)
    [ 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 ]
    Found progression of 10 elements, difference: 16 starts: 694000045, ends: 694000189.

    real    0m0.065s
    user    0m0.052s
    sys 0m0.004s

```

# Answer
> 4 votes
You recently clarified that you want to solve the following problem:

> Given an input sequence $L\[0..N-1\]$, check whether an arithmetic progression of length $\ge N/4$ appears as a subsequence of $L$.

This is a significantly easier problem, and I can suggest a very efficient algorithm for you. Let me build up to it by first explaining a few key ideas underlying the algorithm.

---

**Idea 1.** Given any two elements of $L$, it is easy to extend them to the maximum-length arithmetic progression containing those two elements. In particular, suppose we have $x,y \in L$ with $x\<y$. Set $d=y-x$. Then we can extend this sequence on the right as the longest prefix of $y+d,y+2d,y+3d,\dots$ that is wholly contained in $L$, and we can extend it on the left with the longest prefix of $x-d,x-2d,x-3d,\dots$ that is wholly contained in $L$.

**Idea 2.** Say that an arithmetic progression has gap $d$ if the difference between consequence elements of the arithmetic progression is $d$. If $L$ contains an arithmetic progression of length $\ge N/4$, then its gap $d$ must satisfy $d \le 4(L\[N-1\]-L\[0\])/N$.

**Idea 3.** Suppose there is an arithmetic progression of length $\ge N/4$, and let $\alpha,\beta$ denote the start and end index (in $L$) of the subsequence. Since the subsequence has to be of length $\ge N/4$, the interval $\[\alpha,\beta\]$ must contain one or more of the following numbers: $0.2N$, $0.4N$, $0.6N$, $0.8N$ (rounding all of them to an integer).

To give you some intuition for this: Imagine you're playing Battleship on a $N \times 1$ board, and your opponent has a single ship: a super-long battleship, that is $N/4$ cells long. Could you find his battleship? You sure could. It's only gonna take you 4 shots to find his battleship. You can shoot at cells $0.2N$, $0.4N$, $0.6N$, $0.8N$, and it's guaranteed that at least one of them will be a hit (that's Idea 3). Moreover, once you get a single hit, it's not going to be hard to sink the rest of his battleship (that's basically Ideas 1 and 2).

---

With these ideas, I'm ready to propose an algorithm:

* Set $d\_\max \gets 4(L\[N-1\]-L\[0\])/N$.
* For each $i\_0 \in \\{0.2N, 0.4N, 0.6N, 0.8N\\}$, do:

+ For each $i$ such that $i\ge i\_0$ and $L\[i\] \le L\[i\_0\]+d\_\max$, do:

    - For each $j$ such that $j\>i$ and $L\[j\] \le L\[i\]+d\_\max$, do:

        * Extend the arithmetic progression $L\[i\],L\[j\]$ on the left and right as far as possible (using Idea 1).
* Look at the longest arithmetic progression found at any point above. If it has length $\ge N/4$, then yes, there exists an arithmetic progression of length $\ge N/4$. If its length is $\< N/4$, then no, there is no arithmetic progression of length $\ge N/4$.

Hopefully you can see why this works. Idea 3 means that, if there is an arithmetic progression of length $\ge N/4$, then at least one of the indices $i$ that are visited in the above algorithm must be the index of one element of that progression. Moreover, the index of the next element of that progression must be one of the values taken on by $j$ in the innermost loop. Therefore, at some point the pair $L\[i\],L\[j\]$ will be a pair of consecutive elements of the arithmetic progression -- which is enough to discover that long arithmetic progression.

---

I would expect that this algorithm will typically be very efficient, on real-world data. If all of the integers in $L$ are in the range $\[1,M\]$, then we know $d\_\max \le 4M/N$. Moreover, the loop over $i$ typically involves about $d\_\max N/M \le 4$ iterations (on average), and similarly for the loop over $j$. So, we expect to perform maybe $5 \times 4 \times 4 = 80$ iterations of the innermost statement, regardless of $N$, if the data is randomly chosen (and in particular, not adversarily chosen). Consequently, this should be extremely efficient if the data doesn't conspire against you.

It is possible to further improve this algorithm, for instance, to improve its worst-case running time and reduce the opportunity for worst-case data to cause the running time to blow up, at the cost of making the code more complicated. However, I suspect that this simple algorithm might be sufficient for your needs.

# Answer
> 0 votes
Subsequences of the form $a,a+d,a+2d,a+3d,\dots$ are called arithmetic progressions. Your problem is to find the longest arithmetic progression that appears as a subsequence of your input (a sorted sequence).

Unfortunately, the method you describe in your question doesn't quite work to find the longest arithmetic progression, but I'll describe one way to fix it up in this answer.

---

You suggested enumerating all pairwise differences and counting how many times each difference occurs. However, that isn't enough to find the longest subsequence, in general. There might be 3 pairs of numbers that differ by 4, but that doesn't necessarily mean that there exists an arithmetic progression of length 3. Consider, e.g., $\[1,2,5,6,20,24\]$, or $\[10,14,100,104,1000,1004\]$.

The following algorithm is slightly better (i.e., it is correct, and often not too much slower):

* For each $i,j$ with $i\<j$:

+ Consider the arithmetic progression $L\[i\],L\[j\]$. It has length 2, and its difference is $d \gets L\[j\]-L\[i\]$.
    + Extend this arithmetic progression rightward as far as possible. In other words, set $z \gets L\[j\]+d$; while $z \in L$, append $z$ to the arithmetic progression and set $z \gets z+d$.

If the input is randomly distributed, each iteration of the loop takes $O(1)$ expected time, so the expected running time is $O(N^2)$. (You can ensure that the test $z \in L$ can be done in $O(1)$ time by precomputing an appropriate data structure, e.g., a hash table.)

Warning: If the input is not randomly distributed, this approach could take be much slower in the worst case. However, this approach might be a pragmatic method, as it's plausible that you might not run into those anomalies in practice if the inputs don't have any structure or nasty patterns.

---

Incidentally, for your parameters, if the numbers are all random, it's very likely that the longest arithmetic progression that appears as a subsequence has length 5 or 6. (There's maybe a $1/1000$ chance that there will be an arithmetic progression of length 7 contained in your list.) I don't know how to find the length-5 or -6 progression efficiently, though, if efficiently means "much faster than $\Theta(N^2)$ time".

---
Tags: algorithms, decision-problem, subsequences
---


# Question
Title: What were the research outcomes of the Univalent Foundations Program year (Homotopy Type Theory)
The Institute for Advanced Study has had a year-long special program devoted to the Univalent Foundations Program.

At the end of this they have produced a book and a code repository.

At the end of this we see a blog entry in Scientific American claiming:

*...it could provide a new, self-contained foundation for all of mathematics.*

Now this is a bold claim. By contrast I can see humbler claims such as a simple proof in Agda that the sum of two odds is always an even.

My question is: **What novel research did these guys actually produce at the end of the year?** All the article indicates is that they wrote some code in Agda. Is it just that we have a new view of Martin-Löf type theory with some applications?

**Assumptions**

* I understand the broader ideas of Martin-Löf type theory as it relates to the isomorphism between Types and Proofs.

# Answer
The book is itself representative of the research product of the program. The code that they wrote actually is mostly in Coq, to my knowledge, and certainly the development that accompanies the book was written in Coq.

Homotopy Type Theory itself essentially constitutes Martin-Löf, together with the *univalence axiom*, which essentially states that equivalent types are equal. The notion of equivalence comes from a view that establishes a connection between a synthetic homotopy theory and Martin-Löf type theory, hence the name. This axiom gives way to a powerful type theory that the book shows is capable of reasoning about a lot of important existing foundational mathematics.

In fact, part 2 of the book comprises developments of a more traditional, topologically-motivated version of homotopy theory, set theory, category theory, and a nice constructive presentation of the real numbers. I have not explored the Coq code that much yet, but my understanding is that all of these presentations are accompanied by corresponding Coq source. Since we can formulate all of these important foundations entirely within homotopy type theory, the hypothesis that it might be an important foundation for mathematics going forward makes sense. The idea is that mathematicians will be able to extend these seminal developments towards more results in fields like algebra, topology, and analysis.

Inasmuch as homotopy type theory pertains to being able to do mathematics in Coq via the Curry-Howard correspondence, you can think of homotopy type theory as corresponding to a more powerful instance of Curry-Howard. The most exciting contribution of this work is really that it gives mathematicians language for speaking about mathematics in terms of type theory, and the idea is that this should enable on the one hand, more mathematics being accompanied by mechanized proofs in provers like Coq, as well as computer proofs that correspond more closely to their plain English equivalents. Anyone who has used Coq will tell you that the proofs that you produce often don't end up looking much like equivalent plain-English proofs at all.
> 7 votes

---
Tags: homotopy-type-theory
---


# Question
Title: Cryptography substitution frequency analysis
I am trying to find the plain text for the following cipher text using a frequency analysis

```
vr pvst yqlp mq nvf

```

But for the letters above this is really difficult, as if I use the alphabetic substitution technique, where I assume that v corresponds to e as this occurs most in the english alphabet. What about p, this also occurs three times, does this mean it corresponds to e. Same for `r,s,t,y,l,m,n,j,f` which occur only once. Is there an algorithm which looks at such duplicated frequencies, or do I guess:

v and p corresponds to e q corresponds to t r to f correspond to a

?

even using the bigram method for something like this is difficult as a bigram of pv is found, if p = t and v = h that means p doesn't correspond to t anymore?

Thanks in advance!

# Answer
I'm by no means an expert but it seems to me that your sample is far too short to be amenable to frequency analysis or, indeed, to cryptanalysis of any kind. Assuming a substitution cypher, you have only the information that eleven letters are used, and characters 1, 4 and 14; 3 and 10; and 8 and 11 are the same. There are fifteen unused characters so there's a huge amount of freedom. You only have a little more information than a one-time pad would give you.

In a long sample of text, it is likely *but is not guaranteed* that the most frequent character is 'e'; in a fifteen character sample, it's perfectly possible that there are no e's at all. ("Look at my odd words" is a sixteen-letter example.) Frequency analysis helps you figure out the substitutions but it doesn't guarantee to give you the answer with no more work.

Assuming the spaces are significant, your message could be "My emus love no imp". Or it could be something completely different.
> 4 votes

---
Tags: cryptography
---


# Question
Title: Minimum number of exchanges needed to get all negative values left of all positive ones
Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ?

# Answer
> 4 votes
You can keep a pointer to the currently first positive value in the list, which initializes to 0. Then scan through the list, when you see a negative value swap it with the positive value, and increment your pointer.

You get O(n) swaps in the worst case.

If the first half is positive and second half is negative, you have to have at least n/2 swaps, as the second half needs to swap places with the first half.

To actually get n/2 swaps, you can first count the # of positive values, and if the positive values are greater, iterate the list in reverse order, and keep a pointer first negative value in the list. You can then stop if you have swapped all the positive or negative values.

# Answer
> -3 votes
For your point we will use Quick sort algorithm but only for one time (one pivot) and for the worst case it will take O(nlogn) as we find solution in the first step.

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


# Question
Title: Prove that <Z> is not a element of NOT-SELF
I know this has been a question but based on a past experience, i thought i would rewrite it so i can get input and ask questions faster.

Suppose we have $$\text{NOT-SELF}=\\{\langle M\rangle \mid M \text{ is a Turing machine that does not accept }\langle M\rangle\\}$$ the set of all machines that don't accept their own coding.

Let $Z$ be a TM such that $L(Z)$ is a subset of $\text{NOT-SELF}$. Prove that $\langle Z\rangle$ is an element of $\text{NOT-SELF}$.

My answer so far is very broad and I'm trying to improve it.

If $\langle Z\rangle$ is not an element of $\text{NOT-SELF}$, than $\langle Z\rangle$ can’t be an element in $L(Z)$. Since there’s a condition that $L(Z)$ is a subset of $\text{NOT-SELF}$, this contradicts so $\langle Z\rangle$ must be an element of $\text{NOT-SELF}$.

# Answer
> 1 votes
Assume (i) $L(Z) \subseteq \text{NOT-SELF}$ and assume towards contradiction that (ii) $\langle Z \rangle \notin \text{NOT-SELF}$.

Because of (ii) and (i) we get that $\langle Z \rangle \notin L(Z)$.

(if it was in $L(Z)$ and $L(Z)$ is a subset of $ \text{NOT-SELF}$, it must also be in $\text{NOT-SELF})$.

Thus, $Z$ does not accepts its own encoding. Thus, by the definition of $ \text{NOT-SELF}$ it should be that $\langle Z \rangle \in \text{NOT-SELF}$, which is a contradiction.

Also see the related question: Can I construct a Turing machine that accepts only its own encoding?

---
Tags: computability, turing-machines, decision-problem
---