Sources for Algorithmic Evolutionary Game Theory I use the title term in a very loose sense.

There is a significant amount of work on evolutionary game theory, including its mathematical foundations. I was recommended "Evolutionary Games and Population Dynamics" but haven't delved into it yet.

There is also a significant amount of work on algorithmic game theory, which is a popular topic on this site.

What I'd like to see is work that makes computational complexity or convergence statements about certain evolutionary dynamics.

Examples (phrased very loosely):

Given a population and an evolutionary scheme, can we give a probabilistic regret bound for the long-term population optimality (compared to the best individual produced?). This seems to relate strongly to ensembles of experts and bandit problems. What about in nonstationary settings?
Given a set of populations of different species that interact in their environment, playing pretty much any sort of multi-player game, what statements can we make about the eventual stability of their strategies or strategy distributions, given their evolutionary strategies.
In any sort of environment with many "niches" (an overbroad way of phrasing it, I understand), either in terms of direct relationship with the environment or in terms of relationships with other species, what statements can we make about how populations will distribute across these niches.
Any problem I haven't asked but should - I'm coming at this with little AGT, TCS, Genetic Algorithms, evolutionary game theory or population biology background; I'm asking my questions from an optimization/machine learning/stats point of view, which may be the wrong one or incomplete.

This is one of the topics where I have been looking for connections for a while. However, they don't seem all the prevalent. The folks working on theoretical biology and economics that use EGT, usually stick to dynamic systems theory and don't don the algorithmic lens. Thus, most results are of the AMath/Physics style, and not of the algorithms and discrete math style. If you are willing to pursue the dynamic systems approach, then there a survey by Hofbauer and Sigmund which is shorter and more recent than their book (I mention it and some passing comments in a previous answer).
One of the places replicator dynamics have been used in complexity related results, is by Marcello Pelillo and co-authors as a heuristic for solving max-clique (reduce max-clique to quadratic programming, solve quadratic programming by using replicator dynamics as your heuristic):

[1] Immanuel M. Bomze, and Marcello Pelillo [2000]. "Approximating the Maximum Weight Clique Using Replicator Dynamics." IEEE Transactions on Neural Networks 11(6)
[2] Marcello Pelillo, and Andrea Torsello [2006]. "Payoff-Monotonic Game Dynamics and the Maximum Clique Problem." Neural Computation 18: 1215-1258.

You can use their results to show that many natural question associated with evolutionary stable strategies are NP-hard (this kind of addresses question 2). In fact, Etessami & Lochbihler showed that it is worse than that and the question of ESS existence is both NP and coNP-hard, but in $\Sigma^P_2$. Recently, Conitzer tightened this to show that "does an ESS exist?" is a $\Sigma^P_2$-complete problem.

[3] Kousha Etessami, and Andreas Lochbihler [2008] "The computational complexity of evolutionarily stable strategies". International Journal of Game Theory, 37(1): 93-113. (First available in 2004 as ECCC tech report TR04-055).
[4] Vincent Conitzer [2013] "The exact computational complexity of evolutionarily stable strategies". The 9th Conference on Web and Internet Economics (WINE). (pdf).

A lot of the interesting EGT questions today are about games on graphs, and although there are some cool dynamic system results, like (also see this question for extensions of this approach):

[5] Hisashi Ohtsuki, and Martin Nowak [2006] "The replicator equation on graphs." _ Journal of Theoretical Biology_, 243 (1), 86-97 (link, blog post)

Most of the work goes through agent-based modeling (see this answer for a spread-of-disease modeling context). These models are usually much more welcoming to complexity and convergence statements. Look at the following book for more:

[6] Yoav Shoham and Kevin Leyton-Brown [2009], "Multiagent systems: algorithmic, game-theoretic, and logical foundations", Cambridge University press.

I think machine learning is a pretty straightforward way to approach EGT, since it is a natural halfway point between the relevant physics (statistical mechanics) and computer science. This has definitely been done, it would take me a bit to find a good reference, but a random reference (which also shows that EGT folks have considered other popular equilibrium concepts, like correlated equilibrium):

[7] Sergiu Hart and Andreu Mas-Colell [2000], "A simple adaptive procedure leading to correlated equilibrium", Econometrica 68(5): 1127-1150
[8] Antonella Ianni [2001], "Learning correlated equilibria in population games", Mathematical Social Sciences 42(3): 271-294.
[9] Ludek Cigler and Boi Faltings [2011], "Reaching Correlated Equilibria Through Multi-agent Learning", AAMAS 2011: 509-516

I definitely hope others give more specific answers, since this is a question I've always wanted to know more about.

I learned from the school of Ashlock. The big take away I got was how useful it was to take the $n^2$ table of outcomes between agents and use K-Means to cluster the rows into strategy groups for analysis.


A random walk that moves to less-visited nodes Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least number of times. If there are several such nodes, it chooses one at random. My question is: what is the (worst-case) cover time of this random walk as a function of the number of nodes $n$?

The answer should be at least $\Omega(n^2)$. Consider a star graph where each node has a self-loop. In this graph, the walk starting at the center will visit the leafs in some order, without loss of generality $1,2,3, \ldots, n-1$ (relabel the vertices if necessary). The time spent at leaf $i$ will be at least $i-1$ because the center will have been visited $i-1$ times before leaf $i$.  Thus the total cover time will scale as $\Omega (n^2)$. If we want an example without self-loops, we can consider a star-like graph where each leaf is replaced by a path of length $2$.

Alternatively, what is the largest hitting time between any two vertices for this random walk? This feels like asking a very similar question.

For the usual random walk which jumps to each out-neighbor, the largest hitting time will be $O(n^3)$ but the standard proofs rely on resistances, which are not applicable here due to lack of reversibility.

The assumption here is that the input graph is not a disconnected graph. If it is then it will run forever since some of the nodes will never be reached from set of nodes.

Since the graph is undirected, at any point in time, the decision is made solely based on at what node you are and from that node a neighbor with least visited is going to be picked. So, it is possible that the node that is used to reach the current node may very well be next node to be visited (returning). As you visit the node, it increases the node's visited count and forces alternate node at next choice. Each node would have a visited count any where from 1 to N and no more than N without all nodes being visited.

The constraint that the next node to be visited be a least visited tracks whether node is visited or not and forcing to visit all nodes. Let us say that a global variable tracks the number of visited nodes. Whenever a node's visited counts goes from 0 to 1, increment this counter by 1 for the newly visited node. Until this count reaches the number of nodes in the input graph, we know that there exists some nodes that are not yet visited.

At every node, the unvisited node(s) gets priority over already visited nodes since the unvisited node's visited count is 0. So, initially it tracks like DFS and avoids cycle unless there is no other way. As you visit the node that is already visited, it increments the node's visited count there by making it least preferred till every node in the connected component's node weight to be increased as well. If there is another way to reach other unvisited nodes, then those nodes would be preferred and thereby making to find alternate path. If there is no other way, then we would end up back to articulation point which would have at least one node that is least visited. This least visited component would be now explored until all nodes in that component are visited.

The visited count of each articulation point would be number of nodes in the largest component it is connected to plus number of components it is connected to. Eventually, the largest count possible for a node in the graph is one plus the count of articulation point that has maximum of sum of largest component it is connected to plus the number of components it is connected to.

Therefore, the largest hitting time will be O(n^2).


A Notion of Monotone Quantum Circuits In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the monotone Boolean circuits model.

My question is simple: Is there a quantum analog for monotone circuits (or more than one)? Is there a quantum Razborov's theorem?

You're really asking two different questions and hoping that there is a single response which answers both: (1) What natural notions of quantum monotone circuits are there? (2) What would a lattice-based Razborov-style quantum result look like?

It isn't obvious how to achieve both at the same time, so I'll describe what to me seems a reasonable notion of quantum monotonic circuits (without indicating whether or not there is a corresponding Razborov result), and a completely different notion of what a "natural" quantum Razborov conjecture would look like (without indicating whether it is likely to be true).

What we want from quantum

As I remark in the comments, I think that it is not necessary to try to squeeze the notion of monotonic circuits into a mold of unitarity. Whether it is in the fact that evolution with time need not preserve the standard basis, or in the fact that there exists multiple bases of measurement in which the outcomes may be entangled, I think the sine qua non of quantum computation is the fact that the standard basis is not the only basis. Even among the product states, it is in some implementations defined only by a choice of frame of reference.

What we must do is to consider things in such a way as to remove the standard basis from its traditional privilidged place — or, in this case, as much as is possible while retaining a meaningful notion of monotonicity.

A simple model of quantum monotone circuits

Consider a circuit model which is implicit in Tsuyoshi Ito's comment about "monotone quantum channels" (and which is pretty much what one must do if one wants a notion of "a circuit" which is not restricted to unitary evolution).

Let $\mathbf H$ be the space of Hermitian operators on $\mathbb C^2$ (so that it contains all density operators on one qubit). How would we define a quantum monotone gate $\mathsf G: \mathbf H_a \otimes \mathbf H_b \to \mathbf H_c$ from two input qubits $a,b$ to an output qubit $c$, in such a way that it isn't effectively a classical monotone gate? I think it's straightforward to say that the output should not be restricted to $|0\rangle\!\langle 0|$ or $|1\rangle\!\langle 1|$, or mixtures of them; bu that to be "monotone", we should require that as $\langle 1 | \,\mathop{\mathrm{Tr}_a}\bigl(\rho_{ab}\bigr)  |1\rangle$ and  $\langle 1 | \,\mathop{\mathrm{Tr}_b}\bigl(\rho_{ab}\bigr) |1\rangle$ increase, the value of $\langle 1 | \mathsf G(\rho_{ab}) | 1 \rangle$ must be non-decreasing. For a two-input-qubit gate, this means that $\mathsf G$ must be implementable in principle as

