Union of every language within group of decidable languages is also decidable? So I was trying to solve following exercise:
Let $(L_{i})_{i \in \mathbb{N}}$ be a family of decidable languages - this means that every $L_{i}$ is decidable. Then $\cup_{i \in \mathbb{N}}L_{i} $ is also decidable. Right or wrong?
The solution states, that this statement is wrong because we can set $L_{i}:=\{f(i)\}$ with $f : \mathbb{N} \rightarrow H_{0}$ and will therefore receive $\cup_{i \in \mathbb{N}}L_{i} = H_{0}$.
At the same time $L_{i}$ languages are still decidable,  for every $i \in \mathbb{N}$ because they are finite.
However I still struggle to understand how exactly a language can be decidable with $f : \mathbb{N} \rightarrow H_{0}$, because I thought that $H_{0}$ was not decidable.
Thanks in advance!!

You don't define $H_0$. Presumably it's an undecidable set.
First, $f : \mathbb{N} \to H_0$ only means that all the values of $f(x)$ are in $H_0$, i.e. the image of $f$ is a subset of $H_0$: $f(\mathbb{N}) \subseteq H_0$. The proof of the counterexample involves a stronger property: it constructs a function $f$ whose image is exactly $H_0$, that is, $f(\mathbb{N}) = H_0$.
Second, the image of a recursive set by a recursive function is not necessarily recursive. It's obviously recursively enumerable, by definition of “recursively enumerable”: if $g$ is recursive, then it's partial recursive, and $g(\mathbb{N})$ is a recursively enumerable set. But $g(\mathbb{N})$ might not be recursive. For example, consider a function $g$ whose input is an encoding of a program (that doesn't take arguments) and an integer: $g(\langle P,n\rangle)$ which runs $P$ for $n$ steps and returns $\langle P\rangle$ if $P$ terminates in less than $n$ steps and $0$ otherwise. The function $g$ is recursive (its definition is an algorithm to run it), but its image is the set of encodings of terminating programs, which is not decidable. Coming back to our original problem, it's possible to have a recursive $f$ such that $f(\mathbb{N}) = H_0$ but $H_0$ is not recursive.
Third, $f$ might not be recursive anyway. (And if you apply the previous paragraph, you'll notice that it can't be recursive if $H_0$ is not recursively enumerable.) All you know is that there exists a function $f$ such that $f(\mathbb{N}) = H_0$. An example of how to define this function is: $f(x) = x$ if $x \in H_0$ and $f(x) = h_0$ if $x \notin H_0$, where $h_0$ is the smallest element of $H_0$. This is a perfectly good mathematical definition, but it isn't an algorithmic definition: since $H_0$ isn't decidable, there's no algorithm to choose between the case $x \in H_0$ and the case $x \notin H_0$.
Intuitively speaking, to decide whether $x \in \bigcup_{i\in\mathbb{N}} L_i$, you need to figure out which $i$ to check, then check whether $x \in L_i$. But there's no reason why there would be an algorithmic way to pick $i$. (And to make things worse, $x$ might be in multiple $L_i$, possibly infinitely many — but the proposed property is wrong even if the $L_i$ are disjoint, as seen with the example of singletons which can easily be renumbered to make them distinct and therefore disjoint.)


Is "represents" a symmetric relation in the provided answer to TAOCP exercise 1.1.9? In exercise 1.1.9 of volume 1 of The Art of Computer Programming, the reader is asked to

  formulate a set-theoretic definition for the concept "$C_2$ is a representation of $C_1$"

where $C_1$ and $C_2$ are computational methods described in the previous few pages (reproduced here so the question can be answered without needing the book).

  Let us formally define a computational method to be a quadruple $(Q,I,\Omega,f)$, in which $Q$ is a set containing subsets $I$ and $Ω$, and $f$ is a function from $Q$ into itself. [...] The four quantities $Q$, $I$, $\Omega$, $f$ are intended to represent repectively the state of the computation, the input, the output, and the computational rule.

When I looked at the answer in the back, this definition was proposed:

  For example we can say $C_2$ represents $C_1$ if there is a function $g$ from $I_1$ into $I_2$, a function $h$ from $Q_2$ into $Q_1$, and a function $j$ from $Q_2$ into the positive integers, satisfying the following conditions:

  a) If $x$ is in $I_1$ then $h(g(x)) = x$
  b) If $q$ is in $Q_2$ then $f_1(h(q)) = h(f_2^{[j(q)]}(q))$, where $f_2^{[j(q)]}$ means that the function $f_2$ is to be iterated $j(q)$ times.
  c) If $q$ is in $Q_2$ then $h(q)$ is in $\Omega_1$ if and only if $q$ is in $\Omega_2$

Later on, discussing this definition, Knuth writes (emphasis mine):

  The relation "$C_2$ represents $C_1$" generates an equivalence relation in which two computational methods apparently are equivalent if and only if they compute isomorphic functions of their inputs ...

To be an equivalence relation, a relation must be symmetric. That is, for a relation $R$, $(a, b) \in R$ implies $(b, a) \in R$. I don't believe this is true of the given definition.

Consider the computational methods $C_1$ and $C_2$, where

\begin{align*}
C_2 &= \{Q_2, I_2, \Omega_2, f_2\}\\
C_1 &= \{Q_1, I_1, \Omega_1, f_1\}\\\\
I_2 &= \{a_1, a_2\}\\
\Omega_2 &= \{b_1, b_2\}\\
Q_2 &= I_2 \cup \Omega_2\\
f_2 &= \{(a_1, b_1), (a_2, b_2), (b_1, b_1), (b_2, b_2)\}\\\\
I_1 &= \{c\}\\
\Omega_1 &= \{d\}\\
Q_1 &= I_1 \cup \Omega_1\\
f_1 &= \{(c, d), (d, d)\}
\end{align*}

It can be shown that $C_2$ represents $C_1$ by $g(q) = a_1$, $h = \{(a_1, c), (a_2, c), (b_1, d), (b_2, d)\}$, and $j(q) = 1$.

However, $C_1$ cannot represent $C_2$, because for any proposed $g: I_2
\rightarrow I_1$ it must be the case that $g(a_1) = g(a_2) = c$. But $h(c)$ can
only be either $a_1$ or $a_2$. If $h(c) = a_1$, then $h(g(a_2)) = a_1 \neq a_2$,
but if $h(c) = a_2$, then $h(g(a_1)) = a_2 \neq a_1$. So in either case,
the first requirement cannot be satisfied.

Has this been discussed elsewhere? So far my online searches haven't revealed any answers on the subject. To the best of my knowledge, this hasn't been errata'd (checked here).

Am I understanding the definition properly?

I'm uncertain about my result because of the specific wording "from $Q_2$ into
$Q_1$", which seems to have varying meanings depending on where you ask (if it means "injection", it adds different inconsistencies). It also
seems strange to me that this property would be overlooked, since Knuth also
specifically mentions that "represents" is transitive, and a counterexample like
this is quite easily constructed.

In summary: is it not symmetric? Has this been addressed somewhere? Am I owed 0x$1.00?

I slept on it and remembered there was another wording issue that was bugging me: "generates an equivalence relation". I wasn't familiar with it and assumed it just meant "is an equivalence relation". Turns out I was wrong. It has a very specific meaning that Wikipedia describes thusly:

  Given any binary relation $A \subset X \times X$ on $X$, the equivalence relation generated by $A$ is the intersection of the equivalence relations on $X$ that contain $A$.

In short, no, "represents" isn't a symmetric relation, nor did Knuth claim it is; he claimed that an equivalence relation could be constructed from it, which is true. Apparently my "knowledge of high school algebra", listed as the primary prerequisite to reading, is lacking.


Bertrand's ballot theorem I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem.
it is this

If i number of people voted for A and j number of people voted for B then dp[i][j] counts the number of ways voting can happen.

dp[ i ] [ j ] = dp[ i ] [ j - 1 ] + dp[ i - 1 ] [ j ] .

basically, I want to find the number of ways candidate A is in the winning position throughout.
Can anyone explain the logic behind the dp equation ?
I think it works like this.
We have a sequence of A and B.In which A wins throughout. Now we add one more A to that sequence or add one more B to it.

Let $N(p,q)$ be the number of sequences containing $p$ many A's and $q$ many B's, such that in every non-empty prefix, the number of A's strictly exceeds the number of B's. Clearly $N(p,q) = 0$ if $q \geq p$ and $q > 0$. When $p = q = 0$ there are no non-empty prefixes, and so $N(p,q) = 1$.

Suppose therefore that $p > q$, and consider any sequence satisfying the condition. If we remove the last element, we still get a sequence satisfying the condition. Conversely, whatever element we add, the resulting sequence will satisfy the condition, since $p > q$. We conclude that
$$
N(p,q) = \begin{cases}
1 & \text{ if } p=q=0, \\
0 & \text{ if } q \geq p \text{ and } q > 0, \\
N(p-1,q) + N(p,q-1) & \text{ if } p > q > 0, \\
N(p-1,q) & \text{ if } p > q = 0.
\end{cases}
$$


