Inductive types for large countable ordinal notations.

Hermann Ruge Jervel has a nice system that goes all the way to the Bachmann-Howard ordinal based on labelled trees.  See: http://folk.uio.no/herman/logsem.pdf

I also like his book on proof theory, which discusses this system: http://folk.uio.no/herman/bevisteori.ps


Questions on unification theory (and its application to DAG isomorphism )

An excellent starting point for information on unification theory
with some information on unification of term dags is the survey
by Baader and Snyder.
http://www.cs.bu.edu/~snyder/publications/UnifChapter.pdf


Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?

The proof for $\mathbf{P}=\mathbf{AltTime}(O(1))$ ($=\mathbf{PH}$) is an induction using $\mathbf{P}=\mathbf{NP}$. The induction shows that for any natural number $k$, $\mathbf{P}=\mathbf{AltTime}(k)$ (and $\mathbf{AltTime}(O(1))$ is just their union).

The induction does not work when the number of alternation can change with the input size (i.e. when the number of possible alternations of the machine is not a number but a function of the input size, i.e. we are not showing that an execution of the machine on a single input can be reduced to no alternation, we are showing that the executions of the machine on all inputs can be "uniformly" reduced to no alternation).

Let's look at a similar but simpler statement. We want to show that the identity function $id(n)=n$ eventually dominates all constant functions ($f \ll g$ iff for all but finitely many $n$ $f(n) \leq g(n)$). It can be proven say by induction. For all $k$, $k \ll n$ (i.e. $f_k \ll id$ where $f_k(n)=k$), but we don't have this for non-constant functions like $n^2$, $n^2 \not \ll n$.


The definition of, e.g., class P is unambiguous.

However, what is ambiguous is something like "the running time is $O(n)$". As you have observed, there are two sources of ambiguity:

What is a single time step? This depends on the model of computation.
What is $n$? This depends on the problem.

To make it completely unambiguous, you would state something like "the running time in the RAM model is $O(n)$, where $n$ is the number nodes."

Usually, we can afford to be a bit sloppy. The model is often clear from the context; in the case of algorithms, it is usually the RAM model unless otherwise specified. Moreover, there are various conventions regarding the definition of $n$. For example, in the context of graph algorithms, $n$ almost always denotes the number of nodes (and $m$ is the number of edges) – these are just conventions that you have to learn.

If you are really interested in logarithmic factors, then you have to be careful with these details. The same algorithm might be $\Theta(n)$ or $\Theta(n \log n)$ or $\Theta(n/\log n)$ if you slightly vary your model of computation or your definition of $n$.

However, if something like "polynomial time" is good enough for you, then you can ignore most of these details. Typical models of computation can simulate each other with a polynomial overhead (time $x$ in one is at most time $\mathrm{poly}(x)$ in the other), and typically an input can be encoded in $\mathrm{poly}(n)$ bits, no matter what happened to be your precise definition of $n$. For example, an $n$-node graph can be encoded as a string of $n^2$ bits. Hence you can usually say "runs in polynomial time" without worrying too much about the details ("polynomial in what?", "polynomial number of what?").


Why non-uniform learnability does not imply PAC learnability?

The following answer is based on chapter 6/7 of the book »Understanding Machine Learning: From Theory to Algorithms«, by Shalev-Shwartz and Ben-David (especially Example 7.1).

It states that the class $\mathcal{H}$ of all polynomial classifiers over $\mathbb{R}$ is not PAC learnable ($\mathrm{VCdim}(\mathcal{H}) = \infty$). We might rewrite $\mathcal{H}$ as $\bigcup_{n \in \mathbb{N}} \mathcal{H}_n$, where for every $n \in \mathbb{N}$, $\mathcal{H}_n$ is the class of all polynomial classifiers over $\mathbb{R}$ of degree $n$.

Each $\mathcal{H}_n$ is PAC learnable with $\mathrm{VCdim}(\mathcal{H}_n) = n + 1$, so using the fundamental theorem of statistical learning (quantified version), we know that the sample complexity of each $h \in \mathcal{H}_n$ is in $\Theta\left(\frac{(d + 1) + \log(1 / \delta)}{\epsilon^2}\right)$, so strictly increasing in $d$, but finite.

So for $0< \epsilon, \delta < 1$, the set $\{ n_{\mathcal{H}}(\epsilon, \delta, h) \mid h \in \mathcal{H} \}$ is not upper bounded. Yet, as a union of PAC learnable classes, $\mathcal{H}$ is nonuniform learnable.


Strong normalization property of CoC inside CoC

I'll summarize the comments from chi, and sketch the proof that

There can be no proof of $\mathrm{False}:=\forall X:*.X$ in the CoC in head normal form. Furthermore, this fact can be proven in a weak theory, say Peano Arithmetic (though the excluded middle is not required).
This fact implies that if the CoC is normalizing, then it is consistent, and furthermore this implication does not use classical logic.

for 1., you proceed by induction on the term structure of a hypothetical closed term $t$ of type $\mathrm{False}$. Actually terms in normal form must be in the form:
 $$ \lambda x_1:T_1\ldots\lambda x_n:T_n.y\ t_1\ldots t_m$$

where $n$ and $m$ may be $0$. If $n$ is zero, then $t=y\ t_1\ldots t_m$, which is not possible since $t$ is closed (typed in the empty context).

Otherwise, we may apply inversion and conclude that $T_1=*$ (and $x_1=X$), and we get
$$ X:*\vdash\lambda x_2\ldots\lambda x_n.y\ t_1\ldots t_m\ :\ X$$
to be derivable in the CoC. Now since $X$ is not a $\Pi$, we can apply inversion again to conclude that $n=1$ and in fact the above term is simply
$$ X:*\vdash y\ t_1\ldots t_m\ :\ X$$
Inversion yet again shows that
$$X:*\vdash y\ :\ \Pi y_1:U_1\ldots\Pi y_m:U_m.X $$
but $y$ must be $X$, since it is the only variable around! Therefore $m=0$, and $X=*$, which is impossible, contradiction.

Now all this reasoning is intuitionistic, as I've proven a negative (there can be no proof of...) and proofs of negations are always constructive. I do rely heavily on inversion, and you'll just have to take it on faith that this also can be proven in arithmetic, without the excluded middle, which is non-trivial.

Now for 2. we define consistency to mean "does not prove $\mathrm{False}$"! Again a negative statement. Now if the CoC is normalizing, one can take any normal form of a proof of $\mathrm{False}$ and use the above argument to get a contradiction. Again a constructive argument!

Finally to tie it all together. Now suppose you had enough arithmetic to carry out the above arguments in CoC. Note that this is almost possible: you actually need to add the axiom $0\neq 1$ to get anything off the ground. You can then prove that normalization implies consistency within the CoC, and you also have enough arithmetic for the second incompleteness theorem to apply. Therefore you cannot (if CoC is consistent!) prove normalization, as then you would have a full proof of consistency within CoC.


Extending cographs with product operation

A path has cliquewidth $3$, but the tensor product of two paths of length $n$ will contain a $\Omega(n) \times \Omega(n)$ size grid as an induced subgraph. And $n \times n$ grids are known to have cliquewidth $\Omega(n)$ (see “The rank-width of the square grid“ by Vít Jelínek)


Everyday encounters with NP-complete problems

My favorite example to use with non-CS friends is this one:

Abraham, A. Blum, Sandholm.  Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.  EC07.

Kidney exchange markets are essentially a restricted form of cycle cover.  I like this example because a) it's easy to explain the gist(if you leave out some of the more technical details) and b) it's one of the few instances I know of where better algorithms can literally save lives!

My second favorite example is the hospitals-and-residents problem (aka the college admissions problem).  Each hospital ranks all residents (graduating medical students) and residents rank hospitals.  Each hospital has a certain number of slots.  From there it's a stable matching problem and can be solved in polynomial time.

But in reality, couples can enter the system (yes, there is indeed a system) together, so that the system won't, for example, split up married couples who are both applying for residency.  The addition of couples makes the problem NP-complete.  In addition to being easy to explain, this nicely demonstrates how the introduction of long-range connections can induce NP-completeness.


The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"):

Woodruff & Zhang: "When Distributed Computation is Communication Expensive" http://arxiv.org/abs/1304.4636

See also this work for closely related models:

Klauck et al.: "Distributed Computation of Large-scale Graph Problems" http://arxiv.org/abs/1311.6209

You may also be interested in the "congested clique" model, which is the special case such that $k = |V|$ and computer number $i$ is aware of the edges incident to node number $i$.


Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

Being pulled down by the gravitational force from $\mathrm{BPP}$, hardly any convincing evidence can be lurking on the surface of $\mathrm{EXP}^{\mathrm{NP}}$ for you to see.

Only after proving $\mathrm{BPP}\subseteq \mathrm{P}^\mathrm{NP}$, this class would give up on $\mathrm{EXP}^\mathrm{NP}$. But then, $\mathrm{EXP}$ and $\mathrm{NEXP}$ would have their chances to thrive (on their own).


Is it possible to encrypt quantum states under reasonable assumptions?

One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse operator is applied to decrypt.)

The resulting scheme is perfectly secure -- if the key is selected uniformly at random, then even an attacker who know a state entangled with the plaintext cannot distinguish the true ciphertext from an independent random state.

This observation was first made in
A Ambainis, M Mosca, A Tapp, R de Wolf. "Private quantum channels", FOCS 2000.

They also showed that 2n bits of key are necessary for encryption of entangled quantum states.

If you have a classical PRG secure against quantum distinguishers, then you can get away with a much shorter key (as short as seed length required by the generator to generate 2 n output bits).


How Much Computing Power would be Required to Fully Simulate a Cubic Meter?

tricky question! there is some diverse crosscutting research into this question, and will attempt to outline it, but will in the end take the position here that the question is contradictory/ impossible at heart (and anticipating some this may be a controversial conclusion). here are two key recent references from a physics pov addressing your question.

Gate count estimates for performing quantum chemistry
on small quantum computers / Wecker et al
Quantum Algorithms for Quantum Field Theories / Jordan, Lee, Preskill

a rough complexity theory estimate of "simulating particle physics" is to count the number of particles, and there are about $O(n^2)$ interactions between particles, and many supercomputer simulations of particle dynamics fit this. so as a rough bound, one would pick the smallest particles, but, wait! the standard model has many subatomic particles! so one might use neutrinos, one of the smallest known stable particles, as an estimate... but then what about unstable particles such as quarks/ leptons?

there is also the whole other problematic accuracy/ precision problem of the butterfly effect long known in computational physics aka "sensitive dependence on initial conditions".

Aaronson write in his essay Is There Anything Beyond Quantum Computing?:

  Is there any such problem that couldn’t be solved efficiently by a quantum computer, but could be solved efficiently by some other computer allowed by the laws of physics?