performing a two-qubit measurement with respect to some orthonormal basis $\{ |00\rangle, |\mu\rangle, |\nu\rangle, |11\rangle \}$, where $|\mu\rangle,|\nu\rangle$ span the subspace of Hamming weight 1, and
producing as output some state $\rho \in \{ \rho_{00}, \rho_\mu, \rho_\nu, \rho_{11} \}$ corresponding to the outcome it measured, where $\langle 1 | \rho_{00} | 1 \rangle \leqslant \langle 1 | \rho_\lambda | 1 \rangle \leqslant \langle 1 | \rho_{11} | 1 \rangle$ for each $\lambda \in \{ \mu, \nu \}$.

The circuits are just compositions of these in the sensible way. We might also allow fan-out, in the form of circuits which unitarily embed $|0\rangle \mapsto |00\cdots 0\rangle$ and $|1\rangle \mapsto |11\cdots 1\rangle$; we should at the very least permit these maps at the input, to allow each (nominally classical) input bit to be copied.

It seems reasonable either to consider the entire continuum of such gates, or to restrict to some finite collection of such gates. Any choice gives rise to a different "quantum monotone gate basis" for the circuits; one can consider what properties different monotone bases have. The states $\rho_{00}, \rho_\mu, \rho_\nu, \rho_{11}$ can be chosen completely independently, subject to the monotonicity constraint; it would undoubtedly be interesting (and probably practical to bound error) to set $\rho_{00} = |0\rangle\!\langle 0|$ and $\rho_{11} = |1\rangle\!\langle 1|$, though I see no reason to require this in the theory. Obviously AND and OR are gates of this type, where $\rho_\mu = \rho_\nu = |0\rangle\!\langle 0|$ and $\rho_\mu = \rho_\nu = |1\rangle\!\langle 1|$ respectively, whatever one chooses $|\mu\rangle$ or $|\nu\rangle$ to be.

For any constant k, one might also consider gate bases including k-input-one-output gates. The simplest approach in this case would probably be to allow gates $\mathsf G: \mathbf H^{\otimes k} \to \mathbf H$ which may be implemented as above, allowing any decomposition of the subspaces $\mathcal V_w \leqslant \mathcal H_2^{\otimes k}$ of each Hamming weight $0 \leqslant w \leqslant k$, and to require that
$$ \max_{|\psi\rangle \in \mathcal V_w}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle \;\;\leqslant\;\; \min_{|\psi\rangle \in \mathcal V_{w+1}}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle $$
for each $0 \leqslant w < k$.
It is not clear how much additional computational power this would give you (nor even in the classical case).

I don't know whether there's anything interesting to say about such circuits beyond the classical case, but this seems to me to be the most promising candidate definition of a "quantum monotone circuit".

A quantum variant of Razborov's result

Consider the exposition by Tim Gowers of the results of Alon & Boppana (1987), Combinatorica 7 pp. 1–22 which strengthen Razborov's results (and makes explicit some of his techniques) for the monotone complexity of CLIQUE. Gowers presents this in terms of a recursive construction of a family of sets, staring from the "half-spaces" $$E_j = \Bigl\{ \mathbf x \in \{0,1\}^n \;:\; x_j = 1 \Bigr\}$$ of the boolean cube for each $1 \leqslant j \leqslant n$. If we remove the priviledged position of the standard basis in the base sets, in analogy to the Quantum Lovász Local Lemma, we may consider a subspace of $\mathcal H_2^{\otimes n}$ to correspond to a binary proposition (whether a state belongs to the subspace, or is instead orthogonal to it) which might arise from measurement. For instance, we may consider $n$ subspaces $\mathcal A_j \leqslant \mathcal H_2^{\otimes n}$ given by
$$\begin{align*} \mathcal A_j = U_j \mathcal E_j \;, & \text{ for each $1 \leqslant j \leqslant n$} \\ \text{where }
&\mathcal E_j := \Bigl\{ | \mathbf x \rangle \;:\; \mathbf x \in E_j \Bigr\} ; \\
&U_j : \mathcal H_2^{\otimes n} \to \mathcal H_2^{\otimes n} \text{ a unitary of bounded complexity}.
\end{align*}$$
We allow the quantum-logical analogues of conjunction and disjunction of subspaces:
$$\begin{gather*}
\mathcal A \wedge \mathcal B = \mathcal A \cap \mathcal B ; \\
\mathcal A \vee \mathcal B = \mathcal A + \mathcal B = \Bigl\{ \mathbf a + \mathbf b \,:\, \mathbf a \in \mathcal A\;,\; \mathbf b \in \mathcal B \Bigr\} .
\end{gather*}$$
We then ask how long a recursive construction of conjunctions and disjunctions of spaces are required to obtain a space $C$, such that the projector $\Pi_C$ onto $C$ differs only slightly from the projector $\Pi_{K(r)}$ onto the space spanned by the indicator functions of graphs having cliques of size $r$; for instance, so that $\| \Pi_C - \Pi_{K(r)} \|_\infty <\; 1/\mathrm{poly}(n) $. The monotonic part is involved in the quantum logical operations, and the primitive propositions about the input are quantum as well.

In the general case, there is a problem with treating this as a computational problem: the disjunction doesn't correspond to any knowledge which could be obtained with certainty by measurements on a finite number of copies using black-box measurements for $\mathcal A$ and $\mathcal B$ alone, unless they are the images of commuting projectors. This general problem can still be treated as an interesting result about geometrico-combinatorical complexity, and might give rise to results related to frustrated local Hamiltionians. However, it might be more natural to just require that the subspaces $\mathcal A_j$ arise from commuting projectors, in which case the disjunction is just the classical OR of the measurement outcomes of those projectors. Then we may require that the unitaries $U_j$ all be the same, and this becomes a problem about a unitary circuit (which gives rise to the "primitive events") with monotone classical post-processing (which performs the logical operations on those events).

Note also that if we do not impose any further restrictions on the spaces $\mathcal A_j$, it may being a subspace with very high overlap with some space $\mathcal E_k^\bot$ spanned by standard basis states $\mathbf x \in \bar E_k$, which are those binary strings in which $x_k = 0$.

If this possibility makes you squeamish, you can always require that $\mathcal A_j$ has an angle of separation from any $\mathcal E_k^\bot$ of at least $\frac{\pi}{2} - 1/\mathrm{poly}(n)$ (so that our primitive subspaces are, at worst, approximately unbiased from the subspaces in which one of the bits is set to 1).
If we don't impose such a restriction, it seems to me that admitting subspaces having high overlap with $\mathcal E_k^\bot$ would be an obstacle to approximating CLIQUE(r) anyway; either we would be more-or-less restricted to considering the absence of a particular edge (rather than its presence), or we would be forced to ignore one of the edges altogether. So, I do not see it as terribly important to impose any restrictions on $\mathcal A_j$, except possibly that they all are the images of a commuting set of projectors, if one's goal is to consider how to "monotonically evaluate CLIQUE from simple quantum propositions". At worst, it would amount classically to allowing NOT gates at the input (and having all fan-out occur after the negation).

Again, it is not clear to me whether substituting the base sets with arbitrary subspaces of $\mathcal H_2^{\otimes n}$ gives rise to a more interesting problem than just using the subspaces $\mathcal E_j$; though if we restrict ourselves to the case of CNF formulae (either in the commuting or the non-commuting case), the results we obtain would correspond to some notion of complexity of a frustration-free Hamiltonian whose ground-state manifold consisted of standard basis states representing cliques.

you ask basically two questions of widely divergent difficulty, at the frontier of two large fields, ie boolean circuits & QM computing, about the possibility of what is sometimes called a "bridge theorem" in mathematics:

quantum analog of monotone circuits
quantum analog of Razborovs thm

the short candid answer is no or not so far.

for (1), not as hard a question, but still apparently rarely considered, did turn up the following reference which could be taken as a related case in the literature.

Hardness of approximation for quantum problems by Gharibian and Kempe

they consider some "monotone" problems in a quantum context eg QMSA, "Quantum Monotone Minimum Satisfying Assignment, QMSA", ie a SAT QM analog; (also another problem Quantum Monotone Minimum Weight Word, QMW) and show some approximation hardness results, ie lower bounds. they dont consider monotone quantum circuits per se but an idea could be that a quantum circuit or algorithm that solves the monotone function QMSA can be taken as a QM analog.

as for (2) it would be a very advanced result if it existed which it does not seem to "so far". Razborov's thm is basically a lower bound "bottleneck" type result considered a distinct breakthrough and near-unrivalled result in (monotone) circuit theory.

so roughly speaking yes of course there are some lower bound bottlenecks found in QM computing, eg related to direct product theorems, for a survey see eg

Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs by Spalek

however, arguably a better analogous QM computing lower bound would put a lower bound on number of qubit operations or possibly based on "complete" gates like Toffoli gates for a monotone function. am not aware of proofs of this type.

another approach might limit the analysis to special quantum AND and OR gates with extra "ancilla" bits added to make the gates reversible.


Complexity Theory in Finance and journals? What journals are there that try to combine these two areas ? I came across the Algorithmic Finance Journal, are there others ? Looking at papers, mixed to overly -ve views about the quality and direction.

Not sure if such a combo can be useful in practice.

To answer your question, I don't think you have done your homework.

Look at the thread:
Computational complexity in quantitative finance

But if this is a general remark about the journal. The editorial board appears almost impeccable. Sure, it looks a bit suspect that the editor in chief advocated a field that has been dubbed controversial as seen in A New Kind of Finance.
Some critics maintain that the creation of the journal is strongly coupled with Wolfram Research's efforts to tap academics in the finance field. Other hidden agendas ?

Also consult with Wilmott's thread:
http://www.wilmott.com/messageview.cfm?catid=11&threadid=89959

Last, my 3 cents. The inaugural issue is one that usually sets the tone. Papers looked good.

