# Question
Title: What is the name for closure-type functions that use the call-site environment?
Closures are functions that borrow the environment in which they are declared and can use and modify its variables at any times indipendently from where they're called, like in this example:

```
function createclosure(x)
    return function() --Anonymous closure
        print(x) --The variable x is caught and can be used anywhere
    end
end

myclosure = createclosure(123)

myclosure() --prints "123"

```

What I am looking for is quite the opposite: functions that borrow the environment in which they are *called* and can use and modify its variables:

```
function anti_closure()
    x = x + 10 --x is borrowed from the environment in which the function is called
    print(x)
end

function environment(x)
    print(x)
    anti_closure()
    x = x - 5
    print(x)
end

environment(23) --prints "23", "33" (from the anticlosure) and then "28" (because x was permanently modified in the anticlosure)

```

Is there a name for these type of functions? Are there languages that implement them? If not, *why*?

# Answer
> 5 votes
You are talking about static vs. dynamic scoping of variables. Most langauges today have static scoping, but famously the early LISP had dynamic scoping.

Scoping is a general feature of a programming language and is not something that a closure does (although I suppose one could organize things so that it does). In any case, look up "dynamic" and "static" scoping.

# Answer
> 1 votes
You are interested in Dynamic scoping. The pure dynamic scoping gives confusion about execution so opposite to static scope you cannot easily read code and be sure how it will execute or in case of languages that support anonymous functions and first-class citizens it is non-trivial task.
With static scope you have to bind function to environment it is called in by declaring it there, binding or using *call* for function.
In dynamic scope the *anti\_closure* should work, but some mechanism were implemented to avoid it in general. Some languages require to mark scope (like perl with *local*) or explicitly define dynamic scoping like Clojure.

Generally this scheme is avoided due to shadowing, saving context of environment and making every variable global (in fact Clojure does that, every variable is global in this case).

Static scope gives the ability to resolve connection between variables at compile time, in dynamic one this gives late binding or a form of function stubs, delegates - which cannot be optimized fully during compile time.

If you substitute *anti\_closure* with global function taking parameter by reference then such helper function works in static scope, without downsides of copying environment.

Why this is avoided? If you are able to introduce new function at any place that is *anti\_closure* then you must have access to tree of environments of all declared variables so it is equivalent to static scope with all variables being global, but still the second one is easier to compile.

---
Tags: terminology, programming-languages
---


# Question
Title: Is the runtime for the general number sieve given in base 10, e or 2?
When the runtime of the GNFS is given as e^(64/9\*b(log b)^2)^1/3, what base is the log? I'm assuming its e, but other options would obviously be 10 and 2.

# Answer
Wikipedia gives the running time as $$ \approx \exp \sqrt\[3\]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3}, $$ where $n$ is the integer being factored. Here $\ln n$ is the natural logarithm (logarithm to base $e$).
> 3 votes

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


title: "taintedness" vs. "taintness"

text:
# Question
Title: "taintedness" vs. "taintness"
In the context of information flow, when you talk about the property of variables being tainted, do you speak about "taintness" or "taintedness"? Both occur online, both sound weird to me.

An example from http://www-verimag.imag.fr/~potet/PUBLI/mdv10.pdf:

> To achieve that, we propose to perform a taint dependency analysis whose objective will be twofold: 1) to compute the variable taintness at each program location; 2) to extract from the program source the whole dependency chains between each vulnerable statement and the corresponding inputs leading to this vulnerability.

# Answer
> 1 votes
Which should you use? Neither. Personally, I think the words "taintness" and "taintedness" both look awkward. I would recommend rephrasing the sentence to avoid using either of those words. Instead, you might try to use something like "whether the variable is tainted". Or, if you desperately need a noun phrase and can't make the prior suggestion work, try something like "taint status".

For example, I might rewrite the quoted sentence as something like:

> To achieve that, we propose to perform a taint dependency analysis whose objective will be twofold: 1) to compute *which variables are tainted* at each program location; 2) to extract from the program source the whole dependency chains between each vulnerable statement and the corresponding inputs leading to this vulnerability.

(I added italics to highlight the part that I changed.)

# Answer
> 0 votes
* Taintness is how much something taints
* Taintedness is how much something is tainted

I would use taintedness. The variables are the recipient, not the cause, of the tainting/poisoning.

---
Tags: terminology, software-verification, static-analysis
---


# Question
Title: Hash for verifying both compressed and uncompressed data?
Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart?

Trivially one could just use a hash function twice (once on the uncompressed version and again on the compressed version) and concatenate the outputs, or use a hash function that internally does that, but I wonder if it's possible otherwise.

For example, imagine we've got these functions:

```
Hash getHash(byte[] data);
byte[] compress(byte[] data);
byte[] decompress(byte[] data);
bool verify(byte[] data, Hash hash);

```

...then I'm looking for these properties for a nontrivial byte array `D` (that is uncompressed):

* `verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true`
* `D == decompress(compress(D))` for all `D`, i.e. lossless compression
* `verify(E, getHash(D)) == false` "most of the time" when `E != D`, i.e. collision "resistant" hashing

This could be useful when verifying persisted compressed data: you could verify the correctness of the compression algorithm and of the uncompressed data both at the same time without having to decompress it or store multiple hashes.

I'm not sure where to start looking for this. I think what I'm describing is some kind of homomorphism but apparently I need to level up my search skills. It seems like a Difficult Problem™; for example, the Deflate algorithm outputs data structures like a Huffman tree/table, and the mathematical relationships of serialized data structures being run through hash functions aren't immediately obvious to this OP.

# Answer
> 2 votes
In most situations you probably don't want to have `D` and `compress(D)` to have the same hash value, as that leads to hash collisions. Usually hash functions are designed to *avoid* hash collisions -- and this is a good thing. For instance, in cryptographic contexts, any hash scheme that has the properties you ask for would automatically be considered cryptographically insecure.

Therefore, trying to design a hash function with this property is probably a bad idea. Instead, you should probably use the alternative solution: when you verify a hash value, hash both the data `D` and the compressed version `compress(D)` and see if either of those hash digests match the expected value. That's probably a much better solution in practice.

---

If you absolutely *must* achieve this by artificially introducing collisions into your hash, here is a way you can do it. Disclaimer: *This is totally theoretical; it is not useful in practice.*

Define the `verify` procedure as follows:

```
Verify(D, Y):
1. If Hash(D)==Y or Hash(Compress(D))==Y or Hash(Uncompress(D))==Y, return true; otherwise, return false.

```

Yes, this is totally trivial.

No, I don't think you'll find anything that is faster than this and that also satisfies the properties to be a good hash function. Hash functions are specifically designed to *avoid* having any mathematical structure, while at the same time being very fast. Mathematical structure is considered a *weakness* in a hash function. In contrast, you are asking for a hash function with some structure. Inserting such artificial structure into the hash function *might* be possible, but the natural ways of doing it probably will either introduce lots of bias into the hash function (e.g., lots of collisions) or slow it down a lot.

To put it another way, right now hash functions are optimized to meet two criteria:

* Be fast.
* Be "random-looking" (few collisions, unbiased, etc).

You are proposing to look for a hash function that meets *three* criteria:

* Be fast.
* Be "random-looking" (few collisions, unbiased, etc).
* Also, satisfy the additional properties you requested that `verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true`.

Obviously, it's harder to meet *three* criteria than to meet *two*. If you want to meet three criteria, something will have to give: and in your situation, that means the resulting hash function will either be *slower* or *less "random-looking"* than standard hash functions (probably significantly so).

So, I don't expect there's any better solution for what you want. Instead, just do the natural solution you mention of hashing twice.

---
Tags: hash, data-compression
---


title: Need explanation of Heap's Algorithm

text:
# Question
Title: Need explanation of Heap's Algorithm
Okay I am trying to understand the Heap's Algorithm from the original research paper published by B.R Heap.

The most confusing aspect I found that while Heap says that the example described on the first page takes **N=12** ie. example **with 12 objects to provide a permutations for them.**

But yet he says that the 12 objects are the letters A to Q. Now unless I have forgotten my counting totally, ***A to Q is 17 objects not 12.*** So am I missing something obvious ?

Secondly, can someone please explain the Table 1 given in the bottom of the first page ?

Thanks.

# Answer
> 2 votes
Pay no attention to the letter $Q$. $Q$ is just a "short-hand" for "the $N$th letter". Think of $Q$ as a kind of variable, rather than a letter itself.

In other words, ignore the Q bit, and keep reading. If you like, think of it as A, B, C, ..., L, and pretend that was just a typo. Keep reading.

Let me give you some advice about reading papers. If you find some detail you don't understand, often you can keep reading and see if you can still understand what is going on. Sometimes there will be a typo in the paper that is small or inconsequential. Sometimes it's a detail but if you keep reading you can still understand much of the rest of the paper. Sometimes the paper is actually correct and once you absorb the rest of the ideas in the paper, when you go back and re-read the paper you'll realize what the authors actually meant. (Of course, occasionally you'll discover a serious fundamental flaw in the paper. But don't jump to assuming that's the case; that should be your last hypothesis, rather than your first hypothesis.)

If you still can't understand the paper, try to find other papers that cover related topics -- e.g., that it cite or that cite it -- and build up your understanding of the area. Then, come back and read the paper again.

Often, if you follow these strategies, you'll be able to work out what is going on. These are useful skills -- they will make you more self-reliant and more effective at getting value out of the research literature.

---
Tags: algorithms, permutations
---


title: classifier accuracy

text:
# Question
Title: classifier accuracy
I’m developing a mutual information based classifier, the output of the classifier is {{0,4,5,6},{1,2,3},{7},{8},{9}} and the correct decision output is {{0,1,2,4,5,6,9},{3},{7,8}}. How to compute the accuracy of this classifier according to the concept of True positive, true negative, false positive and false negative found on https://en.wikipedia.org/wiki/Evaluation\_of\_binary\_classifiers

Thanks

# Answer
> 0 votes
The basic idea would be to **take every pair {(0,1), (0, 2), (0, 3), ... ,(8, 9)}**. **For each one, ask whether it is correctly classified as in the same group or not.**

In your example:

If you take the pair (0, 1), this would be a false negative because it is incorrectly classified in different groups. Then if you move on to the pair (0, 4), this would be a true positive because they are correctly classified in the same group. Then later when you take the pair (1, 3), this would be a false positive because they are incorrectly classified int he same group. If you take the pair (7, 9), this would be a true negative because they are correctly classified into different groups.

You can classify each pair as either being a TP, TN, FP, or FN then apply the formulas you found on the wikipedia page!

