# Question
Title: Why isn't this undecidable problem in NP?
Clearly there aren't any undecidable problems in NP. However, according to Wikipedia:

> NP is the set of all decision problems for which the instances where the answer is "yes" have \[.. proofs that are\] verifiable in polynomial time by a deterministic Turing machine.
>
> \[...\]
>
> A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Now consider the following problem:

> Given a Diophantine equation, does it have any integer solutions?

Given a solution, it's easy to verify in polynomial time that it really *is* a solution: just plug the numbers into the equation. Thus, the problem is in NP. However, *solving* this problem is famously known to be undecidable!

*(Similarly, it seems the halting problem should be in NP, since the "yes"-solution of "this program halts at the N-th step" can be verified in N steps.)*

Obviously there's something wrong with my understanding, but what is it?

# Answer
> 12 votes
An equivalent definition of NP is that it consists of all problems that are *decidable* (not just verifiable) in polynomial time by a non-deterministic Turing machine. NTMs are known to be no more powerful than TMs in the sense that the set of problems decidable by NTMs is identical to the set of problems decidable by TMs, so clearly by this definition there can be no undecidable problems in NP.

To demonstrate that the two definitions of NP are equivalent, given the existence of a deterministic verifier you can demonstrate that a non-deterministic decider exists, and vice versa.

Say you have a deterministic polynomial verifier. Then there is also a machine that non-deterministically guesses a certificate of a length bounded by the polynomial corresponding to the certificate size bound of this problem/verifier and then runs the verifier. Since the alphabet is finite, the certificate for any given input is finite (and at most polynomial in the size of the input), and the verifier runs in polynomial time, the machine halts on all branches for all input and runs in (non-deterministic) polynomial time. Thus there is a non-deterministic decider for every deterministic verifier.

If you have a non-deterministic decider, then for every accepting computation you can write down the path of choices taken by the decider to reach the accept state. Since the decider runs in polynomial time, this path will be of at most polynomial length. And it's easy for a deterministic TM to validate that such a path *is* a valid path through an NTM to an accept state, so such paths form certificates for a polynomial time verifier for the problem. Thus there is a deterministic verifier for every non-deterministic decider.

Thus any undecidable problem *cannot* have a verifier that works on certificates of polynomial size (otherwise the existence of the verifier would imply the existence of a decider).

---

When you claim that a verifier exists for the halting problem, the certificate you're talking about is some encoding of (TM, I, N), where the TM halts on input I in N steps. This can indeed be verified in N steps, but the size of the certificate is not polynomial in the size of the (TM, I) input to the original problem (the halting problem); N can be arbitrarily large (regardless of encoding). If you try to convert such a verifier to a non-deterministic decider, you end up with a somewhat interesting machine. You should be able to prove that when run on (TM, I) for a TM that *doesn't* halt on input I no non-halting paths through the machine exist, but also that for any path leading to a halting state there is always another longer path (corresponding to a guess of a larger N), and thus there is no finite bound on its execution time. Essentially this is because there is an infinite space that needs to be explored by the initial non-deterministic guess. Converting such an NTM to a *deterministic* TM leads to one of those machines that neither loops nor halts on some input. In fact no NTM exists that can decide the halting problem, and so there is no verifier that works on certificates with a bounded size.

I'm not so familiar with Diophantine equations, but it looks like essentially the same problem applies to your argument there.

For this reason I find it easier to reason about the NTM definition of NP. There are verifiers for problems that are undecidable (just not ones that work on certificates that have a polynomial size bound in the size of the input to the original problem). In fact any TM that *recognises* but does not *decide* some language can be easily converted into a verifier for the same language.

If you do think about verifiers, I suppose you have to give their time bounds in terms of the size of the *original problem* input, not in terms of the certificate size; you can arbitrarily inflate the size of certificates so that the verifier runs in a lower time bound in terms of the size of the certificate.

# Answer
> 29 votes
I think you misunderstood what it means to solve a diophantine equation, and Matiyasevich's indecidability theorem.

Matiyasevich proved that for every RE set $S$ there is a diophentine equation $f(n;x\_1,...,x\_k)$ such that $n \in S$ only if there exists integer coefficients $x\_1$,..,$x\_k$ such that $f(n;x\_1,...,x\_k) = 0$. In particular, the halting problem is a typical RE set, and so solving the above problem is undecidable.

Note that $x\_1, ... x\_k$ are not bounded in size, and in general can be arbitrarily large, so there is no "polynomial sized certificate" evident in this problem.

To expand: the integers $x\_1, ... , x\_k$ need to be written in binary to be a certificate. Since these integers can be arbitrarily large (regardless of $n$), we have that the certificate is not polynomial in $\log n$ or more importantly, not bounded by and computable function.

Every problem in $\mathsf{NP}$ however, has a certificate that is bounded by some polynomial $p(N)$ (where $N$ is size of input). So $\mathsf{NP}$ questions are trivially decidable, since you can enumerate every possible bit string upto length $p(N)$ and if none of them certify the input, return false. If some does then return true.

# Answer
> 9 votes
You should have scrolled down to the formal definition:

> A language $L$ is in NP if and only if there exist polynomials $p$ and $q$, and a deterministic Turing machine $M$, such that
>
> * For all $x$ and y, the machine $M$ runs in time $p(|x|)$ on input $(x,y)$.
> * For all $x \in L$, there exists a string $y$ of length $q(|x|)$ such that $M(x,y) = 1$.
> * For all $x \not\in L$ and all strings $y$ of length $q(|x|)$, $M(x,y) = 0$.

That is, a verifier has to work also on non-solutions. Somewhere in there , undecidable problems fail (in your case, the length restriction of solution candidates is probably not fulfilled), as is obvious by the (in the computability sense) more clearer definition:

> NP is the set of decision problems decidable by a non-deterministic Turing machine that runs in polynomial time.

# Answer
> -1 votes
I try to provide more details for my above answer.

In fact, this question is a dilemma problem.

On one hand, the Diophantine Equation Problem (DEP) is undecidable according to Matiyesevich’s theorem (Matiyesevich’s theorem answers Hilbert's tenth problem, and Turing’s Halting problem answers the generalization of Hilbert's tenth problem, that is, the Entscheidungsproblem); but on the other hand, there isn't any undecidable problem in NP according to the definition of NP (decidable and verifiable).

That is to say, either DEP is not in NP, or DEP is in NP. Both of them concern the definition of NP.

If DEP is not in NP, that means problems in NP (NDTM＝NonDeterminstic Turing Machine) are decidable and verifiable, that is to say we accept P=NP (NDTM).

If DEP is in NP, then NP (NTM＝Non Turing Machine) contains decidable and undecidable, obviously decidable is verifiable, therefore the problem is whether undecidable is verifiable? In fact, that is the famous problem of P vs. NP. Certainly, undecidable is unverifiable, so NP corresponds to NTM (Non Turing Machine) instead of NDTM (NonDeterminstic Turing Machine).

Going on the premise of DEP is in NP (NTM), we think that the NP (NTM) is Nondeterministic Problem (undecidable), and the current definition of NP (NDTM, decidable and verifiable) has lost this nondeterminism (undecidable), so we think that it needs to be questioned.

# Answer
> -2 votes
We think that the dilemma you raised about Diophantine equation is very significant, because it reveals something abnormal in the current definition of NP : \- A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Concerning the definition of NP, it can be traced to the 60’s, where a great number of applicable and significant problems were discovered for which no polynomial algorithms could be found to solve them, in order to recognize these problems from those problems solvable in Polynomial time (P), the concept of NP was put out.

However, the current definition of NP defined as verifiable in polynomial time confuses NP with P, because a problem in P is also verifiable in polynomial time. In another word, such definition leads to the loss of the essence of NP, « nondeterminisme ». Consequently, it causes serious ambiguities in understanding NP, for example, your dilemma : by nature the problem of Diophantine equation is undecidable; but by the definition of NP, it is decidable, …

In our opinion, the difficulty in solving « P versus NP » lies firstly at cognition level, so if we hope to get an insight into « P versus NP », we need at first to question : What is NP?

---
Tags: complexity-theory, computability, undecidability, decision-problem
---


# Question
Title: Is it possible to compute -12 (decimal) in 4 bits binary
This is what I have so far

1 1 0 0

Switch values by 2s Complement

0 0 1 1 \+ 1

---

0 1 0 0

# Answer
> 7 votes
No, it's not possible, at least using the standard representations. An unsigned $n$-bit number can represent any integer in the interval $\[0, 2^{n} - 1\]$. A signed $n$-bit number using two's complement can represent integers in the interval $\[-2^{n - 1}, 2^{n - 1} - 1\]$. With $n = 4$, that gives an interval of $\[-8, 7\]$, which obviously doesn't include $12$. One's complement can use $n$ bits to represent the interval $\[-(2^{n - 1} - 1), 2^{n - 1} - 1\]$, giving the interval $\[-7, 7\]$ for four bits, which also doesn't work. You'd have to contrive a nonstandard representation to represent $-12$ in four bits.

---
Tags: computer-architecture, arithmetic
---


# Question
Title: How to write an EBNF grammar for Java float literals?
I've got this question on my study guide: "Write an EBNF grammar description for Java float literals and one for Java double literals."

I've browsed the Oracle site and found the grammar for java float literals, but I'm not entirely sure how to convert that to EBNF grammar. I understand EBNF notation but for some reason I'm stuck on this.

I was hoping/wondering someone would be able to get me started? It would be highly appreciated.

# Answer
> -1 votes
You could try answer the question *"How do I define `double` and `float` literals?"*

`double`s are usually defined as:

```
double a = 12d;
//or
double b = 12.1;
//or
double c = 12.1d;
//or
double d = 12;

```

while `float`s could be defined as:

```
float m = 10;
//or
float n = 10.4f;
//but this is invalid:
float p = 10.4;

```

Note that by default a literal like `10.123` is considered to be `double`, so if you really want to assign it to a `float` variable, you need to append a `f` character in the end. However, `f` is optional when the literal is `10`.

Let's also list the properties of both types:

`float`: 32 bits (4 bytes) where 23 bits are used for the mantissa (up to 9 decimal digits). 8 bits are used for the exponent, so a float can *move* the decimal point to the right or to the left using those 8 bits. There is 1 bit used as the sign bit. The max `long` value that double can hold is $10\_18$

`double`: 64 bits (8 bytes) where 52 bits are used for the mantissa (up to 19 decimal digits). 11 bits are used for the exponent and 1 bit is the sign bit.

So, `double` and `float` could be defined like:

```
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

double = 19 * digit, [ [, | .]  18 * digit]["d" | "D"];
float = 19 * digit, [ [, | .]  18 * digit, "f" | "F"];

```