Efficient Greek Estimation in Generic Swap-Rate Market Models.
This is by the great Mark Joshi. It deals with how to compute Greeks using automatic differentiation for a range of swap-rate market models. It's useful to practitioners since they want fast Greeks.

Markets are Efficient if and Only if P = NP. Not an expert in TCS, so refer to thread above computational-complexity-in-quantitative-finance for comments.

Forecasting Prices from Level-I Quotes in the Presence of Hidden Liquidity. Seemed important.

Binomial Options Pricing Has No Closed-Form Solution. Nifty. Nice read.


Why is P vs. NP so hard? Why is $\mathsf{P}$ vs. $\mathsf{NP}$ problem considered so important?

Is $\mathsf{P}$ vs. $\mathsf{NP}$ the hardest mathematical problem?

Why is it so hard?

All I'm looking for is the hindrances to solving $\mathsf{P}$ vs. $\mathsf{NP}$. Are there any theorems that help explain why $\mathsf{P}$ vs. $\mathsf{NP}$ is so hard?

I guess the best answer to your question is to point out that there have been several "barriers" to proving the P vs NP problem which have been identified and which rule out a number of approaches to a proof.

The three main barriers identified are relativization, natural proofs and algebrization. All of these are described on the P vs NP Wikipedia page under the heading "Results about the difficulty of proof", here.

A more detailed explanation can be found in the papers outlining these barriers referenced on the same Wikipedia page.

The patronizing answer is that it amounts to a non-existence proof.

If P != NP (as is commonly considered to be very likely), then proving it amounts to proving that something doesn't exist. Proofs of that type tend to be fairly simple (Comparison sort can't be faster than O(n log n) because it take that many comparisons/bits to be able to enumerate all reordering. A solution to the halting problem directly leads to a contradiction.) or darn near impossible (Fermat's Last Theorem, the four color map problem)


coNP certificate for Graph Isomorphism It is easy to see that graph isomorphism(GI) is in NP. It is a major open problem whether GI is in coNP. Are there any potential candidates of properties of graphs that can be used as coNP certificates of GI. Any conjectures that imply $GI \in coNP$ ? What are some implications of $GI \in coNP$ ?

If $GI$ is in $coNP$, then we would have the result: $GI$ is not $NP$-complete unless $NP=coNP=PH$.  (Currently known: $GI$ is not $NP$-complete unless $\Sigma_2 P = \Pi_2 P = PH$).

Since $GI$ is in $coAM$, obviously derandomizing $coAM$ (doi link) would put $GI \in coNP$, but I don't know of any candidate graph properties for putting $GI \in coNP$ otherwise. I look forward to more answers though!

Interestingly, in that paper they also show that Graph Non-Isomorphism has subexponential size proofs -- that is, $GI \in co NSUBEXP$ -- unless $PH = \Sigma_3 P$.  This is at least headed in the direction of showing conditionally that $GI \in coNP$.

It could be interesting to point out that if GI is not in coNP then P ≠ NP.

1)If GI is not in coNp then GI ≠ NGI

2)If GI ≠ NGI then GI ≠ P

3)If GI ≠ P then P ≠ NP

As a corollary of the upon propositions we have: if GI is not in coNP then P ≠ NP.
The same holds if NGI is not in NP.


Algorithm Suggestion for Scoring System - weighted solution I'm trying to validate a series of words that are provided by users. I'm trying to come up with a scoring system that will determine the likelihood that the series of words are indeed valid words.

Assume the following input:

xxx yyy zzz

The first thing I do is check each word individually against a database of words that I have. So, let's say that xxx was in the database, so we are 100% sure it's a valid word. Then let's say that yyy doesn't exist in the database, but a possible variation of its spelling exist (say yyyy). We don't give yyy a score of 100%, but maybe something lower (let's say 90%). Then zzz just doesn't exist at all in the database. So, zzz gets a score of 0%.

So we have something like this:

xxx = 100%
yyy = 90%
zzz = 0%

Assume further that the users are either going to either:

Provide a list of all valid words (most likely)
Provide a list of all invalid words (likely)
Provide a list of a mix of valid and invalid words (not likely)

As a whole, what is a good scoring system to determine a confidence score that xxx yyy zzz is a series of valid words? I'm not looking for anything too complex, but getting the average of the scores doesn't seem right. If some words in the list of words are valid, I think it increases the likelihood that the word not found in the database is an actual word also (it's just a limitation of the database that it doesn't contain that particular word).

NOTE: The input will generally be a minimum of 2 words (and mostly 2 words), but can be 3, 4, 5 (and maybe even more in some rare cases).

I don't think this question is related at all with approximation algorithms, or theoretical CS.

Please take the following as some free, non-exhaustive, thoughts on your question.

It seems to me that what you want is just the probability that a given sequence of words contains only valid words.