---
Tags: algorithms, machine-learning, classification
---


# Question
Title: Why does using unary in subset sum problem result polynomial time complexity?
From my understanding, the complexity of the algorithm is `O(number of inputs * number of bits for input)`. The number of bits in binary notation is obviously less than the number of bits in unary notation. Then why is it that for binary, complexity is exponential but for unary, it is polynomial?

EDIT: I think the binary time is still faster. It just appears to be faster in case of unary due to notations. If x bits are used, then n has to be less than equal to x. So it becomes polynomial. while in case of binary, it's obviously O(n\*2^number of bits). There might be something wrong in my explanation. Feel free add an answer to correct it.

# Answer
> 12 votes
Consider the following (silly) function `cow`, which accepts a number $n$:

```
def cow(n):
   k = 0
   for i in range(0, n):
       k =  k + 1
   return k

```

The loop takes $n$ steps, so the time needed for the function to complete on input $n$ is $\Theta(n)$.

*However*, the size of the input is *not* $n$ but rather $\log\_2 n$ because computers represent numbers in binary. That is, if $b = \log\_2 n$ is the size of the input, then the complexity is $\Theta(2^b)$ (because $n = 2^{\log\_2 n}$), which is an exponential algorithm *when measured in size of the input $b$*. If we measure in terms of $n$ then it is a linear algorithm.

If we represented numbers in unary then we would have $b = n$, i.e., it would take $n$ "units" (not "bits" anymore) to represent $n$. In this case the complexity would be $\Theta(b)$, a linear algorithm.

---
Tags: algorithms, complexity-theory, algorithm-analysis, runtime-analysis
---


# Question
Title: What does the exact $\mu$-recursive program for minimization look like?
The minimization of a given primitive recursive function $f$ is computed by the following expression:

$ \newcommand{\pr}\[2\]{\text{pr}^{#1}\_{#2}} \newcommand{\gpr}{\text{Pr}} \newcommand{\sig}{\text{sgn}} \text{Mn}\[f\] = \gpr\[g, h\] \circ (\pr{1}{1}, \pr{1}{1}) $

$g = \sig \circ f \circ (\pr{1}{1}, c^1\_0)$

$h = \text{Cond}\[\text{t}\_\leqslant \circ (\pr{3}{3}, \pr{3}{2}), \pr{3}{3}, \text{Cond}\[ \text{add} \circ (\text{t}\_= \circ (\pr{3}{3}, \text{ suc} \circ \pr{3}{2}), f \circ (\pr{3}{1}, \text{suc} \circ \pr{3}{2})), \text{suc} \circ \pr{3}{2}, \text{suc} \circ \text{suc} \circ \pr{3}{2} \]\]$

The first call to the function ($\text{Mn}\[f\] \circ (\pr{1}{1}, \pr{1}{1}) (n, k)$) will return at most k+1 and terminate for all inputs, if $f$ is total recursive.

A $\mu$-recursive search would not necessarily terminate, if no $z \leqslant k$ such that $f(n, z) = 0$. But I fail to see how that $\mu$-recursive expression would look in contrast to the above one, meaning $-$ what would the part of the expression look like, that makes the function not terminate.

# Answer
I think you're confused about definitions. What you represented above is *bounded* minimization where we look for the least number $z$ *below* a given bound $k$ such that $f(n,z) = 0$. Such bounded minimization can be defined without any extra gadgets, using only primitive recursion.

The so-called $\mu$ operation performs *unbounded* search. It is not something we can define using primitive recursion. It is a *new* primitive operation which we add to primitive recursive functions to obtain recursive functions.

That is, if $f$ is a function of several arguments then $\mu(f)$ is a *partial* function which satisfies $$ \mu(f)(\vec{n}) = k \iff f(\vec{n},k) = 0 \land \forall j \< k, f(n,k) \neq 0. $$ If there is no such $k$ then $\mu(f)(\vec{n})$ is undefined.

Every primitive recursive function is total. However, $\mu$ allows us to create non-total functions, for instance $\mu(f)(1)$, where $f(n,k) = 1$, is everywhere undefined. Therefore, $\mu$ is not something that can be defined using primitive recursion.

There are various mechanisms that exceed the power of primitive recursion which allow us to define $\mu$. One such is a *general recursion*, and another is a *fixed-point operator*.
> 7 votes

---
Tags: computability, primitive-recursion, mu-recursion
---


title: Meaning of `<==>` in documentation?

text:
# Question
Title: Meaning of `<==>` in documentation?
Title says it all. I just need to confirm that... `X.__add__(y) <==> x+y` ...doesn't mean anything more than just 'same as'

The problem is Google returns zero results when you search for `<==>`

# Answer
> 1 votes
Yes, it means "logically equivalent to".

---
Tags: notation
---


# Question
Title: Is there any precedence for symbols for constructing parse trees?
I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees.

For example, the sentence: `p ∧ q → r`, would  take precedence over  in becoming the root of the parse tree or vice versa?
Or is there no precedence meaning,  or  could be used the root?

# Answer
Operator precendences have to be specified, either in the grammar or using other means. There is no inherent precendence to rules, but you can fix one arbitrarily.
> 0 votes

---
Tags: parsers, propositional-logic
---


title: Sequential execution in $\pi$-calculus

text:
# Question
Title: Sequential execution in $\pi$-calculus
I am relatively new to $\pi$-Caculus and have a doubt wrt sequential execution in In $\pi$-Calculus .

Does passing of common names over common channels shared between two Agents, represent a sequential execution ? so is the below reduction semantics correct if I have to represent a sequential execution between Agent A,B and C where A and B share common channel x and share data c' and similarly B and C share channel y?

\begin{equation} \begin{gathered} \label{eq23} \frac{A \xrightarrow{\overline{x}(c)} A' \quad B \xrightarrow{{x}(c').\overline{y}(c'')} B' \quad C \xrightarrow{y(c''')}C' \ } {A|B|C \xrightarrow{\tau} A'| B'\left\\{c/c' \right\\}|C'\left\\{c''/c''' \right\\}} \end{gathered} \end{equation}

# Answer
> 4 votes
$\pi$-calculus can represent all sequential behaviour. The key rule responsible for sequential behaviour is that for input:

$$ \overline{x}y \ |\ x(v).P \quad \rightarrow\quad P\\{y/v\\} $$

(and its replicated variant). The process $P$ becomes active only *after* the interaction at $x$ has taken place. You can generalise this: if $X$ and $Y$ are two arbitrary processes such that $Y$ should execute only *after* $X$ has terminated, you can use something like:

$$ (\nu a)(X' \ |\ a().Y) $$

Here $a$ is a fresh name, i.e. does not occur in $X$ and $Y$. The process $X'$ is exactly like $X$, except it outputs an empty message on $a$ upon termination of $X$. Defining $X'$ depends on the precise nature of $X$ since $X$ may itself have multiple threads. If $X$ is sequential, then it's easy to define $X'$, just replace $0$ by $\overline{a}\langle\rangle$. The whole purpose of the handshake on $a$ is to exchange one bit of information, namely that $X'$ has terminated.

The answer to your question "*Does passing of common names over common channels shared between two Agents, represent a sequential execution?*" is positive in a narrow sense that the continuation of the input side will only start after this interaction. However the sender might do other things in parallel. BTW, the rule you give isn't quite right. You need two $\tau$-actions because you are doing two interactions. Moreover, it looks like you are doing a *bound* output of $c$ abd $c''$, so the resulting processes should have an outermost $(\nu c'')(\nu c)$, or something like that.

You can also define subcalculi of $\pi$-calculus where all computation is sequential: for example by considering only processes that have at most one active output (heriditarily). An output is active, it it's not under an input. This property being heriditary means simply that it's stable under reduction.

I close with a quote of R. Milner's from his "*Elements of interaction*":

> I make a disclaimer. I reject the idea that there can be a unique conceptual model, or one preferred formalism, for all aspects of something as large as concurrent computation, which is in a sense the whole of our subject -- containing sequential computation as a well-behaved special area.

---
Tags: computation-models, pi-calculus
---


# Question
Title: MTBF calculation with 2 units connected in series
Me and a friend have a opinion difference regarding a question that got asked in a previous IT test.

The short version:

2 units, `n` and `m` are connected in series but operate as one system. `n` has a MTBF of 200, `m` of 300. What is the MTBF of the entire system?

possible solutions:

* 200
* 250
* 300
* 500

I am convinced (as is the guy who made the question) that the correct answer is 250.

My friend is convinced it is 120 and the question contains a mistake.

How were I to calculate this?

# Answer
If the MTBF of a device is $N$, then the probability that the device will fail in 1 time unit is $1/N$. With two devices in series with failure probabilities $p\_1$ and $p\_2$, the system will fail in one time unit if device 1 fails or if device 1 doesn't fail and device 2 fails. The probability of that happening is $$ p\_1 + (1-p\_1)p\_2=p\_1+p\_2-p\_1p\_2 $$ In your problem, $p\_1=1/200, p\_2=1/300$ so the probability that the system will fail in one time unit is $$ (1/200)+(1/300)-(1/200)(1/300)=499/60000\approx0.00832 $$ and so the MTBF of the whole system is $1/0.00832\approx120.24$. Your friend is right: none of the proposed solutions are correct.
> 1 votes

---
Tags: logic
---


title: Does my grammar contradict LL ⊆ LR(1)?

text:
# Question
Title: Does my grammar contradict LL ⊆ LR(1)?
This answer claims that $ LL \subseteq LR \left( 1 \right )$ where $LL = \bigcup\_k LL(k)$.

But is this true? Is this grammar a valid counterexample?

$ S \rightarrow a | Aaa $, $ A \rightarrow \varepsilon $

It's easy to show that this grammar is not $LR \left( 1 \right )$, but I think that it is in $LL(2)$ - the longest string that can be derived is two letters so a lookahead of two tokens should be sufficient.

# Answer
> 3 votes
Confusingly, the terms $LL$ and $LR$ are overloaded. There are two related but fundamentally different classes of objects that we'd call $LL$ or $LR$:

* The sets of all *grammars* that are $LL(k)$ or $LR(k)$ for some choice of $k$. Let's call these sets $LL\_{CFG}$ and $LR\_{CFG}$.
* The sets of all *languages* that have an $LL(k)$ or $LR(k)$ grammar for some choice of $k$. Let's call these sets $LL\_{LANG}$ and $LR\_{LANG}$.

The example you've given is a grammar that is $LL(2)$ (I believe) but not $LR(1)$. This shows that $LL\_{CFG} \not\subseteq LR(1)\_{CFG}$. However, there is a different grammar that you could pick for the same language that is $LR(1)$, which follows because $LL\_{LANG} \subseteq LR(1)\_{LANG}$. This happens because $LR(1)\_{LANG}$ is precisely the set of all deterministic context-free languages and all $LL$ languages are deterministic.

---
Tags: formal-languages, formal-grammars, parsers
---


# Question
Title: Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets
I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the math, specifically the optimization part (for selecting weights), I ran into a problem: I couldn’t understand the Broyden–Fletcher–Goldfarb–Shanno algorithm. I understand that it (basically) uses newton's method, expect that it finds the zeroes of the derivative of the original function (to find the local minima of the original function).

However I was having trouble following the notation and math that is written on Wikipedia about it:

First of, I do understand that Bk is a Hessian matrix that holds the partial second derivatives and f(x) is the original function that we are finding the local minima of. Moving on to step 1, I do not understand why the search direction needs to be solved. (Is it because we need to figure out whether the zero of the derivative is a local maximum or minimum of f(x) aka perform the first derivative test). In step 2, I do not understand why line search needs to be performed. In step 3, I do not understand what the product of ak and pk means. In step four, (correct me if I am wrong), yk equals the change in y or f(x). Finally, I know step 5 is trying to approximate Bk+1, which is what newton's method does, but I do not understand why its trying to estimate another Hessian matrix, shouldn't it be estimating a point? Or is it estimating a matrix because the algorithm is supposed to work with a multidimensional space, but then how does the partial second derivative matrix lead to finding the local minima of the original function? Also, what does the right side of the equation mean with all the vector/matrix multiplication and division. (I know this is a quasi-netown method but do not really understand it).

I tried to search the internet for my answers, but I couldn't really find anything. I am only in high school and don't have anyone who can explain me this math. So I really appreciate your help. Thank you so much in advance.

# Answer
The purpose of the "search direction" is that we want to move closer to a minimum of $f(x)$. The gradient tells us the direction of steepest descent (as in gradient descent).

The reason we do the line search is to figure out *how far* to travel in that direction. The gradient tells us the direction; but it doesn't tell us how far to go in that direction.

The product $\alpha\_k \mathbf{p}\_k$ is an ordinary product of a scalar and a vector; i.e., component-wise product. You probably need to study a bit of linear algebra and multivariate calculus to get familiar with this sort of thing -- that's a vitally important foundation.

Step 5 is the heart of BFGS. A full Newton method would calculate the Hessian (matrix of second partial derivatives) at each point; i.e., it would re-calculate the Hessian in step 5. BFGS doesn't re-calculate it from scratch, as re-calculating it is expensive. Instead, it tries to make an estimate/guess of how the Hessian has changed. That's what step 5 is doing. This estimate is less accurate than simply recomputing the full Hessian matrix, but it's faster.

You're not going to be able to understand what's going on in BFGS from Wikipedia. Wikipedia's description is not very good, and there is no explanation of where the method came from. Look for a better, more detailed explanation that explains where these steps came from, the intuition of what's going on, and how these particular formulas were derived. Wikipedia is a great resource, but it's not a very good source for learning BFGS.
> 3 votes

---
Tags: algorithms, optimization, artificial-intelligence, neural-networks, numerical-algorithms
---


# Question
Title: Count elements in the real world in constant time by weighing them
I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out the total weight so in the real world you can count n elements O(1) just by putting all the elements on a scale and dividing by the weight of one elements.

Is my reasoning correct that physically it is possible to speed up a calculation by this trick, or am I mistaken?

# Answer
> 3 votes
Weighing elements works faster than counting them, because the scale is a fully parallel computing device. It sums the weighs of all elements in constant time. Of course you need an infinitely large scale if you want to talk about asymptotic runtimes. In practice your scale can only weigh a constant number of items at once, so your speedup is only a constant factor.

A related algorithm is Spaghetti sort.

# Answer
> 1 votes
You make an accurate but rather basic observation: complexities depend on the model of computation you assume. In your informally described model "the real world", some things may indeed work differently than they do for TMs. Be wary of making wrong assumptions, though.

Here, you change the problem. You move from "counting" to "computing total weight". These are only the same if all items have the same weight.

Keep in mind that you have to put the items on the scale first. Assuming you can only put constantly many things on the scale at a time, this makes your method take linear time as well. And that's assuming a scale with unlimited capacity, which you probably don't have. Simply counting items where they lie is probably faster and more energy efficient.

# Answer
> 1 votes
You're mistaken: it takes more than constant time to divide the total mass by the weight of a single object to compute the count.

Physical considerations, such as whether your scales can measure arbitrary weights or whether you can put arbitrary numbers of things on the scales at the same time (as mentioned by adrianN and Raphael) could maybe be swept under the carpet by just defining the computational model to allow that. But assuming that you can divide two arbitrarily long numbers in constant time seems to be a much bigger deal.

---
Tags: time-complexity, computation-models, counting
---


title: Is this language semi-decidable?

text:
# Question
Title: Is this language semi-decidable?
Let $M\_w$ be the DTM encoded by the binary string $w$ and let $$L=\\{w\\#x\\,|\\,\text{all states are reached when running }M\_w\text{ on }x\\}.$$ I've already proved that this language is undecidable (the halting problem can be reduced to this), but is this language semi-decidable? I.e., is there an enumeration of $L$ or a reduction of $L $ to a semi-decidable language?

# Answer
You can start by considering this related problem:

$$L'=\\{w\\#x\\#n\\,|\\,\text{all states are reached when running }M\_w\text{ on }x\text{ within $|n|$ steps}\\}.$$

Argue that $L'$ is decidable. Then, noting that

$$L=\\{w\\#x\\,|\\,\exists n.\ w\\#x\\#n \in L'\\}.$$

should give you an idea about how to proceed.
> 1 votes

---
Tags: turing-machines, decision-problem, semi-decidability
---


# Question
Title: General number field sieve is slower then exhaustive search for 'small' numbers?
In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes. The calculations seem to indicate the GNFS runs *slower* than exhaustive search for smallish n. For example: suppose I want to factor the number 247 (ie 13 * 19).

To do this I can just check all the numbers (exhaustive search) below $$ \sqrt{247} \approx 16$$ to see if they divide 247.

The General number field sieve has a runtime of $$ \approx \exp \sqrt\[3\]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3}, $$

So calculating the GNFS runtime... $$ \approx \exp \sqrt\[3\]{\frac{64}{9}} (\ln 247)^{1/3} (\ln \ln 247)^{2/3}, $$ $$ \approx \exp \sqrt\[3\]{\frac{64}{9}} (5.5)^{1/3} (\ln 5.5)^{2/3}, $$ $$ \approx \exp \sqrt\[3\]{\frac{64}{9}} (5.5)^{1/3} (1.7)^{2/3}, $$ $$ \approx \exp (1.9 * 1.8 * 1.4), $$ $$ \approx \exp (4.87) \approx 120 $$

This is obviously bigger than 16. What am I missing here?

# Answer
First of all, the number 120 that you got is completely meaningless. There is a scaling factor that can only be determined experimentally. Even worse, there are lower order factors which are probably very significant for such small numbers. Finally, the running time you quote is *heuristic* – it's just an educated guess.

You are correct that GNFS is a lot less efficient than trivial methods for small numbers. That's why you don't use it for small numbers. The better asymptotics kick in only for large enough numbers.
> 3 votes

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


# Question
Title: The class of languages that can be certified in a small amount of space
NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time.

I wonder, if we consider the same notion but with space considerations to get a class $X$, Is such a class known to be of any importance? Why?

To be more precise, $L\in X$ iff there exists a TM $M$ s.t.

$\forall x\in \\{0,1\\}^\* (x\in L \iff \exists u \in \\{0,1\\}^{p(n)}$ s.t. $M(x,u)=1$ s.t. $M$ uses space bounded by a polynomial $P$.

Clearly, NP$\subset$ X. Is there any interesting thing that we can know about $X$?

# Answer
(Note that X is not known to differ from NP.)  Yes - X is equal to PSPACE.  In fact, one gets that from just brute force, rather than needing Savitch's theorem.

You might also be interested in NL, which is only known to satisfy
L  $\subseteq$  NL  $\subseteq$  coNLGLOGTIME-uniform SAC1   .

(Note that, to get a certificate characterization of NL, we probably must
"restrict the verifier to have *one-way access* to the certificate".)
> 3 votes

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


# Question
Title: Label coloring to maximize number of "balanced" triangles (NP-hardness)
Define a triangle in undirected graph $G$ is *balanced* if the edge labels in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory).

Problem definition:

Given undirected graph $G=(V, E)$, initial edge label function $f: E \rightarrow \\{+1, 0, -1\\}$ and $k \in \mathbb{Z}^{+}$, find another label coloring function $g: E \rightarrow \\{+1, 0, -1\\}$ that maximizes the number of "balanced triangles" in $G$

s.t.

1. $\forall e \in E \text{ such that } f(e) \neq 0, g(e)=f(e) \text{ holds}$ ($g$ conforms with $f$ for non-zero valued edges).
2. $|\\{e \in E \mid g(e) \neq 0 \text{ and } g(e) \neq f(e)\\}| \le k$ (up to $k$ unlabeled edges can be labeled.)

I am trying to prove the NP-hardness of this problem, failing to find an appropriate problem reduction.

Here is what I have thought:

---

First, the problem can be decomposed using recursion.

We consider assigning label to only one edge, then fix it and solve the sub-problem with updated $f$ and $k-1$ labelings. However, this approach runs in exponential time.

Second, this problem can be seen from the "set cover" perspective.

We can consider each edge as a set containing a subset of all triangles (the universe), triangles can be classified into three types:

1. 1st-order triangle which has only one unknown label edge ($f(e) = 0$)
2. 2nd-order triangle which has two unknown label edges
3. 3rd-oder triangle where all the labels in the triangle are unknown.

A triangle is considered covered if it's 1st-order and the labeled edge makes it balanced.

If we consider some greedy approach by labeling the best edge one by one, then whenever each edge is labeled, the triangle type information will change accordingly.

For example, some 1st-order triangles will no longer be 1st-order while some 2nd-order triangles will become 1st-order because of the newly-labeled edge.

The "chaining" effect actually couples edges together, which makes things more difficult.

# Answer
> 2 votes
Reduce from 2-Lin(2):
Start with a star that has one edge per variable, and let those initial-labels all be 0.
For each equation    xi \+ xj  =  b  ,    create an edge from the outer vertex of xi's edge to the outer vertex of xj's edge, and let that edge's initial-weight be (-1)b.
That will produce the output weighted-graph.  Just let k be the number of variables, so the cardinality constraint doesn't matter.

Triangles whose weights are all forced are forced to be good or bad, so their existence affects approximation quality but not which g's are optimal.  Other triangles use at least one variable-edge, and so exactly 2 variable-edges, since being a variable-edge is equivalent to being incident with the central vertex.  Thus no unintended triangles affect which g's are optimal, so those g's are exactly the g's for which composing with log-1 yields an optimal solution to the input 2-Lin(2) instance.

Your problem is obviously in W\[P\]O, and I have no other clue regarding its parameterized complexity.

---
Tags: complexity-theory, graphs, np-complete, reductions, colorings
---


# Question
Title: Why do we reject turing machines that use space less than the log of the length of the input?
In **Computational complexity: Modern Approach by Arora and Barak**, it's mentioned that

> We will require however that $S(n)\> \log n$ since the work tape has length $n$, and we would like the machine to at least be able to remember the index of the cell of the input tape that is currently reading.

What does that ***exactly*** mean? I don't see the point, what does "*remembering* the index of the cell currently read by the head of the input-tape" mean? Any clarifications?

Note that we does not count the movements of the input-tape into our space considerations so we only count for the work-tape

# Answer
> 6 votes
Consider any program in high-level language that has a loop going over all items:

```
for i from 1 to n
    do something
end for

```

Implementing this loop takes $O(\log n)$ work space, since the variable $i$ takes $O(\log n)$ bits to store. If you're not allowed to use even that much memory, then you have to be very careful when implementing any non-trivial algorithm, if it is possible at all; for instance, any results will be highly dependent on the exact definition of the model of computation.

Arora and Barak don't want to focus on such issues, so they just assume that you are given at least logarithmic space. There are enough interesting things to say without having to worry whether some general reduction can be carried out in sublogarithmic space. (And if you want to study regular languages -- languages that can be recognized with constant space -- you don't need complexity theory.)

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


# Question
Title: Gramatical evolution doesn't result on creating good constants
I'm using Grammatical Evolution for symbolic regression tasks (i.e. searching the space of mathematical expressions to find the model that best fits a given dataset).

I'm evolving solutions according to a user-specified grammar:

```
 (0)
 <expr> ::= <expr> <op> <expr>      (0)
          | <const>                 (1)
          | <var>                   (2)
          | <unop>                  (3)

 (1)
 <op> ::= *     (0)
        | +     (1)
        | -     (2)
        | /     (3)

 (2)
 <const> ::= 0.1            (0)
           | 1.0            (1)
           | 10.0           (2)

 (3)
 <var> ::= x                (0)

 (4)
 <unop> ::= sin             (0)
          | cos             (1)
          | -               (2)

```

The population is a collection of arrays of integers. For example:

```
[0, 1, 2, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

```

is the genotype of the individual `+(x, +(1, +(1, 1))` (function $x + 3$).

The translation is performed using the integers to look up the table which describe the BNF grammar:

```
Step  Sequence  Rule   State
  1      0       0.0   <expr> <op> <expr>
  2      1       1.1   <expr> + <expr>
  3      2       0.2   <var> + <expr>
  4      0       3.0   x + <expr>
  5      0       0.0   x + <expr> <op> <expr>
  6      1       1.1   x + <expr> + <expr>
  7      1       0.1   x + <const> + <expr>
  8      1       0.1   x + 1.0 + <expr>
  9      0       0.1   x + 1.0 + <expr> <op> <expr>
 10      1       1.1   x + 1.0 + <expr> + <expr>
 11      1       0.1   x + 1.0 + <const> + <expr>
 12      1       2.1   x + 1.0 + 1.0 + <expr>
 13      1       0.1   x + 1.0 + 1.0 + <const>
 14      1       2.1   x + 1.0 + 1.0 + 1.0

```

The fitness function is the reciprocal of the sum, taken over the fitness cases, of the absolute error between the evolved and the target function.

My problem is that, while the algorithm finds the general model, it often has trouble finding the right constants.

For example, if the target function is $x^2 + x - 12$, it finds something like:

$$x^2 + x - (10 + \sin(x))$$

or

$$x^2 + x - (1 + 1) \times (10 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1) \times ((10 - (10 / (1 + 1)) - (10 / (1 + 1 + 1 + 1 + 1)))$$

which is correct but requires a great effort to discover the constant.

Are there efficient techniques for generating numerical constants?

# Answer
It sounds like you're saying that your approach is able to effectively find the shape of the expression, but it takes it a lot longer to find the right constants.

One possible approach is to generate an expression of the correct shape using your genetic programming method, then fill in the constants using a different method. I would recommend trying numerical optimization techniques. Replace each constant in your expression with a symbolic value $\alpha$. Each different constant (at each different syntactic position) gets its own symbolic value. Then, use numerical optimization to find the value of the constants.

**Example 1.** For instance, consider your complex expression $x^2 + x - (\text{stuff})$. Replace this with $x^2 + x - \alpha$ (when you have an entire subtree that contains only constants, no variables, replace the entire subtree with a single symbolic value). We now get a function $f(x,\alpha) = x^2 + x - \alpha$. Use the training set $(x\_1,y\_n),\dots,(x\_n,y\_n)$ to define an objective function:

$$\Phi(\alpha) = \sum\_{i=1}^n (f(x\_i,\alpha) - y\_i)^2.$$

Finally, use numerical optimization methods to search for $\alpha$ that minimizes $\Phi(\alpha)$. You could try gradient descent, Newton's method, or other techniques. The value for that subtree deriving using genetic programming supplies a reasonable starting point for the search.

**Example 2.** In some cases, you will have more than one constant. For instance, you might get the expression $x^2 + 2x - 3$. Replace each constant with a symbolic value, so we get $f(x,\alpha,\beta) = x^2 + \alpha x - \beta$. Now you can derive an objective function as above:

$$\Phi(\alpha,\beta) = \sum\_{i=1}^n (f(x\_i,\alpha,\beta)-y\_i)^2,$$

and use optimization methods to search for $\alpha,\beta$ that minimize $\Phi(\alpha,\beta)$.
> 3 votes

# Answer
In Grammatical Evolution there are three well known approaches to the problem of constant creation:

1. **expression based** (the "traditional" approach). This is what you're using (arithmetic operators are required to produce new constants);
2. **digit concatenation**. An example is:

```
    <int> ::= <int><digit> | <digit>
    <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

or

```
    <catR> ::= <cat> <dot> <cat> | <cat>
    <cat>  ::= <cat> <catT> | <catT>
    <catT> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    <dot>  ::= .

```

These allow the creation of constants through the concatenation of digits. *Digit concatenation* is usually considered superior over the *expression based approach*;
3. **grammatical ephemeral random constants**. Generate a number of real values within a prespecified range and **add** them to the grammar to be used.

```
    <ephemeral> ::= <ephemeral> <op> <ephemeral> | <ephemeralT>
    <ephemeralT> ::= "x randomly generated real constants"

```

Random numbers become available to the evolutionary process throughout the lifetime of the experiment (they are part of the grammar itself).

This gives a better coverage of the search space.

A variation of this idea requires the introduction of the production rule:

```
    <constant> ::= ephemeral

```

> The terminal symbol ephemeral carries a special meaning: whenever it is selected during the program's decoding process, the next `n` bits are decoded into a real number. Afterwards, the decoding process resumes normally past those `n` decoded bit.

*<sub>(A New Approach for Generating Numerical Constants in Grammatical Evolution)</sub>*

This effectively decouples the number of bits used to encode the grammar's production rules from the number of bits used to represent a constant.

There isn't a clear winner between (2) and (3). Both mitigate the problem of constant creation.

Discovering (/tuning) useful numerical constants is a weakness of Genetic Programming (not only of Grammatical Evolution), so you might find useful to explore further the GP literature (especially the mixed approaches GP + local search).

For further details:
> 3 votes

---
Tags: algorithms, formal-grammars, data-mining, evolutionary-computing
---


# Question
Title: Calculate the number of instructions replaced ?
I was studying a cs book for computer architecture(computer organization and design) and I found this exercise:

`Program A runs on a processor with clock rate 1GHz in 10s. To improve the performance of the program we substitute each instruction(X*4) with 2 add instructions(X + X and then X + X). The CPI of multiplication is 4 and for the addition is 1. The new program runs in 9s. How many multiplication instructions have been substituted?`

To solve this I used the MIPS equation:

```
I named the program with additions B, so :
MIPS(A) = (Clock Rate * 10^9 Hz) / (CPI * 10^6) = 250

For B:
MIPS(B) = .... = 1000

Then I used the other MIPS equation: MIPS = Instruction count / (Execution time * 10^6)
So solving both for Instruction count my final two formulas yield:
Instruction Count(A) = ..... = 25 * 10^8
Instruction Count(B) = ..... = 90 * 10^8

Therefore,there were added 65 * 10^8 instructions.

```

Because there are no solutions for the book I would like to know if I am correct or not. Thank you in advance!

# Answer
This is the wrong approach, because you are assuming that each program does **nothing but** add or **nothing but** multiply.

I don't know what "the MIPS equations" are but I recommend that you try first principles rather than looking for official-sounding equations.

Each replacement of $X\*4$ with $X+X,\\,X+X$ saves $2$ clock cycles.

The replacement has reduced the run time by one second, which is $10^9$ clock cycles.

Simple division will tell you how many replacements have been made.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Can there be a context-sensitive pumping lemma?
A "pumping" property (words of a certain length imply the existence of loops in the language-defining mechanism) are known to exist for regular and context-free languages and a few more (usually used to disprove a language's membership to a certain class).

Within the discussion around this question, Daisy's answer suggests that there **can't be** a pumping lemma for context-sensitive languages - since they're so complex.

Is that true - can it be shown that there can't be some type of pumping property - and is there a good reference for that (or against that)?

# Answer
> 8 votes
Here is some evidence that there is no pumping lemma for the context-sensitive languages.

Of course, an answer hinges on the question what constitutes a pumping lemma. The weakest reasonable definition I could think of is this: A language class $\mathcal{C}$ has a *pumping lemma* if there is a decidable ternary predicate $P(\cdot,\cdot,\cdot)$ where $P(g,w,d)$ means:

* $g$ is a word encoding a language $L(g)$ from $\mathcal{C}$ (think: grammar),
* $w$ is a word in the language encoded by $g$
* $d$ is a word encoding a *pumpable* computation/derivation for $w$ (think: NFA computation with repeated state or CFG derivation tree with repeated nonterminal). Here, *pumpable* means: there exist infinitely many words in $L(g)$.

Moreover, we want that given a language $L$ in $\mathcal{C}$ encoded by $g$, for every sufficiently long word $w\in L$, there exists a word $d$ such that $P(g,w,d)$.

For example, the pumping lemma for regular languages would give rise to the predicate "$g$ encodes an $\varepsilon$-free NFA and $d$ encodes a run that repeats a state and reads $w$". For suitable encodings, this clearly satisfies the above conditions.

Now let us show that such a predicate does not exist for the context-sensitive languages.

Observe that if a language class has a pumping lemma, then the infinity problem (Given a grammar, does it generate an infinite language?) is recursively enumerable: Given an encoding $g$, we can enumerate words $w$ and $d$ and check whether $P(g,w,d)$. If we found such $w,d$, we answer 'yes', otherwise, we continue the enumeration.

However, we show that the infinity problem for the context-sensitive languages is not recursively enumerable. Recall that $\Pi\_2^0$ is a level of the arithmetic hierarchy that strictly includes the recursively enumerable languages. Hence, it suffices to prove:

**Claim**: The infinity problem for the context-sensitive languages is $\Pi\_2^0$-complete.

It is well-known that the infinity problem for recursively enumerable languages is $\Pi\_2^0$-complete (more often, one finds the formulation that the finiteness problem is $\Sigma\_2^0$-complete). Hence, it suffices to reduce the latter problem to the infinity problem for the context-sensitive languages.

Given a TM $M$, we construct an LBA $A$ for the language $$ \\{u\\#v \mid \text{$v$ is a shortlex-minimal accepting computation of $M$ on input $u$}\\}. $$ Then, $L(A)$ is infinite iff $L(M)$ is infinite, which completes our proof.

Update: Tried to be clearer. Update: Added example.

---
Tags: formal-languages, pumping-lemma, context-sensitive
---


title: Stack depth for QuickSort

text:
# Question
Title: Stack depth for QuickSort
*CLRS Problem : 7.4*

How does `Tail-Recursive-QuickSort` improve the efficiency of quick sort any better ?

*Original quicksort*

---

*Tail recursive quicksort*

---

*Question*

Modify the code for TAIL-RECURSIVE-QUICKSORT so that the worst-case stack depth is `O(n log n)`. Maintain the `O(n log n)` expected running time of the algorithm.

*Answer*

We are always doing a tail-recursive call on the second partition. We can modify the algorithm to do the tail recursion on the larger partition. That way, we'll consume less stack.

Both algorithms sort the both partitions. But how does the stack consume less space by operating `Tail-Recursive-QuickSort` on larger partition?

# Answer
> 1 votes
Quicksort may split an array of size n into two arrays of size (n-1) and 1 if you are unlucky. So a recursive call might be given an array of size (n-1) and make a recursive call with an array of size (n-2) and so on, for a maximum recursion depth of n.

Note that one of the array parts must have a size ≤ n/2. So which one do you sort by starting at the beginning of the loop, and which one do you sort by recursion?

---
Tags: algorithms, algorithm-analysis, quicksort, tail-recursion
---


# Question
Title: set with maximum sum consisting of mutually co-prime numbers
**Definitions.** Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and *mutually co-prime*. Then find the maximum sum the set $S$ can have.
**Example.** Let $n=10$, then the maximum sum $S$ can have is $30$ corresponding to $S=\\{1,5,7,8,9\\}$.

**What I tried.** I tried to implement the following greedy algorithm.

1. First I divide primes $\le n$ into $3$ lists: $list\_1$ containing primes $\le \lfloor \sqrt{n} \rfloor$, $\\; list\_2$ containing primes in range $\big( \lfloor \sqrt(n) \rfloor,\lfloor \frac{n}{2} \rfloor \big )$ and finally $list\_3$ containing prime in the range $\big\[\lfloor \frac{n}{2} \rfloor+1,n \big \]$.
2. Next I define a function $largest(a,b,n)$, which returns the largest number of the form $a\*b^{r}$ less than equal to $n$.
3. If there exist two numbers $l\_1 \in list\_1$ and $l\_2 \in list\_2$ such that $diff = largest(l\_2,l\_1,n)-( largest(1,l\_1,n) + l\_2 ) \> 0$, I chose the pair $(l\_1,l\_2)$ such that $diff$ is maximised. I delete $l\_1$ from $list\_1$, $l\_2$ from $list\_2$ and append $largest(l\_2,l\_1,n)$ in $list\_2$ and repeat step $3$. If no such pair $(l\_1,l\_2)$ exists such that $diff\>0$, I go to step $4$.
4. I don't change anything in $list\_3$.
5. In the end $ \\{1\\} \cup \\{ l\_1^r \\; | \\;l\_1 \\; \in list\_1 \text{ and } largest(1,l\_1,n)=r \\} \cup list\_2 \cup list\_3$ is my desired set $S$ and I report the sum of it's elements.

**Running example of my algorithm.** If $n=30$,

```
#list_1 = {2,3,5}
#list_2 = {7,11,13}
#list_3 = {17,19,23,29}

#The first time step 3 is evaluated I get l_1 = 2 and l_2 = 7 ..
#.. as  diff = ( 28 - ( 16 + 7 ) ) = 5 > 0 and diff is maximised
# so I delete 2 from list_1 and 7 from list_2 and append 28 in list_2

#When step 3 is evaluated again no such pair (l_1,l_2) is found

#So our desired list becomes S={1,27,25,11,13,28,17,19,23,29} with sum 193.

```

But my algorithm only seems to give correct for few simple cases only. Plus I am not able to prove/disprove or modify any of my assumptions .Now I am hopelessly stuck at the problem and I am not making any progress. But I still believe that some greedy algorithm is at work here.

PS: The question is from project Euler max-sum co-prime set. I would really appreciate just some hint or new direction to think.

# Answer
Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating.

Since the numbers are mutually co-prime, each prime number p is a factor of at most one element of S. On the other hand, if p is small enough then a number could have a factor $p^2$, $p^3$, $p^4$ and so on. We also know that every prime number p ≤ N is used (if p is not used as a factor of any number in the set then we just add p). And don't forget to include the number 1 in the set S :-)

A number x ≤ N cannot have two prime factors greater than $N^{1/2}$. Therefore the set S contains among other numbers one number $x\_p$ ≤ N which is a multiple of a prime $p \> N^{1/2}$. That's a good start for finding the optimal set S. We then take the primes $q ≤ N^{1/2}$, and either multiply one of the numbers $x\_p$ by a power of q, or we add a new number $x\_q$ which is some power of q.

In the Project Euler project with N = 200,000, there are fewer than 90 primes $q ≤ N^{1/2}$. We can take each of these primes q in turn, and either multiply one of the existing $x\_p$ by a power of q, or add a new number $x\_q$. We would try to do this achieving the highest possible increase in the sum. If no two q, q' achieve the highest increase in the same way, we can pick the optimal way for each.

In the example N = 30, we would start with $x\_p$ = 7, 11, 13, 17, 19, 23, 29. We can use q = 2 to change 7 -\> 28. q = 3 -\> 27, q = 5 -\> 25. The gains are 21, 27, 25. Each gain is \> N/2. So an optimal solution cannot include a number created by two or more of the q's - that number would be ≤ N, but we would give up two gains \> N/2, so this wouldn't be optimal. So in the simple example, we multiply 7 by $2^2$ and add $3^3$ and $5^2$.

With N = 100, we would have $x\_p$ = 11, 13, 17, 19, 23, ... and q = 2, 3, 5, 7. q = 2: 11 -\> 88 gains 77. q = 3: 11 -\> 99 gains 88. q = 5: 19 -\> 95 gains 76. q = 7: 13 -\> 91 gains 78. Unfortunately we have a conflict; q = 2 and q = 3 would both use $x\_{11}$. If we use 11-\>88 (gain 77), then q = 3: 31-\>93 with a gain of 62; total gain 139. If we use 11-\>99 (gain 88) then q = 2: 23-\>92 (gain 69) has a total gain of 157. So optimal for N = 100 is

```
S = { 1, 99, 91, 17, 95, 92, 29, 31, 37, 41, ,,, }

```

So here is the algorithm: Start with $x\_p$ = primes \> $N^{1/2}$. Find the primes $q ≤ N^{1/2}$. For each q, find the maximum gain that can be achieved using q: Either $q^k$ by adding the number $q^k$, or $p * (q^k - 1)$ by multiplying $x\_p$ by $q^k$. If each optimal gain is achieved in a different way, and each gain is ≥ N/2, then we found the optimal solution.

Otherwise, we choose one set of q's that use the same $x\_p$. For each of these q's: We assume that this q uses $x\_p$, find the optimal solution under the restriction that no other q uses this $x\_p$, and choose which q using $x\_p$ gives the best total.

If there is a case where the two smallest gains add up to less than N, ask someone for a more complex solution :-)
> 5 votes

# Answer
I did not follow gnasher729 completely on how he resolved the *conflicts* he mentions in his answer ( will look into it now ). So as suggested by D.W. I spent more on it and finally solved it. I followed the same algorithm described in my question except for the fact, that in place of doing greedy, one has to use maximum weighted bipartite matching ( a suggestion by Evil ), while trying to pair up a prime less than $\sqrt(n)$ with a prime greater than $\sqrt(n)$. But as I did not know how to implement maximum weight bipartite matching, I looked closely and the bi-partite graph formed in this case was too easy and one could resolve the conflicts and thus solve for maximum weight manually ( by pen and paper calculator :), the bipartite graph formed had interesting patterns too ). Finally the solution rests on a conjecture I am still unable to proof ( which I assumed in my post ) : to increase the sum of set $S$ you *can* pair up a prime less than $\sqrt{n}$ with exactly one prime greater equal to $\sqrt{n}$.
> 2 votes

---
Tags: greedy-algorithms, number-theory
---


# Question
Title: Does 'subexponential algorithm' refer to input or number of bits used to represent input?
When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N? Consider the following: trial division for integer factorization (i.e. try all numbers less than $\sqrt N$) is subexponential in terms of N.

**Note:** here I'm using the definition of 'subexponential' to be $2^{O(n^\epsilon)}$ for *some* $\epsilon \< 1$.

That is it takes $2^{\log\_2 \sqrt N}$ steps to factor N. This is obviously subexponential in terms of N. However, in terms of the number of bits B needed to represent N this is $2^{\frac B 2}$ which is not subexponential in terms of B.

So would trial division be considered subexponential or not? Or would it be considered both depending on whether you're referring to N or B?

# Answer
It refers to the number of bits to represent N. More generally, the complexity of a problem is normally taken to be a function of the *length* of the input (the number of bits needed to represent the input).

Trial division is exponential: its running time is $O(N^{1/2})$, i.e., $O(2^{B/2})$ where $B=\lg N$ is the length of the input in bits. That's an exponential function (of $B$). See Are there subexponential-time algorithms for NP-complete problems?.
> 2 votes

# Answer
We always express the running time of an algorithm in terms of the number of bits of input when we talk of subexponential.

Not all algorithms are about numbers, so it doesn't always make sense to interpret the input string as a number and express the running time in terms of that number. If your algorithm is about graphs, then its input might be a string of $n^2$ zeroes and ones for a graph of $n$ vertices. Then if it runs in time $n^3$, we say it runs in time $O(n^3)$ or time $O(|V|^3)$ or $O(b^{\frac{3}{2}})$ if $b=n^2$ is the size of the input. If the input to an algorithm is a set of numbers, such as in the subset sum problem or the knapsack problem, the size of the input depends on the amount of numbers, and the size of those numbers, so the input may be expressed in terms of both the number of variables and their length. Indeed the best known algorithm, due to Horowitz and Sahni, runs in time $O(b\cdot 2^{\frac{1}{2}n})=O(b\cdot 2^{\frac{1}{2}b})$ for instances with $n$ variables, taking up in total $b$ bits. (somebody may correct me if I'm wrong)

The reason is that we want to express time taken by computers (or Turing Machines) as 'if the input is so and so long, then the machine will take so and so long', without worrying about whether the input actually represented a number, or a graph, or something else.
> 2 votes

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


# Question
Title: Dynamically Learning Haar Cascade (in OpenCV)
I am new to computer vision so please excuse me if this question is very simple.

I am trying to learn how to use the Haar Cascade creation tool provided with OpenCV to train a cascade classifier. It seems relatively easy, with the tools provided, but I was wondering if there was a way to improve the network after the initial training. I plan to gather an initial set of positive images and train the cascade on those, but afterwards, continue collection and feed new positive images into the cascade to improve detection rates, reduce false positives and allow for better results in more difficult scenarios. Instead of retraining the cascade every time a new batch of positive images is produced, it would be extremely helpful if the cascade could prune itself and improve predictions based on the new images. I was wondering if this is possible, and how one would go about implementing it.

(Note: In this tutorial, the author discusses the use of more than one training epochs in a Deep Belief Network to improve detection rates by strengthening connections that result don't. I'm not sure how this works, but I would assume that if new images are added in each epoch, they could be incorporated without a full retraining, just a pruning. I would like to apply a similar approach to the cascade classifier.)

(Note on Note: The reason that I am using a cascade classifier and not a DBN is because I don't want to be restricted to defining a set number of output neurons. There may any number of detectable objects in the image, in addition to the fact that some results may be a plain boolean value. It doesn't seem that a DBN will work well. However, I have relatively little knowledge of the subjects and any suggestions on what approach to take to achieve the above implementation would be helpful.)

Thank you.

# Answer
Sadly, I don't know of any simple way to achieve this, for Haar cascades.

The problem is that Haar cascades are trained using boosting. A cascade is a multi-stage classifier: we use the first stage to quickly discard candidates: if the first stage says "no", we immediately reject, and only go on to process the input with the second stage if the first stage says "yes". That means that the second stage is trained on only images that the first stage classifies "yes". If you add some more training examples and want to update the first stage, then now this has cascading effects on all of the subsequent stages: naively, you need to re-train all subsequent stages, because the set of images they should be trained on has now changed.

There might be a clever way to do it, but it's not straightforward.
> 1 votes

---
Tags: machine-learning, image-processing, classification
---


title: Finding a match in two collections

text:
# Question
Title: Finding a match in two collections
Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a \< b = card(B)$. Both collections are sorted in ascending order. There is at least one item ${x}$ which is contained both in $A$ and $B$.

Question: what is the fastest algorithm to find **the smallest** $x$ and what is its $T(n)$ in Big O notation?

Note: card() means the size of array (say: card(A) = 10 means a declaration in C/C++ would be int\[10\] A with indices 0...9).

Note 2: as I am new to CS.SE and learn CS as enthusiast, so far I have not been exposed to any fancy algorithm to solve this. My initial (naive) guess would be brute-search approach, but this is obviously not efficient for large $A$ and $B$. Your thoughts and pieces of advice would be then highly appreciated.

The priority is practical efficiency, so something around polynomial time-algorithm would be nice. Note, that the number of elements in both collections will be very substantial (above 10^30).

# Answer
> 1 votes
Some ideas for a special case.

If all the elements have a limited range N (all the elements in A and B are bigger than zero and smaller than N), then you can accomplish this task by O(N\*log(|A| + |B|)) as following:

```
for i <- 0, 1, ..., N:
    binary search in A to see whether i is in A
    binary search in A to see whether i is in B
    if i is both in A and B then
        x <- i
        break

```

This solution will be practically efficient if the N is not so big (for example 10^7) then it will solve the problem even when |A| and |B| are as large as 10^30 (though it is not practical to store them in any place).

The calculation: $N\*\log{(|A| + |B|)} = 10^7 * \log{(2\*10^{30})} \approx 3\*10^8$

Besides, I do not think you can find a practically efficient algorithm for general case for card(A) and card(B) as much as 10^30. The general algorithm, in my opinion, is at least O(|A|+|B|) as following:

```
ia <- 0
ib <- 0
while A[ia] != B[ib] do
    if A[ia] > B[ib] then
        ib <- ib + 1
    else
        ia <- ia + 1
x <- A[ia]

```

---
Tags: algorithms, search-algorithms, arrays
---


# Question
Title: Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?
Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching.

In short, the regular expression `a+b`, when running on the string `aaaaaaaaaaaaaac`, runs in $O(n^2)$ time where $n$ is the number of `a` characters, because it uses backtracking.

You can reproduce the issue with the following Python code, which on my computer, takes over 4 seconds to run:

```
import re, time
start = time.time()
re.findall(r'\s+$', ' '*20000 + 'x')
print(time.time() - start)

```

This was very surprising to me; I'd have thought that a regex matcher works more efficiently, e.g. by constructing a DFA from the regex and then running the wanted string through it, which I'd have thought would be $O(n)$ (not including the DFA construction).

(For instance, the book Introduction to Algorithms by Cormen, Leiserson, Rivest goes through a similar algorithm on the way to introducing the Knuth-Morris-Pratt algorithm).

My question: **Is there something inherently difficult in regular expression matching that does not allow an $O(n)$ algorithm**, or are we simply talking about an inefficient implementation (in Python, in whatever StackOverflow uses, etc.)?

# Answer
> 9 votes
If you only wanted to parse regular expressions then you wouldn't have such problems (unless you were a really incompetent programmer, I guess). Caveats include the time needed to build an automaton; an asymptotically worse algorithm may outperform the automaton approach in many cases in practice.

The real issue is probably that they use library functions that deal with *regexps* which are *way* more powerful than plain regular expressions. Also, features like matching groups introduce further complexity.

In this case, trouble arose because these engines match *substrings* (with plain regular expressions, we typically only match whole inputs) and use *backtracking*; long partial matches that eventually mismatch cause long backtracks. In essence, this is the worst-case for naive, quadratic-time string matching.

Can this be improved? Maybe. Using the ideas from string matching automata we would backtrack not to the second symbol, but to the start of the longest suffix that matches a prefix of the pattern. But since the pattern is not fixed anymore, it's certainly not trivial to extend the ideas.

---
Tags: algorithms, time-complexity, regular-expressions
---


title: Proving that a CFG generates a language

text:
# Question
Title: Proving that a CFG generates a language
Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree?

What if the tree is infinite? What would then be a better way to prove that a given CFG generates a given language?

# Answer
> 1 votes
Suppose that we have a context-free grammar $G$ and a set of words $S$, and we would like to prove that the language $L(G)$ generated by $G$ is precisely the set $S$. The most direct way of doing this is to prove $L(G) \subseteq S$ and $S \subseteq L(G)$, which amounts to showing:

1. For every $x \in L(G)$ we have $x \in S$.
2. For every $y \in S$ we have $y \in L(G)$.

How this is done depends on how the set $S$ is given, so there is no further, more specific advice that I can offer, except that drawing trees is not really going to result in a proof.

# Answer
> 0 votes
If your language $L$ is, as you state in the comment, given as a regular expression, you can prove that the grammar $G$ generates it in two steps.

1. Prove that $G$ is regular
2. Show that the two automatons (from $G$ and from the expression for $L$) recognizing the language are the same.

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


# Question
Title: Estimating the complexity of an algorithm by looking at code
Time complexity seems rather a difficult notion for people who were not professionally trained in math or computer science. I understand it informally and can high-level compare which one is better and which one is worse (say: polynomial time algorithm is more efficient/faster than exponential time algorithm), but my question is how can one roughly assess the time complexity of his/her own algorithm?

A good example is the grand-canonical problem of integer factorization. Say one tries to write a new method to factor these awfully big integers. We know that the input has x-decimal digits and b-bytes. What does technically make an algorithm inefficient from the start? (say nested loops kills the program already and it's not even worth in-depth measurement? Does one need to obey certain programming rigours in order to ensure time complexity is capped at certain (reasonable) level)?

Sorry if this sounds really informal and amateurish, but I am just very curious about this kind of things, though have little professional knowledge to understand it on my own.

# Answer
> 2 votes
This question is rather informal, and you may enjoy reading this. What you are asking about is a topic discussed often in Computer Science and Mathematics (perhaps all subjects, but my perspective is not so broad) - "developing an intuition". Often, students are looking for some sort of cheat code to solving problems quickly without going through all of the steps. The honest answer is that you can only develop such intuition and speed by doing precisely the opposite - practicing slowly and without any sort of shortcut.

Practice calculating time complexity - it really isn't too difficult. A quick google search gave me this page, which is pretty informal and may suit the needs of some practice problems. Once you have gone through the process enough times, you will ascend to a sought-after plane of intuition.

Having very little professional knowledge is not an issue. If the example page I sent is too formal, there are plenty of other pages on the web explaining time complexity. You just have to be willing to sit down and put some hours into it (which no different than what a "professional" does to get the same knowledge, except perhaps they pay more for it?).

# Answer
> 2 votes
There are cases where it's easy - you have a few nested loops, you can estimate how often they are executed or at least give some upper bounds, just by looking at the code.

There are things where it's not easy at all. Example: Numerical solution of a differential equation with a given precision. You need to solve this step by step, with the step size small enough to guarantee the wanted precision. But you can't look at the code and see what the step size would be, and the execution time depends directly on the step size.

Example: Find a primitive root of a prime number p. The algorithm is very simple, you check the integers 2, 3, 4, ... until you find one that is a primitive root. The time for checking is reasonable straightforward (although it involves factoring p - 1). However, the average number of integers to check is a mathematical problem. The number could be as large as p which would make this totally unfeasible. Fortunately it isn't, and on average 2 or 3 or 4 attempts will find you a primitive root. But it's not something that you can decide by looking at the code.

Here set with maximum sum consisting of mutually co-prime numbers you'll find the description of an algorithm where I have not the slightest idea how long it would take. I think it will be quick. Someone tested it and said it was quick. But you'd have to prove that (it might be exponential in $N^{1/2}$ which would be awful but I think it isn't). Giving a reasonable upper bound could require some serious mathematics.

Given k, find three positive integers a, b, c such that $a^3 + b^3 = c^3 ± k$. Finding all solutions with c ≤ N is easily done in $O (N^2)$ and can be done faster, but the first solution might be very, very large. If k = ± 3 (modulo 9) then there is about a 10 percent chance to find a solution with N ≤ c ≤ 10N no matter how large N is. The execution time of an algorithm finding a solution is impossible to predict.

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?
Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a problem known to be in NP had a polynomial time quantum solution, would that be enough to show that P=NP?

# Answer
No.

The class $P$ refers to the classical Turing machine model, we don't know if $BQP\subseteq P$ (we suspect that it isn't), thus this does not mean that factoring is in $P$. We don't know how to simulate a quantum algorithm in a classical machine with only polynomial slowdown (the naive translation would result in an exponential algorithm for factoring).

Many problems in $NP$ have a quantum polynomial time solution, and also classical polynomial time solution, since $P\subseteq NP$. See our reference question for an overview and precise definitions.

The more interesting question would be if quantum computers can solve NP-hard problems efficiently, or formally, if $NP\subseteq BQP$. We suspect that this statement is false, though even $PH\subseteq BQP$ is still open. Proving $NP\not\subset BQP$ would also in turn prove that $P\neq NP$ (since $P\subseteq BQP)$.

It is also worth mentioning that factoring in not known to be NP-hard (and believed not to be) so we can still have both $NP\not\subset BQP$, and a polynomial algorithm for factoring in a quantum computer.

See these questions:

Consequences of SAT∈BQP,

Can a parallel computer simulate a quantum computer? Is BQP inside NP?,

for a discussion on the possibility of $NP\subseteq BQP$.
> 3 votes

---
Tags: complexity-theory, time-complexity, quantum-computing
---


# Question
Title: Clarification on the inapproximability of set cover
I'm trying to understand the inapproximability of the minimum set cover problem.

The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the size of the ground set. It references the work of Dinur and Steurer (2013) who state that, for every $\varepsilon\>0$, it is NP-hard to approximate min set cover within a factor of $(1-\varepsilon)\ln n$ where $n$ **refers to the size of the instance**. It seems they don't define what they mean by "size of the instance," but I take that to mean an encoding of the instance (which takes more space than just the size of the ground set).

Would I be correct in saying that set cover is hard to approximate within a factor of $(1-\varepsilon)\ln N$, where $N$ is the size of the ground set plus the sizes of all the subsets? Or, if $N$ is the size of the ground set plus the number of subsets?

# Answer
> 5 votes
The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection Games Conjecture, thus completing the NP-hardness proof. Moshkovitz clearly states that $n$ is the size of the universe, and she also assumes that the number of sets is polynomial in $n$.

Feige had proved earlier that if you can approximate set cover better than $\ln n$ then $\mathsf{NP}\subseteq \mathsf{DTIME}(N^{\log\log N})$. He improved on earlier result of Lund and Yannakakis which showed a hardness of $0.72\ln n$ under the same assumption.

The threshold $\ln n$ (where $n$ is the size of the universe) is important since it is achieved by the greedy algorithm. The analysis of the greedy algorithm shows that after $OPT \cdot t$ steps (where $OPT$ is the size of an optimal solution), we have covered a $1-e^{-t}$ fraction of the universe. When $e^{-t} \< 1/n$, we have covered the entire universe (since we cover more than $n-1$ elements). Hence after at most $t = OPT \cdot \ln n$ steps, the greedy algorithm manages to cover the entire universe. This is where the dependence on the size of the universe comes from.

---
Tags: approximation, set-cover
---


title: Minimum number of transpositions

text:
# Question
Title: Minimum number of transpositions
Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \sim n^2$ but I cannot find a formal proof.

# Answer
> 1 votes
If your transpositions form a permutation $\pi$ then (using the appropriate convention for multiplication) $A\pi = B$ and so $\pi = A^{-1} B$. This shows that we can assume without loss of generality that $A$ is the identity, and the question now becomes: how many transpositions do we need to multiply in the worst case to get any particular permutation? This might be a question you already know how to answer.

---
Tags: combinatorics, permutations
---


# Question
Title: Why do source and sink have to be distinct in Ford-Fulkerson?
Recently I have been studying the Ford-Fulkerson algorithm for determining max flow. I do not see why it is not allowed to have the source vertex be the same as the sink vertex. From what I have heard, doing this allows infinite flow. However if you take a graph where the source (which equals the sink) has no arcs leading into it shouldn't the max flow be $0$?

# Answer
> 1 votes
In a flow network, the source and sink are "special". The source is *defined* to have infinite incoming capacity, and the sink is defined to have infinite outgoing capacity -- they are different from all the other networks. For any node with no incoming edges *other than the source*, it's true that the flow through that node has to be zero -- but the source is different, because it is special.

Why can't the source and sink be the same node? Basically, because then you get a different problem with different characteristics. That other problem is called the circulation problem, and there are algorithms for it. They are a bit different, though, and your teacher probably doesn't want to confuse you by adding unnecessary complications.

# Answer
> 0 votes
In the Maximum Flow problem at first step you assume that source has $\infty$ capacity, if it had limited capacity you would denote that by auxiliary arc to node.
Then you cut it to comply with constraints - weighted edges gives capacity. Since there are no arcs with weights -\> there are no limits, what you put in source is immediately in the sink.
Otherwise if source had $0$ capacity then there would be no flow at all.

---
Tags: algorithms, network-flow, max-flow
---


# Question
Title: Interval Scheduling Problem with Three Resources
So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources. Consider this example interval scheduling problem.

Say there are n requests for a lecture hall and three lecture halls are available to satisfy these requests. Each request has a starting time and an ending time. Create an algorithm to get a maximal scheduling.

I am familiar with the process and I know how the ISP would work if I had only one resource. But how would I apply it in this scenario if I had two, three, or a predefined set of resources.

Any input will be appreciated.

# Answer
The greedy scheduling with a first fit resource selection is actually not correct. Consider the case where the intervals are:

${ (1, 3) , (2, 5) , (6, 7) , (4, 8) }$,

for simplicity assume we only have 2 resources. The greedy algorithm will assign intervals 1, 2, 3 to resources 1, 2, 1 respectively and will fail to assign a resource for the last interval. Although, a more optimal assignment would have been assigning all 4 of them 1, 2, 2, 1 in the following order.

So another greedy choice has to be made which is the selection of the resource to host the interval. The greedy choice would be selecting the **compatible** resource with the **latest** finish time. That way resources which are good (i.e. support more intervals) are kept free.

## Intuition to the correctness of the algorithm:

There are 2 claims: 1) Intervals with early finishing time are always better to schedule first.

This is proven by an exchange argument, assume we would leave an interval with early finish time unscheduled to take a later interval, future intervals will definitely have a harder job finding a free room.

2) When an interval is compatible, it is always better to select the worst compatible room.

Since by claim 1, the interval will be taken anyway, the state of the rooms will have a room with $nextFreeTime = endTime\_{cur}$ leaving 2 rooms with their previous $nextFreeTime$. Selecting the room with a larger $nextFreeTime$ will leave the better rooms for worse intervals.

**Note:** The problem can be solved with a less efficient but more obviously correct algorithm using a 3D dynamic programming approach. The state of the dp would indicate the last taken resource in each of the rooms, and the transitions are for each current interval, try selecting all of the compatible rooms updating their states. The intervals are still taken in order of finish time (Claim 1 still holds). The complexity becomes $O(n^3)$, however this is not scalable for k resources unlike the greedy algorithm.
> 3 votes

# Answer
Scheduling could still be done greedily.

Psuedocode:

```
sort requests by finishing time
list of schedules = [[]]
for each request
    for each schedule in list of schedules
        if request can be appended to schedule
            append and break
    if not appended
        create new schedule
        add request to schedule
        append schedule to list
sort list of schedules by number of requests in each

```

This should work for any number of requests and 'resources'.
> 0 votes

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?
Papadimitriou's "Computational Complexity" states that VALIDITY, the problem of deciding whether a first-order logic (without arithmetic) formula is valid, is recursively enumerable. This follows from the completeness and soundness theorems, which equate VALIDITY and THEOREMHOOD, the latter being the problem of finding a proof for a formula, which had previously been shown to be recursively enumerable.

However, I am not seeing why VALIDITY is not recursive as well, because given a formula $\phi$, one could run two Turing Machines for THEOREMHOOD, one on $\phi$ and the other on $\neg \phi$, concurrently. Since at least one of them is valid, it is always possible to decide whether $\phi$ is valid, or not valid. What am I missing?

Note: this question refers to first-order logic *without* arithmetic, so Gödel's Incompleteness Theorem does not have a bearing here.

# Answer
> 5 votes
> However, I am not seeing why VALIDITY is not recursive as well, because given a formula $\phi$, one could run two Turing Machines for THEOREMHOOD, one on $\phi$ and the other on $\neg \phi$, concurrently. Since at least one of them is valid, it is always possible to decide whether $\phi$ is valid, or not valid. What am I missing?

This is wrong. A formula $\phi$ is valid iff it holds in **all** models.

It is not true that at least one of $\phi$ and $\lnot\phi$ must be valid: both might hold in some models, but not all of them.

Trivial example: take FOL with two constant symbols ${\sf a}, {\sf b}$, and the formula $\phi \equiv {\sf a}={\sf b}$. Then $\phi$ holds in some models (those which interpret $\sf a$ and $\sf b$ with the same point), but not all of them (a model can map them to distinct points). And indeed, FOL can not prove ${\sf a} = {\sf b}$ nor ${\sf a} \neq {\sf b}$.

# Answer
> 1 votes
A first-order sentence is *valid* if it is true in every possible model, i.e., if it is true for all choices of what the relation symbols, function symbols (if there are any) and constant symbols mean. A sentence is *provable* in some proof system if that proof system contains a proof of the sentence.

Note that provability and validity are two separate concepts, but your attempt to show that validity is recursive actually determines provability, not validity.

Validity and provability are tied together by two further notions:

* a proof system is *sound* if everything it can prove is valid, i.e., it only lets you prove things that are actually true;
* a proof system is *complete* if it can prove everything that is valid, i.e., it lets you prove all things that are true.

So your proposed method would be fine if you were using a sound and complete proof system: that would mean you could prove exactly all the valid sentences so deciding provability would be the same thing as deciding validity. Unfortunately, Gödel's famous incompleteness theorems say that there is no sound and complete proof system for first-order logic.

So, if your system is sound (it only proves true things) then it is incomplete (it doesn't prove *all* true things). In particular, there are some sentences $\varphi$ such that neither $\varphi$ nor $\neg\varphi$ has a proof in your system, which means that your Turing machine doesn't halt on input $\varphi$, so it doesn't actually decide any language. Alternatively, if your system is complete (it proves all true things), then it is unsound: it proves at least one false thing and, in fact, since false implies anything, it proves that *every* sentence is valid. In that case, the Turing machine that you thought was going to decide validity actually decides $\Sigma^\*$.

---
Tags: complexity-theory, undecidability, first-order-logic
---


# Question
Title: Processing weighted points of interest. Is there a name for this task/algorithm?
Is there a name for the following problem? Is there a measure of quality of a given solution? How can we even define what a proper solution is?

**Context:** I want to detect long lines (most lines over 1000 pixel long) in an image. It is known that most of the lines have similar alignment. To detect those I use the Standard Hough Transform. To detect long lines I need a high angle resolution of the accumulator. Now the idea is not to use an equidistant partition of the angle axis but to create a new partition based on the number of votes for each angle.

**The Problem:** Given weights $$a\_0, \ldots, a\_{n-1} \in \[0,1\] \text{ with } \sum\_{k=0}^{n-1}a\_k = 1$$ which correspond to the equidistant partition of the interval $\[0,1\[$ $$0, \frac{1}{n}, \frac{2}{n}, ..., \frac{n-1}{n},$$ return a new partition with less or equal elements which is "finer" around points with larger weights and "coarser" around points with smaller weights. E.g. given the weights $(0.75, 0, 0, 0.25)$ on the partition $(0, 0.25, 0.5, 0.75)$ the result should be a new partition like $(-0.083, 0.0, 0.083, 0.75)$. As $0$ seems to be a point of interest there are three points near it which reflects that.

**My solution:** The idea is to treat the vector of weights as a density function and to use the quantile function of its cumulative distribution function (cdf).

Example: Given the weights $(0, 0.5, 0, 0.5, 0)$ we construct the density function:

Then the cdf looks like this:

Now we shift the given equidistant partition by $+1/(2n) = 1/10$ and put its values into the quantile function, i.e. we put those values on the $y$-axis and search for corresponding $x$-values of the cdf as marked by the blue lines. $y=0.5$ is omitted since it "cannot decide" which peak it contributes to. The so obtained $x$-values are shifted by $-1/(2n) = -1/10$ and returned as the new partition. The returned partition in this example is $(0.14, 0.22, 0.58, 0.66)$.

Here is a C++ function which performes those tasks, where the vector "weights" represents the input weights and "sample" contains the new partition after execution:

```
#include <vector>
using std::vector;

void weighted_partition(vector<double>& sample, const vector<double>& weights) {
    const int n = (int)weights.size();
    double y;
    double F = 0.0;
    int i = 0;

    for (int j = 1; j < 2*n; j += 2) {
        y = (double)j/(2*n);

        while (F < y) {
            F += weights[i];
            ++i;
        }

        if (F == y) {
            continue;
        }

        --i;
        F -= weights[i];

        sample.push_back((y - F + weights[i] * i) / (weights[i] * n) - 1.0/(2.0 * n));
    }
}

```

This algorithm seems to return solutions which are intuitively correct but how can you define "correct"?

# Answer
> 1 votes
## Solution to your algorithm problem

There's a simple solution to your algorithmic problem. Treat the $a\_0,a\_1,\dots,a\_{k-1}$ as a probability distribution. Apply kernel smoothing to turn this into a smooth probability distribution. At this point, you have a probability density function (pdf). Now compute a cumulative density function (cdf), and find the $n+1$ quartiles of the cdf. These endpoints of your new bins.

This is "optimal", in the sense that given all of the information available to you, it gives the optimal bin-sizing for a particular distribution. We could prove this by proving that for a particular pdf, this definition of bins ensures that each bin has exactly $1/n$ probability mass falling within it.

## Other approaches to your computer vision task

The Hough transform might not be optimal. There are other approaches you could also try. For instance, there are algorithms for detecting lines that are approximately horizontal. So, the following approach might be better:

* Find one long line and approximately find its angle.
* Rotate the image so that it is approximately horizontal (since the lines are all approximately parallel, that means all the lines will now be approximately horizontal).
* Find all long, approximately-horizontal lines.

The problem of finding long, approximately-horizontal lines has been studied in the literature on image processing and deskewing scanned documents. Or, if you want a free tool, take a look at existing tools, e.g., Leptonica, pagetools, ImageMagick (`convert -deskew`), and others.

Another standard approach is to apply the Hough transform twice:

* First use the Hough transform to get a rough estimate of the angle. For instance, you might sweep over some range of possible angles, sensitive to 1 degree or 0.1 degree increments.
* Then, use a second Hough transform to get a rough estimate of the angle. Now you have a much narrower range of possible angles (1 degree or 0.1 degree wide); do the Hough transform over this narrower range, sensitive to 0.01 degree increments (say).

This is more efficient then doing a single Hough transform sensitive to 0.01 degree increments.

---
Tags: algorithms, computer-vision
---


# Question
Title: Negligible functions in definitions of statistical closeness and computational indistinguishability
Statistical closeness implies computational indistinguishability.

Is there any (simple) relationship between negligible function that is used in definition of statistical closeness and negligible function that is used in definition of computational indistinguishability?

Can we say anything about the negligible function used in computational indistinguishability if we know how the negligible function in definition of statistical closeness looks like?

What about the special case: negligible function in definition of statistical closeness is zero?

---

Definitions from Goldreich, Foundations of Cryptography:

Ensemble = sequence of random variables, $\\{X\_i\\}\_{i \in \mathbb{N}}$

Computational indistinguishability:

Two ensembles $\\{X\_i\\}\_{i \in \mathbb{N}}$ and $\\{Y\_i\\}\_{i \in \mathbb{N}}$ are computationally indistinguishable if for every probabilistic polynomial-time algorithm $D$, every positive polynomial $p$ and all sufficiently large $n$'s,

$ |P(D(X\_n) = 1) - P(D(Y\_n) = 1)| \< \frac{1}{p(n)}. $

(this definition actually says that $|P(D(X\_n) = 1) - P(D(Y\_n) = 1)|$ is negligible function in $n$)

Statistical closeness:

Ensembles $\\{X\_i\\}\_{i \in \mathbb{N}}$ and $\\{Y\_i\\}\_{i \in \mathbb{N}}$ are statistically close if their statistical difference $\triangle(n)$ is negligible.

$ \triangle(n) = \frac{1}{2} \sum\_a |P(X\_n = a) - P(Y\_n = a)| $

# Answer
> 3 votes
Statistical distance between $X\_n$ and $Y\_n$ can be defined as the maximum, over all functions $D$, of $$ |P(D(X\_n) = 1) - P(D(Y\_n) = 1)|. $$

In particular, if the statistical distance between two sequences of distributions $\\{X\_i\\}\_{i \in \mathbb{N}}$ and $\\{Y\_i\\}\_{i \in \mathbb{N}}$ is negligible (eventually smaller than $1/p(n)$ for any polynomial $n$) then they are computationally indistinguishable. The other direction is not true, and this is what drives all of cryptography.

I leave it an exercise to show that if two sequences distributions have zero statistical distance (i.e., they are copies of the same random variables) then they are computationally indistinguishable.

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


title: Deep DFS traverse on graph

text:
# Question
Title: Deep DFS traverse on graph
According to chess rules, the (undirected) graph generated from the Knight move on a keypad is the following:

$$ \begin{array}{ccccc} 3 & - & 4 & - & 9 \\ | & & | & & | \\ 8 & & 0 & & 2 \\ | & & | & & | \\ 1 & - & 6 & - & 7 \end{array} $$

The question is:

Consider the uniform distribution on all $n+1$-sequences $(s\_i)\_{i=0}^n$ starting with $s\_0=0$. What is the expected value and the standard deviation of $\sum\_{i=1}^n s\_i \bmod n$, under this distribution on sequences?

My naive approach is simply traverse every single sequence of fixed given length and do the calculation. But as the $n$ grows, the number of visits grows exponentially. For example, for $n=1024$, the number of sequences exceeds $6.04\times 10^{367}$. Hence a DFS or any kind of traverse is not a feasible approach.

So my second thought is using some analytic method. To get a few ideas, I first did some simulations on $\sum s\_i$ (without modular reduction) with $10^5$ trials. The program generates the following distribution which doesn't match any obvious candidate so I couldn't advance further. So I am thinking if this is the correct way to tackle this problem. Any hint or help is appreciated.

# Answer
You can compute the exact distribution of $\sum\_{i=1}^n s\_i$ using dynamic programming: for each vertex $v$, index $m \in \\{0,\ldots,n\\}$ and index $S \in \\{0,\ldots,9m\\}$, calculate the number of walks of length $m$ starting at $0$, ending at $v$, and summing to $S$. The running time is roughly $O(n^3)$ (the extra $n$ factor is due to the length of the numbers involved).

If you want an estimate, you should first find the stationary distribution of the Markov chain corresponding to a random walk on your graph. Given that, $\sum\_{i=1}^n s\_i$ has roughly Gaussian distribution with parameters that you can calculate from the stationary distribution; more specifically, roughly $N(n\mu, n\sigma^2)$ (this requires a version of the central limit theorem for Markov chains). This Gaussian approximation shows that the sum lies inside the interval of width $n$ centered around $n\mu$ with high probability, so taking modulo $n$ doesn't have much effect beyond shifting this interval to $\\{0,\ldots,n-1\\}$.
> 4 votes

---
Tags: graphs, probability-theory, simulation
---