---
Tags: formal-grammars, java
---


# Question
Title: Constrain certain variables in CNF to unique satisfying assignments
\[Reposted because the original question was deleted by the poster.\]

I'm looking for a way to add additional clauses (and maybe additional variables) to an already existing SAT instance so that solutions with non-unique assignments for certain variables are invalidated.

Currently I enumerate all the original solutions, and filter out the bad solutions having duplicate partial assignments on specific variables. But this becomes impractical when there are many solutions to the original instance, compared to a very small number of good solutions.

*If the SAT solver had information within the CNF that duplicate partial assignments on certain variables invalidate any solution that contains those partial assignments, it would speed up the search significantly.*

Here's an example with 16 variables: 90 original solutions, 42 filtered solutions. https://gist.github.com/re-curse/7b1c970768400ef5d0fe

This example instance generates 90 solutions, but 48 solutions are bad because they duplicate assignments for variables 1-8 or variables 8-16. I need to add clauses to the CNF to filter out those bad 48 solutions **while the solver searches** instead of retroactively filtering after enumerating all original solutions.

An example of two bad solutions for this instance are (00110110 00110110) and (00110110 00111001) because variables 1-8 have an assignment \[ie. 00110110\] that shows up more than once in the 90 original solutions.

# Answer
If you could add clauses to a CNF formula to cause it to be unsatisfiable iff certain sets of variables don't have non-unique assignments among the formula's satisfying assignments, you could use this same method to solve UNIQUE-SAT for any CNF formula. Since UNIQUE-SAT is co-NP-complete, you'll have proven NP = co-NP. So it is unlikely there is a solution to the problem that involves simply adding clauses.
> 1 votes

# Answer
Below are links to a SAT-2015 paper titled "#∃SAT: Projected Model Counting" by Rehan Abdul Aziz, Geoffrey Chu, Christian Muise, and Peter Stuckey. The paper includes descriptions of the problem in general as well as algorithms for solving such problems expressed in CNF.

Full paper: http://link.springer.com/chapter/10.1007/978-3-319-24318-4\_10

Preprint: http://arxiv.org/pdf/1507.07648v1.pdf
> 1 votes

---
Tags: satisfiability, sat-solvers
---


# Question
Title: Can I change the input of my reductionduring the proof?
To prove that a problem $\Pi\_2$ is NP-hard one has to:

1. select a known NP-hard problem $\Pi\_1$;
2. from an arbitrary instance of $\Pi\_1$, create an instance of $\Pi\_2$ in polynomial-time; and
3. show that solve $\Pi\_1$ with the given instance $\iff$ solve $\Pi\_2$ with the created instance.

Now, my question is the following.

Suppose now I did 1., 2. and only solve $\Pi\_1\Rightarrow$ solve $\Pi\_2$ but when I am trying to show the inverse, i.e., solve $\Pi\_2\Rightarrow$ solve $\Pi\_1$, the instance of $\Pi\_1$ is changed a little. Is this proof correct?

More precisely, let $I\_1=(n, a\_1,\ldots,a\_n,b\_1,\ldots,b\_n,\alpha,\beta,k)$ be an arbitrary instance of $\Pi\_1$. The created instance (in polynomial-time) of $\Pi\_2$ is $I\_2=(n, a\_1,\ldots,a\_n,b\_1,\ldots,b\_n,\Delta,k)$. Now when I tried to show solve $\Pi\_2$ with $I\_2\Rightarrow$ solve $\Pi\_1$ with $I\_1$, I found another instance of $\Pi\_1$, $I\_1'=(n, a\_1,\ldots,a\_n,b\_1,\ldots,b\_n,a,b,k)$ where $a\neq \alpha$ and $b\neq\beta$. Hence I did not solve $\Pi\_1$ with $I\_1$ but with $I\_1'$.

My guess is that the proof still correct, right?

# Answer
> 3 votes
No, you may not modify $I\_1$. By the time you get to Step 3, everything is determined and you might not change your instances. Say $f$ is the polytime transformation from Step 2. Then you need to show

$I\_1$ is a yes-instance of $\Pi\_1$ if and only if $f(I\_1) = I\_2$ is a yes-instance of $\Pi\_2$.

If after arriving at Step 3 you notice that your $I\_2$ instance does not allow you to prove the statement, then you might want to change $f$ in your Step 2, and redo Step 3.

---
Tags: complexity-theory, reductions, proof-techniques, np-hard
---