Let me assume that each word is chosen independently (which it isn't true).
Suppose we have $k$ words, call $\sigma_i$ the i-th of such words.
Call $A_i$ the event "$\sigma_i$ is a valid word" and $A$ the event "all words are valid".

Under this assumptions you have:
$$
P(A) = \prod_{i=1}^{k}P(A_i)
$$

so you only need to assign a probability to each word (and you've already given such a distribution in you question).
However you may want to apply some smoothing: if you set $P(A_i)=0$ for some $A_i$ then also $P(A)$ will be $0$ (if you are sure that a word is not valid, then then the whole phrase cannot be valid).

A bayesian approach only requires conditional independency. For example you can compare the following two quantities (and choose the highest):

$$
P(A | \sigma_1, \dots, \sigma_k) \propto  P(\sigma_1, \dots, \sigma_k | A) P(A) = \prod_{i=1}^{k}P(\sigma_i|A) P(A)
$$
$$
P(A^C | \sigma_1, \dots, \sigma_k) \propto  P(\sigma_1, \dots, \sigma_k | A^C) P(A^C) = \prod_{i=1}^{k}P(\sigma_i|A^C) (1 - P(A))
$$

where $P(\sigma_i|A)$ is the probability that the word $\sigma_i$ appears in a valid phrase, $P(\sigma_i|A^C)$ is the probability that $\sigma_i$ appears in an invalid phrase and and P(A) is the probability that a valid phrase shows up.

In the above we are just differentiating "valid" from "invalid" phrases. If you want to account for "completely valid", "completely invalid" and "mixed up" phrases you can do something similar.

You'll need to assign three probabilities to each word $\sigma_i$: $P(\sigma_i|valid)$, $P(\sigma_i|invalid)$, $P(\sigma_i|mixed)$ and three "a priori" probabilities, for example:

$P(valid) = 0.55$  (most likely)
$P(invalid) = 0.40$ (likely)
$P(mixed) = 0.05$ (not likely)

As you are coming from SOF you are looking for a pragmatic solution which may not be theoretically complete and yet such a solution is hard to be found in SOF. Although the information is incomplete by the nature of your question, so the trade-offs cannot figured precisely, according to your example:

It is clear what to do with xxx
Scoring yyy is highly based on missing data of your question. For  now, I guess there would be more than just one yyyy with 90% correlation i.g. yyyyy with 80% correlation... What I go for, if possible, based on the problem, is checking which option user will pick up at that point (get a user feedback, i.g. Google suggestions) so if the word still is not in main table, spelling error is less common since user has not made a choice from provided list. Word correlation algorithm would be the heart of your solution and I have no suggestion for it with given amount of data in your question. Personally I prefer to adhere to a standard one based on my purpose rather than creating a new one. If the correlation is one-to-one it would be easy, but if the context matters i.e. yyyy is surrounded by with words and whats their position, it would become a nightmare. That case the scoring should be based on domain's Ontology.
I would not score zzz to zero without consequences. Store them in a temporary table and every-time a new instance shows up, after checking main table, I'll check temp table and if the word is there, will score it up (not just +1, preferably a fraction of user reputation which could be considered as a mutation in compare to biological systems), but yet score it zero. After the word gets enough reputation (one of your constants which is affected by you policies; you need a bunch of these parameters in your design), I'll move it to main table and update the previous interpretations according to new fact (New Fact is:zzz is now a valid word like xxx, mutation is selected by nature)
After all, a reputation system for users is inevitable i.e. what Wikipedia does under the hood. I say inevitable because from System Thinking perspective, you need feed-backs to keep your system alive. For example ratio of matching or non-matching words could be counted as part of this score. You can add up new ideas i.e. if a word from temp table get enough score to move to main table, the first user who suggested the word (word owner in temp table) could get a bonus for his creativity and courage, and also subsequent confirming guys, by a fraction. This is up to your policy and what you are going to motivate. Latter example will motivate users in such a way which results in fast dbase growth if it is intended. Precise of this growing dbase is dependent on how fast you move words from temp table to main table (a trade-off between growth rate and precision).
When implementing a reputation system, consider storing real data (not information, which is processed data), your parameters and some cache tables which would be updated by triggers. New valid word, invalid words and user reputations could be calculated based on new rules as like as these rules have been used from the first day of system existence. That way upon policy changes, you will lose noting important, just interpretations will change. From here, you should analyze stored system's data periodically and update policies/rules according to new recognized patterns which could be considered as the system's knowledge. So your system's knowledge iteratively increases over the time.


Edge-weight updates in all pair shortest path problem I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network.  An answer to my previous question led me to Hiroki Yanagisawa's paper "A multi-source label-correcting algorithm for the all-pairs shortest paths problem" [IPDPS 2010] which is performing really well.

But what about updates?  I couldn't produce a technique which can update the shortest paths quickly when the weight of an edge changes.  On researching, I came across a paper "On Dynamic Shortest Path problems", which states that

  Reductions that show that the incremental and decremental single-source
  shortest-paths problems, for weighted directed or undirected
  graphs, are, in a strong sense, at least as hard as the static all-pairs
  shortest-paths problem.

So the question is: Are there useful heuristic approaches to solve this problem?

your question seems quite advanced and it seems unlikely anyone has considered the incremental problem for the particular algorithm you are implementing when the new nonincremental algorithm was published by Yanagisawa as recently as 2010.

the algorithm you cite is apparently designed to be parallelizable therefore that seems like the 1st approach to optimizing it. ie implement it in a highly parallel implementation and just recompute all paths.

I have not seen a paper describing this, but how about this approach which seems to work in theory & in general but details could be tricky (maybe it appears in a paper somewhere-- would be interested if anyone has seen a similar technique). every algorithm to solve the problem must basically reduce to a (2-way?) comparison of edge weights. the resulting paths are built out of the results of these comparisons. the "comparison tree" for every optimal path can be stored during the 1st computation of all pairs.

then when any weights are changed, traverse through all prior stored/built-up comparison trees to recompute the answer. probably, for small changes, one would not have to descend "deeply" into those trees because the results of some or "many" prior comparisons are unchanged. one may have to modify the trees if new "comparison paths" in the trees are triggered but again this might not be expensive. however there would be a threshold where it is simpler to recompute everything from scratch when there are too many weight changes.

the main question of course is the memory cost of storing all the comparison trees.

(fineprint: and if all this actually worked, it would likely be a significant advance & publishable result.)

And in what kinds of updates are you interested? Both weight increase and decrease? Obviously, it should not be hard to solve edge increases since such an update influences only those optimal paths containing the changed edge and it is not hard to recomputed them quickly (actually, it can be done even more efficiently). Weight decrease is harder case but it does not make sense in route planning practice (usually).

Anyway, if you are already using some route planning (all pairs shortest path) approach, you should look for its "dynamization". I would not consider heuristics since I am not aware of any good heuristic route planning algorithm.

So what kind of updates are we talking about?


How do continuations represent negations (under the Curry–Howard correspondence)? Under the Curry–Howard correspondence, types can be thought of as propositions, and values inhabiting a type can be thought of as proofs that the corresponding proposition is true. (E.g., the Cartesian product is logical conjunction.)

Negation is represented as $A \to \bot$, where $\bot$ is the empty type. This works because if a type is inhabited, there can't be any function $A \to \bot$ (if you do you have such a function and the type is inhabited, feed the value into it and you get an element of the empty type, hence a contradiction), and vice versa (if $A$ is empty, the empty function $A \to \bot$ exists).

But once you add continuations to your language, an $A$-continuation can also be given the type $A \to \bot$. (see e.g. the symmetric lambda calculus). This apparently provides computational meaning to classical theorems; for example, the $\mathcal{C}$-operator (a basic operator for manipulating continuations), has type $\neg\neg A \to A$.

But can't you have continuations for non-empty types? If you add continuations, does $\neg A$ no longer express "$A$ is-empty/is-false/has-no-proofs"? It can't, right? This formulation makes an inhabitant of $\mathbb{N} \to \bot$ axiomatic, and $\mathbb{N}$ certainly isn't uninhabited. So what does "$\neg A$" actually express, if not "$A$ is-empty/is-false/has-no-proof"? And how do you actually express "$A$ is-empty/is-false/has-no-proof" when continuations exist?

When one associates negation with continuations, it is probably not ideal to think of it in terms of an 'empty' type. Continuation passing can be done with respect to any result type, and if that type is held abstract, it works a lot like 'false' in that there is no introduction rule for it.

With respect to the paper you linked (I'm by no means an expert on it, and just skimmed it, really), I think it might help to study the reduction rules. It appears to me that the goal of the logic is to construct an expression $e : +\mathsf{int}$ and reduce that expression to a numeral $n$. This means that the continuation $\bullet : ¬int$ is not something that would be valid as a program in itself. Rather it is a clue that the abstract 'result type' is actually $\mathsf{int}$, because we are interested in using continuation-based computations that eventually result in integers. $\bullet$ is something that immediately completes the computation, hence the rules:

$$(begin)\ \ \ \  e : +int \leadsto \langle e | \bullet \rangle$$
$$(end)\ \ \ \  \langle n | \bullet \rangle \leadsto n$$

I don't know what happens if you have $\bullet$ involved in other situations, or if you can, but I might expect it to abort other continuations and end the computation. It seems more like it can only be the initial continuation based on the rules, though.

Now, one answer to your question is that this system is not even trying to reason about uninhabited types. It is using a correspondence between the logical rules and control flow, without the specific semantic meaning of negation. One thing you might want to check out is linear logic, because it actually has two sorts of 'false' or zero, one which is about control flow, and one which is about emptiness. The linearity is important for keeping them separate.

In that setting, $⊥$ is the 'false' that has to do with control flow, and it gets things like double negation elimination and excluded middle (with a corresponding 'or' that is more related to representing functions via continuations than it is disjoint union), while there is also $0$, which gets the principle of explosion (which is arguably the distinct part of the empty type1). An interesting thing about this setting is that even though the logic seems classical, it is actually constructive because of the more restricted rules. Double negation by the 'control flow' bottom $⊥$ is just a different (possibly more convenient) way of structuring a program that computes the doubly-negated type (and 'excluded middle' is a decomposed identity function).

Fillinski's 'Linear Continuations' might be a good place to start reading, although there are probably other references as well.

In the continuation-with-abstract-result-type setting, you can also interpret explosion, but it has sort of a different meaning. Effectively such interpretations are always 'delimited' somewhere, even if it's only the end of your program. Explosion means that if you somehow get a value of the abstract result type, you can throw away your current continuation and jump to the delimiter. So it is an 'abort' operation. Linear logic doesn't allow this; all continuations must be used (and used exactly once), so explosion must be justified by involving an 'impossible' situation, like having a value of an empty type.

The type of a function (lambda) is the type of its argument and the type of what it returns. Some functions do not return anything - they go into an infinite loop or in some theories raise an error, and thus their return type is empty. It's not that their return type is null (or unit type, or really they are procedures). It's that they never return anything and any potential capture of their result value will never happen.

Continuations are, for all practical purposes, infinite loops. They never return anything and thus their return type is void. Waiting for them to finish will take forever.

Now you can modify your theory slightly. You may say that when a continuation receives a special value from the void type, it finishes and returns null, for instance.
This does not affect the definition of a continuation. The continuation will still never return, because this value from the void type does not exist. However, the type of continuation behaves as negation from now. When you feed a value from non-empty type, the continuation loops forever. When you feed it a hypothetical value from a void type, it returns null, which is non-empty.

You could make it a little bit less hypothetical if you introduce a special "error" value. The use of this value is forbidden, that means when you use it, an error happens (compare it to throwing an exception). Now "empty type" does not mean "looping forever" but "raising an error, failing to finish normally". You define a continuation in such a way that when they encounter an error, they quit gracefully returning a normal value.

Now when you feed the continuation a normal value, they would loop forever, as expected. When you feed them the "error" value, they encounter an error the moment they try to use it and exit, returning a value.

Again, this works as a type negation. Here "false type" does mean "a type without any non-error value". This could be a valid theory for a language featuring weak pointers (like C) where the "error" value is a null pointer. You can define some void type without any normal value but you still can make a null pointer to that type, where dereferencing always fails. (Side note: "void" in C doesn't mean a "false type" but unit type actually.)

The key point is that you can always extend your theory with some axiom that says: when we receive a value from the empty type, something happens. This is always compatible with the theory, as this can never happen, yet it can serve some theoretical purposes.


Büchi automata with acceptance strategy The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense : there is a function $\sigma:\Sigma^*\to Q$ which can be used to pilot runs of $A$. We formalize this by the following conditions :

$\sigma(\epsilon)=q_0$

for all $u\in\Sigma^*$ and $a\in\Sigma$, $(\sigma(u),a,\sigma(ua))\in\Delta$

for all $w=a_0a_1a_2\dots\in L$, the run piloted by $\sigma$ is accepting, i.e. the sequence $\sigma(\epsilon),\sigma(a_0),\sigma(a_0a_1),\sigma(a_0a_1a_2),\dots$ has infinitely many elements in $F$.

To subsume the conditions, $A$ can accept any word of its language without having to guess anything about the future.
Then, under these assumptions on $A$, is it true that $A$ can be determinized just by removing transitions ? In other words, can we always choose the next transition depending only on the current state and letter ? Is there any reference on the subject ? The same question can then be asked on co-Büchi automata, and more generally on parity automata.
What is known
Here are some partial results.
First, we can restrict $\sigma$ to nondeterminstic choices between states having the same residual. Indeed, if $L(q)$ is the language accepted from $q$, an accepting strategy cannot choose $q_1$ over $q_2$ at some point, if there is $w\in L(q_2)\setminus L(q_1)$.
Notice that the remaining choices do matter, so despite the intuition, this is not enough to get rid of the nondeterminism. This is because it is possible to stay ad infinitum in a good residual (i.e. the remaining of the word is in the residual), but reject the word because not infinitely many Büchi states are seen. This is the main difficulty of the problem : an infinite run can be wrong, without making any fatal mistake at some point.
Second, the problem is solved if $L=\Sigma^\omega$, i.e. all words are accepted by $A$. In this case, we can view $A$ as a Büchi game where Player I chooses input letters and Player II chooses transitions. Then we can use positional determinacy of Büchi games to extract a positional strategy for Player II. This arguments even works in the more general case of parity automata. The difficulty of this problem comes from the fact that some words are not in $L$, and in this case the strategy $\sigma$ can have any behaviour.
Third, here is a proof that under the assumptions, the language $L$ is in the class of deterministic Büchi languages, witnessed by an automaton with states $2^Q$.
Notice that this implies that $L$ cannot be any $\omega$-regular language, for instance  if $L=(a+b)^*a^\omega$, no strategy $\sigma$ matching the conditions can exist.
We start by restricting the transitions according to the first remark : the only choices we can make do not impact on the residual language. We only take successors with the maximum residual, they must exist because $\sigma$ exists.
Then, we build $A'=\langle \Sigma, 2^Q, \{ q_0\},F',\Delta'\rangle$ in the following way. $A'$ is the subset automaton of $A$, but every time a Büchi state $q$ appears in the component, all other states can be removed from the component, and we start again from the singleton $\{ q\}$. Then we can set $F'=\{\{ q\} : q\in F\}$. We can verify that $A'$ is a deterministic Büchi automaton for $L$.
Finally, by putting together the second and the third remarks, we can always obtain a finite memory-strategy $\sigma$, by using a positional strategy for Player II in the game $A\times A'$ where Player I chooses letters, Player II chooses transitions in $A$ and wins if $A$ accepts whenever $A'$ accepts.

It turns out the answer is no, some counter-examples can be found in this paper.
Also here is a more recent work showing that such Büchi automata can be recognized in polynomial time.

As you pointed out, non-deterministic and deterministic Buchi automata accept different languages. The most famous 'determinization' for a Buchi automaton is given by Safra (search "Safra's construction" on web. Here's one document that comes up: www.cs.cornell.edu/courses/cs686/2003sp/Handouts/safra.pdf). The procedure is quite intricate and involves transforming given Buchi automaton into a deterministic Rabin automaton (having 'accepting' F states and 'rejecting' G states: \sigma has only finitely many states in G). Safra's construction involves much more than simply removing transitions and/or usual subset construction.


The complexity of recognizing optimal set systems for the V-C dimension The Vapnik-Chervonenkis dimension of a set system $(X,\mathcal S)$ with ground set $X$ is the maximum size of a set $X'\subseteq X$ such that for each subset $X'_i\subseteq X'$, there is a set $S_i\in\mathcal S$ with $S_i\cap X'=X'_i$.

The following decision problem is then natural:

  VC DIMENSION
  Input: a set system $(X,\mathcal S)$ and an integer $k$.
  Task: decide whether the VC dimension of $(X,\mathcal S)$ is at least $k$.

Since there are $2^{|X'|}$ subsets of $X'$, we have $|X'|\leq\log_2(|\mathcal S|)$, and hence VC DIMENSION can be solved in time $O\binom{|X|}{\log_2(|\mathcal S|)}$. For the hardness side, VC DIMENSION is LOGNP-hard (see here). However, I wonder whether something is known for the following specific case:

  My question: what is the complexity of deciding whether a given set system $(X,\mathcal S)$ has VC dimension exactly $\log_2(|\mathcal S|)$?

This doesn't answer the question, but it might be helpful.  Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented:

On the Complexity of Approximating the VC Dimension
http://users.cms.caltech.edu/~umans/papers/MU01-final.ps

For the VC dimension to be exactly $\log_2(|\mathcal{S}|)$, $\mathcal{S}$ must be the powerset of some subset of $X$ of size $\log_2(|\mathcal{S}|)$, so you would need to check whether this is true, which takes, I'd say, time $O(|\mathcal{S}|)$.


Distinguishing semantics vs syntactic techniques and the syntax of your semantic domains Consider a denotational semantics from simply-typed $\lambda$-calculus into dependent type theory. Is that actually a (trivial) term transformation into that dependent type theory? After all, type theory has a syntax.

In fact, even set theory has a syntax*! So how do we distinguish a denotational semantics from a compositional term transformation?

Now, let's generalize to less trivial program transformations — say, transformation to continuation-passing style (or store-passing style, environment passing style, ...). You can show the same idea through a non-standard semantics (here, a continuation-passing semantics) or a term transformation into a continuation-passing term, and they're distinguished by a binding-time shift. Again, isn't the non-standard semantics also a term transformation?

This is a concrete confusion which I've observed at least twice:

In my work (on incremental computation) I've used a non-standard denotational semantics into type theory (a "change-passing" semantics). After a presentation of that, Gabriel Scherer remarked (kindly) that for him, that was a term transformation into a dependently typed language.
"F-ing modules" preempts this confusion — they defend their presentation of the syntax of semantic objects.

  Semantic signatures. The syntax of semantic signatures is given in Figure 9. (And no, this is not an oxymoron, for in our setting the “semantic objects” we are using to model modules are merely pieces of Fω syntax.) [Emphasis added.]

*Apparently, some (non-formalists) claim that set theory is not "just syntax", but something ontologically different. I'll ignore this subtle philosophical issue; the only reference I know on it is Raymond Turner's Understanding Programming Languages.

I think I understand your difficulties, indeed if you consider just a programming language both a denotational semantics and a term transformation (into another language) are nothing but mappings of syntactic elements of the given language in mathematical objects (elements of a domain in the first case, terms of the language in the second case).

Notheless differences between these two semantics start to arise if you put an operational semantics in your programming language and so you want that the denotational semantics and term transformations are compatible with this operational semantic.

In the first case you would like that denotation of terms/programs that compute the same results have the same denotation, hence the denotational semantics should associates to operational convertible terms the same denotation.

In the second case you would simply like that the term transformation maps terms/programs in such a way to preserve the derivations (if you reguard terms and reduction/derivations respectively as objects and morphisms of a category you can say that a term transformation should be a functor).
In the first case we lost information about the reduction between terms in the second case we preserve it.

In the first case semantically equivalent terms are mapped in the same denotation in the second they are mapped just in operationally equivalent terms but the term translation does not guaratee that equivalent terms are mapped in the same term (and usually that's not the case).

Denotational semantics  allows to easily find different terms, supposing that the denotation-mapping is easily computable, in order to distinguish two programs we just need to compute the denotation an see if they are different values.
Nonetheless in this way we lost information about the reductions (computations of our operational semantics) which are instead preserved by the term transformations.

I hope this helps.

There's at least one important difference between a (compositional) term transformation and a semantics — the output of a term transformation is written in the syntax of an object language, the output of a semantics is written in the syntax of the metalanguage. While a metalanguage has a syntax, you needn't deal with that additional complexity any more — the metatheory takes care of that.

Consider for instance proving $f(a) = f(b)$ from $a = b$.

In a syntactic framework, to do the corresponding thing (go from $a = b$ to $f(a) = f(b)$) you need to apply (in some form) a substitution lemma to the terms $a$, $b$, $f(x)$. EDIT: Also, you need to pick an appropriate equality (usually observational equivalence, but see For what languages is there already a theory of observational equivalence?).
In a semantic framework, you just go from $a = b$ to $f(a) = f(b)$, because $f$ is a "function" and thus takes equals to equals, and because = has been defined appropriately. That's because the metatheory already proved that "functions" satisfy the specification of functions.

According to many, the specification of functions is category theory. I'm tempted to conclude: "One can ignore the syntax of the metalanguage because somebody else proved that the metalanguage operations model the axioms of categories" — but I'm ignoring all the subtle issues for languages bigger than simply-typed $\lambda$-calculus, and I'm not sure that's a good idea.


Is it known whether $BPP\cap NP\subseteq RP$? The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which inequality holds and one relative to which equality holds. It's fairly easy to give an oracle relative to which the classes are equal: any oracle which has $\mathrm{BPP} = \mathrm{RP}$ will work (eg any oracle relative to which "randomness doesn't help much"), as will any oracle which has $\mathrm{NP} \subseteq \mathrm{BPP}$ (eg any oracle relative to which "randomness helps a lot"). There are a lot of these, so I won't bother with the specifics.

It's somewhat more challenging, though still fairly straightforward, to design an oracle relative to which we get $\mathrm{RP} \subsetneq \mathrm{BPP} \cap \mathrm{NP}$. The construction below actually does a bit better: for any constant $c$, there is an oracle relative to which there is a language in $\mathrm{coRP} \cap \mathrm{UP}$ which is not in $\mathrm{RPTIME}[2^{n^c}]$. I'll outline it below.

We'll design an oracle $A$ that contains strings of the form $(x,b,z)$, where $x$ is an $n$-bit string, $b$ is a single bit, and $z$ is a bit string of length $2n^c$. We will also give a language $L^A$ which will be decided by a $\mathrm{coRP}$ machine and a $\mathrm{UP}$ machine as follows:

The $\mathrm{coRP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$ randomly, queries $(x,\mathtt{0},z)$, and copies the answer.
The $\mathrm{UP}$ machine, on input $x$, guesses $z$ of length $2|x|^c$, queries $(x,\mathtt{1},z)$, and copies the answer.

To make the above-specified machines actually meet their promises, we need $A$ to satisfy some properties. For every $x$, one of these two options must be the case:

Option 1: At most half of $z$ choices have $(x,\mathtt{0},z) \in A$ and zero $z$ choices have $(x,\mathtt{1},z) \in A$. (In this case, $x \not\in L^A$.)
Option 2: Every $z$ choice has $(x,\mathtt{0},z) \in A$ and precisely one $z$ choice has $(x,\mathtt{1},z) \in A$. (In this case, $x \in L^A$.)

Our aim will be to specify $A$ satisfying these promises so that $L^A$ diagonalizes against every $\mathrm{RPTIME}[2^{n^c}]$ machine. To try to keep this already long answer short, I'll drop the oracle construction machinery and a lot of the unimportant details, and explain how to diagonalize against a particular machine. Fix $M$ a randomized Turing machine, and let $x$ be an input so that we have full control over the selection of $b$'s and $z$'s so that $(x,b,z) \in A$. We will break $M$ on $x$.

Case 1: Suppose there is a way to select the $z$'s so that $A$ satisfies the first option of its promise, and $M$ has a choice of randomness which accepts. Then we will commit $A$ to this selection. Then $M$ cannot simultaneously satisfy the $\mathrm{RP}$ promise and reject $x$. Nevertheless, $x \not\in L^A$. So we have diagonalized against $M$.
Case 2: Next, assume that the previous case did not work out. We will now show that then $M$ can be forced either to break the $\mathrm{RP}$ promise or to reject on some choice of $A$ satisfying the second option of its promise. This diagonalizes against $M$. We will do this in two steps:

Show that for every fixed choice $r$ of $M$'s random bits, $M$ must reject when all of its queries of the form $(x,\mathtt{0},z)$ are in $A$ and all of its queries of the form $(x,\mathtt{1},z)$ are not in $A$.
Show that we can flip an answer $(x,\mathtt{1},z)$ of $A$ for some choice of $z$ without affecting the acceptance probability of $M$ by much.

Indeed, if we start with $A$ from step 1, $M$'s acceptance probability is zero. $A$ doesn't quite satisfy the second option of its promise, but we can then flip a single bit as in step 2 and it will. Since flipping the bit causes $M$'s acceptance probability to stay near zero, it follows that $M$ cannot simultaneously accept $x$ and satisfy the $\mathrm{RP}$ promise.

It remains to argue the two steps in Case 2:

Fix a choice of random bits $r$ for $M$. Now simulate $M$ using $r$ as the randomness and answering the queries so that $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$. Observe that $M$ makes at most $2^{n^c}$ queries. Since there are $2^{2n^c}$ choices of $z$, we can fix the unqueried choices of $z$ to have $(x,\mathtt{0},z) \not\in A$, and have $A$ still satisfy the first option of its promise. Since we couldn't make Case 2 work for $M$, this means $M$ must reject on all its choices of randomness relative to $A$, and in particular on $r$. It follows that if we select $A$ to have $(x,\mathtt{0},z) \in A$ and $(x,\mathtt{1},z) \not\in A$ for every choice of $z$, then for every choice of random bits $r$, $M$ rejects relative to $A$.
Suppose that for every $z$, the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is at least $1/2$. Then the total number of queries is at least $2^{2n^c} 2^{2^{n^c}}/2$. On the other hand, $M$ makes at most $2^{2^{n^c}} 2^{n^c}$ queries across all its branches, a contradiction. Hence there is a choice of $z$ so that the fraction of random bits for which $M$ queries $(x,\mathtt{1},z)$ is less than 1/2. Flipping the value of $A$ on this string therefore affects the acceptance probability of $M$ by less than $1/2$.

No, it's not known.
This might not be the most convincing proof, but take a look at
this Google search.


Concepts in theoretical CS that would be approachable ages 8-14 Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.

Computer Science Unplugged addresses kids (and teachers) in primary school.

study of the mandelbrot set & fractals via visual/graphical explorations. the simple formula $z \leftarrow z^2 + c$ can be understood by kids who have learned complex numbers or even by kids who havent by replacing it with the formula written with reals only. also another case of complex or emergent phenomena arising from simple equations.


Concise introduction to algorithms for mathematicians I am looking for a concise introductory text on algorithms with a high ratio $$\frac{\mbox{theory covered}}{\mbox{total number of pages}}.$$ It should begin at the beginning but then progress quickly without spending too much time on real world examples, elementary proof techniques, etc. As a research mathematician I have a solid background in mathematics which I happily employ to understand formalisms and condensed proofs, for example.

Do there exist such texts? Any recommendations?

I like this textbook very much:

Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani: Algorithms
Published by McGraw-Hill 2007.

I don't calculate your suggested ratio but I think you will also like it :)

try Concise encyclopedia of computer science, Wiley. unfortunately a complete/thorough table of contents for this ref does not seem to be available on the web [a somewhat unusual omission nowadays, maybe Wiley could correct this on request] but the complete index appears to be browsable on amazon. it has coverage that is much broader than TCS such as hardware concepts etc, but it appears to cover significant parts of TCS eg:

Information and Data
Software
Mathematics of Computing
Theory of Computation
Methodologies
Applications

it is a 902pp abridged version of the complete encyclopedia, Encyclopedia of Computer Science, 4th Edition, 2064pp


What is the enlightenment I'm supposed to attain after studying finite automata? I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we study deterministic and non-deterministic finite automata (DFA/NFAs)? So here are some answers I came up with after soliloquing  but still fail to see their overall contribution to the 'aha' moment:

To study what they are and aren't capable of i.e. limitations

Why?

Since they are the basic models of theoretical computation and would lay the foundation of other more capable models of computation.

What makes them 'basic'? Is it that they have only one bit of storage and state transitions?

Okay, so what? How does all this contribute to answer the question of computability? It seems Turing machines help understand this really well and there are 'lesser' models of computations like PDAs, DFA/NFAs/Regexes etc. But if one didn't know FAs what is it that they are missing out on?

So although I 'get it' to some extent, I am unable to answer this question to myself? How best would you explain 'why study D/N-FAs'? What's the question they seek to answer? How does it help and why is it the first thing taught in Automata Theory?

PS: I'm aware of the various lexicographic applications and pattern matchers that can be implemented as such. However, I don't wish to know what it can be used for practically but what was their reason for use/invention/design during the culmination of studying the theory of computation. Historically speaking what led one to start with this and what 'aha' understanding is it supposed to lead to? If you were to explain their importance to CS students just beginning to study Automata Theory, how'd you do it?

I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole.

Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. Understanding this difference for Turing machines is at the core of (theoretical) computer science. NFAs and DFAs provide the simplest example I know where you can explicitly see the strict gap between determinism and non-determinism.
Computability != Complexity. NFAs and DFAs both represent regular languages and are equivalent in what they compute. They differ in how they compute.
Machines Refine Languages. This is a different take on what we compute and how we compute. You can think of computable languages (and functions) as defining an equivalence class of automata. This is a fundamental perspective change in TCS, where we focus not just on the what, but the how of computation and try to choose the right 'how' when designing an algorithm or understand the space of different how's in studying complexity classes.
The Value of Canonical Representation. DFAs are the quintessential example of a data-structure admitting a canonical representation. Every regular language has a unique, minimal DFA. This means that given a minimal DFA, important operations like language inclusion, complementation, and checking acceptance of a word become trivial. Devising and exploiting canonical representations is a useful trick when developing algorithms.
The Absence of Canonical Representations. There is no well accepted canonical representation of regular expressions or NFA. So, despite the point above, canonical representations do not always exist. You will see this point in many different areas in computer science. (for example, propositional logic formulae also do not have canonical representations, while ROBDDs do).
The Cost of a Canonical Representation. You can even understand the difference between NFAs and DFAs as an algorithmic no-free-lunch theorem. If we want to check language inclusion between, or complement an NFA, you can determinize and minimize it and continue from there. However, this "reduction" operation comes at a cost. You will see examples of canonization at a cost in several other areas of computer science.
Infinite != Undecidable. A common misconception is that problems of an infinitary nature are inherently undecidable. Regular languages contain infinitely many strings and yet have several decidable properties. The theory of regular languages shows you that infinity alone is not the source of undecidability.
Hold Infinity in the Palm of Your Automaton. You can view a finite automaton purely as a data-structure for representing infinite sets. An ROBDD is a data-structure for representing Boolean functions, which you can understand as representing finite sets. A finite-automaton is a natural, infinitary extension of an ROBDD.
The Humble Processor. A modern processor has a lot in it, but you can understand it as a finite automaton. Just this realisation made computer architecture and processor design far less intimidating to me. It also shows that, in practice, if you structure and manipulate your states carefully, you can get very far with finite automata.
The Algebraic Perspective. Regular languages form a syntactic monoid and can be studied from that perspective. More generally, you can in later studies also ask, what is the right algebraic structure corresponding to some computational problem.
The Combinatorial Perspective. A finite-automaton is a labelled graph. Checking if a word is accepted reduces to finding a path in a labelled graph. Automata algorithms amount to graph transformations. Understanding the structure of automata for various sub-families of regular languages is an active research area.
The Algebra-Language-Combinatorics love triangle. The Myhill-Nerode theorem allows you to start with a language and generate an automaton or a syntactic monoid. Mathematically, we obtain a translation between very different types of mathematical objects. It is useful to keep such translations in mind and look for them in other areas of computer science, and to move between them depending on your application.
Mathematics is the Language of Big-Pictures. Regular languages can be characterised by NFAs (graphs), regular expressions (formal grammar), read-only Turing machines (machine), syntactic monoids (algebra), Kleene algebras (algebra), monadic second-order logic, etc. The more general phenomenon is that important, enduring concepts have many different mathematical characterizations, each of which brings different flavours to our understanding of the idea.
Lemmas for the Working Mathematician. The Pumping Lemma is a great example of a theoretical tool that you can leverage to solve different problems. Working with Lemmas is good practice for trying to build upon existing results.
Necessary != Sufficient. The Myhill-Nerode theorem gives you necessary and sufficient conditions for a language to be regular. The Pumping Lemma gives us necessary conditions. Comparing the two and using them in different situations helped me understand the difference between necessary and sufficient conditions in mathematical practice. I also learnt that a reusable necessary and sufficient condition is a luxury.
The Programming Language Perspective. Regular expressions are a simple and beautiful example of a programming language. In concatenation, you have an analogue of sequential composition and in Kleene star, you have the analogue of iteration. In defining the syntax and semantics of regular expressions, you make a baby step in the direction of programming language theory by seeing inductive definitions and compositional semantics.
The Compiler Perspective. The translation from a regular expression to a finite automaton is also a simple, theoretical compiler. You can see the difference between parsing, intermediate-code generation, and compiler optimizations, because of the difference in reading a regular expression, generating an automaton, and then minimizing/determinizing the automaton.
The Power of Iteration. In seeing what you can do in a finite-automaton with a loop and one without, you can appreciate the power of iteration. This can help understanding differences between circuits and machines, or between classical logics and fixed point logics.
Algebra and Coalgebra. Regular languages form a syntactic monoid, which is an algebraic structure. Finite automata form what in the language of category theory is called a coalgebra. In the case of a deterministic automaton, we can easily move between an algebraic and a coalgebraic representation, but in the case of NFAs, this is not so easy.
The Arithmetic Perspective. There is a deep connection between computation and number-theory. You may choose to understand this as a statement about the power of number theory, and/or the universality of computation. You usually know that finite automata can recognize an even number of symbols, and that they cannot count enough to match parenthesis. But how much arithmetic are they capable of? Finite automata can decide Presburger arithmetic formulae. The simplest decision procedure I know for Presburger arithmetic reduces a formula to an automaton. This is one glimpse from which you can progress to Hilbert's 10th problem and it's resolution which led to discovery of a connection between Diophantine equations and Turing machines.
The Logical Perspective. Computation can be understood from a purely logical perspective. Finite automata can be characterised by weak, monadic second order logic over finite words. This is my favourite, non-trivial example of a logical characterisation of a computational device. Descriptive complexity theory shows that many complexity classes have purely logical characterisations too.
Finite Automata are Hiding in Places you Never Imagined.  (Hat-tip to Martin Berger's comment on the connection to coding theory) The 2011 Nobel Prize in Chemistry was given to the discovery of quasi-crystals. The mathematics behind quasi-crystals is connected to aperiodic tilings. One specific aperiodic tiling of the plane is called the Cartwheel Tiling, which consists of a kite shape and a bow-tie shape. You can encode these shapes in terms of 0s and 1s and then study properties of these sequences, which code sequences of patterns. In fact, if you map 0 to 01 and 1 to 0, and repeatedly apply this map to the digit 0, you will get, 0, 01, 010, 01001, etc. Observe that the lengths of these strings follow the Fibonacci sequence. Words generated in this manner are called Fibonacci words. Certain shape sequences observed in Penrose tilings can be coded as Fibonacci words. Such words have been studied from an automat-theoretic perspective, and guess what, some families of words are accepted by finite automata, and even provide examples of worst-case behaviour for standard algorithms such as Hopcroft's minimization algorithm. Please tell me you are dizzy.

I could go on.(And on.)* I find it useful to have automata in the back of my head and recall them every now and then to understand a new concept or to gain intuition about high-level mathematical ideas. I doubt that everything I mention above can be communicated in the first few lectures of a course, or even in a first course. These are long-term rewards based on an initial investment made in the initial lectures of an automata theory course.

To address your title: I don't always seek enlightenment, but when I do, I prefer finite automata. Stay thirsty, my friend.

I see several answers calling FM's "lesser" than Turing machines.

A primary focus in the Post-grad class I took lay in their equivalence, not distinctions. For every FSM model we studied, we had to prove their equivalence to Turing Machines. This is done by implementing a Turing Machine in the FSM. IIRC, we also studied some other computing models that cold not implement a TM, but I forget what those were. The point is, if you can implement a TM, you can run any TM program on the model, given a sufficiently large tape analog for the problem being run.

The thrust of the answer to the question was: TM is the basic computability model, but not very practical when it comes to building useful machines. Hence FSM models.

This was brought home viscerally to me when, at around the same time (1984), I discovered the FORTH language. It's execution engine is built on a pure realization of a Dual Stack PDA. Going deeper I fond this same engine under expression compilers

Although, for me, the real impact of FSM was discovering the book "Theory of Finite Automata" by Trakhtenbrot and Korzynski (?) when I was 18, a discovery that essentially gave me my career.


Where is the proof of universality of Rule110 in Stephen Wolfram's book? I have Stephen Wolfram's book A New Kind Of Science. And I want to find the proof of the universality of Rule 110. I couldn't find the clue in the contents page since it only shows 12 chapters and no details.

Could some one help me please? Does he show the proof in his book at all? What is the page number where he shows the proof?

I'm reading the paper by Matthew Cook for sure. It's just more pictures help me understand things better. I now know pretty well what is the tag system and the cyclic tag system, but still trying to find a way to visualize the equivalence between the tag system and the turing machine. Other resources about this are welcome, too!

Many thanks!

Found it:

cyclic tag system to tag system p.669

glider p.678

The pictures are very helpful!


Intractability of NP-complete problems as a principle of physics? I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical verification, I'm not aware of similar evidence for the P vs NP question.

Additionally, I'm not aware of any direct physical world consequences of the existence of undecidable problems (or existence of uncomputable functions). Protein folding is NP-complete problem but it appears to be taking place very efficiently in biological systems. Scott Aaronson proposed using the NP Hardness Assumption as a principle of physics. He states the assumption informally as "NP-complete problems are intractable in the physical world".

  Assuming NP Hardness Assumption, Why is it hard to design a scientific experiment that decides whether our universe respects the NP Hardness Assumption or not?

Also, Is there any known numerical evidence from experimental mathematics for or against $P\ne NP$?

EDIT: Here is a nice presentation by Scott Aaronson titled Computational Intractability As A Law of Physics

I don't think that the fact that $P\neq NP$ is an asymptotic statement is an automatic "dealbreaker". One can make concrete conjectures that are consistent with our knowledge but stronger than P vs NP such as "It takes at least $2^{n/10}$ steps to find a satisfying assignment for a random n variable 10SAT formula" (with "random" being e.g., the planted model of Achlioptas Coja-Oghlan, this is just an example - I don't know what are reasonable concrete numbers offhand).

Such conjecture can result in a refutable prediction that any natural system that will try to solve this will fail (e.g., get stuck in a local minima), something you can verify with experiments. Indeed, I'm not an expert on this but to my knowledge, as Joe Fitzsimons mentioned, such predictions had been confirmed with Adiabatic computing. (Scott Aaronson also had some entertaining experiments with soap bubbles.)

Of course you can also see some "empirical evidence" for $P \neq NP$  in the fact that people have been trying to solve optimization problems, cryptoanalyze encryptions, etc.. and haven't been successful so far...

We can't efficiently solve the $n$-body problem, but those rocks-for-brains planets seem to manage just fine.


Characterization of union of DCFLs We know that DCFL is not closed under the union operation and
CFL is closed under union and contains the union of DCFLs.

Is there a characterization of finite unions of DCFLs?

One direction is clear:  the union of any finite number of DCFL's is a CFL.

However, a precise characterization of the union-closure of DCFL's was not obvious to me at all (and I teach this stuff and wrote a book on it), so I went searching with a google search.  I found this paper by my colleagues  Martin Kutrib and Andreas Malcher:   Context-Dependent Nondeterminism for Pushdown Automata, O.H. Ibarra and Z. Dang (Eds.): DLT 2006, LNCS 4036, pp. 133–144, 2006.  Theorem 1 gives a characterization of this class.

DCFLs not closed under union hence we will see language higher than DCFLs in Chomsky's classification hierarchy
CFLs are closed under union hence union of two DCFL if not DCFL then CFL you can take the example of a^nb^n and a^2n b^n.


largest language class for which inclusion is decidable am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable.

am also interested in the same question for what were once called "GSMs", generalized sequential machines, or maybe more modernly, FSM "transducers", where if $f(x)$ is the transducer, $C \subset f(C)$, $C$ in the class.

(of course, the problem is also equivalent to determining whether the intersection of a complement is empty.)

[simply asking for the "largest known" language is a literature related question. however some kind of proof that there exists a "largest class" I believe is an open question. although, there might be a straightfwd argument of nonexistence via diagonalization...?]

unfortunately wikipedia does not have some of this basic info for major language classes. wonder if there is any table, paper, or reference esp online.

there is a nice table of decidability & undecidability of basic language questions in [1] but its quite dated at this point.

[1] Hopcroft/Ullman, Intro to Automata Theory, Languages & Computation, 1979

Converted from comment: language inclusion is decidable for very simple deterministic pushdown automata ("On the Inclusion Problem for Very Simple Deterministic Pushdown Automata (1999)" by E. Makinen, 1999)
and a restricted version of timed finite state machine ("On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap" by J. Ouaknine and J. Worrell, 2004).

for a 1st cut answer to this question see p281 of hopcroft/ullman 1979. its a nice table of lots of properties/decision problems wrt basic known languages ie regular, DCFL, CFL, CSL, recursive, r.e. on the horizontal axis and basic questions like "w in L, L= $\oslash $, L=$\Sigma *$" etc on vertical axis.

now they do not explicitly state how the languages are given, but the assumption is they are using their characteristic form eg regular grammars or DFAs for regular languages, DCGs for DCFLs, CSGs for CSLs etc.; nor do they give reference for all the results in cells of the grid, that would be a big effort because of the large size of the table & the diversity of results.

for $L_1 \subseteq L_2$ its decidable for regular sets but undecidable for DCFLs and higher (CFLs, CSLs, recursive, r.e.)

[I typed this question from old memory & had forgotten this result, oops. namely, inclusion problem is decidable for regular sets but not for all standard well known larger language classes. however,still do wonder, could there be a language class "between" regular sets and DCFLs for which inclusion is decidable? or possibly some language class not contained in any of those standard classes?]

but the case for FSM transducers raised in the question may have a different answer.

& I am still not clear on the table, because [as raised in comments] what is the characteristic form for a recursive set? [the r.e. sets are surely given by TMs]

sorry for any confusion in the way the original question was phrased, as always there might be a better way to phrase it.


Algorithms from the Book. Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.

If God had a similar book for algorithms, what algorithm(s) do you think would be a candidate(s)?

If possible, please also supply a clickable reference and the key insight(s) which make it work.

Only one algorithm per answer, please.

Union-find is a beautiful problem whose best algorithm/datastructure (Disjoint Set Forest) is based on a spaghetti stack. While very simple and intuitive enough to explain to an intelligent child, it took several years to get a tight bound on its runtime. Ultimately, its behavior was discovered to be related to the inverse Ackermann Function, a function whose discovery marked a shift in perspective about computation (and was in fact included in Hilbert's On the Infinite).

Wikipedia provides a good introduction to Disjoint Set Forests.

I would like to make a basic remark which doesn't appear in the other answers. The elegance/beauty is somewhat subjective so I wouldn't pick it as a primary criterion for a book of algorithms. It seems more rational to consider the following criterions:

usefulness: does the algorithm have important applications?
intuitivity: is the algorithm easy to understand/implement; does it avoid complex data structures?
conciseness: does the algorithm have a short description in pseudo-code or natural language?

Personally, I rank these three criterions in this order, from the most to the least important. In particular, I advocate a "principle of maximum usefulness", i.e. a good algorithm is one that finds multiple uses for seemingly unrelated applications.

An example is provided by the "merge sort" algorithm: in addition to providing a fast sorting method, it also allows to compute the number of inversions of a permutation in quasi-linear time, i.e. better than the naive quadratic approach. Another example is the simple polynomial algorithm for coloring chordal graphs, which finds applications such as timetabling and register allocation.


Is the following problem NP-Hard? I'm not expert on complexity theory and combinatorial optimization.
I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete.
Thank you in advance for your help.

Input:

Two parameters X and Y, which can be equal.
n customers C1, C2, ... Cn
m types of goods M1, M2 ... Mm

There are X pieces available for each good Mi: a piece of 1kg, another piece of 2kg, ...., a piece of X kg.
Every customer wants to buy a certain number of goods. For example, the client C1 may be interested in buying goods M1, M4, M8 and M9.
A customer is satisfied if he can find all the goods he wants to buy. In addition, the weights of the parts he was able to purchase must satisfy a constraint that I'll explain below.

Output:
How many customers can be satisfied?

The constraint on the weights is as follows:
Take for example the client C1 who is interested in buying goods M1, M4, M8 and M9. Assume that C1 was able to purchase all four goods. Let P1, P2, P3, P4 be the weights of the pieces he was able to buy.
C1 is satisfied if $\sum_i  P_i -1 <Y$.

Edit: Note that the limit Y is common for all customers. The intuition behind the constraint is that we want to limit the number of pieces whose weight is not equal to 1kg.

(I have posted this answer as a comment on the question, but I am reposting it with a little more detail.)

This problem is NP-hard as follows.

As is usual in a proof of NP-hardness, suppose that a natural number K is also given as part of input, and consider the yes/no problem of deciding whether at least K customers are satisfied.  Then this problem is NP-complete, even if it is restricted to the case where X=1, m=3K and each customer wants to buy exactly three goods.  (Note that if X=1, the value of Y is irrelevant as long as Y>0.)  In this case, the problem is equivalent to the NP-complete problem called Exact Cover by 3-Sets.

See Garey and Johnson for more on complexity theory and NP-completeness, including the definition of the Exact Cover by 3-Sets and the proof of its NP-completeness.

As the problem is phrased there is no dependency between the customers so it should be easy to solve: check your constraint for every customer independently. This is clearly fast (linear in the number of purchased pieces times number of customers).


Can neural networks be used to devise algorithms? After the newer and newer successes of neural networks in playing board games, one feels that the next goal we set could be something more useful than beating humans in Starcraft. More precisely, I wondered whether

  Can neural networks be trained to solve classic algorithmic problems?

Here I mean that for example the network would get an input graph $G$ with weighted edges, and two vertices $s$ and $t$ specified, and we asked it to find a shortest $st$ path as fast as possible.
Then I guess the neural network would discover and train itself to use Dijkstra or something similar.

On one hand, we know that the computational power of neural networks is $TC^0$.
On the other, I don't know if this is necessarily related to my question.
Even so, for most problems we don't know whether they can be solved in $TC^0$ or not.
Seeing whether a neural network can train itself, might be a good indicator whether there's a fast algorithm or not.
For example, if neural networks can't train themselves to solve SAT fast, then that makes it (even more) likely that $NP\not\subset TC^0$.
I wonder what a neural network would do with GRAPHISOMORPHISM or FACTORIZATION.

Of course, extracting the algorithm is a whole different question.
I suspect experts know how to do that, but discussing it is not the topic of this question.

Added two days later: After seeing the answers, let me specify that if you answer in the negative, then I would like to know

  Why is playing chess easier than Dijkstra or Graphisomorphism?

According to this blog By Reza Zadeh, training a neural network to produce correct output even for just two-thirds of the training examples is computationally hard:

Indeed, in 1988 J. Stephen Judd shows the following problem to be NP-hard:
Given a general neural network and a set of training examples, does there exist a set of edge weights for the network so that the network produces the correct output for all the training examples?
Judd also shows that the problem remains NP-hard even if it only requires a network to produce the correct output for just two-thirds of the training examples, which implies that even approximately training a neural network is intrinsically difficult in the worst case. In 1993, Blum and Rivest make the news worse: even a simple network with just two layers and three nodes is NP-hard to train!

I am a QA Automation engineer so don't claim expertise at neural networks, but, tautologically, yes NN can themselves create algorithms. Humans themselves are NN at some level, and we create algorithms, so it stands to reason that artificial NN systems we create can themselves create algorithms.


Can a computer simulate itself as part of a simulated world? Let's say you build a computer that will calculate the state of all atoms in the Universe at certain future point in time. Because the Universe is, by definition, everything that exists (and anything that interacts with the rest), it also includes the computer that you are building. Can you calculate the state of all atoms in the Universe using your computer, including the atoms of the computer itself?

If such a computer is not possible for some other theoretical or practical reason, then what is it?

No, a computer cannot perfectly simulate itself in addition to something else without violating basic information theory: there exist strings which are not compressible.

Here's the simplest possible proof: suppose the computer has a total of $N$ possible states, and suppose there is something outside of the computer in the universe, so the universe has at least $N+1$ possible distinct states.  With zero overhead, each state of the computer can correspond to a state of the universe, but since the universe has more states than the computer, some states of the universe will map to the same state of the computer, in which case the simulation will not be able to distinguish between them.

A finite computer cannot simulate itself, in contrast to a Turing machine that has an infinite tape and can simulate any other Turing machine. It is, however, possible to simulate any computer on a similar computer, but you need a little more memory than the "simulated" one (like in a virtual machine): http://meaningofstuff.blogspot.com/2016/03/can-computer-or-human-simulate-itself.html


Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights? The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in reasonable time is an approximate one (Synopsis diffusion), but increasing its precision is exponential in the number of bits (and I need a lot of bits).

Background: this task is done (several times with different 'weights') as part of the probability calculations in  BBChop (http://github.com/ealdwulf/bbchop) a program for finding intermittent bugs (ie, a bayesian version of 'git bisect'). The DAG in question is therefore a  revision history. That means that the number of edges is unlikely to approach the square of the number of nodes, it's likely to be less than k times the number of nodes for some smallish k.
Unfortunately I haven't found any other useful properties of revision DAGs. For example, I was hoping that the largest triconnected component would grow only as the square-root of the number of nodes, but sadly (at least in the history of the linux kernel) it grows linearly.

We assume that vertex weights can be arbitrary positive integers, or more precisely, they can be positive integers at most 2n.  Then the current task cannot be performed even in a slightly weaker time bound O(n2), unless the transitive closure of an arbitrary directed graph can be computed in O(n2) time, where n denotes the number of vertices.  (Note that an O(n2)-time algorithm for the transitive closure will be a breakthrough.)  This is the contrapositive of the following claim:

Claim.  If the current task can be performed in time O(n2), the transitive closure of an arbitrary directed graph given as its adjacency matrix can be computed in O(n2) time (assuming some reasonable computational model).

Proof.  As a preprocessing, we compute the strongly connected component decomposition of the given directed graph G in time O(n2) to obtain a DAG G′.  Note that if we can compute the transitive closure of G′, we can reconstruct the transitive closure of G.

Now assign the weight 2i to each vertex i of the DAG G′ and use the algorithm for the current problem.  Then the binary representation of the sum assigned to each vertex i describes exactly the set of ancestors of i, in other words, we have computed the transitive closure of G′.  QED.

The converse of the claim also holds: if you can compute the transitive closure of a given DAG, it is easy to compute the required sums by additional work in time O(n2).  Therefore, in theory you can achieve the current task in time O(n2.376) by using the algorithm for the transitive closure based on the Coppersmith-Winograd matrix multiplication algorithm.

Edit: Revision 2 and earlier did not state the assumption about the range of vertex weights explicitly.  Per Vognsen pointed out in a comment that this implicit assumption may not be reasonable (thanks!), and I agree.  Even if arbitrary weights are not needed in applications, I guess that this answer might rule out some approaches by the following line of reasoning: “If this approach worked, it would give an algorithm for the arbitrary weights, which is ruled out unless the transitive closure can be computed in time O(n2).”

Edit: Revision 4 and earlier stated the direction of edges incorrectly.

This is wrong and is based on a misunderstanding on the question.  Thanks to Tsuyoshi for patiently pointing out my error.  Leaving up in case others make the same mistake.

If the number of immediate predecessors of a node is bounded by $k$, then an algorithm that first does a topological sort, then processes the nodes in this order will do the job.  Measuring the number of immediate predecessors is suggested by viewing the DAG as a partial order.  A model with bounded number of immediate predecessors may be appropriate for a revision history, where only a few files are changed by most revisions.

The point is that for this special case, for each node there are at most $k$ predecessors in the linear order that need to be looked at, so this can be done with $O(k|V|)$ additions.

The topological sort requires $O(|V|+|E|)$ time, which gives you the asymptotic bound you are looking for.  But in the application you describe, the linear number of additions is likely to dominate.

This approach should also work well if there are some nodes with many immediate predecessors, as long as they are relatively infrequent.