Why does P/Poly can also receive bad advice? (from my class's slides)

"NP and P/Poly both use an external string for computation. However, for L in NP, any witness is rejected if x $\notin$ L. For L in P/Poly, there can be bad advice!"

I'm having a hard time understanding why this is true. My intuition is that if there are indeed 'bad advice', i.e advice that make the Turing Machine return bad answers, doesn't it mean that a situation where ALL of the advice are 'bad' is technically possible?

Lets review the definition of the class $P/poly$ by Turing machines which take advice.

The class $T(n)/a(n)$ is the set of languages decidable by a Turing machine which runs in time $T(n)$ with advice of length $a(n)$.

More formally, $L\in T(n)/a(n)$ if there exists a Turing machine $M(x,y)$ and a sequence of strings $\left\{\alpha_n\right\}_{n\in\mathbb{N}}$, with $\alpha_n\in\left\{0,1\right\}^{a(n)}$, such that for all $x\in\left\{0,1\right\}^n$ $M$ runs in time $T(n)$ and $x\in L \iff M(x,\alpha_n)=1$.

$P/Poly=\bigcup\limits_{c,d}n^c/n^d$.

As you can see in the definition above, we only require the existence of some sequence of advice $\alpha_n$ that we can trust. Perhaps for some different sequence, $\beta_n\in\left\{0,1\right\}^{a(n)}$, and some $x\notin L$, it holds that $M(x,\beta_{|x|})=1$, but we don't care, since we only required the existence of a "good" sequence of advice.

This is unlike the case with $NP$, where if $x\notin L$, all witnesses must be rejected.


$\lambda$-calculus with reflection I'm looking for a simple calculus that supports reasoning about reflection, namely, the introspection and manipulation of running programs.

  Is there an untyped $\lambda$-calculus extension that enables one to convert $\lambda$-terms into a form that can be syntactically manipulated and then subsequently evaluated?

I imagine that the calculus has two main additional terms:

$\mathtt{reflect}\ v$: takes $v$ and produces a representation of $v$ amendable to
syntactic manipulation.
$\mathtt{eval}\ v$: takes a syntactic representation of a term and evaluates it.

In order to support reflection, a syntactic representation of terms is required. It would look something like:

$\lambda x.e$ would be represented as a term $(\mathsf{LAM}\ R(e))$, where
$R(e)$ is the reflected version of $e$,
$e\ e'$ would be represented as term $(\mathsf{APP}\ R(e)\ R(e'))$, and
$x$ would be represented as $(\mathsf{VAR}\ x)$.

With this representation, pattern matching could be used to manipulate terms.

But we run into a problem. $\mathtt{reflect}$ and $\mathtt{eval}$ need to be encoded as terms, as does pattern matching. Dealing with this seems to be straightforward,
adding $\mathsf{REFLECT}$, $\mathsf{EVAL}$ and $\mathsf{MATCH}$, but will I need to add other terms to support the manipulation of these?

There are design choices that need to be made. What should the $R(-)$ function alluded to above do with
the body of $\mathtt{reflect}$ and $\mathtt{eval}$? Should $R(-)$ transform the body or
not?

As I am not so much interested in studying reflection itself -- the calculus would serve as a vehicle for other research -- I do not want to reinvent the wheel.

  Are there any existing calculi that match what I have just described?

As far as I can tell, calculi such as MetaML, suggested in a comment, go a long way, but they do not include the ability to pattern match and deconstruct code fragments that have already been built.

One thing I would like to be able to do is the following:

$\mathtt{let}\ x=\lambda y.y\ \mathtt{in}\ \mathtt{reflect}\ x
\to (\mathsf{LAM}\ (\mathsf{VAR}\ y)\ (\mathsf{VAR}\ y))$

And then perform pattern matching on the result to build a completely different
expression.

This is certainly not a conservative extension to the $\lambda$-calculus and the meta-theory is likely to be ugly, but this is kind of the point for my application. I want to break $\lambda$-abstractions apart.

Jean Louis Krivine introduced an abstract calculus which extends the "Krivine Machine" in a very non-trivial way (note that the Krivine machine already supports the call/cc instruction from lisp):

He introduces a "quote" operator in this article defined in the following manner: if $\phi$ is a $\lambda$-term, note $n_\phi$ the image of $\phi$ by some bijection $\pi: \Lambda \rightarrow \mathbb{N}$ from lambda terms to natural numbers. Note $\overline{n}$ the church numeral which corresponds to $n\in\mathbb{N}$. Krivine defines the operator $\chi$ by the evaluation rule:
$$ \chi\ \phi \rightarrow \phi\ \overline{n_\phi}$$
I believe Kleene wizardry will show that this is sufficient to do what you wish: i.e. define a quote and eval operators, if $\pi$ is computable.

Note that Krivine is notoriously challenging to read (please don't get mad if you read this, Jean-Louis!), and some researchers have done the charitable act of trying to extract the technical content in a more readable manner. You might try to take a look at these notes by Christophe Raffali.

Hope this helps!

It occurs to me that there is another reference that may be relevant to your interests: the Pure Pattern Calculus by Jay and Kesner formalizes a variant of the $\lambda$-calculus which extends simple abstraction over a variable to an abstraction over a pattern representing a pattern calculus itself. This is phenomenally expressive and in particular allows one to deconstruct an application itself: if I am not mistaken, the term:

$$ (\lambda (x\ y). x)((\lambda x.x\ x)\ (\lambda y.y)) $$

reduces to $\lambda x.x\ x$. Again, I belive that this is more than enough to implement the quote and eval operators.


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

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

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


Can we find the largest intersecting subfamily of convex polygons in quadratic time? Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (you can assume general position, no two vertices are the same, no edges intersects a vertex other than its endpoints, no three edges intersect at the same point).
I'm curious to know if you can you compute a subfamily of largest cardinality possible such that all polygons share a single common intersection point in $\mathcal{O}(n^2)$ time? (In the Real RAM model, i.e. you can store an arbitrary precision real number in a register and perform arithmetic operations on them in constant time)
The best I've managed to come up with is $\mathcal{O}(n^2\log(n))$:

I can modify the Bentley-Ottman algorithm (with the segments being the polygon edges) so that at every event point $p$, I count the number of "lower hull" edges and "upper hull" edges under $p$ on the sweep line (modifying my search tree so this can be done in $\mathcal{O}(\log(n))$ time) and compute the difference, giving me the number of polygons containing $p$. I simply keep track of the "best" point $p$, then test every polygon against $p$ in $\mathcal{O}(n)$ total time.

Alternatively, by computing the $\mathcal{O}(m^2)$ points which are the leftmost in the intersection of a pair of polygons (which can be shown to be doable in $\mathcal{O}(nm)$ time) and then counting the total number of polygons which contains each point (in $\mathcal{O}(nm^2)$ time), you can solve the problem in $\mathcal{O}(nm^2)$ time, which is better for small $m$ (and you can probably also get $\mathcal{O}(n^\alpha m^\beta)$ for different values of $\alpha + \beta > 2$ using more sophisticated simplex range counting datastructures).
Is anything faster possible (asymptotically)?
Or is there some (conditional) lower bound showing that $\mathcal{O}(n^2)$ is hard/impossible to achieve?

As Discrete lizard pointed out in a comment, I misinterpreted the statement of "sharing a common point", which I read as "pairwise sharing a common point".
You can thus ignore the below answer.  I will delete it later.

I'm not an expert in this area but I do actually believe that the problem you are talking about is surprisingly enough NP-complete.
The problem, known as Maximum Clique in convex planar sets (graph class: Conv)  was proved NP-hard by Kratochvíl and Kuběna [1] who write the following:

We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This fact has a complexity consequence — it follows that the problem of determining the clique number of an intersection graph of convex sets in the plane is NP-hard. We note that the complexity of this problem for intersection graphs of straight line segments in the plane is unknown.

[1] Kratochvíl, Jan, and Aleš Kuběna. "On intersection representations of co-planar graphs." Discrete Mathematics 178.1-3 (1998): 251-255


Complexity of (SAT to 3-SAT) Problem? It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula  by using new variables (see here). If using new variables is not allowed, it is not always possible (take for instance the single clause formula : $(x_1 \lor x_2 \lor x_3 \lor x_4)$).

Let define the (SAT to 3-SAT) problem : Given $F$, a CNF formula. Is it possible to transform $F$ into an equivalent 3-CNF defined on the same variables as $F$ ? - where "equivalent" means with the same set of models.

What is the complexity of this problem ?

Edit : It has been shown on cstheory that the problem is co-NP hard.

This has been answered on the CS Theory StackExchange site:
https://cstheory.stackexchange.com/a/19833/5038

(I'm posting an answer here, so this question does not get treated as a question-without-an-answer and get periodically rotated back onto the front page by the Community user.  Normally, questions without any upvoted or accepted answer are re-displayed on the front page every so often.  Since this question now has been solved answered elsewhere, there doesn't seem any need for that.  As long as someone upvotes or accepts this answer, that should prevent this question from being rotated back onto the front page.  I'm ticking the community wiki box so I won't get any rep from this answer.)


Does applying Hadamard gate is identical to applying a measurement gate that is perpendicular to the current qubit state? Cause applying H (hadamard gate) on a state |0> will evolve to 50% |0> and 50% |1>, assuming we are meausring along the vertical axis (Z-axis).

While applying a measurement along a horizontal axis (e.g. X-axis), will force the state to "evolve" (destroied) and let it be perpendicular to the vertical axis. In another word the state now will have a 50% chance to be measured along the vertical axis to be |0> and 50% to be |1>.

I know that measuring a state will destroy the state, while H gate is unitary and conserves the state from destruction. But I really need to know how the physics behind the Quantum Computer gates.

As Yuval points out, you have already answered your own question. If I have a state $|q\rangle = a|0\rangle + b|1\rangle$ and I apply a Hadamard gate to that state, I end up with a new state: $$H\cdot|q\rangle = \frac{1}{\sqrt{2}}(a+b)|0\rangle + \frac{1}{\sqrt{2}}(a-b)|1\rangle$$

However, if I measure the state $|q\rangle$ in the standard basis, I get either $|0\rangle$ with probability $|a|^2$ or $|1\rangle$ with probability $|b|^2$. Notice that both $|0\rangle$ and $|1\rangle$ are different states than what you would have gotten had you applied the Hadamard transform instead of a measurement. I admit that a Hadamard-transformed state of 50% $0$ and 50% $1$ looks very much like having done a measurement, but this is not true: you haven't done the measurement yet, and the state is still in superposition. This matters if you do other transformations afterward, or if you work in a multi-qubit system. Then when measuring later, it matters whether you did a Hadamard transform or a measurement.

A good thing to do to acquaint yourself with transformations and measurements is to just compute some by hand on one qubit and on two qubits, and to write out in full the intermediate states in Deutsch's algorithm. You'll get the hang of it.


What is the Code2 and other concepts of variable encoding in Coding Redundancy? Am learning the concept of Coding Redundancy in image compression and am finding it hard to understand the table on page 3 of this document. All other explanations seem to follow the same symbols and methodology but don't explain the concept clearly.

Question1:
In the first column, r1=1/7, r2=2/7 etc and r7 is 1. Why is that? According to the column "Code1", the Code1 is created based on the r value which should range from 0 to 7. Why then are there fractions like 1/7, 2/7 etc?

Question2:
What is "Code2"? At least for Code1, when the value is 000, I know it is the binary representation of 0. But the same thing in Code2, is 11. I don't understand what and how they are trying to represent with Code2.

Question3:
Even if 0 is represented by 11 and 6 is represented by 000001 in variable length encoding, how is the algorithm supposed to know which 0 starts where and which 1 ends where? For example, to represent 60, I'd have to encode it as 00000111. When decoding, how is the algorithm supposed to know that it's 60?

In the first column, $r_k$ is the gray level. It ranges from 0 to 1, where 0 is 0% white (i.e., black) and 1 is 100% white. There are 8 gray levels arranged in regular intervals of 1/7.

Code 1 and Code 2 are two different ways of encoding the gray level. Code 1 is a fixed-length code (all codewords have the same length) whereas Code 2 is a variable-length code, specifically a prefix code, presumably a Huffman code for the distribution in the second column. Code 2 is better because the expected codeword length is 2.7 bits, which is smaller than the 3 bits that you get with Code 1.

Since Code 2 is a prefix code, decoding it is actually very simple, and requires no lookahead. (That's why prefix codes are sometimes called instantaneous codes.)


When is the AKS primality test actually faster than other tests? I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality testing on computers.

The test has polynomial runtime but with high degree and possible high constants. So, in practive, at which $n$ does it surpass other primality tests?
Here, $n$ is the number of digits of the prime, and "surpass" refers to the approximate runtime of the tests on typical computer architectures.

I am interested in functionally comparable algorithms, that is deterministic ones that do not need conjectures for correctness.

Additionally, is using such a test over the others practical given the test's memory requirements?

Quick answer:  Never, for practical purposes.  It is not currently of any practical use.

First, let's separate out "practical" compositeness testing from primality proofs.  The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate.  For numbers under 2^64, no more than 7 Miller-Rabin tests, or one BPSW test is required for a deterministic answer.  This will be vastly faster than AKS and be just as correct in all cases.  For numbers over 2^64, BPSW is a good choice, with some additional random-base Miller-Rabin tests adding some extra confidence for very little cost.  Almost all of the proof methods will start out (or they should) with a test like this because it is cheap and means we only do the hard work on numbers which are almost certainly prime.

Moving on to proofs.  In each case the resulting proof requires no conjectures, so these may be functionally compared.  The "gotcha" of APR-CL is that it isn't quite polynomial, and the "gotcha" of ECPP/fastECPP is that there may exist numbers that take longer than expected.

In the graph, we see two open source AKS implementations -- the first being from the v6 paper, the second including improvements from Bernstein and Voloch and a nice r/s heuristic from Bornemann.  These use binary segmentation in GMP for the polynomial multiplies so are pretty efficient, and memory use is a non-issue for the sizes considered here.  They produce nice straight lines with a slope of ~6.4 on the log-log graph, which is great.  But extrapolating out to 1000 digits arrives at estimated times in the hundreds of thousands to millions of years, vs. a few minutes for APR-CL and ECPP.  There are further optimizations which could be done from the 2002 Bernstein paper, but I don't think this will materially change the situation (though until implemented this isn't proven).

Eventually AKS beats trial division.  The BLS75 theorem 5 (e.g. n-1 proof) method requires partial factoring of n-1.  This works great at small sizes, and also when we're lucky and n-1 is easy to factor, but eventually we'll get stuck having to factor some large semi-prime.  There are more efficient implementations, but it really doesn't scale past 100 digits regardless.  We can see that AKS will pass this method.  So if you asked the question in 1975 (and had the AKS algorithm back then) we could calculate the crossover for where AKS was the most practical algorithm.  But by the late 1980s, APR-CL and other cyclotomic methods was the correct comparison, and by the mid 1990s we'd have to include ECPP.

The APR-CL and ECPP methods are both open source implementations.  Primo (free but not open source ECPP) will be faster for larger digit sizes and I'm sure has a nicer curve (I haven't done new benchmarking yet).  APR-CL is non-polynomial but the exponent has a factor $\log \log \log n$ which as someone quipped "goes to infinity but has never been observed to do so".  This leads us to believe that in theory the lines would not cross for any value of n where AKS would finish before our sun burned out.  ECPP is a Las Vegas algorithm, in that when we get an answer it is 100% correct, we expect a result in conjectured $O(\log^{5+\epsilon}(n))$ (ECPP) or $O(\log^{4+\epsilon}(n))$ ("fastECPP") time, but there may be numbers that take longer.  So our expectation is that standard AKS will always be slower than ECPP for almost all numbers (it certainly has shown itself so for numbers up to 25k digits).