so he sketches out weird physics such as black holes or quantum gravity that might not be simulable by a quantum computer. but flipping this whole essay on its head (in a manner it which it was unintended), what he is describing are frontier areas of physics that currently do not have complete/ definite physical theories known by humans (at best, only plausible candidates/ approximations floating around.) eg:

black holes
time curves
quantum gravity

(adding to his list)

dark matter/ energy
virtual particles, vacuum energy

so the problem comes in your title that you literally want to fully simulate a cubic meter of space. but the standard model is actually ultimately/ technically widely acknowledged/ conceded by physicists themselves (if pressed!) as an incomplete model of reality due to all the extreme/ problematic "edge cases" listed above, and others not known. even the standard model itself is problematic in that new particles/ tiny forces and revisions are added/ modified all the time, nearly "regularly", even the famous/ celebrated Higgs particle recently.

so actually its a major open question of physics whether the basic rules of reality are computable. this ties in with the digital physics research agenda.

so physicists generally regard the idea that physics of reality is computable as something of an "approximation" that physical theories are in the continual process of evolving/ finetuning but "very thorough/ precise models" are ultimately not to be confused with accurate simulations.

also relevant to this question/ impinging is that there is new "cutting edge/ borderline" physics theory/ research and experiments to attempt detect if we are "living in a hologram" ie some kind of "simulation". it is theorized that cosmic rays might have detectable properties indicating this, or other very sensitive experiments could reveal kinds of "digitization artifacts", etc.; one example:

The Measurement That Would Reveal The Universe As A Computer Simulation / MIT tech review


2D Cutting Stock Problem for Glass - Details mentioned

It sounds like your glass cutting problem is exactly like the 2D guillotine stock cutting problem -- am I correct that there is no difference?

I think Macleod et al's O(n^3) approximation algorithm from the 1990s is still the best known result with proven optimality bounds for very large instances of this problem, but for only 100-200 pieces the exact algorithm by Christofides and Hadjiconstantinou should be able to find the optimal solution in reasonable time.  There are also good heuristics for this problem via dynamic programming.

A survey on software solvers for the cutting stock problem was written by Macedo et al here in case you're looking for practical solutions.


An explanation of Whirlpool C implementation - or the general algorithm

In the following, I try to minimize the background knowledge needed to understand the answer. If you need more details, I suggest taking a look at section 12.2 of Cryptography and Network Security Principles and Practices, Fourth Edition. (Though it requires a fair knowledge of crypto.)

First take a look at Merkle–Damgård construction. Virtually all hash functions follow such construction. Informally, it applies a compression function iteratively to reduce the input size to get some fixed-length output. For instance, you can hash a whole DVD (~ 4.3 GB) and get a 128-bit code.

Let $M$ be the input to an MD-based hash function. The MD construction appends a pad and the length of $M$ to it, so as to prevent several attacks.

Whirlpool uses a compression function named $W$. $W$ is similar to a block cipher named Rijndael, which is now standardized under the name AES (Advanced Encryption Standard). Rijndael has 3 variants: 128-bit, 192-bit, and 256-bit. The inventors of Whirlpool decided that no Rijndael variant is secure enough to be used as the compression function for a hash. Thus, $W$ is designed so as it accepts 512-bit inputs, and produces 512-bit outputs. The key size of $W$ is 512 bits as well.

Whirlpool works as follows. Let $M$ be the input. $M$ is divided into 512-bit segments: $M=(M_0,M_1,\ldots,M_t)$. Let $h_0$ be some initial value (fixed by Whirlpool standard).

For $i=1,2,\ldots,t$, apply $W$ iteratively as follows:

$h_i = W(h_{i-1},m_i) \oplus h_{i-1} \oplus m_i$

where the first input to $W$ is a block-to-be-encrypted, and its second input is the encryption key. $\oplus$ denotes the XOR operation.

$h_t$ is considered as the output of the Whirlpool hash function.

The whole complexity lies in designing $W$. As pointed out before, it is similar to Rijndael, so you can understand it if you get familiar with Rijndael, on which I have designed a set of slides. The slides are self-contained and do not assume any math background beyond high school.


Running an algorithm for fixed amount of time on RAM model machine

One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed.  I suspect it should be possible to build an interpreter that incurs at most a $O(1)$-factor slowdown, but I haven't checked the details (the instruction set is so primitive that the programming is ugly) -- you should be able to check whether the obvious approach works.


How to efficiently find a loop between two nodes in a directed graph?

This problem has been shown to be NP-complete in the following paper:

  S. Fortune, J. Hopcroft, J. Wyllie:
  "The directed subgraph homeomorphism problem"
  Theoretical Computer Science 10 (1980), pp. 111-121


Knapsack with dependent profits (pairs of items)

This is a very interesting problem. But cannot be addressed in its general form. Assumptions need to be made in relation to the application domain. You may find the attached paper useful. The paper assumes strengths of value-related dependencies are imprecise.

please see this: https://link.springer.com/chapter/10.1007/978-3-319-63004-5_12


What does it mean for CvRDT replicas to transmit their state "infinitely often"?