# Question
Title: What are witnesses C and k for an O-bound?
Can someone explain the following about big-O from the textbook to me? (I'm trying to catch up after missing classes due to illness.)

> Show that $f(x) \in O(x^2)$ where $f(x) = 8x+9$. List the witnesses $C$ and $k$.

From what I have gathered I am looking at/for a distinct point witnessed by $C$/$k$ wherein there is a (lower bound?) point to where one of the functions ($f(x)$ or $g(x)$) is increasing at a faster rate for any given point $\geq C$?

The textbook talks testing/trying out different $C$ witnesses (ex. 1) to where I then solve for $8x+9\leq(1)x^2$ or (ex. 2) and solve for $8x+9\leq(2)x^2$, but I'm not sure where I go from there. If I'm letting $C=1$ then I get:

\begin{gather\*} 8x+9\leq(1)x^2\\ 0\leq x^2-8x-9\\,. \end{gather\*}

Then from here I have tried the quadratic equation resulting in $(8 \pm \sqrt{100})/(2)$ or I saw where $0\leq x^2-8x-9$ could be factored to $(x+1)(x-9)$ so I know $-1$ and $9$ make zeroes on my number line, and I tried plugging in test points where I found everything less than $-1$ or greater than $9$ yields a positive, and everything between $-1$ and $9$ yields a negative, but from this point I am lost.

Can someone explain what I'm supposed to be doing and how to go about it?

# Answer
I am going to guess what $C$ and $k$ mean in your context:

$f(x) = O(g(x))$ if and only if $\exists C, k \\;\\; \forall x \ge k \\;\\; (f(x) \le C|g(x)|)$.

You are asked to find constants $C$ and $k$ and prove that for all $x \ge k$ you have $8x+9 \le C x^2$.

I am going to take $C = 1$ and $k = 9$. We have $x \ge 9$ so $C g(x) = C x^2 = x^2 \ge 9 x = 8x + x \ge 8x + 9 = f(x)$.
> 2 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Why is the processes address space a continuous block in RAM?
I need some clarification regarding how the process address space is organized in memory. I went through basic concepts of virtual memory and adress translation and according to the size of the page, it seems that a virtual adress can have its equivalent physical address located anywhere in RAM, it that right ?

I saw the following representation of RAM :

It seems that processes address space is continuous in RAM, how come ? I though that we could have, for example, the stack of a process(or some part of it) located at a totally different region of RAM than, for example, the heap.

# Answer
The term *virtual memory* applies as soon as there is a mapping from logical (process specific) addresses to physical one. The mapping may be as simple as adding a base to the logical address to get the physical one or as complex as the segmentation followed by paging of x86. The representation you show seems to assume the first.
> 3 votes

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


# Question
Title: Are accepting states and unaccepting states distinguishable?
Is it true that for all DFA that if $A$ is an accepting state and $B$ is not, that $B$ is always distinguishable from $A$.

I don't think it's true, just because I think I can create a DFA.

$B$ reads b -\> $A$

$A$ reads b -\> $A$

If you start at $B$ while reading a b and at $A$ you read a b you end up in the accepting state $A$. Now is there an algorithm to see if my construction is valid?

# Answer
This depends on your definition on distinguishable. Let's assume the following definition: $A,B$ are distinguishable if for some word $x$, if the automaton starts at $A$ and reads $x$ then it accepts, while if it starts at $B$ and reads $x$ then it rejects; or vice versa.

Under than definition, any accepting state is distinguishable from any non-accepting state: just take $x$ to be the empty string.
> 4 votes

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


# Question
Title: Not respecting the 3rd rule of a LL(1) grammar
I'm trying to build a grammar that violate only the 3rd rule. I'm trying to figure out what kind of grammar would not respect that.

I think the grammar has to be left-recursive to not respect it.

if $\beta \Rightarrow^\* \epsilon$ then $\alpha$ does not derive any string beginning with a terminal in $\mathop {FOLLOW}(A)$. Where $A \to \alpha \mid \beta$

Am I right to think that?

# Answer
Something like the following:

$\begin{align} S &\to A a \\ A &\to a \mid \epsilon \end{align}$
> 0 votes

---
Tags: formal-grammars, ll-k
---


# Question
Title: Is there any uncountable Turing decidable language?
There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?

# Answer
> 16 votes
We can have uncountable languages only if we allow words of infinite length, see for example Omega-regular language. These languages are called $\omega$-languages. Another example will be language of subset of reals which contains, say, decimal expansions of all real numbers.

There are some models in which Turing Machines are modified to accept $\omega$-languages. Some of these model use Buchi condition for acceptance. Since you cannot see whole of the input in finite time, we say the input is accepted if the Turing Machine enters the accept state infinitely many times. If we can prove this by analyzing the input (not by running it), we say that the input is accepted.

# Answer
> 26 votes
Every language over a finite (or even countable) alphabet is countable. Assuming your Turing machine alphabet is finite, any language it can possibly accept is countable.

# Answer
> 5 votes
Classical computability discusses functions over finite strings from a finite alphabet. As a result all languages whether decidable or undecidable are countable.

To consider **uncountable languages** we have to look at **infinite strings** in place of finite strings. (AFAIK, having an infinite alphabet is not very interesting and doesn't correspond to a realistic model of computation by itself.)

There are models of computation where we can deal with infinite strings which allow us to represent objects from uncountable domains like real numbers. These are often represented as higher-type computations. One model which uses Turing machines is the TTE model. In this model the input can be infinite strings and the machines can access any item in the string it wants. The machine does not need to terminate, however there are conditions to make sure the machine's output converges.

Let's assume that our machine's input is from $\Sigma^\omega$, i.e. infinite strings from alphabet $\Sigma$, e.g. $\Sigma = \\{0,1\\}$. Then there are $\Sigma^\mathbb{N} = 2^\mathbb{N}$ strings. Therefore there are $2^{2^\mathbb{N}}$ possible languages. The number of TTE Turing machines is still countable. So most of these languages are undecidable.

But there is something even more interesting here: if you want the machine to always halt it will be able to read only a finite initial part of the input. As a result we have the following: Let $M$ be a TTE machines that always halts (in finite time). Then there is a prefix-free language $L \in \Sigma^\*$ and Turing machine $N$ such that for any $x\in \Sigma^\omega$, $M$ accepts $x$ iff $N$ accepts the initial part of $x$ which is in $L$.

To put in simple terms, *the computaion of TTE Turing machines that always halt is determined by computation of a Turing machine on finite strings.*

---

Let me give some example of decidable and undecidable languages of infinite strings:

1. For any $k\in \mathbb{N}$ the language of infinite strings whose $k$th position is 0 is decidable. The same with $k$th position being 1. Intersection of any two decidable languages is decidable, e.g. strings whose $3$th position is 0 and $6$th position is 1.
2. The union of any two decidable languages is decidable. E.g. strings which start with $0$ or $10$.
3. Let $L\_i$ be a computably enumerable list of decidable languages. Then $L = \cup\_i L\_i$ is semi-decidable, i.e. there is machine that halts and accepts whenever a strings in $L$ and does not accept when the strings is not in $L$. If it is not in $L$ the machine might not halt. Any semi-decidable language can be obtains through taking union of an enumerable list of language of the form given in item 1 above.
4. A language is decidable iff both the language and its complement are semi-decidable.
5. The language containing the inifinite strings of 0s is not decidable. This might look strange but look at it this way: when reading the string when can be halt and say the input consists of all 0s? If you stop after reading $k$ 0s your machine will also accept the language which starts with $k$ 0s and follows by all 1s. Note that the only access we have to the string in this model is asking for a bit and getting it.

---

This might make you think that TTE is not an interesting model. But it turns out that computation over infinite strings using TTE model is actually quite interesting. It is based on the intuition that to obtain any finite part of the output you can read only a finite part of the input. In other words, any finite information about the output depends only on finite amount of information about the input. It turns out that functions we are interested in computing follow this rule, otherwise we could not compute them. E.g. consider read numbers encoded as binary strings and the function $x \mapsto \lg x$. We give a finite approximation of the number $x$ to the machine and it returns a finite approximation of the number $\lg x$ to us.

---

Many of these become more intuitive if you know a bit of topology. The essential idea here is that we can define an information topology on strings and with respect to that topology any computable function has to be continues. As a result, when we have a total computable function $f$ whose codomain is $\\{0,1\\}$ the $f^{-1}(1)$ has to be clopen. Other realistic models of computation over real numbers (not just floating point but really infinite real numbers) have this property. If you are interested a good place to read about TTE is Klaus Weihrauch's book "Computable Analysis". There are also lots of other references on the website for Computability and Complexity in Analysis Network.

---
Tags: formal-languages, turing-machines, regular-languages, church-turing-thesis
---


# Question
Title: Can I use the set of "used arguments values" as a memoization key for a deterministic function?
I have a deterministic function $f(x\_1, x\_2, ..., x\_n)$ that takes $n$ arguments.

Given a set of arguments $X = (x\_i)$, I can compute $U\_X = \\{ i \in \[1, n\] : x\_i \text{ was read during the evaluation of } f(X) \\}$

Would it be valid to use the set $K\_X = \\{(i, x\_i): i \in U\_X\\}$ as a memoization key for $f(X)$?

In particular, I am worried that there may exist $X=(x\_i)$ and $Y=(y\_i)$ such that:

$$ \tag1 U\_X \subset U\_Y $$ $$ \tag2 \forall i \in U\_X, x\_i = y\_i $$ $$ \tag3 f(X) \neq f(Y) $$

In my case, the consequence of the existence of such $X$ and $Y$ would be that $K\_X$ would be used as a memoization key for $f(Y)$, and would thus return the wrong result.

My intuition says that, with $f$ being a deterministic function of its arguments, there should not even exist $X$ and $Y$ (with $U\_X$ a strict subset of $U\_Y$) such that both $(1)$ and $(2)$ hold (much less all three!), but I would like a demonstration of it (and, if it turns out to be trivial, at least pointers to the formalism that makes it trivial).

# Answer
> 3 votes
As long as $f$ is deterministic and depends only on its arguments (not on other global variables), yes, you can safely use that as a memoization key. The bad case cannot happen.

You can see this by thinking about what happens as it reads the $t$th argument and using induction on $t$. Let $i\_1,i\_2,i\_3,\dots,i\_t$ be the sequence of argument indices read (i.e., $f$ first reads $i\_1$ when running on input $x$, then reads $i\_2$, etc.). For each $t$, if $f(x)$ and $f(y)$ have behaved the same up until just before they read the $t$th of these, then the next index examined by $f(x)$ and $f(y)$ will be the same, say $i\_t$; if additionally $x\_{i\_t} = y\_{i\_t}$, then it follows $f(x)$ and $f(y)$ will behave the same up until just before they read the $t+1$st of their arguments. Since $i\_t \in U\_X$, $x\_{i\_t} = y\_{i\_t}$ is guaranteed by your assumptions. Now use induction.

This assumes everything is deterministic. For instance, $f$ had better not be allowed to read a random-number generator, the current time of day, or other global variables. Beware that on some platforms there can be surprising sources of non-determinism, e.g., due to aspects of behavior that are unspecified and might depend on external factors. For instance, I have a recollection that floating-point math in Java can introduce non-determinism in some cases, and so if you want to write code that is verifiably deterministic, you probably want to avoid all floating-point math.

# Answer
> 2 votes
You can simulate $f$ by what is known in complexity theory as a *decision tree*. Each node is labelled by an input $x\_i$, and the edges going downwards are labelled by the possible values of $x\_i$. Leaves are labelled by the output of $f$. For decision trees you can prove your claim by induction on the height of the decision tree.

This reduces what you want to show to fleshing out the claim that $f$ can be simulated by a decision tree. If you have a computing formalism then you can prove this by induction on the length of the program, but we don't normally do that in complexity theory. We just spend a few seconds thinking about the matter, and see that the claim is obvious, and go on with our life.

---
Tags: algorithms, correctness-proof, memoization
---


# Question
Title: Applying information theory to processor clocks
Has there been any research on the subject of applying information theory to a processors clock? It occurred to me that a clock is actually transmitting data that is used for synchronization of different processor components. Once I started to apply information theory concepts to the clock a lot of interesting ideas came up. I.e. clock speed is equivalent to bandwidth, the two voltage levels it transmits are the equivalent to symbols making is a 2-level transmitter (duh), and the logical limitations on how to usefully apply those two symbols is equivalent to noise. Processor manufacturers increase channel capacity by increasing processor speed and processor architects try to increase information rate by designing smarter encoding/decoding techniques like pipe-lining, branch prediction, speculative execution, and even multi-core processors.

After looking at it like this, and considering that systems designers are going to greater and greater lengths to squeeze greater information rates from just two symbols, wouldn't it make sense to increase the symbol rate? I don't mean going to ternary or quaternary or any other-ary processing, but just giving the clock more symbols or using multiple "clocks". Of course the incredibly high speeds in modern processors and the extremely tiny transistor sizes tend toward not doing so, but it does introduce some interesting thought experiments.

Has anyone explored this in an academic or experimental setting?

# Answer
> 2 votes
Technically, clock skew does this already. Specifically the technique known as "useful skew". When a data signal is going to travel from one storage element to another (both updating based on the clock), the clock that the source and destination elements receive are not quite the same.

In "useful skew", the clock at the destination is delayed such that the data has more time to travel before the capture clock edge arrives at the destination storage element. This allowed more distance of travel as well as more computation.

---
Tags: computer-architecture, information-theory, cpu, clocks
---


# Question
Title: Acceptance behavior of L and NL with and without cycling
The complexity class NL seems to allow cycling, otherwise we wouldn't have SL $\subset$ NL. What about L? If an algorithm from L cycles for a given input, it certainly cannot accept (because it won't enter the accepting state), so we could define that it rejects in this case (which would be consistent with NL). Or is cycling simply not allowed for L?

Does this makes any difference at all, i.e. would NL or L get weaker (in the sense that we can't prove that they still accept the same languages), if we would completely forbid cycling?

# Answer
> 1 votes
Shaull's comment answers the question:

> Do you mean that the TM repeats a configuration? If so, it can always be avoided by keeping a (logspace) counter for the maximal number of configurations, and halting when the counter resets.

This technique can even be used, without knowing (beforehand) any bound for the amount of space used. The TM can just keep track of the amount of space used till the current step (excluding the additional counter), and halt when the counter exceeds the maximal possible number of different configurations given the space used.

The additional counter will take the same amount of space as the computation already used plus the logarithm of the length of the input already scanned. Tracking of the amount of space used adds the logarithm of that used space to the total used space. So this approach to detect (avoid) repeated configurations works for any non-sublogarithmic space complexity class.

---

When I asked that question, I had in mind a technique for finding cycles which only works for deterministic machines: I take two copies of the machine, and always perform one step for the first machine and two steps for the second machine, and then compare the configurations of the two machines. Those configurations can only be equal if the machines cycles, and any cycle will be found before the first machine repeats a configuration.

This technique only works for deterministic machines, and only when copying the machine doesn't violate any resource restrictions. For example, it doesn't work for stack machines (because having two stacks is fundamentally different from having only one stack), and it doesn't work for machines which may only read their input once.

---

For machines which can read their input only in forward direction and only once, the above two techniques can be slightly modified. Each time a new symbol from the input is read, the entire machinery for detection of repeated configurations is reset, and starts again from zero. So the input position must no longer be included in the number of possible states, and the copied machines (of the second technique) no longer need any access to the input. This allows to apply those techniques also to DFAs.

Similar modifications to also make those techniques applicable to stack machines would be nice, because we know that PDAs have no problems with repeated configurations either.

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Why is universal turing machine considered with only one head?
While defining the following time hierarchy theorem (for deterministic case ) :

> If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$

The $\log$ factor comes due to the overhead of simulation by universal Turing machine, as the universal Turing machine has only one head. But what if the universal Turing machine uses same number of tapes and tape heads as some Turing machine $M$, when $\<M,x\>$ is given as an input to it ? Does the $log$ factor vanish ? Am I missing something ?

# Answer
There are two (related) answers to your question. The first answer is that the time complexity classes are traditionally defined using one-head Turing machines. For the diagonalization argument to work, we need the simulating machine to be of the same kind as the simulated machines.

The second answer is that even if you consider time complexity classes defined using $N\>1$ heads, then you are going to encounter a similar problem with the universal Turing machine who only has $N$ heads but has to simulate both the original $N$ heads and to read the program. (It could be that the performance hit is not as bad for more than one head.) Making the number of heads finite but unbounded will make things even worse, since the universal Turing machine has a fixed number of heads.
> 3 votes

---
Tags: complexity-theory, turing-machines, computation-models, simulation
---


# Question
Title: Minimal basis for set of binary vectors using XOR
I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \\{0,1\\}^n$. The problem is to find another set of binary $n$-vectors $B \subset \\{0,1\\}^n$, with minimal size $|B|$, such that every vector in $S$ can be expressed by the XOR results of some subset of $B$ (so $B$ is essentially a basis for $S$ using XOR instead of addition and allowing only binary coefficients in the linear combination).

In a way, this is a form of PCA for binary vectors. While searching for literature on this problem, I came across the Discrete Basis Problem also discussed in this PhD thesis, which seems closely related. Instead of XOR it uses OR, and here $|B|$ is an additional input (and the task is it to minimise the error in representing $S$ with vectors from $B$). This problem is NP-hard. Does the same apply to the problem I've presented above, or is there an efficient solution? Any pointers to existing literature would be much appreciated.

# Answer
If you treat your vectors as over the field $GF(2)$ rather than over the set $\\{0,1\\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear algebra, which you probably know the solution for. (One option is Gaussian elimination.)
> 11 votes

---
Tags: complexity-theory, arithmetic, matrices, linear-algebra
---


# Question
Title: Find the number of words in a language of given length
I was asked the following question:

> Consider the language $S^\*$, where $S = \\{ab, ba\\}$, write out all the words that have seven or fewer letters?

How do I go about calculating the number of words? Are there any resources that break this down to the most basic level?

# Answer
> 2 votes
You can solve the general problem using linear algebra. First, construct a DFA for the language $S^\*$. Then, describe its transition function in matrix form: if the state space is $Q$, construct a $Q \times Q$ matrix $A$ in which $A(s\_1,s\_2)$ is the number of letters that would cause a transition from $s\_1$ to $s\_2$. If $s$ is the starting state, let $1\_s$ be the corresponding vector, and let $j$ be the all-one vector. The number of words of length exactly $n$ is $1\_s A^n j$ (or perhaps $j A^n 1\_s$ if I mixed things up). You can use the spectral decomposition of $A$ to get a formula, or you can calculate it quickly using repeated squaring.

That is the general theory. In your case, it's not too hard to enumerate all words of length up to $7$ by hand. I challenge you to do that.

---
Tags: formal-languages
---


# Question
Title: What would dynamically-typed languages actually do if type enforcement was removed?
I program in Python, which is a well-known dynamically typed language. I understand dynamic typing to mean mainly that "operations" (in a loose sense) in the language are either allowed or denied (raise an exception) based on the type of their operands, and that this type-checking is deferred as long as possible. My question is this: if that is what a fair characterization of dynamic languages, **what would happen if the run-time type checking was removed**?

It seems to me that if you want to make a meaningful distinction between a dynamically typed language like Python and an *untyped* language, you would have to define what actually would happen in the untyped language in situations in which the type system of a dynamic language would take action. For example, in Python, if I attempt to subtract an Integer from a String, e.g., "spam" - 5, I receive a TypeError. If that's what makes Python dynamically typed, what would an "untyped Python" do in that situation?

# Answer
Your characterization of dynamically typed languages¹ is broadly correct. However, it is somewhat incomplete. Types go beyond type checking: they also characterize values. In Python, this is a fundamental part of the language.

In Python, every value is an object, and the type of a value is for the most part determined by the methods it supports. This is known as structural typing, and especially when done dynamically as duck typing. The main job of the `-` operator is to invoke the method `__sub__` on an object. It performs a few additional type checks, and you can explore what happens when those type checks are removed by calling `__sub__` directly.

```
>>> (3).__sub__("a")
NotImplemented
>>> "a".__sub__(3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'str' object has no attribute '__sub__'

```

The type errors are actually coming from verifications performed by the `-` operator. When you get down to `__sub__`, what happens is up to the method provided by the object.

* The object constructed by the literal `3` is a built-in integer; its `__sub__` method performs case analysis on the type of the argument. The innards of that method do something like this:

```
if the argument looks like an integer:
    perform integer subtraction
else if the argument looks like a floating-point number:
    convert the integer to floating point
    perform float subtraction
…
else: return NotImplemented

```

The fallback case is a design choice of the built-in `__sub__` method. It doesn't do a dynamic type check with a boolean result, but a dynamic type analysis.
* The object constructed by the literal `"a"` is a built-in string; it has no `__sub__` method. There is no type check per se here. The runtime engine does check whether there is a `__sub__` method, but only as part of locating it: there isn't a check operation that's not intrinsically part of locating the method.

Thus “untyped Python” is a difficult concept to define — you can't take out the types without taking out fundamental parts of the language. You could phrase the question differently: what if, say, the code of the `__add__` method of a string (`"a".__add__`) was applied to the data of a built-in integer?

```
>>> int.__add__("a",1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: descriptor '__add__' requires a 'int' object but received a 'str'

```

This here is an actual type check. If this type check wasn't performed, what would happen would depend on the implementation. In a typical implementation, the code of the `__add__` method for integers would attempt to access the object `"a"` as if it was an integer. Depending on the exact layout of objects in memory, it might do things like:

* treat `"a"` as the integer 97 (because it's reading the same bytes and interpreting them differently);
* interpret a location in memory as a pointer to an address, and operate on a bunch of bytes that happen to be present at that address, and thus construct a bogus integer as a result;
* interpret a location in memory as a pointer to an address, and trigger a page fault because this address is not mapped in the calling process, resulting in the process dying of a segmentation fault;

In general, what happens on a typical computer when you remove type checks (static or dynamic) is undefined behavior. Eventually a bunch of bytes is interpreted in a way that's unrelated to the way it was constructed, which can lead to anything: a wrong result (because the bytes happen to mean something), a segmentation fault or other crash (because the bogus data leads to attempting to access a memory address that isn't mapped, or to execute data as code which may contain an invalid instruction), weird things happening (because the bogus data leads down a code path that has nothing to do with what the program should have been doing), etc. In  (a language which has no strong typing, meaning that the programmer can easily lie to the compiler about the type of objects), undefined behavior is a fact of life, and it famously can do anything including making daemons fly out of your nose (most computers fortunately lack the requisite hardware).

¹ <sub> Not “dynamic languages”, which I don't recommend using as it's a lot fuzzier. </sub>
> 9 votes

# Answer
A language in which automatic type checking is not available, an operation would make assumptions about the types of its operands. On the event that these assumptions are false, the operation, not knowing anything about this, may produce nonsense results.

Assembly is such language. It has, for instance, separate addition operations for integers and floats. If you perform integer addition on floating point values you will get a result which is correct as neither integer nor float. Depending on your definition of correct.
> 10 votes

# Answer
One possibility is that the operation produces nonsense results, as Karolis Juodelė explains so nicely.

Another possibility is that the operation causes memory corruption, undefined behavior, or introduces a security vulnerability. Consider array access, e.g., writing to `A[i]`. Some languages define a type system to ensure that the index `i` is in bounds. Some do run-time checking of whether the index is in bounds and throw an exception if it is not. And then there there are others -- like C and C++ -- that do no array bounds checking. If you try to write to `A[i]` at an index `i` that is out of bounds, the program goes ahead and writes to some other memory location outside of `A`. This can cause memory corruption and crashes, but worse, it can introduce security vulnerabilities: an attacker who controls the value of `i` can exploit the buffer overrun vulnerability, inject malicious code into the program, and take control of the program. That's about the most severe kind of security vulnerability possible, and it is possible because of the lack of any run-time checking.

So, another possible outcome of such a mis-typed operation is that this might introduce security vulnerabilities that could be exploited by an attacker to take control of your program. This is a reasonable argument in favor of some kind of type checking (whether run-time or static) over absence of any type checking.
> 2 votes

# Answer
The below is the conclusion that I have drawn from answers to the SO question Does “untyped” also mean “dynamically typed” in the academic CS world?.

For a dynamic programming language *L* the following two statements are **equivalent**:

1. *L* is **dynamically typed**.
2. *L* is **untyped**.

In other words, there is no meaningful distinction between a *dynamically typed* language and an *untyped* language, whenever we speak about dynamic languages like Python, Ruby or JavaScript. These are high-level languages that implement some *object model*. Objects are the only data entities that can be referenced. There is no notion of pointers to memory chunks, no pointer arithmetic. There are two main kinds of situations that are reported as type error: (1) evaluation request is not understood, (2) the request is understood but rejected because a transition to an illegal state is requested.

A canonic representant of the (1) group is method (or attribute) resolution failure. That is, for an object `o`, there is a request of method invocation `o.m()` but no method is associated with `o` under the name `m`. (And no interception handler is defined.)

An example for the (2) group is a request to create a class that is a subclass of a non-class object (applies to both Python and Ruby). Or, in Python, to create a class with the `metaclass` parameter used whose value is a class that is not a descendant of the `type` class (i.e. whose value is not a metaclass). Or, in Ruby (as of 2016), to create a subclass of the `Class` class.

In my opinion, only the type enforcements of the (2) group can conceivably be removed. This would result into the possibility to create wild and/or unsupported structures between objects. But in the case of the (1) group, there is no clear candidate of what a "type enforcement removal" should mean. One can only invent some nonsense behavior in response to such situations.

---

(Added after 2 days.)

To me, the title question can be formulated as: **How can a dynamic object-oriented language like Python potentially be untyped?** My answer is that there are basically just two ways how to achieve this:

1. Via the **dynamically typed****untyped** equivalence.
2. By inventing nonsense behavior (a *generalized nasal demon*) for method resolution.

Let us consider **Python**, **Ruby** and **JavaScript** as three significant languages that are **relevant** to the title question. All of them are popular dynamic OO languages in which *"classes are objects"* and in all of them there is a built-in `TypeError` class. (JavaScript is sometimes claimed to be classless. We will follow here *JavaScript: The Definitive Guide* by D. Flanagan, where there classes are explicitly mentioned, including the `TypeError` class. Moreover, the notion of a class is explicitly supported in ECMAScript 6.) At this point let us emphasize, that **assembly** or the **C** language mentioned in some answers or comments are **NOT relevant**.

Having established the group of three languages that *are* relevant to the question we can observe that the *dynamically typed**untyped* equivalence has already been established in the literature. There are probably more statements that the 3 languages are dynamically typed but there is also considerable amount of statements about their **untyped**ness or **typeless**ness. As for Python: (Py1), (Py2), (Py3), (Py4), (Py5), (Py6) (Py7), (Py8), (Py9), (Py10), (Py11), (Py12). As for Ruby: (Rb1), (Rb2), (Rb3), (Rb4), (Rb5). As for JavaScript: (Js1) – quoted by Wikipedia in the opening sentence, (Js2), (Js3). Moreover, there are also articles ((eq1), (eq2)) where the equivalence (*dynamically typed**untyped*) is suggested explicitly.

The reason behind this terminological paradox is that removing what is called *run-time type checking* would mean not throwing any `TypeError`s which is absurd. (Why then throw any `Error` at all?) One can imagine that there is no detection of possible invalid states as I have mentioned before. (To give an example also for JavaScript, the `x.`__proto__` = x` assignment is a request to form a cycle in inheritance, and thus rejected as a `TypeError`.) But without the (absurd) concept of nasal demons, I cannot imagine what should a "removal of type enforcement" mean in the `o.m()` case of method resolution failure. What is a possible meaning of calling a missing method?

I also think that the `1 + "a"` example of typechecked Python code provided in the answer by Gilles should be presented for a user-defined function, rather than a built-in one. In this case, disallowing type checking would in fact mean to prohibit the programmer from using `isinstance` (`issubclass`, `type()`, ``__class__``, ...) and/or throwing `Error`s. This is absurd too.

The only non-absurd removal of a type constraint that I am aware of is disregarding the number of method arguments – something that is realized in JavaScript (probably due to missing default argument values). But I doubt that this should be the dividing point - the reason why JavaScript should be considered untyped while Python and Ruby dynamically typed.

Summed up, the **dynamically typed****untyped** equivalence can be used as a mnemonic for an inconsistency in the terminology. It is better than to pretend that the notions are well established.
> 0 votes

---
Tags: programming-languages, type-theory, type-checking
---


# Question
Title: What can be said in general about a homomorphism between two regular languages?
In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can find a homomorphisms? And if not that, are there maybe a finite number of families of homomorphisms which divide all regular languages into classes?

---

My motivation for asking this question is from taking an undergrad course in group theory, and wanting to see if the treatment of polynomials by group theory can be applied to regular languages.

# Answer
> 5 votes
Some examples, to get the discussion going:

* For an infinite family of languages with no homomorphisms between them, consider the languages $L\_k=\\{a,a^k\\}\subseteq\\{a\\}^\*$ for $k\ge 2$. If $f:L\_i\to L\_j$ were a homomorphism for $i\neq j$, then $f(a)$ would be either $a$ or $a^j$, and $f(a^i)$ would be $a^i$ or $a^{ij}$, neither of which is in $L\_j$.
* On the other hand, it is easy to find infinite chains of languages with homomorphisms between them, just consider $L\_i=\\{a^k\ |\ 1\le k\le i\\}\subseteq\\{a\\}^\*$ and the inclusion $L\_i\to L\_j$ for $i\<j$.

---
Tags: formal-languages, regular-languages, group-theory
---


# Question
Title: Find all pairs of strings in a set with Levenshtein distance < d
I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that string. The Levenshtein distance (also called the edit distance) between two strings is the number of insertions, deletions and/or replacements required to convert one string into the another.

This should be possible in $O((d + 1)^{2d + 1} \cdot l \cdot n)$ time with a Levenshtein transducer, which takes a single query string at a time and find all the matches in a set with Levenshtein distance $\le d$. However, using the implementation at that link, it appears to take more like $O(n \log n)$ time rather than $O(n)$, and uses more than 200 GB of memory.

Is there an alternate $O(n)$ approach that might be faster in practice? The Levenshtein transducer is more general than it needs to be for this application, since it finds matches for each string independently and doesn't exploit the fact that you're comparing every string against every other string.

# Answer
> 6 votes
There's a "trick" you can use that might potentially speed up your algorithm a little: shingling. No guarantees that it'll necessarily help in your particular case, though.

**Lemma.** If the edit distance between two words $w,x$ is $\le 4$, and the two words both have length 20, then there exists some 4-gram that is common to both words (i.e., some $u$ of length 4 that is a substring of both $w$ and $x$).

This lemma then suggests the algorithmic trick. Build a table with $4^4$ buckets, one bucket for each possible $4$-gram. Given a word $w$, extract all of its 4-grams (there will be 17 of them) and insert it into those 17 buckets. Do this for each word.

Now, if there is a pair of words at edit distance $\le 4$, then there must be some bucket that contains both words. So, for each bucket, we search the set of words within that bucket for a pair of words at edit distance $\le 4$. Use whatever algorithm you like for that task. I would suggest trying BK-trees or metric trees.

Will this trick help? The only way to know for sure is to try it. But here's the intuition. We'll have 256 buckets. Each word will get mapped into 17 buckets. Thus, heuristically, we expect each bucket to have $n'=17n/256$ words in it. If we have an algorithm that can search for pairs of words at edit distance $\le 4$ among a set of words in $T(n)$ time, then applying that directly to the original set of words takes $T(n)$ time. In contrast, after applying this trick, we apply it once to each bucket. Now if $256 T(17n/256)$ is smaller than $T(n)$, this trick might yield improvements in running time. My prediction is that it'll yield improvements for $\Theta(n^2)$-runtime algorithms, but not for $O(n \lg n)$ or $O(n)$ time algorithms.

This trick can be combined with any algorithm for looking for a pair of words with edit distance $\le 4$ in a set of $n$ words.

---

The "trick" can be improved further. Define a "slate" of the word $w$ to be a pair $(i,u)$ where $i$ is a position ($1 \le i \le 17$) and $u$ is the 4-gram that occurs at position $i$ within $w$. From each word you get 17 slates. Now we get a refined lemma:

**Lemma.** If the edit distance between two words $w,x$ of length 20 is $\le 4$, then there exists a slate $(i,u)$ of $w$ and a slate $(j,v)$ of $x$ such that $u=v$ and $|i \le j| \le 2$.

(It might be possible to improve the latter condition to $|i \le j| \le 1$, but I haven't tried to check.)

We'll do the same thing as before, but identifying each bucket with a slate. We get $20 \times 256$ different buckets. Now, for each word $w$, extract its 17 slates and store the word in the corresponding 17 buckets. Let $B\_{i,u}$ denote the set of words in the bucket for the slate $(i,u)$. Finally, for each slate $(i,u)$, we check whether there exists a word $w \in B\_{i-2,u} \cup B\_{i-1,u} \cup B\_{i,u} \cup B\_{i+1,u} \cup B\_{i+2,u}$ that is within edit distance $\le 4$ of some word in $B\_{i,u}$.

Heuristically, we expect each bucket to have $n'=17n/(20 \times 256) \approx 0.0033 n$ words in it. We expect the running time for each bucket to be something like $5 T(n')$, and we need to do that $20 \times 256$ times, for a total running time of $25600 T(0.0033n)$.

Is this better than the prior trick? The only way to know for sure is to try it. My prediction is that this'll be better for $\Theta(n^2)$-runtime algorithms, but worse for $O(n \lg n)$ or $O(n)$ time algorithms.

---

Finally, I don't think you have the running time of your scheme right. I believe the Levenshtein transducer automata approach will have running time $\Omega(n^2)$ in your setting, as several folks have outlined in the comment thread under your question.

---
Tags: algorithms, strings, string-metrics, edit-distance
---


# Question
Title: How do I select a subset such that the sum and the product are greater than some value?
I have asked few days ago this question. Now I am simplifying the problem a little bit.

Given two sets $A=\\{a\_1,\ldots,a\_n\\}$, and $B=\\{b\_1,\ldots,b\_n\\}$ of non-negative integers, a positive integer $k\<n$ and a positive integer $\Delta$. The question is: is there a subset of $S$ of $\\{1,\ldots,n\\}$ of size $|S|\leq k$ such that $$\left(1+\sum\_{i\in S}a\_i\right)\left(1+\sum\_{i\in S}b\_i\right)\geq\Delta$$ Say no, if no such subset exists. Note.$ \Delta$ is greater than $1$ and not big enough.

My question is:

* How do I solve this problem? I do not know if this is an NP-complete problem or not. Do you see some hardness or reduction?

My attempt: First I failed to to prove that it is a hard problem. I tried to reduce from PARTITION but no way. I give up and I tried to design an algorithm. Here is my algorithm.

1. Choose $S=\emptyset$ and $P=0$
2. Choose the $i$ of the largest sum $a\_i+b\_i$ and add it to $S$
3. Let $j$ go from $1$ to $n$ except $i$ do
    * 3.1. Add $j$ to $S$
    * 3.2. Calculate the product above with $S=\\{i,j\\}$ and store it in $P$
4. Pick the $j$ with the highest $P$
5. Re-do this $k$ times.

In this algorithm optimal?

Note: The real question is about the hardness of the problem. Thanks.

# Answer
Thanks to Yuval for the link. I think I can prove now that the problem, called PRODUCT, is NP-hard by a reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes.

Given an instance $\\{x\_1,\ldots,x\_n\\}$ of EQUAL-PARTITION (with $x\_i \> 0$ and $n$ is even), consider an instance of my problem with $k = n/2$, $\Delta=\left(1+nM/2+A/2\right)^2$ for large enough $M$ (i.e., $M = \max\_i x\_i$ ) and $A=\sum\_{i}x\_i$ , and let $a\_i=M+x\_i$ for all $i$ and $b\_i=M+2A/n-x\_i$ for all $i$.

This is a polynomial time reduction.

Now let us prove that EQUAL-PARTITION is solved $\iff$ PRODUCT is solved.

* "$\Rightarrow$" Suppose that EQUAL-PARTITION is solved. Then there exists $S$ of size $|S|=n/2$ such that $$ \sum\_{i\in S}x\_i=\sum\_{i\in S'}x\_i=A/2, $$ where $S\cup S'=\\{1,\ldots,n\\}$ and $S\cap S'=\emptyset$ and $|S|=|S'|=n/2$. Now take the solution to PRODUCT to be $S$. We have \begin{align} &\left(1+\sum\_{i\in S}a\_i\right)\left(1+\sum\_{i\in S}b\_i\right)\geq\Delta\\ \iff&\left(1+\sum\_{i\in S}(M+x\_i)\right)\left(1+\sum\_{i\in S}(M+2A/n-x\_i)\right)\geq\Delta\\ \iff&\left(1+nM/2+\sum\_{i\in S}x\_i\right)\left(1+nM/2+A-\sum\_{i\in S}x\_i\right)\geq\Delta\\ \iff&\left(1+nM/2+A/2\right)\left(1+nM/2+A/2\right)=\left(1+nM/2+A/2\right)^2\\ \end{align}
* "$\Leftarrow$" Suppose that PRODUCT is solved. Then there exists $S$ of size $|S|=n/2$ such that \begin{align} \require{overset} &\left(1+\sum\_{i\in S}a\_i\right)\left(1+\sum\_{i\in S}b\_i\right)\geq\Delta\\ \iff&\left(1+\sum\_{i\in S}(M+x\_i)\right)\left(1+\sum\_{i\in S}(M+2A/n-x\_i)\right)\geq\Delta\\ \iff&\left(1+nM/2+\sum\_{i\in S}x\_i\right)\left(1+nM/2+A-\sum\_{i\in S}x\_i\right)\geq\Delta\\ \iff&\left(\alpha+\sum\_{i\in S}x\_i\right)\left(\alpha+A-\sum\_{i\in S}x\_i\right)\geq\Delta\\ \iff&\alpha^2+\alpha A+A\sum\_{i\in S}x\_i-\left(\sum\_{i\in S}x\_i\right)^2\geq\Delta\\ \iff&\left(\sum\_{i\in S}x\_i\right)^2-A\sum\_{i\in S}x\_i+\Delta-\alpha^2-\alpha A\leq 0\\ \iff&X^2-AX+\Delta-\alpha^2-\alpha A\leq 0\\ \overset{(a)}{\iff}&X^2-AX+\Delta-\alpha^2-\alpha A= 0\\ \iff&X= A/2\\ \end{align}

Finally, PRODUCT is NP-hard.
> 3 votes

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


# Question
Title: Communication allowed in the NC^i model?
I want to verify if I am correct in my interpretation of the $\mathrm{NC}^i$ model.

In this model the input is given to at most $O(n^k)$ processors and each processor takes at most $O(\log^i n)$ time to arrive at a solution.

Can the processors communicate on any intermediate data?

How is the result whether accept or reject announced?

---

**A fine grained problem**

So the output of the algorithm can depend on partial results computed on previous processors?

There are $O(n^k)$ processors. So even if each processor computes $1$ bit of intermediate data that is useful for all processors then reading the intermediate results will itself take $\Omega(n^k)$ time then there is no way processors can finish in $O(\log^in)$ time.

So what limitations are there in the length and dependency on intermediate results?

# Answer
> 1 votes
The model of parallel computing used in the definition of Nick's class is PRAM (see this wiki page, note: particular policy for handling read/write conflicts is irrelevant for Nick's class). In this model, the processors share memory and a common clock, but are otherwise independent. Therefore, any communication that happens between processors uses memory as the channel. The result of the computation can be announced in some pre specified register.

Edit:

Note there are a couple ambiguities in your statements: to show that a problem belongs to $\mathrm{NC}^i$ you can choose $k$ (the power in your polynomial number of processors) depending on the particular problem, while $i$ is fixed. Also, all the quantities should only be specified up to a constant, e.g. $O(\log^i n)$ time and $O(n^k)$ processors.

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


# Question
Title: Which types of mathematical functions are the least complex for a computer to compute ?
Let's consider these four function types : Polynomial, Exponential, Logarithmic and Trigonometric.

Considering that both input and output values are floating point numbers.

How do they rank in terms of time complexity (of computing an output value for a given input value) ?

# Answer
> 1 votes
To evaluate polynomial you use Horners scheme, or if you do not know how to compute it, still straightforward naive approach works. It depends on "how big" is this polynomial...

For logarithm and exponent you could use BKM and for trigonometric functions CORDIC.
So ranking by time polynomial is the fastest, and the rest is equally time consuming.
It is hard to tell apart, as basically the same algorithm can compute all these functions.

Using floating point numbers (so inexact results are obvious) the time complexity of special functions is $O(1)$, because underneath you have constant number of rounds no matter what the input was.
Number of iterations is fixed for given precision, so it does not depend on particular input (although angle reduction is time consuming for huge input value).
Polynomial evaluation is $O(n)$ in number of given coefficients using Horner, otherwise it is $O(n^2)$.

# Answer
> 0 votes
If by "computer" you mean e.g. a bog-standard PC, polynomials are harder to compute. The basic elementary functions (square root, sin, cos, natural logarithm, exponential) are computed in hardware, by specialized instructions.

To compute a polynomial, the best technique is Horner's method. It can be shown optimal if the coefficients aren't known beforehand.

---
Tags: complexity-theory, time-complexity, mathematical-programming, numerical-algorithms
---


# Question
Title: Conflict Driven Clause Learning combined with brute force
I am learning about the Conflict Driven Clause Learning method to solve SAT problems. In this method it is possible to learn clauses and add these in the set of the initial clauses. I understand a learned clause as the negation of a conjunction of clauses such that these make a formula false (conflict).

I have thinking in another way to add learned clauses, in parallel way, to the set of learned clauses. That is, select a random set of assignments for the all variables of a formula $\phi$. If these assignments make the formula false then add this to the set of learned clauses, using negation operator. Sorry by my ignorance but, Do you know if is it reasoning valid?

For example in the next formula in Dimacs format

```
1 4 0
1 -3 -8 0
1 8 12 0
2 11 0
-7 -3 9 0
-7 8 -9 0
7 8 -10 0
7 10 -12 0

```

If 1=0 and 2=1 and 3=1 and 4=0 and 5=0 and 6=0 and 7=0 and 8=0 and 9=0 and 10=0 and 11=0 and 12=1 then $\phi$ is false. Then, the new set of formulas is

```
1 4 0
1 -3 -8 0
1 8 12 0
2 11 0
-7 -3 9 0
-7 8 -9 0
7 8 -10 0
7 10 -12 0
1 -2 -3 4 5 6 7 8 9 10 11 -12

```

# Answer
> 5 votes
Your reasoning is valid, but it won't help a SAT solver go much faster. Your method produces long clauses that only forbid a single assignment. What you want to speed up a recursively searching SAT solver is to learn short clauses that forbid many assignments. That requires a more sophisticated learning strategy than adding a simple disjunction of the negation of the current variable assignment.

---
Tags: algorithms, machine-learning, satisfiability
---


title: Why is FACTOR in Co-NP?

text:
# Question
Title: Why is FACTOR in Co-NP?
I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS primality test, and I believe this works for COMPOSITE as well.

As for FACTOR,

$$FACTOR = \\{(m,r) :\\;\\; \exists s \text{ such that} 1\<s\<r \text{ and } s \text{ divides } m\\} $$

from what I have read it seems that it is in $NP \cap Co-NP$. I see that it is in $NP$ since a certificate would consist of a prime divisor of $m$ less than $r$. But what kind of certificate can establish that there is no such prime divisor (in polynomial time)?

# Answer
> 14 votes
A certificate for there being no non-trivial divisor of $m$ smaller than $r$ is the factorization of $m$. We can check in polynomial time that all factors are indeed prime (since primality is in P by AKS primality test), that their product is $m$, and that all of them are at least $r$.

# Answer
> 6 votes
To add to Yuval's answer: AKS primality testing was discovered in 2002. Prior to that we didn't have a polynomial time algorithm to check if a number is prime. However Pratt discovered in 1975 what is now known as Pratt certificates for primality and proved that Primes is in NP. We can include these Pratt certificates of primality for the factors in our certificate to show that FACTOR is in coNP in place of using the AKS algorithm to check if factors are prime directly.

---
Tags: complexity-theory, factoring
---


# Question
Title: Why is simulation by non deterministic Turing machine faster than a deterministic one?
A deterministic universal Turing machine $U\_D$ can simulate a deterministic turing machine $M\_D$ in $O(T(n)log(T(n)))$ where $M\_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and Boaz Barak that a non-deterministic universal Turing machine $U\_{ND}$ can simulate a non deterministic Turing machine $M\_{ND}$ in $O(T(n))$ where $M\_{ND}$ runs in $O(T(n))$.
The hint to the exercise is that $U\_{ND}$ first non deterministically guesses tape contents of $M\_{ND}$ and verifies then later. But how does this help as any branch of $U\_{ND}$ can simulate a branch of $M\_{ND}$ in $O(T(n)log(T(n)))$, similar to the deterministic case. Am I missing something ?

# Answer
First of all, simulation of non-deterministic universal TM is better than simulation of deterministic universal TM only time-wise. But number of parallel executing threads is very high. In parallel algorithms parlance, $T(n)$ will be smaller but another metric $T(n)P(n)$ will be higher.

Deterministic UTM has extra $\log T(n)$ factor because it has to simulate multiple working tapes in a single working tape. If we use it as a simple multiple track tape, then to simulate a single step we will need to go to and forth for maximum $T(n)$ steps. We can improve this time by a clever trick. Instead of moving heads on the multiple tracks, we keep the head of the track(s) stationary and move the content of the tracks. We also keep a gradually increasing number of interspersed blank spaces (another special blank space, instead of regular blank space) on both sides of head to do the shifting of tape content efficiently. By successfully executing this trick, each step can be simulated in amortized $O(\log T(n))$ steps.

We have to see how we can simulate non-deterministic UTM cleverly that does not require us to go to and fro, thus saving us $O(\log T(n))$ factor. Going to and fro in $k$ working tapes is the real bottleneck. We assume input and output tape are separate in both UTM and simulated TM, so they do not matter much.

Let us think how we can simulate a single work tape without going to and fro. What we do, is whenever we need to go left, we do not go left, instead we guess what is in the left, maybe 0 or may be 1 (or maybe $B$ ot may be \>, beginning of tape), and proceed to the right (non-deterministically of course, for both the cases), but we write what we guessed on a work tape. Since we are not moving left correctly, we cannot know tape symbols when we move right too. So whether we move left or right, we non-deterministically guess what is under the head, make note of our guess, and move on.

After the computation is over (by a series of $T(n)$ fake or correct guesses and writings), for each thread of computation we have the content of guesses on a work tape, and we can check if the guesses and writings on the tape match in linear time $O(T(n))$ by actually going to and fro in yet another work tape. If we need our UTM not to exceed $T(n)$ execution time then we need to keep a counter for $T(n)$, some of the errant threads may go on executing for infinite time (there is a requirement on some non-deterministic TM models that every thread should stop after $T(n)$ time for acceptance, while in others only accepting threads need to stop after $T(n)$ time).

If we do this for all $k$ tapes together in a single tape, then too will be able to do this trick, but we will have to go to and fro $k$ times, one for each tape, to check if the guesses of each tape are consistent with what we are writing and what we are guessing later. This checking will take $O(kT(n))$ additional time overall for all tapes. So total running time of the non-deterministic UTM will be $O(CT(n)+kT(n))$.
> 9 votes

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


# Question
Title: DP - Removing contiguous subsequences from a sequence optimally
I was asked this question a while ago and I'm very stuck:

> You have a sequence of `0`'s and `1`'s, and you can perform one operation it: removing at least $K$ consecutive `0`'s or $K$ consecutive `1`'s from the sequence. After performing one of these operations, the ends of the sequence that are on the sides of the removed portion come together and close the gap created by the removal.
>
> Can you make operations such that the sequence becomes empty? If so, what is the least number of operations that you can make? I'm hazy on the restraints on the problem, but assume both $N$ and $K$ have at most two digits, and that $K$ is a lot smaller than $N$.
>
> For example, say you have the sequence `1111000001`, and $K = 5$. The solution is to remove the middle line of `0`'s. You cannot remove any `1`'s on the first step, because the longest consecutive substring of `1`'s is only four long. Afterwards, however, the gap closes, and the sequence `11111` is created, which can also be removed, creating the desired empty sequence. Only two operations are needed to make the sequence empty.

I believe that this is a DP problem, but I'm having trouble on what to represent as a state and how to construct a state from previous ones. Could anyone give me a hint?

# Answer
1. First collect the consecutive alphabets together. Say the input string is "1110000110100" then I mean form the array $A=\\{(3,1),(4,0),(2,1),(1,0),(1,1),(2,0)\\}$ where an element ( called chunk ) of $A$ $(a,b)$ means there are $a$ consecutive $b \in \\{0,1\\}$. Now the problem has been reduced to removal of chunks and we will concern ourselves with $A$ rather than the original string.
2. Now make a DP table $D$ where $D\[i\]\[j\]\[k\]$ means least number of steps used to removed all chunks till $A\[i\]$ such that last chunk removed was of $k \in \\{0,1\\}$ and the size of the last chunk removed was $j$. If it is not possible assign it $\infty$ ( take care of the boundary cases and initial condition for table $D$ ).
3. Now say you are at chunk $i$ and it is a chunk made of 0's and it's size is $t$. Now you have to fill the table $D\[i\]\[\]\[\]$ given that you have already filled the tables $D\[1\]\[\]\[\],D\[2\]\[\]\[\]......D\[i-1\]\[\]\[\]$. You have two options (a) If $t \ge K$ remove this chunk first and now you are left with subproblem with $A\[1\]...A\[i-1\]$; (b) or if its possible to remove the chunks of 1's before , and then if the chunk of 0's get's size greater than equal to $K$, you can remove it ( rwe will take minimum of all cases while filling the DP table ). As you asked for only hint I leave it upto you for coming up with the recurrence relation.

As you said $N$ and $K$ are small, I think this method would suffice.
> 0 votes

---
Tags: algorithms, dynamic-programming, decision-problem
---


# Question
Title: Is Post's correspondence problem recognizable?
I want to know whether Post Correspondence Problem (PCP) is recognizable. I learnt how to demonstrate the undecidability of PCP. I thought to use the similar approach for recognizability too i.e. to considering MPCP and show whether it is recognizable. I am not sure if it is a good approach.

# Answer
> 7 votes
We can recognize acceptable inputs of PCP by exhaustively checking all valid possibilities (preferably by non-deterministic TM). *That is it!*. If the input is acceptable then the TM will stop, if it is not then the TM may not stop. Thus PCP is an RE language. Recognizability should not be confused with decidability.

We can do the same with deterministic TM by essentially simulating each thread of NDTM one step at a time.

---
Tags: computability, semi-decidability
---


# Question
Title: Computing the intersection of N sets over an M-element universe
Suppose I have $N$ sets $S\_1,\dots,S\_N$ each with elements from set $\\{1,\dots,M\\}$.

**1.)** What is a good algorithm to find $S\_1\cap\dots\cap S\_N$?

**2.)** I am also looking for a good parallel and a good distributed algorithm.

# Answer
> 1 votes
Usual method is you sort all the sets, and select common elements by looking at the beginning of each sorted sequence. This gives you $O(NM)$ algorithm if you do bucket sort. Or in the bucket sort step itself you may check if all the sorted sequence has common elements by doing an operation AND on the bits.

There is even better algorithm that runs in $O(\Sigma\_{i=1}^N |S\_i| + M$ (i.e. $O(n+M)$) if sets are not multisets (which is the case here). Let $V\[1..M\]$ be a zero vector. For each $i \in 1..N$, for each $x \in S\_i$ do increment $V\[x\]$. Select those $x$ for which $V\[x\] = N$. (Note: For multisets also we can do something similar, but we need to do some housekeeping to ensure that we increment only once for a particular element $x$ in a set $S\_i$ even if it occurs multiple times.)

If the elements of each sets are already stored in efficient search data structure they you can do it another way. This also works if you have domain as general values rather than values from $Z\_M$. You take the smallest sized set $S\_{min}$ and select elements from $S\_{min}$ one by one by checking if it belongs to every set $S\_i$ in time $O(\log |S\_i|)$. This gives you $O(N\cdot |S\_{min}|\cdot \log(|S\_{max}|))$-time algorithm, where $S\_{max}$ is the largest set, and which might be better than $O(NM)$ if smallest and largest sets are small enough.

# Answer
> 0 votes
Represent each set $S\_i$ as a 0-1 vector $V\_i$, then sum all of them. Then your intersection set is the fields where you have $N$ in the sum vector $\Sigma V\_i$.

Runtime is $O(N.M)$

# Answer
> -2 votes
Here is an O(n) algorithm:

Create an std::unordered\_set

Put all items of vector A into the set

Go through all items of vector B, checking that they are present in the unordered\_set, and incrementing the count for each item that is present. Return the final count.

Here is an implementation in C++11, using a lambda for brevity:

`vector<int> a {2, 3, 5, 7, 11, 13};
vector<int> b {1, 3, 5, 7, 9, 11};
unordered_set<int> s(a.begin(), a.end());
int res = count_if(b.begin(), b.end(), [&](int k) {return s.find(k) != s.end();});
// Lambda above captures the set by reference. count_if passes each element of b
// to the lambda. The lambda returns true if there is a match, and false otherwise.`

---
Tags: algorithms, distributed-systems, parallel-computing, sets
---


# Question
Title: Finding the number of square prefixes of a string in linear time
> Let *square* denote a concatenation of two identical, nonempty strings. Given a string $w$, devise an $O(|w|)$ algorithm that counts the number of prefixes of $w$ that are squares.

My initial idea was to use the prefix function $P$ from the Morris-Pratt algorithm ($P\[i\]$ is the length of the longest proper prefix of $w\[1..i\]$, being also its suffix), which can be calculated in linear time. Then, for each even index $i$ (we do not need to consider prefixes of odd length, as those obviously cannot be squares) the corresponding prefix $w\[1..i\]$ is a square if $P\[i\] = i/2$ and is not a square if $P\[i\] \< i/2$.

Now, the missing case which I am unsure how to handle is $P\[i\] \> i/2$. For example, let's consider the two strings: $abababab$ and $ababab$. The longest proper prefix-suffix of each of them is bigger than half the length of the string (6 and 4 correspondingly), yet the first one is a square and the second isn't.

Can anyone point me to an observation needed to resolve the missing part of the algorithm? Or is the idea to use the $P$ array wrong and a different approach should be applied to this problem?

# Answer
Suppose there is an $O(|W|)$ algorithm that computes a slightly different prefix function: $Z\[i\]$ is the longest prefix of $W$ that is also a prefix of $W\[i..n\]$. Note then that your answer will simply be the count of indices $i$ such that $Z\[i\] \>= i$, assuming 0-indexing.

Fortunately, such an algorithm exists and is quite elegant! It's (as always) a good idea to try to devise it on your own. If you get stuck, here's a pretty good explanation: http://codeforces.com/blog/entry/3107.
> 4 votes

# Answer
It's also easy to do with a Rabin-Karp-type hash: https://en.wikipedia.org/wiki/Rolling\_hash, which you can use to check equality of any two substrings in $O(1)$ time, albeit with a probability of error. This probability can be made negligible and works very well in practice.

I prefer the above-suggested "Z-Algorithm" solution because it's deterministic, but more so because it's a cool algorithm that is not well-known.
> 3 votes

---
Tags: algorithms, strings, counting
---


# Question
Title: How is a human brain the same as a computer?
Which functions performed by the brain equal which parts/functions of a computer? For example, human memories are like data saved to a hard drive?

# Answer
Whether human brain is or is not same as a Turing Machine has not been proven yet. There is a famous unsolved Church Turing Thesis. It still remains a hypothesis till today.

Also the comparison of memory to hard drive aka tape of Turing Machine is not correct. Just as tape of Turing Machine is infinite, a human brain (which has finite memory size) also can use infinite memory by writing down information in potentially infinite number of pieces of paper. Just like what you do for long multiplications, you do not keep all the intermediate numbers calculated in memory but write down on the paper.
> 1 votes

---
Tags: computer-architecture
---


title: Variation on Bellman-Ford Algorithms?

text:
# Question
Title: Variation on Bellman-Ford Algorithms?
We have a Directed Graph with 100 vertexes. v1 --\> v2 --\> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this algorithm in each step check all edges in arbitrary order. if in each step the shortest distance v1 to all others vertexes is not changed, this algorithm halt. the number of steps is related to checking order of edges. what is the minimum and maximum of steps in this problem?

Solution: 2 and 100.

How this solution will be achieved?

# Answer
Since we are checking edges in different order each time, the time taken will depend on the order of the edges being checked in Bellman-Ford algorithm.

We will get the final result in 2 steps if our order is $v\_1v\_2, v\_2v\_3, v\_3v\_4, ... v\_{99}v\_{100}$.

However we will get the final result in 100 steps if our order is $v\_{99}v\_{100}, v\_{98}v\_{99}, ..., v\_3v\_2, v\_2v\_1$. We can prove that this is worst possible by noting that in Bellman-Ford algorithm with positive weights, in every iteration at least one shortest distance is calculated correctly. So in first iteration we will only determine the shortest distance to $v\_2$, others will remain $\infty$, in second iteration we will determine the shortest distance to $v\_2$ and $v\_3$ while others still remain $\infty$, and so on so forth.
> 4 votes

---
Tags: algorithms, graphs, data-structures, trees, shortest-path
---


# Question
Title: What are the reasons to learn different algorithms / data structures serving the same purpose?
I have been wondering about this question since I was an undergraduate student. It is a general question but I will elaborate with examples below.

I have seen a lot of algorithms - for example, for maximum flow problems, I know around 3 algorithms which can solve the problem: Ford-Fulkerson, Edmonds-Karp & Dinic, with Dinic having the best complexity.

For data structures - for example, heaps - there are binary heaps, binomial heaps & Fibonacci heaps, with Fibonacci heap having the best overall complexity.

What keeps me confusing is: are there any reasons why we need to know them all? Why not just learn and get familiar with the best complexity one?

I know it is the best if we know them all, I just want to know are there any "more valid" reasons, like some problems / algorithms can only be solved by using **A** but not **B**, etc.

# Answer
There's a textbook waiting to be written at some point, with the working title *Data Structures, Algorithms, and Tradeoffs*. Almost every algorithm or data structure which you're likely to learn at the undergraduate level has some feature which makes it better for some applications than others.

Let's take sorting as an example, since everyone is familiar with the standard sort algorithms.

First off, complexity isn't the only concern. In practice, constant factors matter, which is why (say) quick sort tends to be used more than heap sort even though quick sort has terrible worst-case complexity.

Secondly, there's always the chance that you find yourself in a situation where you're programming under strange constraints. I once had to do quantile extraction from a modest-sized (1000 or so) collection of samples as fast as possible, but it was on a small microcontroller which had very little spare read-write memory, so that ruled out most $O(n \log n)$ sort algorithms. Shell sort was the best tradeoff, since it was sub-quadratic and didn't require additional memory.

In other cases, ideas from an algorithm or data structure might be applicable to a special-purpose problem. Bubble sort seems to be always slower than insertion sort on real hardware, but the idea of performing a bubble pass is sometimes exactly what you need.

Consider, for example, some kind of 3D visualisation or video game on a modern video card, where you'd like to draw objects in order from closest-to-the-camera to furthest-from-the-camera for performance reasons, but if you don't get the order exact, the hardware will take care of it. If you're moving around the 3D environment, the relative order of objects won't change very much between frames, so performing one bubble pass every frame might be a reasonable tradeoff. (The Source engine by Valve does this for particle effects.)

There's persistence, concurrency, cache locality, scalability onto a cluster/cloud, and a host of other possible reasons why one data structure or algorithm may be more appropriate than another even given the same computational complexity for the operations that you care about.

Having said that, that doesn't mean that you should memorise a bunch of algorithms and data structures just in case. Most of the battle is realising that there is a tradeoff to be exploited in the first place, and knowing where to look if you think there might be something appropriate.
> 129 votes

# Answer
Aside from the fact that there are myriads of cost measures (running time, memory usage, cache misses, branch mispredictions, implementation complexity, feasibility of verification...) on myriads of machine models (TM, RAM, PRAM,...), average-vs-worst-case as well as amortization considerations to weigh against each other, there are often also **functional differences** beyond the scope of the basic textbook specification.

Some examples:

* Mergesort is stable where Quicksort is not.
* Binary search trees give you in-order iteration, hashtables do not.
* Bellman-Ford can deal with negative edge weights, Dijkstra can not.

There are also **didactic considerations** to make:

* How easy is it to understand a more involved solution before simpler ones? (AVL trees (and their analysis) without BSTs; Dinic without Ford-Fulkerson; ...)
* Do you see the same principles and patterns when you are exposed to only one solution per problem compared to being exposed to many solutions?
* Does exposition to only one solution per problem provide enough training (towards mastery)?
* Should you know the breadth of which solutions have been found (so as to prevent you from reinventing the wheel over and over¹)?
* When exposed to only one solution per problem, will you understand other solutions you find in the wild (say, in a real-world programming library)?

---

1. This is something we see a *lot* from programmer types who do not have a rich CS toolbox at their disposal.
> 52 votes

# Answer
In the *real world*, at some point you are likely to be working on software that has been written by a team of other people. Some of this software will have been written before you were born!

So as to understand the algorithms / data structures that are used, it is very helpful to know a large number of algorithms / data structures, including options that are no longer consider “state of the art”.

You will also have to work on algorithms that are not standard and are just used in the application you are working on. When you have to improve these algorithms, you will find that your brain has been filled with useful methods to improve algorithms, as you have studied how other people have improved algorithms.

This is what sets somebody who has studied computer science apart from someone that has just learned how to program. In most jobs I have worked in, there has been time when having studied computer science I could solve a problem that a “learned from books” programmer could not, **but 95% of the time I found that having studied computer science gave me no advantage over other experienced programmers**.
> 7 votes

# Answer
Many people have rightly mentioned that often there's no one best algorithm - it depends on the situation.

There's also the possibility that one day you'll come across an unfamiliar situation. The more algorithms you know, the more chance that you'll know one that's *nearly* a solution that you can use as a base.
> 5 votes

# Answer
A lot of great answers, just something I think is missing, though Raphael's answer somewhat mentions this.

Ease of implementation is also something to take into consideration.
That's usually not an issue with sort algorithms, because most platforms/languages already have one implemented (and often better than what you could do), but more unusual algorithms might not be available.
Depending on your problem, you might not need the absolute best algorithm if the implementation time is 1 day versus 2 weeks.
> 2 votes

---
Tags: algorithms, data-structures, education, didactics
---


# Question
Title: Compare regex in programming languages with regular expression from automata/formal language?
I'm trying to reconcile the differences/similarities between regular expression from formal language theory and automata, and the "regex" offered by programming languages.

These two differ not just in "syntax" (the union `+` in regular expressions means `|` in regex, and there's no such meta-character as `.` in regular expressions, etc.), but also in "semantics", e.g. the regular expression `(a+b)*c` describes the regular language, L=`{a,b}*{c}`, which the string `abcd` is not a member of, but the equivalent regex `(a|b)*c` would actually find a "match" in the string `abcd` (unless I do `(a|b)*c$`). Not to mention that "regex" can describe some non-regular languages as well.

Is there a good resource/summary that compares regular expression with "regex"?

# Answer
In programming, "regular expressions" are used for *searching* (if a match happens in the string), not for simple *accepting*. I.e., it is as if what is written is `.*your-re-here.*`.

It is often of interest to know not only if it matched, but exactly where. And so the above isn't all the story, most RE machines also look for the *longest* match. For simplicity, many RE libraries don't handle alternation (e.g. `ed(1)` in Unix of yore didn't), as characters, character classes, star applied to the last character, and anchors (beginning/end of line) were enough to handle 90% or more of the "text editing" requirements. And that can be written in simple, short code.

Furthermore, depending on the exact machinery used, it is more or less easy to extend the "regular expressions" with non-regular constructs, like "match what matched between parenteses before", like `([a-z]*) \1` to mean "the same word twice, separated by a space". Such constructs are handled e.g. in `vi(1)`, as tasks like the mentioned are useful to catch typos (a common error is to to write the same word twice).
> 5 votes

# Answer
Regular expressions in programming languages provide many short cuts. Standard regular expressions only have only the following operators: $E+F,EF, E^\*$ and $(E)$.

For example, say, POSIX regeular expression $\[a-z\]$. If we write this in standard way it will be $a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+w+x+y+z$. So $\[a-z\]$ is just a shortcut. And, say POSIX regular expression $\[$^$abc\]$ which is anything but $a$ or $b$ or $c$.

Apart from these shortcuts, there is no other difference. There is just a difference in syntax, but no semantic difference really.
> 1 votes

---
Tags: reference-request, programming-languages, regular-expressions
---


# Question
Title: What is the difference between a function and a procedure
In general, what is the difference between a function and a procedure when talking about programming languages?

# Answer
This is rather old distincion (from pascal - which is the most recognisable for this - see vonbrand's answer).
Function returns value, procedure does not.
This is only naming convention, the more common is just calling the both function, and if needed say that one does not return value.
Some programming languages always return value (like the last statement is sent) or get returning cell on stack and does not use it.
Other languages explicitly return empty value, so still you can assign it to variable, so there is no point of this distinction.
> 4 votes

# Answer
This dates at least from FORTRAN (which had FUNCTIONs, returning values, and PROCEDUREs, called for their side effects). Later languages (like Pascal and descendants) kept the distinction. Pascal is probably the best known language with the distinction.

The "just call both function" common today comes from ubiquitous C, which originally (K&R, as described in Kernighan and Ritchie's "The C Programming Language", first edition) had just functions (returning `ìnt` by default). You could (and still can) just ignore the function's return value (really, the result of any expression), and you could just fall through the end (and return gibberish) in a function, giving the functionality of procedures without extra syntax.

Today's more strict C (and C++) still have only functions, but a function can return `void` (i.e., nothing), making it a procedure. In today's C, in a function returning a value a `return` has to give a value to return, and just falling off the end of the function isn't valid. If the function returns `void`, any `return` has to be bare (no value to return) and falling off the end (no `return`, for example) is legal.
> 4 votes

---
Tags: programming-languages
---


title: Do Scheme operators have associativity?

text:
# Question
Title: Do Scheme operators have associativity?
Do operators in the Scheme programming language have associativity. For example, the code `(- 5 2 1)` evaluates to 2, but it could evaluate to 4 if it was evaluated right-associative. However, it is unambiguous if you were to write the expression as `(- (- 5 2) 1)`. The first example, however, leads me to believe that Scheme is left-associative in the case that you do not group all operations into only two arguments at a time.

# Answer
Scheme computes `(- a b c)` as `a - b - c`, i.e., strictly left to right.

It really makes no sense to talk about associativity in Scheme, which applies to how an otherwise ambiguous expression like `a # b # c` is to be interpreted, either as `(a # b) # c` or `a # (b # c)` (or even forbid such combinations). In Scheme no such ambiguity is possible, everything is prefix. And the function called is responsible to decide what to do with it's arguments, even if the number of arguments is variable (as in this case). It is probably more natural to work left-to-right.
> 4 votes

---
Tags: programming-languages
---


# Question
Title: Hyper parameter and complexity in $K$ nearest neighbors
I'm wondering if choosing K in the Nearest Neighbors Classifier can be stated as model selection, since the computational complexity is getting higher, the higher K is.

My understanding is: since the complexity increases it means, that K is a hyper parameter.

Am I getting the concept of hyper parameters correctly?

# Answer
First let's define what a hyper parameter is. In the context of statistical learning, a hyper parameter is a fixed constant that describes the prior distribution for a model's parameters. For example, if $X \sim \text{Binomial}(n,p)$ and $p \sim \text{Beta}(\alpha, \beta)$, then $\alpha, \beta$ would be hyper parameters where $n, p$ would be the "parameters" (I use quotes because $p$ is a random variable now).

$k$NN is non-parametric in the sense that you aren't explicitly modeling your data as a function of underlying parameters. $k$ only describes how many neighbors to "learn" from. As $k$ increases the *computational* complexity can increase; however, it doesn't explicitly control the complexity of the *model*. An example where model size $k$ acts as a hyper parameter is linear regression. Imagine trying to determine a-priori which $k$ of the $N$ features you would like to select for inclusion in the model.

Given this, I would not say that $k$ describes $k$NN model complexity in the sense that typical Bayesian model selection is and therefore should not be viewed as a hyperparameter.
> 1 votes

---
Tags: algorithms, complexity-theory, machine-learning
---