AKS may have more improvements waiting to be discovered that makes it practical.  Bernstein's Quartic paper discusses an AKS-based randomized $O(\log^{4+\epsilon}(n))$ algorithm, and Morain's fastECPP paper references other non-deterministic AKS-based methods.  This is a fundamental change, but shows how AKS opened up some new research areas.  However, almost 10 years later I have not seen anyone use this method (or even any implementations).  He writes in the introduction, "Is the $(\lg n)^{4+o(1)}$ time for the new algorithm smaller than the $(\lg n)^{4+o(1)}$ time to find elliptic-curve certificates?  My current impression is that the answer is no, but that further results [...] could change the answer."

Some of these algorithms can be easily parallelized or distributed.  AKS very easily (each 's' test is independent).  ECPP isn't too hard.  I'm not sure about APR-CL.

ECPP and the BLS75 methods produce certificates which can be independently and quickly verified.  This is a huge advantage over AKS and APR-CL, where we just have to trust the implementation and computer that produced it.


How come O(n) + O(logn) = O(logn) How come O(n) + O(logn) = O(logn)?

When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is O(logn). It doesn't make sense to me since n is bigger than logn.

As Chi say to you, if you have in a program two operations, one $\mathcal{O}(log{}n)$ and another $\mathcal{O}(n) $ you must take a superior bound, and your result will be $\mathcal{O}(n)$ in this case.

you can see here the complexity graph.
If you say, that one operation take time $\mathcal{O}(n) $ , and nobody other operations take more of this, you can be at least $\mathcal{O}(n) $ time complexity.
If just one operation are over $\mathcal{O}(n) $, the complexity will be change in new bound (and so on).

P.s Sum two bound, will maintain the most higher, multiply  increse time complexity, like two neasted loop of $\mathcal{O}(n)$ will give you $\mathcal{O}(n^2)$ complexity.

I hope that this will help you.


How is algorithm complexity modeled for functional languages? Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case in pure functional languages. The Haskell list takes linear time for access. Modifying a node in a tree involves making a new copy of the tree.

Should then there be an alternate modeling of algorithm complexity for functional languages?

If you assume that the $\lambda$-calculus is a good model of functional programming languages, then one may think: the $\lambda$-calculus has a
seemingly simple notion of
time-complexity: just count
the number of $\beta$-reduction
steps $(\lambda x.M)N \rightarrow M[N/x]$.

But is this a good complexity measure?

To answer this
question, we should clarify what we mean by complexity measure in the
first place. One good answer is given by the Slot and van Emde
Boas thesis: any good complexity measure should have
a polynomial
relationship to the canonical notion of time-complexity defined using
Turing machines. In other words, there should be a 'reasonable'
encoding $tr(.)$ from $\lambda$-calculus terms to Turing machines, such for some polynomial $p$, it is the case that for
each term $M$ of size $|M|$: $M$ reduces to a value in $p(|M|)$ $\beta$-reduction steps exactly
when $tr(M)$ reduces to a value in $p(|tr(M)|)$ steps of a Turing machine.

For a long time, it was unclear if this can be achieved in the λ-calculus. The main problems are the following.

There are terms that produce normal forms (in a polynomial number of steps) that are of exponential size. Even writing down the normal forms takes exponential time.
The chosen reduction strategy plays an important role. For example there exists a family of terms which reduces in a polynomial number of parallel β-steps (in the sense of optimal λ-reduction), but whose complexity is non-elementary (meaning worse then exponential).

The paper "Beta Reduction is Invariant, Indeed" by B. Accattoli and  U. Dal Lago clarifies the issue by showing a 'reasonable' encoding that preserves the complexity class P of polynomial time functions,  assuming leftmost-outermost call-by-name reductions. The key insight is the exponential blow-up can only happen for 'uninteresting' reasons which can be defeated by proper sharing. In other words, the class P is the same whether you define it counting Turing machine steps or (leftmost-outermost) $\beta$-reductions.

I'm not sure what the situation is for other evaluation strategies.
I'm not aware that a similar programme has been carried out for space complexity.


Find k compatible objects with minimum total penalty Assume we have a set of $n$ objects $X=\{x_1,x_2,\ldots,x_n\}$, where each object $x_i$ has a penalty $p_i$. Additionally, we have a set of incompatibility constraints $C=\{(x_i,x_j),\ldots\}$, where a tuple $(x_i,x_j)$ says that object $x_i$ is incompatible with object $x_j$.  The problem is to find a subset $Y$ of $k<n$ compatible objects that minimize the sum of penalties, i.e. $\min_{Y} \sum_{x_i \in Y} p_i$. The objects in $Y$ need to be compatible, i.e. $\forall x_i,x_j \in Y: (x_i,x_j) \not\in C$.

Let me make an example. Assume we have 4 objects $X=\{x_1,\ldots,x_4\}$ with penalties $p_1 = 2,\ p_2 = 0.1,\ p_3=3,\ p_4=100$. Furthermore the following incompatibilities are given: $C=\{(x_1,x_2),\ (x_2,x_3),\ (x_3,x_4)\}$. The $k=2$ compatible objects that minimize the function are $Y = \{x_1,x_3\}$ with a total penalty of $5$. Object $x_2$ with the least penalty is not part of the solution, because the only compatible object is $x_4$ with a penalty $p_4=100$.

I have two questions:

Is this problem already known under some name or a variation of a known problem?
Is there an efficient (polynomial time) algorithm to solve it?

Well, the graph is obvious, isn't it? Independent set


How can a 16-bit or more processor store a byte in a byte-addressed memory I am confused as to how a 16-bit (or 32, 64) processor can store multiple adjacent bytes at once without supplying multiple addresses