From my understanding of CvRDTs (though I haven't read that exact paper recently)

I believe after receiving new state m is always called, however this should be part of the send/receive machinery, rather than something the application has to deal with. That doesn't prevent the application calling m if it sees the need, but in lots of cases there isn't one.
u has to be inflationary otherwise it will get "lost" by a merge. Given a merge could happen at any time, a non-inflationary update could disappear beneath the CvRDT user as they were performing operations on it. And while non-inflationary updates don't pose a problem for convergence, they do pose a problem for equality: a <merge> b may not be deterministic in the presence of non-inflationary updates.
I don't have an answer for this. Maybe it's worth reading as "unboundedly many times between each update", but that's a guess.


How efficiently can circuits over sets of naturals be transformed to boolean circuits?

A simple conversion process for $\boldsymbol\cup\,$, $\boldsymbol\cap\,$, constants, and complements

Note that any integer-set circuit representing a set $S \subseteq \{0,1,\ldots,N-1\}$ can be represented by a boolean circuit which tests $x \mathbin{\in?} S$ for $0 \leqslant x < N$. If $N = 2^n$, this is a boolean circuit with $n$ inputs. We may construct such a circuit $C_n$ as follows.
$\def\GE#1{\mathrm{GE#1}}\def\PRIME={\mathrm{PRIME}}$

Using AND, OR, and NOT gates, we can very easily simulate equality of the input with a binary representation of any integer $0 \leqslant x < 2^n$ with a circuit of size $n$ and depth $\log (n)$.
Next, we may represent your input sets as also being constructed by $\cup$ circuits, constructed from singletons $\{x\}$ for $1 \leqslant x < N$. If $S_j$ has size $m_j \leqslant M$, this requires a circuit with a boolean tree structure, with $m-1$ union gates, having depth at most $\log(m)$.
Finally, we may represent unions and intersections of your sets $S_j$ by logical ANDs and ORs of membership in the input sets. This part of the circuit has the same size $s$ and depth $d$ as the depth of your integer-set-circuit.

We may then obtain a boolean circuit $C_n$ of depth at most $d + \log m + \log n$ and size at most $s + m + mn$. The complexity of building this circuit is essentially $O(s + m(\log m + n \log n))$, arising from doing the necessary construction of the binary trees for the gates representing each $S_j$ and $\{x\}$ for $x \in S_j$.

Note that the complexity does not increase at all if you allow logical complementation, which would represent in principle an infinitely large set including numbers larger than the input size; though to represent numbers which are $N$ or larger, we must use uniform circuit families $\{C_n\}$ rather than a single circuit $C_n$. The construction above will build these efficiently, however.

Remarks on the power of integer-set circuits with arithmetic

In the (extremely powerful!) model of arithmetic circuits including $+$ and $\times$ gates, this construction fails because the outputs to those gates implicitly involve existential quantifiers over satisfying inputs to subcircuits of arbitrary size. As your linked article notes, the Goldbach conjecture can be tested by evaluating $G(0)$, where $G$ is a (finite depth!) circuit,
$$ G :=\overline{\{0\} \times \Bigl(\bigl[ \{2\} \times \GE2 \bigr] \cap \bigl[\; \overline{\PRIME + \PRIME}\;\bigr]\Bigr)} \;, $$
where $\GE2 := \overline{\{0\} \cup \{1\}}$ tests whether an input is $\geqslant 2$, and $\PRIME := \GE2 \cap \bigl[\,\overline{\GE2 \times \GE2}\,\bigr]$ tests whether an input is prime. The enormous power of these circuits seem to me to come from combining negation (which allows you to obtain infinite sets from finite ones) with the $+$ and $\times$ gates (which allow existential quantification over all inputs to sub-circuits, as to whether there are accepted inputs whose sum or product is equal to the input integer). If you do not have additions or multiplications, those quantifications are absent, and the problem becomes much simpler — indeed, very close in flavour to a run-of-the-mill boolean circuit.


Application of Yao's Minmax Principle for Adaptive Randomized Algorithms

You may find this video useful:
https://www.youtube.com/watch?v=0vrqCDcxbxs&t=22s
Also, this video here (time 00:43) states some books that can help:
https://www.youtube.com/watch?v=mQQ36cDnmR8&t=158s


Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence?

I don't know about the weakest possible conditions, but if a graph has a subgraph with minimum degree $k-1$ (that is, if its degeneracy is at least $k-1$) then a greedy algorithm can easily find a path of $k$ nodes starting at any node. The example of $K_{k-1}$, which has no $k$-path and has minimum degree $k-2$, shows that this is tight.


Can we infer the next player in chess from the current board configuration?

There is, in fact, a subcategory of chess problems, the goal of which is to determine whose turn it is to move in the given position. Examples here. So while you need the "who moved flag" in general, for all the reasons given above, it seems to me that classification of all types of positions where you don't need the flag is a genuine research problem. Another question:

Given a mover-determinable position in chess on an n by n board, what is the complexity of determining who moved?

So you might want to look at things like that, if you want a theoretical project out of the problem.


Languages and their operations: determining equivalence

Nope. Let $A = \{a\}$, $B= \{b\}$. Then $A^* = \{\epsilon,a,aa,
\ldots\}$ and similarly for $B$. So, $A^*\cup B^*$ contains strings of repeated "a" or repeated "b". But $(A\cup B)^*$ contains strings like $ab$, which you can't get from $A^*$ or $B^*$.

I'd suggest looking at a book like Sipser for a good coverage of languages like these and how to prove properties like equivalence. In particular, he has a great number of exercises to work through. Good luck!


How to specify and verify Horn clauses (logic programming programs)? Semantics of Horn clauses

You should have a look at Uniform Proofs as a Foudation for Logic Programming by Dale Miller, Gopalan Nadathur, Frank Pfenning and Andre Scedrov, 1991. The idea of this work and the rich area that has seen spawn from these ideas is to understand the execution of a logic program as proof search in simple and expressive logics, such as intuitionistic logic or linear logic. A particular class of formulas with good proof search properties are the Hereditary Harrop Formulas, which nicely generalize Horn Clauses.


Why is it so difficult for a computer to prove something?

While there are plans to formalize Fermat's Last Theorem (see this presentation), I have never read or heard that a computer can prove even a "simple" theorem like Pythagoras'.

In 1949 Tarski proved that almost everything in The Elements lies within a decidable fragment of logic, when he showed the decidability of the first-order theory of real closed fields. So the Pythagorean theorem in particular is not talked about much because it's not especially hard.

In general, the thing that makes theorem proving hard is induction. First-order logic without induction has a very useful property called the subformula property: true formulas $A$ have proofs involving only the subterms of $A$. This means that it's possible to build theorem provers which can decide what to prove next based on an analysis of the theorem they are instructed to prove. (Quantifier instantiation can make the right notion of subformula a bit more subtle, but we have reasonable techniques to cope with this.)

However, the addition of the induction schema to the axioms breaks this property. The only proof of a true formula $A$ may require doing a proof $B$ which is not syntactically a subformula of $A$. When we run into this in a paper proof, we say we have to "strengthen the induction hypothesis". This is quite hard for a computer to do, because the appropriate strengthening can require both significant domain-specific information, and an understanding of why you're proving a particular theorem. Without this information, truly relevant generalizations can get lost in a forest of irrelevant ones.


Let's just take the reduction from SAT to IP and see if it works. For a 3-CNF $\phi$, define a polytope $P$ which contains all $x \in \mathbb{R}^n$ satisfying the constraints

$0\le x_i \le 1$ for all $i$,
clause constraints for any clause $C$ of $\phi$: for example if $C = x_i \vee \bar{x}_j \vee x_k$ put the constraint $x_i + 1-x_j + x_k \ge 1$. (I trust you can figure out the general rule.)

Clearly $P$ has an integer point if and only if $\phi$ is satisfiable. Also the number of integer points in $P$ equals the number of solutions of $\phi$. So as long as the ratio between the diameter and the width of $P$ is polynomial, this answers both your questions.

Let us then compute its diameter and width. $P \subseteq [0,1]^n$, so the diameter of $P$ is at most $\sqrt{n}$. By width, I am assuming you mean the standard

$$
\min_{\theta: \|\theta\|_2 = 1} \max_{x, y \in P} \langle \theta, x-y\rangle,
$$

i.e. the smallest distance between two parallel hyperplanes that sandwich $P$. Notice that any $x$ which satisfies $\frac13 \le x_i \le \frac23$  for all $i$ is in $P$. So, for a $\theta$, pick $x_i$ to be $\frac23$ if $\theta_i > 0$ and $\frac13$ otherwise, and pick $y_i$ to be $\frac13$ if $\theta_i > 0$ and $\frac23$ otherwise. Then:

$$
\langle \theta, x - y \rangle = \sum_{i = 1}^n \frac{|\theta_i|}{3} = \frac13 \|\theta\|_1 \ge \frac13 \|\theta\|_2.
$$

So the width is at least $\frac13$.


Where does the information in a fractal come from?

To a large extent, the answer will depend on exactly what you mean by "information". The fractal has very low Kolmogorov complexity, as there is a very simple rule describing how you generate it. So in one sense, it contains very little information. On the other hand, a picture of such a fractal appears very complicated, even though there is a simple rule underlying it. This is not at all uncommon. Many times very simple rules give rise to very complex behavior. Examples of this range from cellular automata and Conway's game of life to things like the apparent complexity in the digits of $\pi$. The fact is that this new representation doesn't contain anything fundamentally new, but is rather a less efficient expression of the same object.


Do many-one reductions and Turing reductions define the same class NPC

The "Boolean Hierarchy" BP is a whole hierarchy of combinations of NP problems under Karp reductions which are all in P^NP.


Consider a set $E$. The theory of $E$-exceptions is an algebraic theory given by:

for every $e \in E$ a nullary operation symbol $\mathsf{raise}_e$
no equations.

Given a set $X$, we may consider the free algebra $A$ for the theory of $E$-exceptions, with generators from $X$. The algebra $A$ contains everything that we can generate from the generators and the operation symbols. Since our operation symbols are nullary (do not take any arguments), $A$ will contain precisely the generators $X$ and, for each $e \in E$, the operation symbol $\mathsf{raise}_e$. (There are no equations, so we need not quotient at all.) It is not surprising that we would write "$X + E$" for $A$.

In general, an algebra for the theory of $E$-exceptions is given by:

a carrier set $C$
for every $e \in E$, an element $r_e \in C$ which interprets the nullary operation $\mathsf{raise}_e$.

A particulary strange way to create an algebra is to take
$$C = X + E$$
and for each $e \in E$ an element $x_e \in C$. This seems strange only untilwe notice that such an algebra is precisely the same thing as an exception handler. Think of $C$ as the set of "computations" that may either return a "final result" from $X$, or raise an exception from $E$. An exception handler takes an element $c \in C$ and explains how to replace each exception $\mathsf{raise}_e$ with another computation $x_e \in C$ (note: an exception handler may re-raise exceptions, which is why $x_e \in C$ instead of just $x_e \in X$).

$\newcommand{\raise}[1]{\mathsf{raise}_{#1}}$

Supplemental: Perhaps a concrete example will help. A model is given by a set $C$ and a mapping of the constant symbols $\raise{e}$ to elements of $C$.

Let us take $E = \{a,b\}$ and $X = \{u, v, w\}$. Then the free model is given by the carrier
$$X + E = \{u, v, w, \raise{a}, \raise{b}\}$$
together with the mapping
$$\raise{a} \mapsto \raise{a}, \quad \raise{b} \mapsto \raise{b}.$$

The model $\overline{X + E}$ is not fixed, it depends on the mapping $x : E \to X + E$. For example, if we take $x_a = u$ and $x_b = \raise{a}$ then we get the model $\overline{X + E}$ whose carrier is $X + E$ and
$$\raise{a} \mapsto u, \quad \raise{b} \mapsto \raise{a}.$$
Another possibility for $\overline{X + E}$ is to take $x(a) = \raise{b}$ and $(b) = \raise{a}$. This will not be the same as the free model because it exchanges the meaning of $\raise{a}$ and $\raise{b}$. If we take $x(a) = \raise{a}$ and $x(b) = \raise{b}$ then $\overline{X + E}$ is equal to the free model.


Eliminating clauses from a CNF formula based on their unsatisfying truth assignments being covered by some other clause

What you're describing is called subsumption; it is a standard CNF simplification technique for SAT solvers.  None of the operations involved is worse than quadratic to either the number of variables or number of clauses in the formula.


Pathfinding search over a space with known changing costs

In general, finding least-cost paths with arbitrary time-dependent edge costs is NP-hard, assuming that either (a) waiting at nodes is forbidden and your costs are not FIFO-preserving (e.g., see here for brief discussion on this complexity, as well as others: https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf) or (b) the cost you are trying to optimize is not simply pure travel time itself (e.g., see http://algo2.iti.kit.edu/download/gen_obj_func_tch.pdf).

As an illustrative example of this latter situation (which seems most similar to yours) and continuing with your suggested notation, it is shown in the second paper above that it is NP-hard for the case in which the time-dependent edge cost is defined in the form $c_e(t) = f_e(t) + d_e$, where $f_e$ is the (typical) time-dependent travel-time function that returns the travel time along the edge for a particular time of day $t$ and $d_e$ is some arbitrary time-neutral cost function. It is not hard to show that similar hardness results for other such cases as well, where, e.g., the function uses a multiplier instead of addition (i.e., $c_e(t) = f_e(t) \cdot d_e$), and so on.

Regardless, one can derive pseudo-polynomial time bounds on such cases if, e.g., you are representing your time instants as integer values and assuming there are only a finite number of possible time instants bounded by $T$. In this way, you only need to maintain a single least-cost path per time instant $t$ for any given node in the graph, which would give you the running time of $O(T(m + nlogn))$, assuming non-negative cost functions. Taking this idea a step further, since your particular use case assumes that "each edge takes one unit of time to traverse", then this automatically gives you a strongly-polynomial-time algorithm since, in your case, $T \in O(n)$ (because each such path contains $\leq n-1$ edges).


Let me know if I understood the question correctly: you want to count the sets of $n$ positive integers summing exactly $k$, right? This is $\binom{n+k+1}{k}$. If you want for non-negative integers version, add one more number to the count, $\binom{n+k+1}{k+1}$.


Complexity of computing invertible functions with reversible circuits

I have some great news. If you know how to compute a function and its inverse, then you may compute the function reversibly without producing any garbage information (though the computation needs to temporarily use ancilla bits for scratchwork). Let me informally state and prove a couple of results.

$\textbf{Theorem 1:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ is a function which is easy to compute.
Then there exists a known and easy to compute reversible circuit $H:\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}\times\{0,1\}^{r}\times\{0,1\}^{m}$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x}))$ on each input $\mathbf{x}$

$\mathbf{Proof:}$ It is a standard process to turn a conventional irreversible circuit into a reversible circuit at the expense where one produces a lot of garbage information along with the desired output (I will leave the process of simulating irreversible gates such as the AND gate and the OR gate by saving the inputs and using reversible gates such as Toffoli gates or Fredkin gates). Therefore, there exists a circuit $C$ along with a function $L$ such that $$C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{z})=
(0,f(\mathbf{x}),L(\mathbf{x}),\mathbf{z})$$ for each $\mathbf{x},\mathbf{z}$. Let $N$ be the circuit where $N(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{z})=
(\mathbf{w},\mathbf{x},\mathbf{y},\mathbf{x}\oplus\mathbf{z})$. Then
let $H=C^{-1}\circ N\circ C$. Then

$$H(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$

$$=C^{-1}\circ N\circ C(\mathbf{x},\mathbf{0},\mathbf{0},\mathbf{0})$$

$$=C^{-1}\circ N(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),\mathbf{0})$$

$$=C^{-1}(\mathbf{0},f(\mathbf{x}),L(\mathbf{x}),f(\mathbf{x}))$$

$$=(\mathbf{x},\mathbf{0},\mathbf{0},f(\mathbf{x})).$$

Q.E.D.

The technique used in Theorem 1 is known as the compute ($C$)-copy ($N$)-uncompute ($C^{-1}$) technique. This technique is essential for reversible algorithms and quantum algorithms. Since reversible circuits cannot delete any information, for a non-bijective function $f$, one must save the input $\mathbf{x}$. However, the following theorem shows that it is possible to reversibly compute a bijective function without needing to save the input $\mathbf{x}$.