For example say we have (16-bit processor) 0xABCD starting at address 0x0000. For loading, the processor would just supply 0x0000 on the address bus and the way the bytes are laid out physically would produce 0xABCD on the data bus, then the processor would just do some neat bit-shifting to get the correct byte of the word

But for storing a byte, lets say 0xCD at address 0x01, what would the processor do about the other byte? (i.e. what would it do about location 0x00)

Thanks

EDIT: I am asking about big-endian architecures

For a one-byte read to address 0x01, the CPU can read a 16-bit value and discard half of it.

For a one-byte write to address 0x01, if the memory architecture doesn't support that directly, the CPU needs to read the 16-bit value at 0x00, then replace the second byte with 0xCD, then write a 16-bit value to 0x00.


Finding the middle point of the "most populated" area in a set of points? I'm working on a game-related application, and I'm trying to find the middle point of the most populated area in my map.
Example:
Positions (format [x, y]) :

[48, 49]
[51, 50]
[49, 50]
[51, 49]
[49, 48]
[130, 150]
[129, 148]

Excepted output : [50, 50] or something close enough like [49, 51], [51, 50]

To create this algorithm I've access to all entities position (X/Y)
I've tried by creating a position using X average and Y average but it's not what i'm looking for (using example values output would have been [75, 75] or something like this and not [50, 50] as excepted)
Here is an example image:
Red dot: Entities
Green dot: Position i'm looking for

Thanks for reading and for your help!

What you are looking for is called cluster analysis or a clustering algorithm. It's a topic studied in unsupervised machine learning, so there's not necessarily a single "best" algorithm that exists (rather, there are different methods which are meant to optimize for different metrics). For example, do you want your clusters to all be similar size? Do you want a fixed number of clusters, or a variable number of clusters? Different answers to these questions result in different algorithms, so you will have to do some research (or try out directly) the different clustering algorithms available. For example, one of the classic algorithms is called k-means clustering.
Once you find the clusters, you can take the average of the points in the biggest cluster to solve your problem.
You don't have to implement the algorithm yourself -- many machine learning libraries (scikit-learn, Pytorch, ...) have out-of-the-box clustering procedures that you can try out and see what they look like for your dataset.


Which has optimum performance? raw core or multithreaded Let's say there's a single process performed in the machine which utilizes all available processors (whether physical or logical processors). The process use 100% processor utilization most of the time on all processors.
Which machine will perform better?

Machine with 2 cores, 1 thread per core (2 physical processors); or the
Machine with 2 cores, 2 threads per core (4 logical processors)

This is assuming everything (memory, clock speed, etc) is the same and the only thing that differ is the number of threads.
My initial thoughts would be that the former -- machine with 2 raw cores (1 thread) -- will perform better because it doesn't have context switching. Whereas the latter would have overhead on the context switching.
Which machine will perform better?

There's no real way to answer this without a lot of details about both the code to be executed, and the micro-architecture of the CPU executing the code.
A CPU that can execute multiple threads per core will typically start with a pool of instructions, decoded and ready to execute. As instructions enter the pool, a scoreboard1 gets updated to reflect inputs to an instruction, execution resource(s) needed by that instruction, and the output of the instruction.
So you might have an instruction like add r0, r1, r2, meaning add register 0 to register 1 and put the result in register 2. The inputs are registers 0 and 1, the execution resource needed is an integer adder, and the output is register 2.
Then there's a scheduler that looks at the resource usage and tries to find instructions that don't conflict, and each clock cycle, tries to find as many of those as possible to execute. As it does so, it updates the scoreboard so the next clock cycle, it'll know what resources are in use now.
That all leads to the basic question: given the parallel resources provided by this CPU, and the instructions in the streams to be executed, what is the average level of conflict between instructions?
The drastically simplified answer is that more often than not, executing two independent streams of instructions will result in more instructions that can execute with fewer conflicts, so overall speed will increase much more often than not. It's rarely a question of which is faster--only of how much speed you'll gain by executing more threads in parallel, and whether that gain is enough to justify the extra labor to make that work, or whether you'd have gained more by expending more the CPU budget on other things that could have made an even bigger difference (e.g., bigger cache, better branch prediction, etc.)
Goal
There's also room for a bit of question about your goal here. A single core executing two threads will typically execute each thread a little slower than that thread would execute on a core by itself. On the other hand, the overall throughput of the system will be somewhat greater than if you ran only one thread at a time.
For example, if you had a CPU that was split almost perfectly between two threads, each might run at 60% of the speed it would if it was the only thread running on a core.
So, if you really care almost exclusively about the performance of one thread, then running only one thread per core may well improve the speed of a thread when it is running.
At the same time, if you have two threads each running at 60% the speed it would on its own, your overall speed is 120% of what it would be with each thread running on its own, meaning you're getting about 20% more work done per unit time.
In a game (for one example) it's pretty common to have one thread that really matters, so you really want to optimize performance for one thread. If that's your case, you probably only want one thread per core.
On the other hand, with something like a server you often have lots of requests happening all the time, and one major concern is maximizing overall throughput. In such a case, more threads per core can make a lot more sense (but also note that total throughput isn't usually the only concern even in this case).
CPU Utilization
Since "CPU Utilization" was mentioned in a comment, I'll comment on it a bit as well. Generally speaking, when an operating system reports something like percentage of CPU utilization, it's basically irrelevant to questions like this.
An OS is basically just reporting what percentage of CPUs have threads assigned to execute on them at any given time. For example, if a single-threaded CPU executes an instruction to read from main memory, it could easily take 50-100 clock cycles to execute a single instruction. According to the OS, that's keeping the CPU 100% busy for those clock cycles--but most of the CPU's actual resources would be available, so it could perfectly well execute other instructions during that time.

Well, the early versions were called "scoreboards". More recently there are more complex structures with other names, but I'm going to call all of them scoreboards to keep things simple.


Weighted Matching with multiple assignments and min assignments I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, each professor also has a minimum number of students he needs. So even though all students maybe matched best with one professor, some need to distributed amongst the rest, as long as they can be matched of course -- since not all professors and students will have edges between them.

Standard Bipartite matching won't work since they match one to one. Max Flow won't work since they don't consider weights.

Your problem can be solved with minimum-cost network flow, by solving a circulation problem.  The circulation problem is a variation on network flow where edges have an upper bound on the amount of flow through that edge (called the capacity of the edge), a lower bound on the amount of flow through the edge, and a per-unit cost for sending flow through the edge.  In your problem, you have a source vertex $s$, a vertex $v_i$ for each professor, a vertex $w_j$ for each student, and a sink vertex $t$.  You have edges $s \to v_i$, $v_i \to w_j$, and $w_j \to t$.  You put a lower bound on the edge $s \to v_i$ corresponding to the number of students who professor $i$ must be matched with, an upper bound of $1$ on each edge $v_i \to w_j$, and a cost on the edge $v_i \to w_j$ that corresponds to the negative of the weight.  There exist polynomial-time algorithms to solve this variant of network flow.


Is it reasonable to model row buffers in DRAM corresponding to the same bank ID as one big row buffer? I'm creating a simple row buffer simulator to go along with a simple cache simulator in order to count hits and misses in the row buffer. Whenever a cache block isn't in the cache I want to go look for it in the row buffers of the main memory and record whether it is present of not.

How accurate would it be to have just one long "row buffer" struct containing all the data found in all the individual row buffers of each corresponding bank in each DRAM chip? Say that each chip has 8 banks, I would then have to create 8 of these extra long row buffers to simulate these chips. This idea is based on the understanding that all these chips work in unison, so that if I want to load the cache block at address 0, the row buffers of bank 0 in each chip would fill with data from addresses starting at address 0 in chip 0, and ending at address 0 + (length of row buffer * number of DRAM chips) in the last chip. It would assume a row interleaved address mapping (with consecutive rows in consecutive banks) for simplicity's sake.

Are there any major misunderstandings about how DRAM works that causes this to be a very bad way to model row buffer behavior or is this a reasonable simplification? I'd also like to underscore that simplicity is the main goal here.

EDIT added clarification on question posted in comments below:
I assume that all the row buffers for banks with ID, say, 0 work together in unison on the same read or write, with all of them containing data for that particular operation. Couldn't I model these 8 row buffers (if I have 8 DRAM chips) as just one very big row buffer? The total size of this combined row buffer would be the length of the normal row buffer*number of DRAM chips. So if I were to a model chips with 8 banks for example, I'd have 8 of these "combined" row buffers, one for each bank.

You can look at how one of the existing DRAM simulators work. Consider, for example, Ramulator, which is a popular academic DRAM simulator. Ramulator Models main memory as a tree of nodes, where the root node represents a memory channel and lower nodes represent ranks, bank groups (supported in DDR4), banks, rows, and columns. For the DRR4 and DRR3 protocols, these levels are defined in the source code here and here, respectively. Therefore, the physical row buffer of each chip of the same bank are actually treated as a single row buffer whose state is maintained using a single value.


Is $a^n b^m$ never regular if n and m have some relation between them? I know what regular and context free language are and how regular language needs finite memory and other stuff.

What concerns me is that I think if $a^nb^m$ such that $n$ and $m$ have some relation between them then they can not be regular. But I can't find any such thing written anywhere. Am I correct to state so?

For a relation $R(n,m)$, let $L_R = \{ a^n b^m : R(n,m) \}$. Call a relation residual if for some $k \geq 1$ and for some $A \subseteq [k]^2$,
$$ R(n,m) \Leftrightarrow (n,m) \pmod{k} \in A. $$
Call a relation semi-residual if it differs from a residual relation by a finite number of points.

Claim: $L_R$ is regular iff $R$ is semi-residual.

Proof: It is not hard to check that if $R$ is semi-residual then $L_R$ is regular. For the other direction, consider an automaton for $L_R$. For each state $\sigma$, let $L_\sigma$ be the set of all $n$ such that upon reading $a^n$, the automaton reaches $\sigma$. Since $L_\sigma$ is unary, it is eventually periodic. By taking the least common multiple of all periods, we see that the state that for $n \geq n_0$, the automaton find itself upon reading $a^n$ depends only on $n\pmod{k_a}$ from some $k_a$. Doing the same for $b^m$, we see that for $n \in L_\sigma$, the set of all $m$ such that $a^n b^m \in L$ is eventually periodic, and so for $m \geq m_0$, depends only on $\sigma$ and on $m\pmod{k_b}$ for some $k_b$. Taking $k$ to be the LCM of $k_a,k_b$, we find that for $n \geq n_0, m \geq m_0$, $a^n b^m \in L$ depends only on $(n,m) \pmod{k}$. Hence the corresponding $R$ is semi-residual.


Proof by mathematical induction Before we start, my textbook declares lgn as base two.

I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even matter?

Since we're using base-$2$ logs, $\log2=1$, so $$n(\log n-\log 2) = n\big((\log n)-1\big)=n\log n -n\,.$$

All of the stages of the calculation are written as equalities, so nothing should be being discarded as too small to matter (and nothing is).


CRC computation speed vs polynomials features I tried to find information about how features of a CRC polynomials influence computation speed of implementations.

It is obvious that (depending from the CPU architecture the algorithm runs on) algorithms can be optimized for special CRC widths.

However, even when comparing CRC polynomials of the same width there still seems to exist differences in computation speed:

I read a statement that low polynomial weights would
increase computation speed.
Also Prof. Koopman wrote on his 6sub8 CRC page: "Consider only
polynomials with bits set in the bottom 8 bits (in addition to the
topmost bit). This can help speed up computation and reduce lookup
table sizes for CRC calculations in application programs."

I can see why pre-calculated CRC tables can be more compact using a sub8 polynomial.
But I could not wrap my mind around the speed related statements. All implementations I had a look at (various C implementation of bit-wise and table-based algorithms) seem not to benefit from low-weight or sub8 polynomials.
Maybe I missed the point or there are environments (like other algorithms, hardware implementations, special CPU architectures) that would benefit.

My question:
Given a certain CRC width, in which way and under which circumstances does a low polynomial weight and/or a sub8 polynomial speed-up the computation of a CRC?

The speed issue would depend on the hardware / processor. For CRC, what is needed is carryless multiply (CLMUL), and I assume most processors that have carryless multiplies, which date back to 2008 for X86 processors (pclmulqdq using xmm registers) the multiply time is fixed. For a typical hardware implementation, since the multiply is carryless, there's no propagation delay related to carry operations and all the XOR operations occur in parallel.

For standard multiplies (with carry), old processor multiply times were affected by the weight of the multiplier, but multiply times on processors since around 2010 or a bit before have fixed multiply times (for X86, it's 3 clocks). I'm not aware of a carryless multiply that isn't fixed in time, but it could exist on some processor I'm not aware of.


Mean and median distance in unweighted graph I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds.   The graph is an unweighted directed strongly connected graph.

I need to find the mean and median distances of the graph (median and mean distances over all shortest-path distances of the graph). I need the exact mean/median, not an approximation. This problem must be related to all-pairs shortest paths. But the only algorithms I know of for this problem are: Floyd Warshall, Dijkstra starting from each vertex, and Breadth First Search starting from each vertex. However, their running time is $\Omega(V^2)$ for all three of these algorithms, so for such a large graph they are too slow.

Can this problem be solved in linear or linearithmic time?  If not, what is the fastest algorithm for this problem, in asymptotic complexity?

(This is not a full answer.)

The median distance is necessarily an integer [footnote 1].  Therefore, it might be possible to use an approximation algorithm for the median to compute the exact median, if the approximation is sufficiently precise.

Suppose the true median is $\xi$.  Then if we can efficiently compute a $1+1/3\xi$-approximation to the median, we can reconstruct the exact median from that.

I suspect it is possible to get a $\tau$-approximation to the median efficiently through random sampling.  In particular, consider the following procedure:

Repeat $k$ times: in the $i$th iteration, pick a random vertex $v_i$, compute single-source shortest paths from $v_i$ to every vertex, and find the distribution of these distances.
Aggregate these distributions and output the median of this aggregated distribution.

One might hope to get an approximation whose quality increases rapidly with $k$, and where if we want a constant approximation factor $\tau$, then a constant $k$ suffices.  I have no proof that this is possible, though.

We can consider a simpler situation, where given an integer $x$ we are trying to approximately count the fraction of distances that are at most $x$.  If the fraction of such distances is approximately $1/2$ (e.g., because $x$ is approximately the median), then one approach is random sampling: repeat $k$ times where we pick a random pair of vertices $u,v$ and compute the distance from $u$ to $v$ (say using BFS), then count what fraction of those $k$ distances are at most $x$.  The additive error is typically about $1/2\sqrt{k}$; it exceeds $c/\sqrt{k}$ with probability exponentially small in $c$ (it's basically the probability of a Gaussian being more than $2c$ standard deviations away from the mean).  Thus, we can get a $1+\epsilon$-approximation to this count using $O(1/\epsilon^2)$ iterations.  Each iteration takes at most $O(E)$ time, so with $O(E/\epsilon^2)$ time we can get a $1+\epsilon$-approximation to this count.  The probability that our approximation is wrong can be made exponentially small; an error probability of $1/2^{100}$ is so small as to be negligible in practice (e.g., it is smaller than the probability of a cosmic ray causing a bitflip error that causes an error in your code), and this will increase the running time by only a constant factor (say, 100, or something like that).  In this case it might be sufficient to also take $\epsilon$ to be a small constant.

Intuitively, it feels like if we can get a good approximation to this count, it might be possible to extend this to a good approximation to the median.  For instance, if we hypothesize that the median is $x$, we can count the fraction of distances that are $\le x-1$, the fraction that are $\le x$, and the fraction that are $\le x+1$.  If $x$ is indeed the median, hopefully the first fraction will be noticeably smaller than $1/2$ and the latter fraction will be noticeably larger than $1/2$.  I don't know how to turn this into an algorithm that I can prove will always work on all graphs, but I suspect this might work well enough in practice.

Computing the (exact) mean seems like it might be harder, as the mean isn't necessarily an integer.

Footnote 1: The median is either an integer or halfway between two integers.  In the latter case, the rest of the answer carries through if you divide everything by two.


What is a program in self-replicating programs? I'm trying to understand the workings of artificial life as exemplified by systems like Tierra or Avida. The idea behind these systems is that organisms are modeled as assembly-language programs that replicate themselves in the memory of a computer, possibly a virtual machine. But here there is already something I don't understand (I'm not a programmer by vocation or by nature).

My idea of a computer's memory is that it's basically just a list of instructions. By default control proceeds from a given instruction to the next one in the list, but the instruction itself can send control someplace else. My question is: which sublists of this list of instructions count as programs?

Presumably the memory can be partitioned (in the set-theoretic sense) into a bunch of programs (actually copies of programs, since distinct "organisms" are allowed to have the same "genome"), plus some empty space; how does one do this?

The computer's operating system keeps track of which pieces of memory make up which program. The partition into programs is entirely arbitrary, and the only reason a section of memory counts as program is because there is a specially designated piece of memory that keeps a list of all "programs" and their memory locations.


Does computability according to Church-Turing thesis include side effects? To my understanding:

The Church-Turing thesis means that one could theoretically compute anything that can be computed using either a Turing Machine or the Lambda Calculus.
The Lambda Calculus is based on mathematical functions. This leads to the inability of "pure" functional programming languages based on Lambda Calculus to have side-effects (in the sense that a language like C would have side effects).

To me that would imply that side-effects are not part of computability, but something in addition to it.

e.g. I would say that real-world memory writes that cause physical side-effects  are not of the same nature as the imaginary writes to the tape in a Turing Machine. Or put another way: if I'm writing values to memory whose purpose is to serve as a result in a calculation, Turing completeness would be theoretically relevant; but if I'm writing to a region of memory designed to instruct a robot arm to do things, Turing completeness would be theoretically irrelevant.

Is my understanding correct?

The Church-Turing thesis says that Turing machines capture precisely the effectively calculable functions from natural numbers to natural numbers. It says little about what happens when we attach a robotic arm to a computer.

Any kind of machine needs to represent numbers in some way, obviously since numbers are abstract entities. A Turing machine represents them with 0's and 1's written on a tape. In $\lambda$-calculus we represent them with Church numerals. If we attached a robotic arm to an iPhone, we could represent them with a suitable number of up-down movements by the arm. The question of representation is separate from the question of side effects. In particular, the question of what can be computed is separate from how the results can be communicated. Lamenting about the fact that $\lambda$-calculus has no input/output, for instance, would be misguided.

There is a well understood theory of computational side effects. According to this theory, Turing machine have certain side effects. They carry state in their cells, that is a side effect. We can implement quoting on Turing machines, that is the side effect which converts a closure to source code. Turing machines with oracles can be seen as having the "input" side effect (known as a reader monad in functional programming).

In summary, the Church-Turing thesis is largely independent of what computational effects might be present in the computational model. This is so because the Church-Turing thesis is about numer-theoretic functions, not about how computers interact with their environment.


If P=NP, which two languages are NOT NP-complete? In my last exam this question got asked and i just cant find a clear answer:

If P=NP, which two languages are NOT NP-complete?

So I assume there are two special languages, but which?

Thanks in advance

For $L$ to be $NP$-complete, every problem in $NP$ must be reducible to an instance of $L$ in polynomial time. If $P=NP$, you can solve any potential problem in $NP$ directly within polynomial time, and then just branch and output an instance known to be either in or not in $L$ (in constant time), to prove that $L$ is $NP$-complete. However, two languages lack the required pair of instances - the empty language fails to have an instance that accepts, and its complement fails to have an instance that rejects. If at least one problem in $NP$ has some instances that accept and some instances that reject, then you can't reduce it to either of these two languages, and therefore they are not $NP$-complete. To wrap up the proof, you'd need to give an example of such a problem and the instances, which should be fairly trivial.


Adjacency-list to Adjacency matrix in logarithmic space? Input :  Adjacency-list representation of Directed acyclic graph (Boolean circuit).   see Complexity theory by Arora and bark, page no- 104

Find : Adjacency matrix representation of DAG (Boolean circuit).

My attempt :

Let us assume that DAG has $n$ vertices.

First of all create a $n \times n $ table for adjacency matrix. As we have given the list representation, just go through the each list and enter 1 in the adjacency matrix $1$ corresponding to each edge.  At the end make all untouched entries of matrix  0's.

My Question : I want to design an algorithm that uses only $O(\log n)$ space.

Any time you have a problem parameterized by a number $n$ and you need an algorithm whose space usage is logarithmic in $n$, you should immediately think "loop counter". You can store numbers in the range $0$–$n$ in $\Theta(\log n)$ bits.

So, in this case, you can use an algorithm along the lines of

for i = 1 to n
    for j = 1 to n
        if j is in i's adjacency list
            write 1 to the output
        else
            write 0 to the output

The loop counters take $\log n$ bits each, and you might need a small amount of extra storage for book-keeping but you only need to store a constant number of data items, and none of those will be anything bigger than a number in the range $0$–$n$, so that's still only $O(\log n)$.


Interpretation of an asymptotic notation Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no algorithm that solves the given problem in $o(m + \log{n})$?

In particular, does it mean that an $O(\log{n})$ algorithm is possible?

What this means is:

  For every algorithm solving the problem, it is not the case that the worst-case running time $T(m,n)$ in terms of $m,n$ satisfies the following property: for every $c > 0$ there is $m_0(c)$ such that for all $n \geq m \geq m_0(c)$,
  $$ T(m,n) < c(m + \log n). $$

This doesn't rule out an $O(\log n)$ algorithm, since $\log n$ doesn't satisfy the property written above.


How do calculators convert from decimal to fraction? Sorry if this question is either obvious or ignorant. I am a high school student with only the computer science knowledge I have taught myself.

Calculators have a function that can convert numbers from decimal to fractional equivalents. For example, 0.5 becomes 1/2, and 0.666666667 becomes 2/3.

I doubt that the calculator has these values kept in storage to look up, so there must be an algorithm for this to be determined.

The simplest possible algorithm I can imagine would resemble this:

for (double i = 0; i < someLimit; i++){
    for (double j = 0; j < someLimit; j += 1){
        if (i / j == decimal){ //return these values }
    }
}

This seems far too inefficient to be the algorithm used by calculators. Even on low power scientific calculators, this operation completes quickly.

How do calculators calculate the fractional equivalent of a decimal?

I don't know what calculators actually use, but there are definitely better algorithms than your brute force search.

There are several notions of “best approximation” of a real number by a rational. Depending on how you rate the benefit of a good approximation compared to the cost of a large denominator, you get different notions.

One of these is the best approximation with a bounded denominator: given $x \in \mathbb{R}$ (real to approximate) and $n \in \mathbb{N}^*$ (denominator bound), find $p/q$ with $p \in \mathbb{Z}$, $q \in \mathbb{N} \cap [1,n]$ that minimizes $x-p/q$. The sequence of best approximations for increasing values of $n$ turns out to be relatively easy to calculate and to have other nice mathematical properties: it's the continued fraction expansion of $x$. The continued fraction expansion is a way to construct an infinite sequence of rationals that converges to $x$, and its terms are exactly¹ the best bounded-denominator approximations of $x$. The series is easy to calculate incrementally.

In a calculator, you don't necessarily want the best approximation in that sense: what denominator bound would you pick? If you pick one that's too low, you'll miss some “interesting” rationals. If you pick one that's too large, you end up treating basically everything as some large integer divided by a power of ten.

¹  Except for some boundary effects when $x$ is rational, see a reference for details.


Why use $\mu$-calculus and not LTL,CTL,CTL*? It is known that the temporal logics LTL,CTL,CTL* can be translated/embedded into the $\mu$-calculus. In other words, the (modal) $\mu$-calculus subsumes these logics,
(i.e. it is more expressive.)

Could you please explain/point me to papers/books that elaborate on this matter.
In particular, are there concrete fairness, liveness, etc. properties not expressible in the temporal logics but in the $\mu$-calculus?

As for a $\mu$-calculus formula not expressible in CTL*, see this post.

As for texts on the subject, you are likely to get further ahead by reading papers, as these topics are not covered in many books.
Still, the Handbook of Modal Logic may be a good start.

As for papers, try:

Expressive power of Temporal Logics

This PhD thesis

Emerson's Model checking and the Mu Calculus

And there are many more. Just google terms like "expressive power", "mu calculus" and "temporal logics".


Local and Global storage with multithreading pools + locking threads I am having difficulty answering the following questions relating to the use of threading.

Question 1 is of relating to the possibility of a local storage per thread and a global storage accessible to all threads. Consider the following scenario; A program creates a series of threads each with their own local storage, kind of like a mutex system except for that no thread can access another's memory, and a square matrix stored in global storage which is accessible to all threads. When the space complexity of the following program is calculated, is the space complexity (# of elements in the square matrix)2 + (local storage of finishing thread) or (# of elements in the square matrix)2 + (local storage of all threads at the time that the finishing thread completed)?

Question 2 relates to timing threads to go at a very precise rate. Consider the following scenario; A program creates a series of threads that continually add a random set of elements to their local storage. The program finishes and returns the thread that received the shortest number of elements in its random set. If one thread was to go faster than another, the program would be incorrect. Is there a way to "lock" the threads to go at the same speed?

Any help on the answering of these questions would be appreciated. Please comment if additional info is required.

I will answer Question 1.  As @DavidRicherby said, you should post the other question separately.

The space complexity is the maximum amount of space required while the algorithm is running. So it certainly would be more than the (number of elements in matrix) + (local storage of just finishing thread).  It might be the total storage of all the threads at the time the program finished but only if (a) you haven't already exited any of the threads, and (b) none of the threads freed up a bunch of memory just before the program finished.

You also need to be careful to not overcount.  As described here there are a lot of optimizations that allow you to reuse space, so you can't just sum up all the memory allocated by every thread that ever existed.  You really need to figure out the point in time during your program execution when the most memory is in use.


Lambda Calculus - free vs. bound variables While I am reducing the following term, I encountered a little Problem:

$$(\lambda w x. w x)(\lambda w x. w x) \rightarrow_\beta (\lambda x.(\lambda w x. w x)  x)$$

Now my first question: Why is it possible to reduce further after doing alpha conversion? Isn't the last x bound be the first lambda?

Second Question:
In my Lectures notes there is mentioned that $(\lambda y . a )b$ -> a. Why can we do this? Shouldn't the result be b? Because we apply b to all free
occurrences of y in a, but there are none so our expression reduces to b.

Iterated abstraction uses abstraction to the right:

\begin{align}
LHS
&= (\quad \lambda wx.wx \space\space\space)\space(\lambda wx.wx) \\
&= (\lambda w.(\lambda x.wx))\space(\lambda wx.wx)
\end{align}

The beta reduction axiom is $(\lambda x. M[x])N = M[x := N]$.

To satisfy your original equation, replace all occurences of $x$ in the beta reduction axiom, with $w$. Then, substitute the following values into the beta reduction axiom: $$M[w] = (\lambda x.wx)$$ $$N = (\lambda wx.wx)$$

The beta reduction axiom with substituted values is $$(\lambda w.(\lambda x .wx))(\lambda wx.wx) = M[w:=(\lambda wx.wx)]$$

where $M[w:=(\lambda wx.wx)]$ means "substitute all occurences of $w$ in $M$ with $(\lambda wx.wx)$". So we get:

$$(\lambda w.(\lambda x .wx))(\lambda wx.wx) = (\lambda x.(\lambda wx.wx)x)$$

as expected.

For the $(\lambda y.a)b \rightarrow a$ equation, $y$ is a bound variable, while $a$ is a free variable. We apply $b$ to all occurences of $y$, but there are none so our expression doesn't change (no $y$ is converted to $b$). The result is still $a$, unchanged.

Source, really well written and accessible if you give it enough time.


How must Grovers algorithm be modified in order to solve 3-SAT? Grover's algorithm was designed for a database with exactly one item that matches a given search criterion, and can be used to find that very item.

However, when checking whether a given formula is in 3-SAT, I don't know how many items match the search criterion (i.e. how many interpretations satisfy the formula) and I just want to know whether there is at least one. So, what steps have to be taken in order to make Grover's algorithm suitable for 3-SAT?

Grover's algorithm is already suitable.  It promises that if there is at least one match, then it will output at least one match.  It doesn't promise to output all matches, but you don't need all matches.

It is usually described to work in the case where there is zero or one items that match, but that's just because those are the hardest cases.  If there are multiple matches, the algorithm will still work and will still find a match; and the running time will remain the same.


Assistance with Notation in the Paper Entitled: "Search Through Systematic Set Enumeration" So I'm reading "Search Through Systematic Set Enumeration" by Ron Rymon (currently available online for free.  I'm having a problem with the notation in the following definition presented bellow:

The
Set-Enumeration
(SE)-tree
is
a
vehicle for representing
and/or
enumerating sets
in
a best-first fashion.
The
complete
SE-tree
systematically enumerates
elements
of
a
power-set using a
pre-imposed
order
on
the
underlying set
of
elements.
In
problems
where
the
search
space
is
a
subset
of
that
power-set
that
is
(or
can
be)
closed
under
set-inclusion,
the
SE-tree
induces
a
complete
irredundant
search technique.
Let
E
be
the
underlying
set
of
elements.
We
first index
E's
elements
using
a
one-to-one
function
ind: E -> $ \mathbb{N} $.
Then,
given
any
subset
S $\subseteq$ E,
we
define
its
SE-tree
view:
Definition 2.1 A Node's View
$View(ind,S) \stackrel{def}{=} \{e \in E | ind(e) \gt max_{e' \in S} ind(e')\}$

In the paper there is an example of a tree made with what appears to be E={1,2,3,4}.  I have some familiarity with set-builder notation, but much of the other parts of the "node's view" is confusing me. I skimmed ahead to see if there were clarifications, but I didn't manage to find them so either: a) the author is assuming a competency I do not have, b) the explanation is there and I couldn't find it, or c) the author is doing a horrible job as an author.
So with the hope that it is one of the first two:

I'm assuming that the prime in e' is for the complement of the set e, so if e = {1}, then e' = {2,3,4}.  Is this correct?

What is this ind function?  What would ind({3,4}) be for example?

$max_{e' \in S}$?  Is this the maximum height of the sub tree of the complement of e?
Any assistance on this would be most appreciated.

Please, one question per question.

The answer to your first question: No, prime most likely does not indicate complement, absent some specific indication of that.  It is just another variable.  $e$ is one variable; $e'$ is another variable (the author could have used a different letter, like $f$ or $x$ or something, but chose to use $e'$ instead).

The answer to your second question: The ind function is defined in the text immediately preceding the definition.  Read it again?

Yes, it's possible you might lack the necessary mathematical background.  You might try taking an online course (or working through a textbook) on discrete mathematics for computer science.


Genetic Algorithm Getting Stuck on Certain Values I'm attempting to teach myself something about genetic algorithms. I found a simple tutorial on it here, and it made enough sense that I was able implement the suggested example of generating a string of single digit numbers and simple arithmetic operators to total 42.

I then attempted the second suggested exercise described at the bottom of the page here. Basically, in a field of randomly placed circles of random size, write a genetic algorithm to find the largest non-overlapping circle you can place in the field.

I have something that seems to work, but I notice that it seems to get hung up on certain values. My "chromosomes" are composed of 3 pieces of data - x position, y position and radius. I'm using crossover and mutation to reproduce in the population. I then rank the results based on how large the resulting circle it is and whether it fits within the field and whether it overlaps other circles or not.

What I'm seeing is that there's a strong tendency for the radius to tend towards values that are just under a power of 2. For example, it will often get stuck bouncing around a radius of 31, 62, 124, etc.

I was trying to determine why this happens. My "genes" are all single precision floating point numbers. Crossover would cause some portion of the bits from one value to replace the corresponding bits of another value. Usually, this will result in the lowest precision bits of one value getting overwritten with those of another value. Occasionally it will cause part of or all of the exponent to get overwritten as well. Once you get a couple generations in, the values are largely of the same magnitude, so this often does very little. Mutation could flip any bit in the float, meaning it could turn a positive to negative 1/32nd of the time. It could change the exponent 7/32nds of the time, and the mantissa the remaining 3/4ths of the time.

Doubling the magnitude (by mutating or crossing over in the exponent, for example) is likely to have a positive effect up to a certain point. But once the generation contains mostly circles that are slightly over 1/2 the maximum value, they'll be less likely to grow by this method. Changes in the mantissa seem to have little effect overall.

My question - is this normal? This seems problematic when trying to generate better generations. I've let my simulation run for millions of generations, and haven't seen it get any better than the next-lowest power-of-2 for the radius. Have I just laid out my data in an unfortunate way, or does this problem come up often in genetic algorithms? Is there a way around it? I tried switching to a 16.16 fixed point representation and it got slightly better. The radiuses would get larger more frequently, but they still seem to hover around powers-of-2.

As @Ray mentioned, the solution was to change how I encode the values. I encoded the positions and radius as floating point values initially. I switch from 32-bit IEEE-754 encoding to a 16.16 fixed point representation, since I didn't need more precision than that. I then converted from the fixed point representation to a 32-bit Gray code to store the genes. That allowed the simulations to converge on a solution much more quickly. It also seemed to help the mutations and crossover produce higher quality variations.


Example of a locally trivial semigroup I was having a look at the block product principle for finite monoids. I wanted to see the derivation of LTT = Acom$*$LI, using an example. But I can't come up with a non-trivial example of a monoid in LI. Any help is appreciated.

There is no nontrivial monoid in LI. LI is actually a (pseudo)-variety of finite semigroups: it is the class of finite semigroups $S$ such that, for every idempotent $e \in S$, $eSe = e$. If $S$ is a monoid, you can take $e = 1$, the identity of the monoid and get $S = 1S1 = 1$ so the monoid has to be trivial.


Power of variants of Turing machines I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine.  I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent.  Such as multiple tapes and nondeterministic Turing machines.

I am to determine if a and b are equal, more powerful or less powerful then a single-tape Turing machine.  Where do I start?

a) A Turing Machine that can only make moves to the right and never left.

b) A Turing Machine that can move right one space or move left two spaces.

I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent.

Hint 1: So your first step should be to determine whether a and b have, or can obtain, unrestricted access to unlimited memory.

Hint 2: If yes, then try to emulate the missing pieces of your preferred Turing machine model.

Hint 3: If no, then try to show that the halting problem (with empty tape as input) is decidable.


Prove that the complement of  $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties I want to prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties.

I understand pumping lemma can be used to prove that $\{0^n1^n \mid n \geq{} 0\}$ is not a regular language. I also understand regular languages are closed under complement operation. However, does that also imply that a non-regular language's complement is also non-regular?

Yes. Since the complement of a regular language is also a regular language, then it follows that the complement of a non-regular language must also be non-regular. Strictly speaking, this works since the complement is its own inverse.


What is a hyper property? I am reading the paper Foundations and tools for the static analysis of Ethereum contracts, by Grischenko et al.
Sometimes the authors speak about hyper properties (e.g. Section 5).
What exactly is a hyper property in this context?

A trace is a (finite or infinite) sequence of program steps. (Some works only consider finite traces, or only infinite ones.)

A property is a set of traces. E.g. all those traces where variable $x$ is never negative.

A hyperproperty is a set of sets of traces. E.g. the sets of traces $T$ where each trace in $T$ is finite.

Some complex security goals can not be described as a property. Non-interference, for instance, can not be checked on a single trace, but only on the set of all the possible traces a given system can generate during execution.


Expressivity of neural networks, how much information can be stored I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps is N! over (N-k)!  ).
For example is a network with 1000 nodes able to store 60 injective maps from {1,2,3} to {1,2,3,4,5}?
(By storing information I mean something like: when classifying information the network can access and use the information)
In particular I was curious if the above question can be translated to a question about the VC-dimension of a neural network. Can a question about storing injective maps in a neural network be translated to a question about the VC-dimension of a neural network?
EDIT: I’m interested in something like the following result
There are 60 functions, note that we can represent this with 6 bits
The codomain consists of 5 elements, which can be encoded by 3 bits (since 5 < 2^3)
We need to map 3 elements of the domain to an element of the co-domain, so we need 3 times 3 bits for each function
So to encode 60 functions we need 60 * 3 * 3 bits
In general we need (N! / (N-k)! ) * k * log_2(N) bits
Note that (N-k+1)^k < N! / (N-k)! < N^k
and even (N-k)^k < (N! / (N-k)! )  * k * log_2(N) < N^k
One weight in a neural network is 32 bits
If we have X weights, then we have X*32 bits
So if X*32 is smaller than log_2(N-k) * k, then it’s not possible to express all the functions in the network
[I’m actually more interested in negative results like the one I gave, sorry if that’s confusing. Positive results are welcome as well.]

You're probably not going to get a theoretical answer, because analyzing exactly what set of functions can be computed by a particular neural network is messy.  Or, at least, you probably won't get a tight analysis.  There are theorems showing that neural networks are universal approximators, meaning that given sufficient capacity it is possible to express every function, but this doesn't tell you the minimize size needed to express every function; it just tells you that there exists a size that is large enough.
However, if you're willing to accept empirical evidence rather than theorems and proofs, research has demonstrated empirically that if you choose a deep neural network architecture with sufficient capacity and you train for long enough, neural nets can memorize the training set and achieve 100% accuracy on the training set, at least for a randomly chosen function $f$ [1].  This may not tell you exactly what size neural network you need to ensure that it can express all such functions, and it's not a proof or a guarantee.
The VC dimension is beautiful theory but it's not clear it has a great deal of relevance to modern use of neural networks in practice.
[1] Understanding deep learning requires rethinking generalization.  Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals.  arXiv:1611.03530


Proof Complexity of a Proof or Disproof of P = NP Has there been any research on the proof complexity of a resolution to the P=NP problem?  If not, given the lack of progress on the problem, would it be unreasonable to conjecture that any proof that resolves the P=NP problem will require a super-polynomial number of steps?

Proof complexity only makes sense when there is a sequence of statements depending on a parameter $n$. For example, the proposition $\mathsf{PHP}_n$ states (informally) that there is no bijection $[n+1] \to [n]$. This sequence of propositions is hard for certain propositional proof systems.

The statement $\mathsf{P} \neq \mathsf{NP}$ is a single statement, so you can't apply proof complexity to it directly. However, the following sequence of statements does make sense, for particular functions $s(n)$: "there is no circuit of size $s(n)$ correctly solving SAT for instances of length $n$". This has been considered in the literature, for example by Razborov (who considered the setting of uniform proof complexity, i.e., bounded arithmetic).


How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm? I am going through the book of Parallel Programming and a parallel algorithm is often classified as Efficient, Optimal or Suboptimal. I googled these terms but I didn't found a clear definition for them.

Define $T(n)$ as the running time of the sequential algorithm, $t(n)$ as the running time of the parallel one, $p(n)$ as the number of processing units. Hence work $w(n)=p(n)t(n)$, speedup factor $S(p)=\frac{T(n)}{t(n)}$, efficiency $E=\frac{T(n)}{p(n)t(n)}\times 100\%$.

The parallel algorithm is efficient if:

$t(n)=O(\log^c n)$ for some constant $c>0$; and
work $w(n)=T(n)O(\log^c n)$

The parallel algorithm is optimal if:

$t(n)=O(\log^c n)$ for some constant $c>0$; and
work $w(n)=O(T(n))$

Are the definitions of efficient and optimal correct? And what about suboptimal?

I am literally a noob to parallel programming and I googled a lot without a clue. Any help would be greatly appreciated. Thanks in advance.

The word "correct" is misplaced, what you should be asking is whether those definitions are meaningful / express the notion of "efficient" that you (or the author) had in mind.

The notion of efficient might vary depending on the context, so there is no "correct" definition. For example, in sequential computing, polynomial time is usually considered efficient. One of the reasons to use polynomial time is because polynomials have nice properties that cause our definition to well-behave, e.g. an efficient algorithm which uses another efficient algorithm as a subroutine is still efficient (this is because polynomials are closed under composition).

With this in mind, I'll try to give a few reasons as to why these definitions might be useful or reflect what you imagine that an efficient parallel algorithm will be.

First, it obviously holds that $w(n)=\Omega(T(n))$, since a sequential algorithm can simulate the parallel one by doing the work of all processors one by one, which takes $p(n)t(n)=w(n)$ time. Here I assumed that $T(n)$ is a lower bound on the time required for a sequencial algorithm to preform the given task. This explains your notion of optimallity, one cannot do better then $w(n)=O(T(n))$.

As for efficient, requiring the running time for each processor to be $O(\log^c n)$ results in exponential speedup over a sequencial algorithm, since $T(n)=\Omega(n)$ (the sequencial algorithm must at least read the entire input), and thus $T(n)=\Omega\left(2^{[t(n)]^{\frac{1}{c}}}\right)$.

The additional requirement of $w(n)=T(n)O(\log^c n)$ means that the overall number of operation does not increase too much (you pay in processing power for better computation time). So in this case, the overall number of operations for the sequencial/parallel algorithm is equivalent up to polylogarithmic factors.


Prove that the language is not regular through Myhill-Nerode Equivalence The language is given by: $$L=\{a^nb^m|n<m\}$$
I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence.
Any help would be appreciated.

You have to find an infinite set of strings $s_i$ such that for every two strings $s_i ≠ s_j$, there is a string $t_{ij}$ such that exactly one of $s_i t_{ij}$ and $s_j t_{ij}$ is in the language, and the other is not.
Now if you look at $a^n$ and $a^m$, n ≠ m, can you find a string t such that exactly one of $a^n t$ and $a^m t$ is in the language, and the other is not?


Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it Is there any known polynomial time algorithm to solve a problem which that  problem is in NP. I was told is False but can't think of any counter example now.

NP is the class of decision problems where any instance with an answer "YES" has a proof that the answer is YES which can be checked in polynomial time. NP contains all problems that are solvable in polynomial time. Therefore there are many problems in NP with known polynomial time algorithms.

If you are talking about NP-complete problems, that's a whole different matter. There is (at this point in time) no NP-complete problem with a known polynomial time algorithm to solve it.

Someone might find a proof that for an NP-complete problem there is no NP-complete problem with a polynomial time algorithm to solve it - not just no known algorithm, but no algoritm at all.

On the other hand someone might actually find an NP-complete that can be solved in polynomial time. It is unlikely though.


Relation between the "Point-Cover-Interval" problem and the "Interval Scheduling" problem Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains some point, that is $\forall I \in \mathcal{I}: \exists p \in P, p \in I$.

  Interval Scheduling Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a maximum number of intervals such that no two of them overlap.

Interestingly, the two problems above have exactly the same greedy algorithm, illustrated by the following figure (from [1]; for the interval scheduling problem; see the "Greedy Algorithm" part below).

Since they share the same algorithm, I expect that they are the same (or, at least closely related) problem, say, in the view of reduction. However, I failed to reduce them to each other.

  Question: Are these two problems the same? Or what is the relation between them? Can we reduce them to each other?

Note that the first problem asks for a minimum solution while the second one for a maximum solution.

Greedy Algorithm:
The greedy algorithm for the "Interval Scheduling" problem is as follows:

sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$.
while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}$, do:

add $I$ into the result-set; (darker lines in the figure)
delete all intervals from $\mathcal{I}$ that conflicts with $I$ (dashed lines in the figure).

For the "Point-Cover-Interval" problem, we simply collect the finishing time point of each interval $I$ chosen in each iteration in the algorithm above.

[1]: Algorithm Design. By Jon Kleinberg and Éva Tardos. (Section 4.1)

Here is a proof that the two numbers are equal:

  For every interval $I$ consider the largest set of disjoint intervals
  with $I$ as the rightmost interval. This has a size, say $D_I$.

  Now if $D_I = D_J$, then $I$ and $J$ have to intersect, so the set of
  intervals with equal $D_I$ values all pairwise intersect each other, and so have a
  common point (by the 1D version of Helly's theorem, or by just considering the intervals arranged in order of their left endpoints).

  Now if $d = \max D_I$ (the size of the largest set of non-intersecting
  intervals), then we have $D_I$ taking all the values $\{1, 2, \dots, d\}$,
  and thus $d$ points are enough to cover all the intervals, and we need at least $d$ to cover the largest set of disjoint intervals.

For some related reading, look at Mirsky's theorem, which is a dual of Dilworth's theorem.

  Dilworth's theorem says that in a set of elements with a partial order defined on them, the size of the largest antichain
  (antichain is a set of elements not comparable to each other) is same
  as the size of the smallest partition into chains (each set of the
  partition is a total ordered set).

  Mirsky's theorem says that the size of the largest chain is the same as the smallest number of antichains into which the set might be
  partitioned.

In this case defines your order relation as follows:

$$I = (i,j) \lt I' = (i', j') \iff j \lt i'$$

Basically, two disjoint intervals are comparable, with the left one being smaller.

Because of Helly's theorem, the two numbers you are computing are exactly the numbers in Mirsky's theorem, which is defined as the height of the the partial order (Dilworth's theorem defines the width).


Composition of handler types in algebraic effects and handlers In the paper "An introduction to algebraic effects and handlers" (Pretnar, Matija. Electronic Notes in Theoretical Computer Science 319 (2015): 19-35), handlers get a handler type that looks like a function type:
$\underline{C} \Rightarrow \underline{D}$.
These can be "applied" with the with h handle c syntax.

What I've noticed is that the only way to get a handler type is with the handler syntax, which means there's no way to get composition of handler types:
given $\underline{A} \Rightarrow \underline{B}$ and $\underline{B} \Rightarrow \underline{C}$ there is no way to get $\underline{A} \Rightarrow \underline{C}$.

I believe this is because there is no abstraction for computations like there is an abstraction for values ($\lambda x . c$). Is this left out because of simplicity of is there a problem with such abstractions which means you can never have composition of handler types in a consistent system?

You are correct that the reason lies in the lack of computation abstractions. They are left out because they are not a standard programming construct, especially in a call-by-value calculus. But even if you added them, I don't think they should be given a type of the form $\underline X \Rightarrow \underline Y$ because they are in general not homomorphisms, what the type would suggest.

You can get around in two ways:

you can apply the function fun t -> with h' handle (with h handle t ()) of type $(\mathtt{unit} \to \underline A) \to \underline C$ on a thunked operation. For example, in Multicore OCaml the only way of making a general handler is through a function that takes a thunked computation.
you can precompose the handler similar to what @chi suggested.
If h is of the form

handler {
    return x -> c_ret,
    op1(x, k) -> c1(x, k),
    ...
}

then the composed handler

handler {
    return x -> with h' handle c_ret,
    op1(x, k) -> with h' handle c1(x, k),
    ...
}

has the type $\underline A \Rightarrow \underline C$.


Resolution of Barber paradox I am trying to prove using the resolution technique that the following two clauses are contradicting:

$\forall_x Shaves(Barber, x) \iff \neg Shaves(x, x)$
$\exists_x Shaves(x, Barber)$

After turing those into the conjunctive normal form and skolemization I get the following clauses:

$\neg Shaves(Barber, x)\  \lor\ \neg Shaves(x, x)$
$Shaves(Barber, x)\  \lor\ Shaves(x, x)$
$Shaves(Someone, Barber)$

where $Someone$ is a Skolem constant (a Skolem function of of zero arity).

I am unable to prove that this set of clauses is contradicting. It looks like something is missing. Shouldn't there be a clause, which prevents $Someone$ from being a barber as well?

No, you don't need to specially add any such clause.

Here's where I think you might have gone wrong.  The result is not 3 clauses (3 conjunctions).  The result is a bunch of clauses.  We get one clause of the form $\neg Shaves(Barber, x)\  \lor\ \neg Shaves(x, x)$ for each $x$, one of the form $Shaves(Barber, x)\  \lor\ Shaves(x, x)$ for each $x$, and one last clause $Shaves(Someone, Barber)$.  Thus, if there are $n$ people ($n$ possible values of $x$), the CNF form has $2n+1$ clauses in it.

Finally, note that the Barber is one of those $n$ people.  Thus, for the clauses corresponding to the case $x=Barber$, we get a clause $\neg Shaves(Barber, Barber)\  \lor\ \neg Shaves(Barber, Barber)$ and a clause $Shaves(Barber, Barber)\  \lor\ Shaves(Barber, Barber)$.  Now you should be able to find a contradiction in there.


Problems with the proof of Huffman Optimality in Cover's book There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me.

First question is why he assumes that we can "Consider an optimal code $C_m$. Is he assuming that we are encoding a finite number of words so that
$\sum p_i l_i$ must have a minimum value? Here I give you the relevant snapshot.

Second, there is an observation made on this notes that was also done in my class before proving the theory of optimality of huffman codes, that is,

  observe that earlier results allow us to restrict our attention to
  instantaneously decodeable codes

I don't really understand why this observation is necessary.

To answer your first question, the index $i$ goes over the range $1,\ldots,m$. The assumption is that there are finitely many symbols. While some theoretical papers consider encodings of countably infinite domains (such as universal codes), usually the set of symbols is assumed to be finite.

To answer your second question, the claim is that a Huffman code has minimum redundancy among the class of uniquely decodable codes. The proof of Theorem 10 in your notes, however, only directly proves that a Huffman code has minimum redundancy among the class of instantaneously decodable codes. It does so when it takes an optimal encoding for $p_1,\ldots,p_{n-2},p_{n-1}+p_n$ and produces an optimal encoding for $p_1,\ldots,p_n$ by adding a disambiguating bit to the codeword corresponding to $p_{n-1}+p_n$; it's not clear how to carry out a similar construction for an arbitrary uniquely decodable code.


Huffman tree generation if the frequency is same for all words Can a valid Huffman tree be generated if the frequency of words is same for all of them?

Example :

Value     | Frequency
--------------------
Google    | 2
Yahoo     | 2
Microsoft | 2
Amazon    | 2

Yes. When creating a Huffman tree, if you ever find you need to select from a set of objects with the same frequencies, then just select objects from the set at random - it will have no effect on the effectiveness of the algorithm.

Of course, one might question why you're bothering to build a Huffman tree if you know all the frequencies are the same - I can tell you what the optimal encoding is.


When do we use parallel algorithms for enumerating combinations? I know that combination is used in many areas. But do we really need parallel version of algorithms for that? If so, where do they used?

Here is a famous example of parallel algorithms, Adaptive and Optimal Parallel Algorithms for Enumerating Permutations and Combinations by S. G. AKL.

I have found one.
A parallel algorithm for finding small sets of genes that are enough to distinguish two biological states

But if you found others, I would like to know.