$\textbf{Theorem 2:}$ Suppose that $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijective function with inverse $f^{-1}$. Suppose furthermore that an irreversible circuit that computes $f$ and an irreversible circuit that computes $f^{-1}$ are known. Then there exists a reversible circuit
$K:\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{m}$ such that
$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{0},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit string $\mathbf{x}.$

$\mathbf{Proof:}$ By Theorem 1, there exists a reversible circuit $H$ such that $H(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathbf{x},f(\mathbf{x}),\mathbf{0})$ on each $n$-bit input $\mathbf{x}$.

Now, there exists a reversible circuit $D:\{0,1\}^{n}\times\{0,1\}^{m}\rightarrow\{0,1\}^{n}\times\{0,1\}^{m}$ along with a function
$L:\{0,1\}^{n}\rightarrow\{0,1\}^{m}$ such that
$D(\mathbf{y},\mathbf{0})=(f^{-1}(\mathbf{y}),L(\mathbf{y}))$ for each $\mathbf{y}\in\{0,1\}^{n}$. Let $M:\{0,1\}^{n}\times\{0,1\}^{n}\rightarrow\{0,1\}^{n}\times\{0,1\}^{n}$ be the function defined by $M(\mathbf{x},\mathbf{y})=(\mathbf{x}\oplus\mathbf{y},\mathbf{y})$.

Let
$$K=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)\circ H.$$

Then $K$ is easily computable by a reversible circuit. However, for each $\mathbf{x}\in\{0,1\}^{n}$, we have
$$K(\mathbf{x},\mathbf{0},\mathbf{0})=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)\circ H(\mathbf{x},\mathbf{0},\mathbf{0})$$

$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})\circ(\mathrm{Id}_{n}\times D)(\mathbf{x},f(\mathbf{x}),\mathbf{0})$$

$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})(\mathbf{x},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$

$$=(\mathrm{Id}_{n}\times D^{-1})\circ(M\times\mathrm{Id}_{m})(\mathbf{x},\mathbf{x},L(f(\mathbf{x}))$$

$$=(\mathrm{Id}_{n}\times D^{-1})(\mathbf{0},\mathbf{x},L(f(\mathbf{x}))$$

$$=(\mathrm{Id}_{n}\times D^{-1})(\mathbf{0},f^{-1}(f(\mathbf{x})),L(f(\mathbf{x}))$$

$$=(\mathbf{0},f(\mathbf{x}),\mathbf{0}).$$ Q.E.D.


Diophantine equations and complexity classes

This paper, Computational complexities of Diophantine equations with parameters by Tung, proves co-NP-completeness of a variant with parameters over natural numbers.


Is there computable function to compute each computable real number?

There is a real question behind the confusion.

A real number $x$ is said to be computable if there a Turing machine, which upon input $n \in \mathbb{N}$ outputs a pair of numbers $a, b \in \mathbb{N}$ such that $|x - a/b| < 2^{-n}$. That is, there is a machine that computes arbitrarily precise rational approximations of $x$.

We can ask whether there is a machine that outputs an infinite list of machines, such that each of the listed machines computes a real number, and all computable real numbers are so included. That would be the way to make sense of the question.

The answer is negative. There is no such machine. The proof is essentially the diagonalization argument that show that a sequence of reals cannot exhaust the set of reals, except it is modified to work for computable reals and computable sequences.


For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?

We just answered this for $k=2$:

Andreas Björklund and Thore Husfeldt, Shortest two disjoint paths in polynomial time, ICALP 2014, to appear.
PDF of proceedings version, rev. e5d5661


State of the art on approximating quadratic assignment problem

See the following paper. There may have been other developments since then.

Maximum Quadratic Assignment Problem,
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko,
ICALP 2010

http://www.cs.princeton.edu/~kmakaryc/pdf/maxqap.pdf


Can this randomized greedy algorithm be made online? Or being proved impossible?

as far as I can tell after looking into this somewhat, there is a misunderstanding of the paper in the question. the question states that some of the algorithms are offline vs some online. but the algorithms in the paper are all online it appears (but agree the authors are not clear on this point). that is what is accomplished by having random edge orderings-- the random edge ordering reflects edges coming "online" in whatever order, right?

the authors seem to make no reference to "offline" algorithms in the paper and they refer to "online" only in the introduction that I see. they dont state this but the 1st algorithm seems to allow edges to come "online" in "batches" (ie random reordering in stages) whereas the 2nd algorithm does not.

while you dont state it exactly you appear to be checking the math in proof for theorem 2.3 in the paper (p3) which establishes a lower bound on the number of colors in a tree and the authors assert it works for both algorithm 1 and 2 ("for the 2nd algorithm.. the same bound holds"). the proof is that no less than $1.23\Delta$ colors ($\Delta$=graph degree) are sufficient for all trees. it seems if this theorem is wrong as you are suggesting then one should be able to exhibit a tree that can be colored with fewer than $1.23\Delta$ colors using those algorithms. from what I can tell your math is off because you are not expressing it using the same formulas in the proof eg you do not calculate the exponential formula in the proof.

a way to empirically verify this lower bound would be to generate many random trees, or some sample from some distribution, run the two algorithms and verify that they always use at least $1.23\Delta$ colors.


Isn't the solution a one-counter language?

The succession of the domino's is easily seen as a finite state restriction. For the unequality of $u'$ and $v'$ you have to find a single position where these strings differ. Keep track of $|u'|-|v'|$ during computation on the stack. You just nondeterministically choose such a letter, on a position of the longest of $u'$ and $v'$. Then keep simulating until the shortest string comes alongside with that same position.

I know this construction from a short paper (Prefix and equality languages of rational functions are co-context-free IPL 28 (1988) 77-79): "Theorem. For every two rational functions F and G, the complement of their prefix language Pref(F,G) is a one-counter language".
However that technique is a slight variation from an earlier result by J. Berstel: Every iterated morphism yields a co-cfl, Inform. Process. Lett. 22 (1986) 7-9.

Provided of course, I read your definition in the right way.


Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

As someone with a long time interest in this complexity class, I don't believe there has been any significant work on $\#P_1$ since. (I was a Ph.D. student of Mitsu Ogihara, the second author of the paper you cite, and actually raised - in informal discussions with Mitsu - the open question you cite; of course, all the actual results on this problem are due to Mitsu and his coauthors only, I did not contribute to any of them)

What is known is that $\#P_1$ is a rather weak class: whereas (by Toda's theorem) $\#P$ is hard for the polynomial hierarchy, the assumption $\#P_1 = FP$ has substantially weaker implications (P=BPP). This is another result due to Mitsu.

There are interesting complexity questions in enumerative combinatorics. But (naturally as it may be) no connection  seems to have been made yet to the class $\#P_1$.


Embarrassingly Parallel: Formal Definition & Citation

There is no formal answer for that question, as the notion of "embarrassingly parallel" is not a formal one; it is an informal and imprecise notion.  I understand it to basically mean that if you do the trivial and obvious thing to parallelize (whatever that may be), it works, and there's no need for sophisticated solutions.


Programming languages with canonical functions

The extent to which this is possible is actually a major open question in the theory of the lambda calculus. Here's a quick summary of what's known:

The simply-typed lambda calculus with unit, products, and function space does have a simple canonical forms property. Two terms are equal if and only if they have the same beta-normal, eta-long form. Computing these normal forms is also quite straightforward.
The addition of sum types greatly complicates matters. The equality problem is still decidable (the keyword to search for is "coproduct equality"), but the known algorithms work for extremely tricky reasons and to my knowledge there is no totally satisfying normal form theorem. Here are the four approaches I know of:

Neil Ghani, Beta-Eta Equality for Coproducts, TLCA 1995.
Vincent Balat, Roberto di Cosimo, Marcelo Fiore, Extensional normalisation and type-directed partial evaluation for typed lambda calculus with sums, POPL 2004.
Sam Lindley, Extensional Rewriting with Sums, TLCA 2007.
Arbob Ahmad, Daniel R. Licata, and Robert Harper, A Proof-Theoretic Decision Procedure for the Finitary Lambda-Calculus. WMM 2007.

The addition of unbounded types, such as natural numbers, makes the problem undecidable. Basically, you can now encode Hilbert's tenth problem.
The addition of recursion makes the problem undecidable, because having normal forms makes equality decidable, and that would let you solve the halting problem.


Yes, you can solve the problem using standard techniques. However, the question may easily be homework, so here is just a hint:

You never need to consider words of the form $aXaYa$, as they cannot be the only most frequent ones.


How many words of length $k$ on $l$ letters avoid a partial word?

Here's a special case: the number of binary words of length $k$ such that no two ones appear consecutively is $F(k+3)$, where $F(n)$ is the $n^{th}$ Fibonacci number (starting with $F(1)=1, F(2)=1$). Proof is via the Zeckendorf representation.

EDIT: We can extend this initial special case into the slightly larger special case of $a\lozenge^0a$. Consider strings of length $k$ over an alphabet of size $l+1$ such that the letter $a$ does not appear twice consecutively. Let $f(k)$ be the number of such strings (which we will call "valid"). We claim that: $$f(k) = l*f(k-1) + l*f(k-2)$$
$$ f(0) = 1, f(1) = l+1$$
The intuition is that we can construct a valid string of length $k$ by either: a) adjoining any of the $l$ letters that are not $a$ to a valid string of length $k-1$, or b) adjoining the letter $a$ and then any other letter but $a$ to a valid string of length $k-2$.

You can verify that the following is a closed form for the above recurrence:
$$f(k) = \sum_{i=0}^{k} {{k+1-i}\choose{i}} l^{k-i}$$
where we understand ${{n}\choose{i}} = 0$ when $i>n$.

EDIT #2: Let's knock out one more case -- a $\lozenge^0 b, a \neq b$. We'll call strings over an $l$-element alphabet that do not contain the substring $ab$, "valid" and let $S_k$ denote the set of valid strings of length $k$. Further, let's define $T_k$ to be the subset of $S_k$ consisting of strings starting with $b$ and $U_k$ to be those not starting with $b$. Finally, let $f(k) = |S_k|$, $g(k) = |T_k|$, $h(k) = |U_k|$.

We observe that $g(0)=0, h(0)=1, f(0)=1$ and $g(1)=1, h(1)=l-1, f(1)=l$. Next, we infer the following recurrences:
\begin{eqnarray}
g(k+1) &=& f(k) \\
h(k+1) &=&(l-1)*h(k) + (l-2)*g(k)
\end{eqnarray}
The first comes from the fact that adding a $b$ to the start of any element of $S_k$ produces an element of $T_{k+1}$. The second comes from observing that we can construct an element of $U_{k+1}$ by adding any character but $b$ to the front of any element of $U_{k}$ or by adding any character but $a$ or $b$ to the front of any element in $T_k$.

Next, we rearrange the recurrence equations to obtain:
\begin{eqnarray}
f(k+1) &=& g(k+1) + h(k+1) \\
&=& f(k) + (l-1)*h(k) + (l-2)*g(k) \\
&=& f(k) + (l-1)*f(k) - g(k) \\
&=& l*f(k) - f(k-1)
\end{eqnarray}

We can get a rather opaque closed-form solution to this recurrence by mucking around a bit with generating function stuff or, if we're lazy, heading straight to Wolfram Alpha. However, with a little bit of googling and poking around in OEIS, we find that we actually have:
$$f(k) = U_k(l/2)$$
where $U_k$ is the $k^{th}$ Chebyshev polynomial of the second kind (!).


Can generalized twenty questions be solved by a greedy algorithm?

No. There's a huge literature on the topic, called combinatorial search theory, you can read more about these types of questions there.
The simplest example that I could think of is the following.

Suppose that you want to find an edge of a graph, and you can ask whether a given vertex is incident to the hidden edge, or not.
Now take the following bipartite graph.
It contains a perfect matching on $100+100$ vertices.
Moreover, it also contains $10$ degree $10$ vertices that are connected to $10$ different vertices each, all on the same side.
So one side of the graph has $100$ vertices, all degree $2$, the other $110$, of which $100$ have degree $1$, the other $10$ degree $10$.

In this case, the greedy algorithm would first query the degree $10$ vertices, and then the rest, taking about $110$ steps.
If instead it started with querying the $100$ vertices of degree $2$, it would be done in $101$ steps.


Is the traditional analysis of Bloom filters wrong?

The traditional analysis is fine.  The "traditional" analysis is, if it is explained correctly, an approximation;  it's based on calculating the expected number of cells that are 0/1 when you hash the keys into the filter, and then analyzing as though that was the actual number.  The point is that the number of cells that are 0 (or 1) are tightly concentrated around their expectation, so it's a fine approximation.  This was well known, and can be found, I think, even back in my survey article with Andrei Broder.

This paper says that really the performance of a Bloom filter is a random variable (corresponding to the actual fraction of 0/1 entries), and if you want to calculate that performance exactly for some reason, you need to do the combinatorics.  For smaller filters, you'll see an arguably non-trivial difference.

I've talked with the authors of this paper.  Their analysis is all well and good (though I'd argue that it isn't deep or new);  their motivation that the "traditional analysis is wrong" was, I think, exaggerated.


Is adiabatic quantum computing as powerful as the circuit model?

Two quick clarifications:

Adiabatic QC is typically "based on qubits" just as much as circuit-based QC is -- I don't know where you got the idea that it isn't!  (Though one could also use qutrits or other building blocks, in either the circuit or the adiabatic models.)
As Mateus pointed out, the justly-famous result of Aharonov et al. says that "adiabatic QC is equivalent to standard QC."  But that result needs to be interpreted with a bit of care.  It holds if the final state of the adiabatic computation can be arbitrary -- so that, in particular, the final state can encode the entire history of a circuit-based quantum computation.  However, if the final state needs to be a classical computational basis state---as it typically is in the adiabatic optimization algorithm (the "original" example of adiabatic QC)---then adiabatic QC can certainly be simulated in the circuit model, but the reverse is not known and is far from clear.  So with the latter assumption, it's possible that adiabatic optimization really does give rise to a new complexity class intermediate between BPP and BQP.


What subjects, topics does a computer science graduate need to learn to apply available machine learning frameworks, esp. SVMs

From the theory end, you should understand how SVMs work (and why they do).  For example, I like the scribe notes from this class for a quick explanation and something like this tutorial for a more in-depth one.  You might also want to consider other machine learning techniques that are suited for binary classification on large data ie. boosting, random forests, ...

As for dealing with open source code issues and with parsing HTML, stackoverflow might be a better place to seek answers.

EDIT:  Given your modified question, I can address your concrete questions about SVMs directly:

$R^n$ "stands for" the fact that the (data) points to be classified lie in a $n$-dimensional Euclidean space.  For example, points in our familiar $2$ dimensions (with, say, latitude and longitude coordinates) lie in $R^2$ -- an $n$-dimensional space generalizes this notion.
A hyperplane (in $R^n$) is a flat of dimension $n-1$.  It is what an SVN uses to classify the data (after they have been mapped to the higher dimensional space by the chosen Kernel).  For example, if your space is $R^2$ (or a plane) then a hyperplane is line, and so on.
How to transform the space? This is done via the Kernel function.  A big part of SVM design is choosing a proper Kernel for the problem at hand.

To understand these three points in more detail, you can read the references above.


Another famous example is Hales' proof of Kepler's conjecture which had a very large computer aided component.

From Wikipedia:

  In August 1998 Hales announced that the proof was complete. At that stage it consisted of 250 pages of notes and 3 gigabytes of computer programs, data and results.


It is clear that your language is in DP. In order to show that it is DP-hard, we will give a reduction from SAT-UNSAT to your language, which we can call CRIT-UNSAT. Given a pair of CNFs $(f,g)$, let $x,y$ be fresh variables, and let
$$
h = (f \lor \lnot x) \land (g \lor x) \land (g \lor y) \land \lnot x \land (x \lor \lnot y).
$$
Here $f \lor \lnot x$ means add $\lnot x$ to all clauses of $f$.

Suppose first that $f$ is satisfiable and $g$ is not satisfiable. Since $g$ is not satisfiable, $h$ is not satisfiable. Since $f$ is satisfiable, $h \setminus \lnot x$ is satisfiable. Thus $h$ is in CRIT-SAT.

Conversely, suppose that $h$ is in CRIT-SAT. Since $h$ is unsatisfiable, $g$ is unsatisfiable. For some clause $c$, $h \setminus c$ is satisfiable. If $c \in f \lor \lnot x$ then clearly $h \setminus c$ is still unsatisfiable. Similarly, if $c \in g \lor x$ then $h \setminus c$ is still unsatisfiable, due to $g \lor y$. If $c \in g \lor y$ or $c = x \lor \lnot y$ then $h \setminus c$ is still unsatisfiable, due to $g \lor x$.
Thus $c = \lnot x$, which means that $h|_{x=1}$ is satisfiable, that is, $f$ is satisfiable.


Joining lists with some common elements in average case

Yes and no.

Set interaction is one of the problems specifically studied in Ben-Or's seminal paper on lower bounds for algebraic decision and computation trees.  The problem is formally defined as follows: Given two sets of n numbers, is their intersection empty? Equivelently, does their union have exactly 2n elements?  Ben-or proves a lower bound of Ω(n log n) for this problem.  If the sets have diffent sizes n>m, the lower bound becomes Ω(n log m), but this only beats the naive O(n log n) bound if m is subpolynomial in n.

On the other hand, if your list elements are integers, you can solve the problem in o(n log n) time using fast integer-RAM sorting algorithms.  For reasonable word sizes, I believe the fastest integer sorting algorithm runs in $O(n \sqrt{\log \log n})$ expected time [Han and Thorup, FOCS 2002].


What you're describing, where you minimize the sum of $f(u,v)w(u,v)$ with a given flow value $|f|$ isn't, in fact, the max-flow problem—it's the min-cost flow problem. If you constrain the flow value to be 1, and all capacities are set to 1, it's pretty clear that this problem is equivalent to finding the shortest path.

Basically, unit-capacity flow problems find edge-disjoint paths. If you set the flow value to be 1, you'll find only a single path. If you're working with min-cost flow, that path will necessarily be the shortest path (and, therefore, the cheapest flow).

If this is not what the book is asking, and it's really asking you about max-flow, I suspect there must be some details missing from your description. (For example, you could easily have a single node $t'$ before $t$, with $c(t',t)=1$, so max-flow would have a flow value of 1, yielding a single path; however, that would still ignore the edge costs, and would just find any path, unless you're specifically using the Edmonds-Karp algorithm, which uses BFS to find its augmenting paths; in that case, you would, at least, find the shortest unweighted path.)


Is there a survey of the semantics of various programming language features?

I don't know of any survey of the semantics of various language features, though
there are many books dealing with the semantics of programming languages. Here are a few of the more comprehensive ones, which also deal with less standard constructs:

Design Concepts in Programming Languages by Franklyn Turbak, David Gifford and Mark Sheldon. A mammoth book full of semantics of many different language constructs.
Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi. This book focusses mainly on the concepts in terms of the language Oz. Every example in the book runs. At the end of the book there is a chapter or two discussing the formal semantics of the language constructs.

More classical texts which put more emphasis on the semantic techniques, rather than on the variety of programming language constructs, include:

Types and Programming Languages by Benjamin Pierce. The book on type systems. Mainly focusses on functional language constructs, while increasing the sophistication of the type system. It also covers Featherweight Java, a core calculus of Java.
Transitions and Trees by Hans Huttel. A nice introduction to operational semantics, covering a variety of languages constructs of increasing complexity.
Semantics with Applications by Hanne Riis Nielson and Flemming Nielson. An introduction to various semantics styles, including some non-obvious applications of them. A great read!
The Structure of Typed Programming Languages  by David A Schmidt. A solid foundational book.
Semantics of Programming Languages: Structures and Techniques by Carl A Gunter. Another  solid foundational book.

Finally, a work-in-progress, generously available for download, Practical Foundations for Programming Languages by Bob Harper  covers a lot of different programming language features, ensuring that everything is formalised along the way.

I should add that if you ask a more specific question, you'll get a more specific answer.  Many scientific papers are out there giving semantics to various programming language features. If you were interested in a specific feature, then I could dig up a paper or two on that feature.


Your question is very brief, so my answer will be as well:

Structure DecidableEquivalenceRelation :=
  {
    carrier :> Type ;
    rel :> carrier -> carrier -> Prop ;
    reflexive : forall x, rel x x ;
    symmetric : forall x y, rel x y -> rel y x ;
    transitive : forall x y z, rel x y -> rel y z -> rel x y ;
    decidable : forall x y, (rel x y) + ~ (rel x y)
  }.


What about { (M,$1^t$) : M is a turing machine that, run on a blank tape, accepts within t steps} ?

The proof of NP-completeness is a simple exercise from the definition.


Explaining input-size of integral arguments to undergraduate CS students

Ask them to them implement the algorithm and then run it on a few dozen 12-digit numbers.


Is the problem NP-C or polynomially solvable?

As said by RB in the comment, if $X_1 \cup X_2  = X; X_1 \cap X_2 = \emptyset$, then setting $B=0$ makes your problem equivalent to PARTITION. But even with the relaxed conditions:
$X_1,X_2 \neq \emptyset, X_1, X_2 \subseteq X;  X_1 \cap X_2 = \emptyset$  (i.e. $X_1,X_2$ not necessarily form a partition of $X$) the problem is still NPC: set $B = 0$ and it becomes equivalent to the EQUAL-SUBSET-SUM problem.

I don't bear papers behind paywalls :-), so this is a quick sketch of an alternative simple reduction from SUBSET-SUM:

Given non-negative integers $A = \{ a_1,a_2,...,a_n\}$ and a target sum $S$, let $k = \lceil \log \sum a_i \rceil$.

For $i = 1,...,n$, set $x_i = 2^{k+3i} + a_i$,
add $n$ new integers $x'_i = 2^{k+3i}$,
add two dum integers $d_1 = d_2 = 2^{k+3(n+1)}$ that are used only to make $X_2$ nonempty
and finally set as target sum (for your problem) $B = S + \sum_{i=1}^n 2^{k+3i}$

The following figure should make things clearer:

(empty cells represent zeros)

If there is a subset $A'$ that sums to $S$ in the original problem, then $X_1 = \{ x_i \mid a_i \in A' \} \cup \{ x'_i \mid a_i \notin A'\} \cup \{d_1\}$, $X_2 = \{d_2\}$ are such that $X_1 - X_2 = B$.

In the opposite direction, suppose that $X_1 - X_2 = B$, then it is easy to prove that if you include one of the $x_i$ (or $x'_i$) in $X_2$, i.e. you subtract them, you'll not be able to "totalize" the $2^{k+3i}$ component of the target sum $B$ anymore. So none of the $x_i$ can be included in $X_2$, and $\sum_{\{ i \mid x_i \in X_1\}} a_i = S$


How can I find dependent rounding procedures with the desirable properties?

Dependent randomized rounding is a broad tool that is used in many approximation algorithms. Lot depends on the problem structure, objective and constraints and there is no single unified answer/framework. Some papers like the ones you mention identify generic settings where one has some nice probabilistic tools and provide some applications. I list a paper below that provides a more general framework and also has pointers to other work on dependent rounding. I also recommend looking at approximation algorithms books such as the ones by Williamson and Shmoys, and Vazirani to see the variety of dependent rounding schemes that are used.

https://arxiv.org/abs/1811.01597 by Nikhil Bansal unifying iterated and dependent rounding.


A direct sum theorem for Resolution clause space complexity?

I wanted to post this as a comment, but since I cannot quite figure out the way to do so I guess it will have to be an "answer" instead.

I agree that the question is nice. Of course, the same question can also be asked about the length of resolution refutations (i.e., the number of clauses occurring in the refutation, counted with repetitions) and the width of refutation (i.e., the size of, or number of literals occurring in, the largest clause in the refutation).

In all of these cases there are "obvious" upper bounds, but it is not clear to me whether one should expect matching lower bounds or not. Therefore, I wanted to add one question and one comment.

The question concerns refutation length. It seems reasonable to believe that the bound for length stated in the comment by Massimo is tight, but do we know this?

And the comment concerns width. Note that for this measure, a moment of thought reveals that a direct sum lower bound does not hold. For width, one instead refutes the whole $A$-formula for each clause $B_i$, in width $w_A$, say, plus the width of the $B$-formula, and then one refutes the $B$-formula in width $w_B$. Assuming that both formulas have constant initial width, the width of the refutation of the direct sum will be essentially $\max (w_A, w_B)$.

This is of course an easy observation, but the point is that it might indicate that the question for space could be tricky. This is so since almost all lower bounds on space in refutation we know of go via width lower bounds. (That is, the space lower bounds were derived independently, but with hindsight they all follow as a corollary from the beautiful paper "A Combinatorial Characterization of Resolution Width" by Atserias and Dalmau.) But if there is a direct sum theorem for resolution clause space, it will not follow from width lower bounds but has to be argued directly, which at least so far has seemed to be much harder. But of course there might be some easy argument that I am missing.


Nontrivial problems solvable in constant time?

The paper Constant-Time Approximation Algorithms via Local Improvements by Nguyen and Onak gives a lot of examples of random constant time approximation schemes: Maximum Matching (the running time depends only on the maximum degree of the graph), Set cover, etc. The authors present a method to design such algorithms.


Implementations of Undirected Disjoint Paths

If you want an implementation, Sage has one. With a LP, as usual ;-)

http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths

Nathann


Applying Expectation Propagation to Factor Graph

The way you are doing is not quite correct. Take a look at these tutorials
 -  http://homepages.inf.ed.ac.uk/csutton/publications/ep-tutorial.pdf
 -  http://web.engr.illinois.edu/~khashab2/learn/ep.pdf

Go over the algorithms which show the EP procedures. Also note the way they explain the projection of the distributions using KL projection.


How to generate graphs with known optimal vertex cover

Expanding vzn's comment into an answer: The standard reduction from CNF-SAT to vertex cover is pretty easy: make a vertex for each term (variable or its negation), connect each variable to its negation by an edge, make a clique for each clause, and connect each vertex in the clique to the vertex for one of the terms in the clause. If you start with a satisfiability problem with a known satisfying assignment, this will give you a vertex cover problem with a known optimal solution (choose the term vertices given by the assignment, and in each clause clique choose all but one vertex, so that the clause vertex that is not chosen is adjacent to a term vertex that is chosen).

So now you need to find satisfiability problems that have a known satisfying assignment but where the solution is hard to find. There are many known ways of generating hard satisfiability problems (e.g. generate random k-SAT instances close to the satisfiability threshold) but the extra requirement that you know the satisfying assignment restricts the possibilities. One thing you can do here is go through another level of reduction, from a cryptographically hard problem such as factorization. I.e. choose two large primes p and q, set up a Boolean circuit for multiplying p and q as binary numbers, and translate it into a CNF formula in which there is a variable for each input (p and q) and for each intermediate value on a wire in the circuit, a clause for each output forcing it to have the right value, and a clause for each gate forcing the inputs and outputs of the gate to be consistent with each other. Then translate this CNF formula into vertex cover.

For a simpler strategy, choose the satisfying assignment to a 3CNF formula first, and then generate clauses at random, keeping only the clauses that are consistent with the assignment, and then convert to vertex cover. If the clauses have uniform probability this will be vulnerable to a degree-based heuristic (the term vertices that match the chosen assignment will have lower degree than the term vertices that do not) but this shortcoming can be avoided by adjusting the probabilities of the clauses according to how many of the clause's terms agree with the chosen assignment. Probably this is vulnerable to some kind of polynomial time attack but it might not be one that's natural for vertex cover, so it might make a good set of test instances despite not having much guarantee of hardness.


Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?

Your "proof" is too vague to convince me, but here's a description of how these maps can be formed. Given a 3-regular 3-connected planar graph, its dual is a maximal planar graph. Every maximal planar graph has a canonical ordering (see references in my earlier comment): an ordering on the vertices of the graph such that the following properties hold:

The first three vertices in the ordering are adjacent
Each prefix of three or more vertices in the ordering defines a subset of the vertices whose boundary is a simple cycle
Each vertex after the first three has as its neighbors a contiguous path of the boundary cycle of the previous vertices

This should allow you to define your rectangular drawing top down. Find a canonical ordering of the dual graph, and make side-by-side rectangles for the first two dual vertices in the canonical ordering (corresponding to two adjacent faces in your graph). Then, add rectangles one by one in the given ordering, below these first two rectangles. For each successive rectangle r, corresponding to a dual vertex v, choose the top vertices on the left and right sides of r to be points on the rectangles corresponding to the endpoints of the contiguous path of neighbors of v from the canonical ordering.

The invariant that makes this work, at each step, is that the boundary cycle of the canonical ordering is exactly the same as the sequence of rectangles that you would see if you stood underneath your drawing and looked upwards.

The circular map should be exactly the same, just starting at the outside and working inwards.

As for the other questions at the end of your post: is this interesting? I don't know. There's some related work in the graph drawing community on representing maps by regions with rectilinear boundaries; the phrase to search for is "rectilinear cartogram". You'd have to show some concrete advantage of your method over previous rectilinear cartogram construction methods such as the one in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.6582&rep=rep1&type=pdf — but suggesting ways to achieve this is probably beyond the scope of this exchange.


Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well

  Asymptotic for very large $n$, a lot of coin flips, after a long time, etc ...

  Equipartition Equally distributed amongst some boxes or bins, Uniformly random, Equilibrium state, "maximum entropy" (if you like statistical physics ... max. ent. is a misnomer if you don't ... see sec. 4.4 of Cover and Thomas), and here's a cool one heat death of the universe

Essentially (strong/weak) AEP is the Information Theory version of the (strong/weak) Law of Large Numbers. In general, if you satisfy some "Law of Large numbers", i.e. your deviations from the mean (or deviations from "typical behavior") decay "quickly" (say perhaps exponentially), then you satisfy an AEP of some kind.

There is a notion of Strong topicality that is used in Csiszár & Körner (Csiszár invented the method of types, a very powerful method in information theory) that might help you understand better i.e. strong typicality means that:

  Strong Typicality: The percentage of $a$'s in $(x_1,...,x_n)$ is approximately equal to $p(a)$.

But what is the probability $p$ in this case!!! That is exactly the point, you have some "equilibrium state" $p$ if you are "ergodic." The point is that you start to behave like a bunch of coin flips at the limit, "when the Markov Process stabilizes."

"Ergodic" is just a vast generalization of i.i.d. with respect to "typical behavior."

The inclusions are (roughly) as follows

  I.I.D. $\subset$ Stationary Markov $\subset$ "Ergodic" $\subset$ $Q$ is "isomorphic/asymptotically equivalent" to a free/independent product space $P^n$

If we keep trying to generalize further and further we eventually reach "abstract non-sense" land (which is a beautiful subject by the way, I personally recommend Aluffi and Awody).

Cover and Thomas are excellent expositors, they were trying to introduce you to the notion of "typical behavior" one baby step at a time. The point is not to jump to the most general possible statement of AEP but to understand the general principles behind the theory of Information; such as how one can "typically" communicate messages perfectly over a "noisy/imperfect" channel. For example, Csiszár & Körner introduce strong typicality early on so that they can get the best error bounds in their proofs right off the bat. Go ahead and try to read Csiszár & Körner casually; while Csiszár is one of the great giants of Information theory he is not necessarily the best expositor. As my fellow Peter (Peter$\cong$Pedro) was trying to point out it would just be poor exposition for him to have done that. The vast majority of applications in Network theory don't even use that, the noise in telephone networks is modeled as white noise in practice etc ...

By the way the proof you are looking for is Thm.16.8 in Cover and Thomas but I really don't recommend you try to attack that monster just yet. At least try out Sec.4.4 in Cover and Thomas first to get a rigorous explanation of some of the stuff I stated here.

Good luck on your mathematical adventures! Bon Voyage, Fred!


An extension to the student/college admissions Gale-Shapley algorithm

I am unsure about matchings of many to many as I haven't seen much of that in the literature but for your extension of exclusivity you may want to look at matching with incomplete lists. This changes the definition of a blocking pair such that they must also find each other acceptable. You could use that to set an agent with only one other agent in its preference list, the result of this would have the agent be unmatched or matched with the agent it ranks. Maybe if many companies can be assigned to one project you could consider this an adaptation of Stable Roommates problem? Where the room is the project and the companies are the people that occupy it. If you want to look further into this I suggest you research:
Stable Matching with incomplete lists (SMI)
Stable Roommates (SR)
Stable roomates with incomplete lists (SRI)
Best of luck!


Other types of uniformity for circuits (incl. by small modifications)

When you want to define (fully) uniform versions of circuit classes, log-space or poly-time uniformity is only sensible for classes of circuits whose power exceeds log-space or poly-time, respectively. This means that poly-time uniformity is next to useless, and log-space uniformity is good for classes like P, NC, $\mathrm{NC}^{k+1}$, $\mathrm{AC}^k$ for $k\ge1$, but not, say, for $\mathrm{NC}^1$.

The standard notion of uniformity for small complexity classes is DLOGTIME-uniformity, where furthermore one has to be careful what exact kind of description of the circuit is asked to be computable in DLOGTIME: in cases where it matters (e.g., $\mathrm{NC}^1$), one needs to use the extended connection language (cf. Ruzzo) of the circuit. This is known as $U_E$-uniformity.


Can we partition NP-complete problem into finite number of polynomially solvable problems?

If you partition the input into sets of instances, each of which has the same solution, then each of these sets of instances is indeed polynomial-time solvable. I'm sure this isn't what you're looking for, but I don't see how to naturally exclude it from your question.


Given a B-Tree, determine the order keys were inserted

Simple... keep two pointers, a next and a previous.


measures for a DAG (directed acyclic graph)?

There are loads of measures of nodes in a DAG you could use.  For example:

How much the removal of node $v$ reduces the max flow from sources to sinks
the betweenness centrality of $v$
the in-degree of $v$ times the out-degree of $v$

The question should not be if there is a measure, but rather which measure is most appropriate.  That depends on the problem you're trying to solve.


Is it a rule that discrete problems are NP-hard and continuous problems are not?

An example that I love is the problem where, given distinct $a_1, a_2, \ldots, a_n \in \mathbb{N}$, decide if: $$\int_{-\pi}^{\pi} \cos(a_1 z) \cos(a_2 z) \ldots \cos(a_n z) \, dz \ne 0$$

This at first seems like a continuous problem to evaluate this integral, however it is easy to show that this integral is not zero iff there exists a balanced partition of the set $\{a_1, \ldots, a_n\}$, so this integral problem is actually NP-complete.

Of course, I encourage playing around with some numerical tools to convince yourself that most (if not all) numerical tricks to evaluate this integral are doomed to failure once $n$ gets large enough.


Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of value at least $n/2$ (give every vertex a value of $1/2$). But the optimal independent set might be of size between $1$ and $n$.

On the other hand, the greedy algorithm does give useful results in some cases. For example, if the number of edges is $m \ll n^2$, then the greedy algorithm would give you an independent set of size $\Omega(n^2/m)$ (always pick the vertex that has the smallest numbeer of neighbors).


What is the goal behind abstract interpretation in programming languages?

Abstract interpretation is a very general concept and depending on whom you ask, you will receive different explanations because versatile concepts admit multiple perspectives. The view in this answer is mine and I would not assume it is general.

Computational hardness as a motivation

Let's start with decision problems, whose solutions have a structure like this:

There is often an NP-hard lower bound on the procedure. Checking semantic properties of programs is even undecidable. What can we do?

Let's make two observations. First, we can sometimes solve specific problem instances even if we cannot solve the general problem. Second, applications like compiler optimization tolerate approximation in that a compiler that eliminates some but not all sources of inefficiency is useful. To make this intuition precise, we must answer:

What does it mean formally to solve some, but not all problem instances?
What is an approximate solution to a decision problem?

Abstract Interpretation Idea 1: Change the Problem Statement

To me, a major insight of abstract interpretation is to change the problem formulation so that instead of asking for a Yes/No answer, we ask for a Yes/No/Maybe answer.

As a consequence, every problem has a trivial, constant time solution (output Maybe). We can now shift our attention to deriving a procedure that does not always produce Maybe. To return to the questions above, a solution that works for some problem instances is one that returns Maybe on problems it cannot solve. Moreover, Maybe is an approximation of Yes and No  because we are not certain what the answer is.

This idea is not restricted to decision problems. Consider these problems concerning programs.

Which lines of code in the program are dead (will never be executed)?
Which variables in the program have constant values?
Which assertions in the program are violated?

In all these situations, we can move from an exact solution to an approximate one by considering solutions that have some uncertainty.

What is a set of lines of code that is dead?
What is a set of variables in the program that have constant values?
What is a set of assertions in the program that is not violated?

The sets produced need not be the largest. This idea is extremely general and applies to problems that have little to do with program analysis.

Instead of adding $m$ and $n$, we can ask for a range $[a,b]$ in which the sum lies.
Instead of multiplying $m$ by $n$ we can ask for $k$ bits of the result (specific, common examples are the sign or the parity bit).
Instead of asking for the satisfying assignments to a formula, we can ask for a set that contains the satisfying assignments.

Note that we have not only changed the problem but also strictly generalized it because a solution to the original problem is still a solution to the modified problem. The big unanswered question now is: How can we find an approximate solution?

Abstract Interpretation Idea 2: Fixed Point Characterization of the Original Solutions

The second big idea is to observe that the set of solutions to many problems has a characterization as a fixed point in a lattice of candidate solutions. As an example, suppose you have a graph and you want to know if a vertex $t$ is reachable from a vertex $s$. We can break this down into finding the set $\mathit{Reach}(s)$ of all vertices reachable from $s$ and then checking if $t$ is in this set. We can further observe that $\mathit{Reach}(s)$ is the least solution to the equation:

  $X = \{s\} \cup \{ w ~|~ v \text{ is in } X \text{ and } (v,w) \text{ is an edge}\}$

The value of a fixed point characterization is that the exact solution can be viewed as the limit of a series of approximations. In this example, the $n$-th element of the series is the set of graph vertices reachable in $n$ steps from $s$ and approximation is a subset of these vertices.

The fixed point characterization is a design decision. There are many different characterizations of a set of solutions. Each of them may have different advantages. In the case of programming languages, we have more structure than just dealing with a graph. The fixed point equations we care about can be defined by induction on structure of the input program. This idea is not specific to programs. When applying abstract interpretation to elements of a structured language such as a grammar, logical formula, program, arithmetic expression, etc. we can define fixed points by induction on the structure of some syntactic object.

By giving this fixed point characterization, we are committing to a specific way of computing solutions. We will not actually calculate this fixed point because it is at least as hard as solving the original problem, which brings us to the next step.

Abstract Interpretation Idea 3: Fixed Point Approximation

Instead of computing a fixed point of a function $F$ in a lattice $L$, we can compute a fixed point of another function $G$ in a lattice $M$. Provided certain conditions are met relating $M$ to $L$, a solution computed in $M$ is guaranteed to be an approximation of the solution in $L$. This is one of the foundational results of abstract interpretation, usually called the fixed point transfer theorem. The soundness condition is given either by Galois connections, or weaker settings involving abstraction or concretization functions, or soundness relations.

The fixed point transfer theorem guarantees that you do not have to prove that you are computing a sound approximation every time you design an approximate analysis. You only have to prove that the lattices $L$ (containing original solutions) and $M$ (containing approximations)  and the functions $F$ and $G$ satisfy certain constraints. This is a big win if you are the designer of an analysis and you care about soundness.

You may find the intuition behind fixed point transfer insightful. We can think of a fixed point as the limit of a (possibly transfinite) chain of elements. Computing approximate solutions amounts to approximating this limit, which we can do by approximating elements of the chain.

The notion of approximation depends on the application. If you are using graph reachability to plan a trip, you may accept an approximation that tells you there is no path between $s$ and $t$ even if there is a path, but you will not be happy if the algorithm says there is a path from $s$ to $t$ where there is no path.

Abstract Interpretation Idea 4: Fixed Point Approximation Algorithms

Everything seen so far has been a mathematical existence result. The final step is to compute the approximation. When the lattice of approximations is finite (or if the ascending/descending chain condition is met), we can use a simple iterative procedure. If the lattice is infinite an iterative procedure may not suffice, though computing a fixed point may still be decidable. In this situation, many techniques are used to further approximate the solution, or to jump to an exact solution faster than a naive iteration algorithm. In the context of computing a solution, you hear terms like widening, narrowing, strategy iteration, acceleration, etc.

Summary

In my opinion, abstract interpretation provides a mathematical basis for the notion of abstraction in the same way that mathematical logic provides a mathematical basis for reasoning. The solutions to many problems we care about have characterizations as fixed points. This observation is not restricted to programming language problems and even to computer science. Approximate solutions can be characterized as approximations of fixed points and are computed with specialized algorithms. These characterizations and algorithms will exploit the structure of the problem instance. In the case of programs, this structure is given by the syntax of the language.

Computing approximations to problems that do not have a natural metric is an art constantly developed and refined by practitioners. Abstract interpretation is one mathematical theory for the science behind this art.

References
There are several good tutorials on abstract interpretation that you can read.

A casual introduction to Abstract Interpretation, Patrick Cousot (Joint work with Radhia Cousot), Workshop on Systems Biology and Formals Methods (SBFM'12)
A gentle introduction to formal verification of computer systems by abstract interpretation, Patrick and Radhia Cousot, Marktoberdorf Summer School 2010.
Lecture 13: Abstraction Part I, Patrick Cousot, Abstract interpretation, MIT Course.
Introduction to Abstract Interpretation, Samson Abramsky and Chris Hankin, Abstract Interpretation of Declarative Languages, 1987.
Abstract interpretation and application to logic programs, Patrick and Radhia Cousot, 1992. The first two sections have a general, high-level overview with several examples.


The construction is optimal in the sense that $\binom{2n}{n}+1 \leadsto n$ cannot hold.  Indeed, it is easy to see that c-to-k coloring matrix exists if and only if there are c subsets A1, …, Ac of the set {1, …, k} such that no distinct i and j satisfy Ai ⊆ Aj.  (For the “only if” direction, take Ai = R(M, i) for a c-to-k coloring matrix M.  For the “if” direction, set mij ∈ Ai ∖ Aj.)  A family of sets none of which contains another is called a Sperner family, and it is Sperner’s theorem that the maximum number of sets in a Sperner family on the universe of size k is $\binom{k}{\lfloor k/2\rfloor}$.  This implies that $c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$.


This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example:

A subquadratic algorithm for minimum palindrome factorization by Fici et al

EERTREE: An Efficient Data Structure for Processing Palindromes in Strings by Rubinchik and Shur.


First order satisfiability that doesn't have finite models

Here's an amusing approach by Brock-Nannestad and Schürmann:

Truthful Monadic Abstractions

The idea is to try to translate first-order sentences into monadic first-order logic, by "forgetting" some of the arguments. Certainly the translation isn't complete: there are some consistent sentences which become inconsistent after translation.

However, monadic first order logic is decidable. One can therefore verify if the translation $\overline F$ of a formula $F$ is consistent:

$$ \overline F\not\vdash\bot$$

can be checked by a decision procedure, and implies

$$ F\not\vdash\bot$$

Which implies that $F$ has a model, by the completeness theorem.

This theme can apply somewhat more generally: identify a decidable sub-logic of your problem, then translate your problem into it, in a way that preserves truth. In particular modern SMT solvers like Z3 have gotten astonishingly good at proving satisfiability of formulas with quantifiers (by default $\Sigma^0_1$, but can perform well on $\Pi^0_2$ formulas).

Forcing seems to be far out of reach of automated methods at the present.


Find items that are in at least $k$ of $n$ sets

OK, I think I found something relevant: this paper mentions a "T-occurrence problem" in section III (p. 2) which is exactly our problem (where $T$ is what we called $k$), hidden behind some domain-specific jargon. The ScanCount algorithm that they propose is the naive approach I suggested in my question. The MergeOpt algorithm is a generalization of the binary search trick. Their main proposal (DivideSkip) is a combination of this binary search trick and a different trick (MergeSkip) to skip multiple values. It even seems that experimentally the clever approaches are much better than the naive approaches (look at the "No filters" column in page 8, the filters are heuristics for their domain-specific stuff).

This can be combined with David Eppstein's trick to make multiple binary searches in $S_2$ more efficient, and with the idea of using interpolation search instead of binary search (an idea from this other paper from the same field).


The area you want to look at for answers to is machine learning. You have desribed a graphical model. I think in this case methods as easy as Belief Propagation should suffice.


Complexity of Membership-Testing for finite abelian groups

Verifying whether $b \in \langle h_1, \ldots, h_n\rangle$ (where $h_i$ are vectors according to the OP's comments) is equivalent to verifying whether there is a solution to this system:
$$
\begin{pmatrix}
h_{1}(1) & \cdots & h_{n}(1) & d_1^{e_1}      & 0 & \cdots & 0 \\\\
\vdots  & \ddots & \vdots  & \vdots & \vdots  & \vdots & \vdots  \\\\
h_{1}(m) & \cdots & h_{n}(m) & 0      & 0 & \cdots & d_m^{e_N}
\end{pmatrix}
\begin{pmatrix}
x(1) \\\\
\vdots \\\\
x(n) \\\\
y(1) \\\\
\vdots \\\\
y(m)
\end{pmatrix}
\equiv
\begin{pmatrix}
b(1) \\\\
\vdots \\\\
b(m)
\end{pmatrix}
$$

In your case $e_1, \ldots, e_N$ are tiny numbers (ie. their value is logartihmic in the input size). Unfortunately, it doesn't seem like we can assume that $d_1, \ldots, d_n$ are tiny.

If they are, then you can find a solution to the system in $\text{NC}^3$ from a result of McKenzie & Cook [1]. This paper shows that solving linear congruences modulo an integer with tiny factors (LCON) is in $\text{NC}^3$. Moreover, this problem is $\text{NC}^1$-equivalent to the abelian permutation group membership problem (AGM). McKenzie's doctoral thesis is fully devoted to those problems [1]. More recently, those problems were considered by Arvind & Vijayaraghavan [3].

[1] Pierre McKenzie & Stephen A. Cook. The parallel complexity of Abelian permutation group problems. 1987.

[2] Pierre McKenzie. Parallel complexity and permutation groups. 1984.

[3] V. Arvind & T. C. Vijayaraghavan. Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes. 2010.


Max weight travel on a graph with deadline

Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem has no such restriction. In other words, in the original version of the problem the "path" is actually a trail (i.e., any sequence of vertices such that each contiguous pair has an edge between them). Thus I will refer to the original version of the problem as the trail max-weight travel problem. The other version, in which the number of uses of each edge/vertex is limited, includes the case in which each edge/vertex can be used at most once (i.e., the trail used must be a simple path); I will call that subproblem the simple path max-weight travel problem.

Below, I prove that trail max-weight travel is weakly NP-hard and that simple path max-weight travel is strongly NP-hard.

trail max-weight travel is weakly NP-hard

We reduce from the Unbounded Knapsack problem: we are given a list of pairs of positive integers $(c_1, s_1), \ldots, (c_k, s_k)$ where pair $i$ represents a type of item with cost $c_i$ and size $s_i$, a maximum size $S$, and a minimum cost $C$, and we are asked to decide whether it is possible to choose some quantity of each item so that the total size is at most $S$ and the total cost is at least $C$.

Suppose we are given an input $(c_1, s_1), \ldots, (c_k, s_k), S, C$ to the knapsack problem. Let $H > S$ be any big ("huge") number. Then we build an instance of trail max-weight travel as follows:

Set the graph size $n$ to be $k + 1$. Let $1, \ldots, k+1$ be the vertices of graph $K_n$.
Set the deadline $D$ to be $(k+1)H + S$.
If $1 \le i < j \le k+1$ then set the weight $w(e_{ij})$ to be $0$. Set the travel time $l(e_{ij})$ to be $(j-i)H$.
If $1 \le i \le k$ then set the weight $w(e_{ii})$ to be $c_i$. Set the travel time $l(e_{ii})$ to be $s_i$.
If $i = k+1$ then set the travel time $l(e_{ii})$ to be $H$. Set weight $w(e_{ii})$ to be some number $M$ that is greater than $D (\max_{i = 1}^k \frac{c_i}{s_i})$.
Set the start node to be vertex $1$.

We will show that a trail of total travel time $D$ has a weight of at least $M + C$ if and only if the answer to the given knapsack instance is "yes". This is sufficient to show NP-hardness.

There are two possible types of trails: those that use edge $e_{ii}$ with $i = k+1$ and those that don't. Call this edge $e'$.

The maximum weight gained per unit of travel time over all edges other than $e'$ is $\max_{i = 1}^k \frac{c_i}{s_i}$. Thus, any trail that does not use edge $e'$ will have a total weight of at most $D (\max_{i = 1}^k \frac{c_i}{s_i}) < M$. Thus, trails that do not use edge $e'$ will have total weight less than $M$.

Clearly, some trail (whose travel time is at most the deadline) has total weight at least $M + C$ if and only if a trail using edge $e'$ (with travel time at most the deadline) has total weight at least $M + C$. Using edge $e'$ requires reaching vertex $k+1$ from vertex $1$. This requires using a travel time of at least $kH$. Then using edge $e'$ requires an additional travel time $H$. After that, there is not enough time left in the deadline to use edge $e'$ again. Thus, any trail whose travel time is at most the deadline and whose weight is at least $M + C$ will use edge $e'$ exactly once.

Since traveling between vertices adds no weight, it should be clear that the optimal solution will always spend the minimum possible travel time between vertices. Fortunately, this is possible without bypassing any vertex (by going through the vertices in order $1, 2, \ldots, k+1$). This means that there is always an optimal solution to the produced trail max-weight travel instance in which we pass through the vertices in order $1, 2, \ldots, k+1$ taking one self loop at vertex $k+1$ (in particular edge $e'$) and some number of self loops at the other vertices. Traveling between the vertices has travel time $kH$ and weight $0$. The self loop at vertex $k+1$ has travel time $H$ and weight $M$. Thus, in order for this optimal solution to reach a weight of at least $M + C$ within a deadline of $D = (k+1)H+S$, it must be the case that the total travel time used on the self loops at vertices $\{1, \ldots, k\}$ is at most $S$ and the total weight gained at those self loops is at least $C$. Since self loop $e_{ii}$ has travel time $s_i$ and weight $c_i$, this is exactly equivalent to the knapsack instance we started with.

simple path max-weight travel is strongly NP-hard

We reduce from the following NP-hard version of the Hamiltonian path problem: given graph $G$ and vertex $v$, decide whether there exists a Hamiltonian path in $G$ starting at $v$.

Suppose we are given an instance of this problem with graph $G = (V, E)$ and vertex $v \in  V$. Then we build an instance of simple path max-weight travel as follows:

Set the graph size $n$ to be $|V|$.
Set the deadline $D$ to be $|V| - 1$.
Identify each vertex of $K_n$ with each vertex of $G$. Then for each edge $e$ of $K_n$: (1) if $e$ corresponds to an edge of $G$, set the travel time $l(e)$ to be $1$ and (2) if $e$ does not correspond to an edge of $G$, set the set the travel time $l(e)$ to be $|V|$. In all cases, set the weight of each edge to be $1$.
Set the start node to be the node corresponding to $v$.
As always in the simple path max-weight travel problem, each vertex/edge can be used at most once: $h(\cdot) = 1$.

Each edge has the same weight, so maximizing weight is equivalent to choosing the longest simple path whose total travel time does not exceed the deadline. The only edges that can be used without exceeding the deadline exactly correspond to edges in $G$. Furthermore, each such edge has the same time limit: $1$. Thus, solving this instance is equivalent to finding the longest simple path in $G$ starting at $v$ of length at most $|V| - 1$. Such a path of length exactly $|V| - 1$ is a Hamiltonian path, so solving this problem requires being able to solve the Hamiltonian path problem in $G$. Thus the reduction is correct. Note that the size of each number in this proof is at most polynomial in the size of the input instance, so this is a proof of strong NP-hardness.


Upperbound for max degree of k-tree completion

It is known that a graph of treewidth $k$ and maximum degree $\Delta$ has tree partition width at most $O(k\Delta)$. See Wood, arXiv:math/0602507.
From a tree partition of width $O(k\Delta)$ a triangulation of width $O(k\Delta)$ and maximum degree $O(k\Delta^2)$ follows pretty directly (start with the tree partition, make every bag into a clique, make every vertex $v$ in $U$ adjacent to all vertices in all bags appearing together with neighbors of $v$).
So you get a (minimal) triangulation with the bounds above.
Note: I would not be surprised if you can get a better degree bound.. the additional $\Delta$ term feels unnecessary.