Computational Complexity of the Divisor summatory function

Based on a "folkore intuition" for a related problem, one might expect this to be at least as hard as factoring:

The folkore intuition suggests that computing the number of prime factors, or even computing essentially any useful information about the prime factorization, is as hard as factoring itself (see Tao's answer to this related question). $d(n)$ gives you exactly such information, and is essentially equivalent (from the computational perspective) to computing $D(n)$, since $d(n) = D(n) - D(n-1)$.

For example, if $n$ is squarefree, then $d(n)$ is equal to $2^{f}$ where $f$ is the number of prime factors. For general $n$, $d(n)$ is $\prod_{p} (m_p + 1)$ where $m_p$ is the number of times the prime $p$ divides $n$ (that is, $n = \prod_{p} p^{m_p}$ is the prime factorization of $n$).


Are there any implementations for zero-knowledge proofs of NP-complete problems?

The answer is yes, check the following paper:

SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer and Madars Virza
http://eprint.iacr.org/2013/507
(also published at Crypto 2013)


Permutations of maximum period: applications to Rubik's cube

Copy/paste from another (slightly different) cstheory question on Rubik's cube:

"What is the shortest sequence that scans all cube's configurations", or "does the configuration graph of the cube have a Hamiltonian path?" is a special case of a more general unsolved problem:

For an arbitrary permutation group with a given generating set, is its Cayley graph Hamiltonian?

There are some good info available online, you can download the lecture notes by W.D.Joyner: Mathematics of the Rubik's cube (downloadable in pdf format).

Chapter 6 of the lecture notes is devoted to Cayley graphs and God's algorithm.

EDIT: If I correctly interpret the question "Does such a permutation even exist?", the answer is yes (the Cayley graph of a finite group is connected); a trivial argument:

let $k$ be the total number of wrong configurations;
for every wrong configuration $W_i, 1 \leq i \leq k$ write down the solving sequence of moves $S_i$;
let $S_i^{-1}$ be the inverse sequence of $S_i$;
obviously the (long) sequence $S_1 \cdot S_1^{-1} \cdot S_2 \cdot S_2^{-1} ... \cdot S_{k-1}^{-1} \cdot S_{k-1}^{-1} \cdot S_k$ will lead you to the solved configuration from any wrong starting configuration, but you must "look at the cube" to see when to stop (there is no "synchronizing sequence").


Bidirectional A*: is an update of the distance estimation feasible while searching?

I think I have found the answer in the paper and it is indeed not just a replacement of the potentials:

  Now, if we want to replace p_f and p_r (forward and reverse potential) , all we need to do is change
  the keys of the labeled vertices for the two searches appropriately
  and update the priority queues containing these vertices. This takes
  time proportional to the number of labeled vertices at this point.


Best known deterministic time complexity lower bound for a natural problem in NP

Adachi, Iwata, and Kasai in a 1984 JACM paper show by reduction that the Cat and $k$-Mice game has an $n^{\Omega(k)}$ time lower bound.   The problem is in P for each $k$.   The problem is played on a directed graph.    The moves consist of the cat and then one of the $k$ mice alternating steps.  The mice win if they can land on a designated cheese node before the cat lands on them.   The question is whether the cat has a forced win.   It is actually a complete problem so the lower bound is really based on the diagonalization that gives the time hierarchy.

Grandjean showed that the Pippenger, Paul, Szemeredi, and Trotter time lower bound applies to a SAT encoding, though the result of Santhanam may subsume it.

In addition to the time-space tradeoff lower bounds for SAT mentioned in other comments, there is a body of work on branching program lower bounds which imply time-space tradeoffs for Turing machines.    For problems like FFT, sorting or computing universal hash functions there are quadratic tradeoff lower bounds of Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari but these are for functions with many outputs.   For decision problems in P, there are time-space tradeoff lower bounds that apply for time bounds that are $O(n \log n)$ but these are weaker than are known for SAT.


Hardness of an extended maximum set packing problem

The previous reduction doesn't work with the current reformulation of your problem (19 July 2014); however I leave it below, because it is correct for that particular maximum k-set packing problem variant (which is defined in the reduction). Here it is a fix for the current version:

CURRENT VERSION

Again your problem is NP-hard for $l \geq 3$. NOTE that  $l$ should not be part of the input otherwise it is simply a generalization of the MAXIMUM $k$-SET PACKING problem (MSP): given an instance of MSP, feed it to your algorithm setting $l = k$; so the NP-hardness proof is immediate.

If $l,k$ are not part of the input, I give you the idea of the reduction for the case $l = k-1$, but it can be easily extended to arbitrary $3 \leq l < k$. Given an instance of MAXIMUM $l$-SET PACKING PROBLEM (MSP), i.e. a collection of sets $A_1, A_2, ..., A_n$ and an integer $p$ that represents the minimum number of sets required for the solution, build an instance of your problem in the following way:

if $A = \{x_1,...,x_m\} = A_1 \cup ... \cup A_n$ are the elements in the $A_i$, "clone" them: $B = \{y_1,...,y_m\}$ using $m$ new elements and build the corresponding $B_i$: $x_j \in A_i \Leftrightarrow y_j \in B_i$;
add to the $A_1,...,A_n,B_1,...,B_n$ a (new) shared element $z$;
the sets $A_1 \cup \{z\},...,A_n\cup \{z\},B_1 \cup \{z\},...,B_n \cup \{z\}$ represent the input of your problem;
sets to $2p$ the minimum number of subsets required for the solution of your problem (each one must contain $l$ unique elements).

Suppose that a solution exists for your problem. Then we can have the following cases:

exactly $p$ subsets of $A'_i \subseteq A_i \cup \{z\}$ and $p$ subsets $B'_i \subseteq B_i\cup \{z\}$ are included in the solution; but, by construction, the element $z$ can only be contained in one of them - suppose one of the $A_i$ - but in that case the $p$ sets $B'_i$ (that don't contain $z$) also represent a valid solution for the original MSP problem (because each one of them contains $l$ unique elements);
or $q > p$ subsets $A'_i \subseteq A_i\cup \{z\}$ and $2p - q$ subsets $B'_i \subseteq B_i\cup \{z\}$ are included in the solution; again the element $z$ can be included in only one of the $A'_i$, but nevertheless we have at least $p$ of them (because $q > p$) that don't include it, so those $p$ subsets $A'_i \subseteq A_i$ represent a valid solution for the original MSP problem;
or $q > p$ subsets $B'_i \subseteq B_i\cup \{z\}$ and $2p - q$ subsets $A'_i \subseteq A_i\cup \{z\}$ are included in the solution; this case is similar to the previous one.

In the opposite direction, if a valid solution to the original MSP exists, it also represent a valid solution to your problem: just pick $A'_i = A_i \subseteq A_i \cup \{z\}, B'_i= B_i \subseteq B_i \cup \{z\}$.

PREVIOUS VERSION

The decision version of your problem MAXIMUM $l$-DISJOINT $k$-SET PACKING PROBLEM is:

Input: an integer $q \geq 0$ and a collection $D$ of finite sets, each set contains $k$ elements; an integer $0 < l < k$
Output: a set packing of $q$ or more sets, i.e. a collection of partially overlapping sets $D' \subseteq D$ with $|D'| >= q$ and foreach $A_i, A_j \in D', | A_i \cap A_j | \leq k - l$ (the last contraint means that two subsets must contain at least $l$ distinct elements)

When $l \geq 3$ the above problem remains NP-hard and this is a reduction from the decision version of MAXIMUM $l$-SET PACKING PROBLEM which is NP-hard because $l \geq 3$ ($k=l$):

Input: an integer $p \geq 0$ and a collection $C$ of finite sets, each set contains $l \geq 3$ elements;
Output: a set packing of $p$ or more sets, i.e. a collection of disjoint sets $C' \subseteq C$ with $|C'| >= p$

Reduction: simply pick $q=p$, and add $k - l$ new shared elements $Y = \{y_1,...,y_{k-l}\}$ to every original set $A_i \in C$; i.e. $D \ni A'_i = A_i \cup Y$

Suppose that $A'_i, A'_j \in D'$ (where a D' is a valid solution to your problem), then by construction they already share $k-l$ elements (the $y_i$s); so they cannot share more elements, otherwise the number of disjoint elements would be less than $l$: $(A'_i \setminus Y) \cap (A'_j \setminus Y) = \emptyset$.

But $A'_i \setminus Y$ contains exactly the elements of the original $A_i \in C$, and  $A'_j \setminus Y$ contains exactly the elements of the original $A_j \in C$, so $A_i \cap A_j = \emptyset$ and we can conclude that the solution $D'$ corresponds to a valid solution $C'$ of the original problem.

The opposite direction (if there exists a valid solution $C'$ for the $l$-SET PACKING PROBLEM then there is also a valid solution $D'$ to your problem) is immediate.


Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

According to Wikipedia, the number of permutations in $S_n$ with exactly $k$ inversions is the coefficient of $X^k$ in
$$1(1+X)(1+X+X^2)\cdots(1+X+\cdots+X^{n-1}).$$
Denote this by $c(n,k)$. This shows that
$$c(n+1,k) = \sum_{l=0}^k c(n,k-l).$$
So the number of permutations in $S_n$ with at most $k$ inversions is equal to the number of permutations in $S_{n+1}$ with exactly $k$ inversions. This has a neat combinatorial proof as well (hint: take $\pi\in S_{n+1}$ and remove $n+1$).

If we are interested only in the coefficient of $X^k$, then factors $X^m$ for $m > k$ don't make any difference. So for $n > k$, $c(n,k)$ is the coefficient of $X^k$ in
$$
\begin{align*}
&1(1+X)\cdots(1+X+\cdots+X^{k-1}) (1+X+\cdots+X^k+\cdots)^{n-k} \\ =
&1(1+X)\cdots(1+X+\cdots+X^{k-1}) \frac{1}{(1-X)^{n-k}} \\ =
&1(1+X)\cdots(1+X+\cdots+X^{k-1}) \sum_{t=0}^\infty \binom{t+n-k-1}{t} X^t.
\end{align*}
$$
This implies the formula
$$
c(n,k) = \sum_{t=0}^k \binom{n+t-k-1}{t} c(k,k-t), \quad n > k.
$$

When $k$ is constant, the asymptotically most important term is the one corresponding to $t = k$, and we have
$$
c(n,k) = \binom{n-1}{k} + O_k(n^{k-1}) = \frac{1}{k!} n^k + O_k(n^{k-1}).
$$
The same asymptotics work for $c(n+1,k)$, which is what you were after.

For non-constant $k$, using the fact that $\binom{n+t-k-1}{t} = \binom{n+t-k-1}{n-k-1}$ is increasing in $t$ and $\sum_{t=0}^k c(k,t) \leq k!$, we get the bounds
$$
\binom{n-1}{k} \leq c(n,k) \leq k! \binom{n-1}{k}.
$$
Better bounds are surely possible, but I'll leave that to you.


Busy Beavers: quadratic relation of output size and running time?

It's true, all current busy beaver candidates have a quadratic relationship between output size and steps. As Ross points out, this has to do with how they act. They move back and forth across much of the output every time they increase the output size by some constant. That means that to get to size N they must run for approximately 1 + 1 + 2 + 2 + 3 + 3 + ... = N(N+1) steps.

However, there are many other types of Turing machines. For example, there are ones often called counters which move back and forth across a section of output, each time incrementing a binary (or other base) counter. These take exponential time to increase the size of the output. One interesting one is Brady's "Surprise in a Box" http://www.drb.insel.de/~heiner/BB/simAB3Y_SB.html which expands quadratically for a little while and then moves completely within the "box" until it halts.

There are also machines which have a sort of recursive "back and forth" behavior so that it takes them N^2 steps to increase the size of the tape. They have a cubic relationship between output size and steps.

I suspect that for larger values busy beavers will not have this relation because they will get more complex in their behavior, but I don't know of any proofs.


Searching for partial match - 1 item to be searched in $n$ preprocessed items

If I understand the problem correctly, this looks like an instance of the Nearest Neighbor Search, under the Hamming distance.

In other words, the "distance" between ordered sets is just the number of mismatched positions. The goal is to preprocess a collection (dataset) of ordered sets, each of size n, so that given a "query" ordered set, the data structure reports an ordered set within Hamming distance n-m. In your case, n is the dimension, and n-m is the distance. (This variant is actually called near neighbor search (the nearest neighbor is one where one reports the closest dataset item).

If that's the problem, then the wiki page may be a good start for pointers on existing work.


Justification of log f in DTIME hierarchy theorem

For n-tape TMs a tight time hierarchy result similar to the space hierarchy theorem is proven by Furer in 1982. The $\lg$ factor is not needed.

The $\lg$ factor for the time hierarchy theorem stated in your post is only for single-tape TMs. Unless you are very committed to the single-tape model for some reason there is not a difference between space and time regarding the hierarchy theorems.

There are some reasons and arguments for using single-tape TMs for defining time complexity classes, but the usage of single-tape TMs for defining complexity classes is not universal, e.g. see Lance Fortnow and Rahul Santhanam's [2007] where they use multiple-tape TMs.

The original reference for the time hierarchy theorem is Hennie and Stearns [1966]. They prove the theorem for two-tape machines. Odifreddi's Classical Recursion Theory cites them and Hartmanis [1968] and describes a proof that looks similar to the one in Sipser's book.

However the proof for single tape TMs in Hartmanis's paper does not use simulation simply. It distinguished between two cases: 1. running-time being $\Omega(n^2)$ and 2. running-time being $o(n^2)$.

For the first case it uses a simulation, and it seems that one can get rid of the $\lg$ factor if the simulations can be done more efficiently.
For the second case, the paper directly gives a language for the separation and doesn't use simulation at all. This uses particular properties of single-tape TMs with sub-quadratic running-time.

One should note that single-tape TMs with time $o(n^2)$ are not as robust and there are quadratic lowerbounds (e.g. for Palindroms) on single-tape TMs whereas a two-tape TM can solve such problems in linear time.

As I said above, unless you are committed to single-tape TM model for some reason, even when time is sub-quadratic, there is not a gap to fill, the time hierarchy theorem is as tight as possible.

PS: if we are using multiple-tape TMs, i.e. a Turing machine in the class can have fixed but arbitrary number of tapes Fürer's result does not apply.

Martin Fürer, "The Tight Deterministic Time Hierarchy", 1982
Piergiorgio Odifreddi, "Classical Recursion Theory", vol. II, 1999
(page 84)
Juris Hartmanis, "Computational Complexity of One-Tape Turing Machine Computations", 1968
F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", 1966
Lance Fortnow and Rahul Santhanam's paper "Time Hierarchies: A Survey", 2007


Computing 'Robustness of Magic' of $n$-bit W states

Here is a proof that $R(W_n) \in \Omega(\sqrt[4]{n})$.

Given a $W_n$ state, it is possible to create $\lg n$ T states with Clifford operations and a single additional T gate. Basically:

Xor together all the qubit's whose binary index has an odd number of 1s, apply a T gate to that xor'd value, then unxor.
Apply an S gate to every qubit whose binary index has a number of 1s that's 2 or 3 more than a multiple of 4.
Apply a Z gate to every qubit whose binary index has a number of 1s that's 4, 5, 6, or 7 more than a multiple of 8.
Compress the unary $W_n$ state down into a binary register.

Here's an example circuit turning $W_8$ into 3 $|T\rangle$ states:

I also tested turning $W_{16}$ into 4 $|T\rangle$ states.

We can produce $\lg n$ T states from a $W_n$ state and a single $T$ state. It must always be the case that an output's robustness of magic is less than or equal than the input's. Therefore:

$$R(W_n) \cdot R(T) \geq R(W_n \otimes T) \geq R(T^{\otimes \lg n})$$

In the paper "Application of a resource theory for magic states to fault-tolerant quantum computing" it is proven (see page 3) that:

$$R(T^{\otimes k}) \in \Omega(1.2^k)$$

Meaning $R(W_n) \cdot R(T)$ is greater than or equal to something asymptotically lowerbounded by $1.2^{\lg n}$. Since $R(T)$ is a constant, we can ignore it and deduce:

$$\begin{align}
R(W_n) &\in Ω(1.2^{\lg n})
       \\&= Ω(n^{\lg 1.2})
       \\&\subset Ω(n^{0.263})
       \\&\subset Ω(\sqrt[4]{n})
\end{align}$$

Therefore $R(W_n)$ is asymptotically somewhere between $\sqrt[4]{n}$ (by synthesizing into Ts) and $n$ (via the decomposition I showed in the question).


You can mechanically transform an LR(k) grammar into an LR(1) grammar (source)

This is not true for LR(*) grammars (k=inf). However, that statement doesn't mean that there isn't such a grammar for the same language. You might just need to rewrite the grammar.

Grammars exist that cannot be transformed, however. Languages for Context-Sensitive grammars can be more expressive than context-free grammars (can only be recognized by linear-bounded automata). Therefore, your hoped-for translation is possible for just a subset.

Update for clarification:

There are languages that can not be represented by LR grammars but do have a grammar that is not LR (the language requires something more powerful than LR). There are also grammars that are not LR that recognize a language that can be recognized by an LR grammar (the language just happens to have a complex grammar, but it is not required).


What are the widely used notations for quickly referring to a single component of a multi-component object?

Papers I've seen that have this issue often present 1 as the initial definition and then also define 2 (or 3 with subscripts) as an additional definition that is used when necessary for clarity.

A common abuse of notation—common enough that I've seen it in multiple places, although it makes my skin crawl every time I see it—is to write something like $S = S(TS)$.

3 with superscripts is unacceptable because superscripts have other widely-understood standard meanings; however, it would be fine if the superscripts were changed to subscripts. 4 is never used outside of programming contexts.

I would also recommend avoiding the two-letter variable name $TS$ in mathematical notation, especially since you are also using $S$ as a separate symbol. Use single letters, resorting to Greek if necessary, for anything in the standard italic "variable" font. Special functions and classes of languages usually get straight font or boldface to distinguish them from surrounding text for this reason.


I think what you're looking for is Las Vegas algorithms. I do not know that the class of functions computable by polytime Las Vegas algorithms has an abbreviation beyond "Las Vegas polynomial time".

As pointed out by Tsuyoshi Ito in the comments, $ZPP$ is exactly the class of decision problems decidable in Las Vegas polynomial time.


$\ell_p$-norm preserving Turing machines

This is not a complete answer to the questions, but it is too long to write as a comment.  It expands my previous comment.

The question “What happens to computation if the axioms of quantum mechanics are modified a little?” is addressed in great detail by a fun paper [Aar04] by Scott Aaronson.  I believe that your questions are essentially answered in the first half of Section 2 of [Aar04].

Aaronson shows that if p>0 and p≠2, then a matrix which preserves the p-norm for all vectors is necessarily a generalized permutation matrix (a product of a permutation matrix and a diagonal matrix).  He states that the same holds in the case p=∞.  All these hold for both over ℝ and over ℂ.  Note that this includes the case of p=1: stochastic matrices preserve the 1-norm for nonnegative vectors but not for all vectors in general.

I guess that a probabilistic Turing machine generalized as in [For00] has a generalized permutation matrix as its global transition matrix only if it is a deterministic Turing machine, but I do not have a proof at hand.

Aaronson discusses also several other modifications of the axioms of quantum mechanics in the paper.  For example, if we change the rule of measurement (instead of the set of allowed gates) so that the outcome x occurs with probability |αx|p/∑y|αy|p, where αy is the amplitude of |y⟩, then this “quantum computer” can solve any problems in PP (including NP-complete problems) in polynomial time unless p=2 (Proposition 5).

References

[Aar04] Scott Aaronson.  Is quantum mechanics an island in theoryspace?  In Proceedings of the Växjö Conference “Quantum Theory: Reconsideration of Foundations,” 2004.  arXiv:quant-ph/0401062v2.

[For00] Lance Fortnow.  One complexity theorist’s view of quantum computing.  In Computing: the Australasian Theory Symposium (CATS 2000), pp. 58–72, Jan. 2000.  http://dx.doi.org/10.1016/S1571-0661(05)80330-5


Most important topics for a short introduction to Prolog

My idea is to teach them enough to write simple provers for (fragments of) the systems of logic used elsewhere in the course.  I had lots of experience writing interpreters from other courses in my curriculum, so I would have been prepared for that sort of approach.  Introduce SLDNF as the basis of sketching the limitations of using prolog in such a fashion, so they can reason about what's going to be hard and what's going to be easy to do in prolog for the remainder of the course.  Of course, my approach needs prolog to be introduced early instead of the last week.  If you like this approach, I suggest giving them libraries to render the proof trees or whatever that you use in the rest of the course.


Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?

The question is similar to the questions about constructive existence of the limit of a sequence of (constructive) objects. Usually if you can uniformly construct those objects (here $M\epsilon$) efficiently enough then you can show the existence of the limit constructively.

For example, assume that we have a TM $N(k,x)$ which runs $M_{|k|^{-1}}$ on $x$ and its running time is $O(n^{a+|k|^{-1}})+O(|k|)$ (here the bounds are also uniform, e.g. something like $O(2^k.n^{a+|k|^{-1}})$ would not work). Then we can combine this uniform simulator with the function $(k,x)\mapsto x$ to obtain the machine $N(x,x)$ that runs in time $O(n^{a+o(1)})$.

PS: $O(n^{a+o(1)})$ is a little bit ambiguous because of nesting of asymptotic notations, I am interpreting it as $n^{a+o(1)}$. Also we need $a$ to be not too small, e.g. at least $1$.


Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

Chaitin  in his 1976 paper

Chaitin, Gregory J., Information-theoretic characterizations of recursive infinite strings, Theor. Comput. Sci. 2, 45-48 (1976). ZBL0328.02029.

studied sets such that there exists  b ∈ℕ  with

$$\forall n\quad C(A\upharpoonright n)\leq C(n)+b.$$

where $C$ denotes the plain Kolmogorov complexity. These sets are known as C-trivial sets. Chaitin showed they coincide with the computable sets.

Interestingly, this is not so for the prefix-free Kolmogorov complexity version, the K-trivial sets.


How to compute ROOK Polynomials for NxM Matrices

See the answers of this question.

Your case is a lot easier, just choose $k$ of the $m$ columns and then you have
$n (n-1)\ldots (n-k+1)$ ways to put the $k$ rooks. So the coefficient of $x^k$ is

$\displaystyle r_k = \binom{m}{k} n (n-1)\ldots (n-k+1) = \binom{m}{k}\binom{n}{k}k!$.

The provided link also gives a dynamic programming approach to compute $r_k$.


Request for references on multicommodity flow-cut results

I can recommend my recent paper http://arxiv.org/abs/1110.6832 on multicommodity flows and cuts in polymatroidal networks; we generalize several known results in standard graphs. Although we do not give a nice table summary we discuss many of the known cases. Some of the results that are not discussed in the paper but are of relevance are those for planar undirected graphs and some special cases. These include the result of
Satish Rao on $O(\sqrt{\log n})$ bound on flow-cut gap and tight bound of $2$ for series-parallel graphs by Chakrabarti-Jaffe-Lee-Vincent and some others. James Lee has several papers on flows and cuts on these graphs and any relatively recent one will discuss the existing literature.


Are there any topics in theoretical CS that are more about pure math?

Here are three more fields that fit your criteria.

Category theory. This is clearly interesting to most pure maths
fields, but also has been very influential in the theory of
(functional, sequential) programming languages.
Logic, particularly proof theory. The connections with computer
science are too many to name, but logic is not only a rich field of
pure mathematical, but the foundation of mathematics.
Number theory, the "queen of mathematics", which was deemed to
be devoid of applications ... until cryptography came along.


Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K

When the costs are all equal, you are looking for the fewest number of edges to bring your graph to being of at most diameter $k$. This is the graph diameter augmentation problem. You are looking for the edge-weighted version, which I believe has been studied as well.

There are a number of versions of diameter augmentation out there: some that fix or bound the amount of bridge you can build and the task is the bring the diameter down to as small as possible. Or, your version, you have some $K$ in mind and you want to find the cheapest amount of bridges in order to acheive that $K$.

Naming of these problems is non-standard or inconsistent in the literature, but searching for 'graph diameter augmentation' will get you on your way.


From what I can tell, strategies involve relaxing balance conditions, then performing rebalancing updates in bursts.  Here is a paper from Hanke et al., 1997 [PDF], which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.


Power of randomness vs. power of indefinite computation

Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects the running time by at most a polynomial factor (the exact factor depending on the model of computation), and so the new machine is also in ZPP. The new machine is also guaranteed to always halt. So bounded-ZPP is the same class as ZPP.


There is some work on developing an algebraic or grammar-based view of string algorithms, for example

Robert Giegerich, Carsten Meyer, Peter Steffen:
A discipline of dynamic programming over sequence data. Sci. Comput. Program. 51(3): 215-263 (2004)

Robert Giegerich, Hélène Touzet:
Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems. Algorithms 7(1): 62-144 (2014)

These approaches deal with string problems that are solved by dynamic programming such as the computation of edit distance or local alignments or comparison of RNA secondary structures. These problems are more difficult in terms of the running time of the best algorithms than the exact pattern matching problem that is solved by Boyer-Moore.

A more conceptual or programmer-friendly approach for exact pattern matching would be to use the right data structures such as suffix arrays or suffix trees. Many pattern matching algorithms become simpler when these data structures are used as a black box or augmented in some relatively easy way.


Why is the multi-step reduction of semantics reflexive?

The practical reason is that it is very convenient to include also the case "zero steps" in the definition of "many steps" (millennia of mathematical experience have taught us that it is usually a good thing to have a 0 around in our set of natural numbers).

One possible technical exemplification of this (but there are probably dozens more, perhaps more interesting than this one) is that $\to^+$, the transitive closure of reduction, does not satisfy the diamond property  (a.k.a. confluence), whereas $\to^\ast$ satisfies it.  For example, if $I:=\lambda x.x$, there is no way to close the following critical pair by means of $\to^+$:

$$I \leftarrow (\lambda x.I)(II) \to (\lambda x.I)I$$

To close the span, you need to consider the empty reduction $I\to^\ast I$.


The best way to understand this is to have a second level of "types above types" which we then call kinds. Kinds can be formed by the following rules:

Type is a kind.
If K and L are kinds then so is K → L.

Kinds have elements:

The elements of Type are types, such as nat, bool, nat → nat, nat × nat, etc.
The elements of K → L are functions which map elements of K to elements of L.

For instance, Pair is an element of Type → Type → Type. It is a "kind-level" function which maps types A and B to type A × B. Another example is List which is an element of Type → Type and it maps a type A to the type List A of lists of As.

A very fancy kind is (Type → Type) → Type which takes a function on types and returns a type. An example of this is "recursive type definition". To see this, consider the most general form of a recursive type definition:

type t = Φ(t)

For instance, we could define lists of numbers like this (using OCaml notation):

type natlist = Nil | Cons of nat * natlist

This is a special case of the general recursive type definition if we take

Φ(a) = Nil | Cons of nat * a

We could actually define an operator rectype and then write

type t = rectype Φ

to define the type t which is equal to Φ(t). Now it takes a moment's thought that rectype is of kind  (Type → Type) → Type. (At this point, if you have never seen this before, you should be having a minor epiphany.)

In Haskell Type is written as * so sometimes Haskell tells you that something has type * → *. This means that the thing is a type-level function taking types to types. In Ocaml there are kinds under the hood but they are never shown to the user (well, kind of since they get exposed through module types).

Professor Pierce of course knows all these things much better than I do, but most likely at this point in the course he does not want to burden you with another layer of $\lambda$-calculus on top of $\lambda$-calculus. A quick and dirty solution is to just put all the kinds together in one big messy pile and call them "improper types". The trouble with such things is that the smart students will get confused (and rightfully so).


You could solve it using a dynamic programming approach:

First lay out vertices in a topological order like $v_1, v_2, ..., v_n$. If start and end vertices are  $s=v_a$ and $e=v_b$, you could get rid of all vertices after $v_b$ and before $v_a$. So let's assume $s=v_1$ and $e=v_n$. Next, define $L_{i,j,p}$ to be the shortest path between $v_i$ and $v_j$ which has $p$ nodes. In other words, among paths between $v_i, v_j$ which have $p$ nodes, it's the length of shortest one. Assume $w_{i,j}$ is the weight between $v_i, v_j$, and it is infinity if there is no edge. Now

Set $L_{i,i,1}=0$.
For $p>1$ we have $L_{i,j,p} = min_k \{L_{i,k,p-1}+w_{k,j} \}$, where  $i\le k<j$.

Now the final answer is $max\{k\}$ for all $k$s that we have $L_{1,n,k}<d$. The table (actually half of it need to be filled, because $i<j$) has $n^3$ elements, and for each element $O(n)$ time it takes to be computed. So the time complexity will be $O(n^4)$, but guess tighter bounds could be achieved.

UPDATE: As Neals pointed out in the comments an $O(n^2 m)$ bound is achievable. Also the algorithm can be thought of as a LDP algorithm running on transformed graph $G'$: make $n$ copies of the original graph $G$ and for each edge $e=(v,w)$ in $G$ connect the $i$th copy of $v$ and $(i+1)$th copy of $w$, for $1 \le i < n$.


Resolution Search (just applying the resolution rule with some good heuristics) is another possible strategy for SAT solvers. Theoretically it's exponentially more powerful (i.e. there exist problems for which it has exponential shorter proofs) than DPLL (which just does tree resolution though you can augment it with nogood learning to increase its power - whether that makes it as powerful as general resolution is still open as far as I know) but I don't know of an actual implementation that performs better.

If you don't limit yourself to complete search, then WalkSat is a local search solver which can be used to find satisfiable solutions and outperforms DPLL-based search in many cases. One can't use it to prove unsatisfiability though unless one caches all the assignments that have failed which would mean exponential memory requirements.

Edit: Forgot to add - Cutting planes can also be used (by reducing SAT to an integer program). In particular Gomory cuts suffice to solve any integer program to optimality. Again in the worst case, an exponential number may be needed. I think Arora & Barak's Computational Complexity book has a few more examples of proof systems that one could in theory use for something like SAT solving. Again, I haven't really seen a fast implementation of anything apart from DPLL-based or local search based methods.


What's the most efficient algorithm for Divisibility?

Fleshing out my comments into an answer: since divisibility is (trivially) reducible to division, and since division is (nontrivially) reducible to multiplication via approaches like Newton's method, then your problem should have the same time complexity as integer multiplication.  AFAIK, there are no known lower bounds for multiplication better than the trivial linear one, so the same should hold true of your problem - and in particular, since multiplication is known to have (essentially) $O(n\log n\log^* n)$ algorithms, your hopes for a $n\log n\log\log n$ lower bound are almost certainly in vain.

The reason that division reduces precisely in complexity to multiplication — as I understand it — is that Newton's method will do a sequence of multiplications of different escalating sizes; this means that if there's an algorithm for multiplication with complexity $\Theta(f(n))$ then the complexity of a division algorithm using this multiplication algorithm as an intermediate step will be along the lines of $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ — and for all of the complexity classes under discussion this is just $\Theta(f(n))$.


APX-Hardness implies that there is a $\delta > 0$ such that the problem does not admit a $(1+\delta)$-approximation unless $P=NP$. Clearly this rules out a PTAS (assuming $P \neq NP$). As for QPTAS, it will rule it out unless you believe that NP is contained in quasi-polynomial time. As far as I know, that is the only reason why APX-Hardness rules out a QPTAS.

Since a couple of people asked more details, here are some more. APX-Hardness for a minimization problem P implies that there is a fixed $\delta > 0$ and a polynomial-time reduction from 3-SAT to P such that a $(1+\delta)$-approximation for P allows one to decide whether the 3-SAT formula is satisfiable or not. If there is a QPTAS for P we can obtain for any fixed $\delta > 0$ a $(1+\delta)$-approximation in time say $n^{O(\log n)}$. But this implies that we can decide whether a 3-SAT formula is satisfiable in $n^{O(\log n)}$ time which in turn implies that NP is in QP.


Why do we use single tape Turing machines for time complexity?

I've seen texts define TIME( $f(n)$ ) using multi-tape Turing machines, but Sipser uses a single tape machine.  You've almost surely first encountered this material through Sipser because it's so fabulously well written.

There is a crystal clear pedagogical reason why Sipser does this, namely the course just naturally flows that way because :

You should introduce the single tape machine before the multi-tape machine, otherwise steepens the learning curve.
There is no compelling reason to introduce the multi-tape machine before introducing O($\cdot$) and TIME($\cdot$) for single tape machines.
You should ideally compare the multi-tape machine with the single tape machine the moment you introduce the multi-tape machine, otherwise the prolonged ignorance will lead to additional confusion.
You could omit introducing the analogous TIME classes for multi-tape machines, thus simplifying notation overall.

There is no reason to quibble over conceptual cleanliness when the pedagogy so clearly dictates the easiest path, and every computer science undergrad must take this elementary course, including all those who still don't understand proofs.


Why is $\{0,1\}^n$ referred to as the Boolean hypercube?

Strictly speaking, the "Boolean hypercube" is not the same as the set $\{0,1\}^n$. The Boolean hypercube is the graph whose vertices are the set $\{0,1\}^n$, and whose edges are defined as follows: two strings are adjacent if and only if they differ on exactly one bit.

I guess that usually, people refer to $\{0,1\}^n$ as the Boolean hypercube when they really want to think of it as a graph and not as a set of strings.


Is it possible to create a "quote" function that, given a native λ-term, returns its λ-encoded representation?

No, this is not possible, assuming you want to go from an arbitrary lambda term to some first-order AST.

The lambda calculus is extensional, which means that the lambda calculus cannot distinguish between two lambda-terms which are behaviourally equivalent. Eg, if you have terms implementing quick sort and merge sort, then no other lambda-term can distinguish them, since they are both extensionally the same function. As a result, full quotation is impossible, since it should let you get different source code for those two terms.


Finding sets of heavily intersecting objects, while minimizing their size

If I understand right, you are interested in finite projective planes.  These are the maximum combinatoric set systems in which all sets intersect each other exactly once.  To briefly answer your question, you can "improve" your construction by getting up to $\Omega(n)$ sets of size $\Omega(n^{1/2})$ and still enforcing the property that any two sets intersect on exactly one element (note: this only works for certain $n$, e.g. $n$ = square of a prime).

I assume you have some unstated restriction on your sets that rules out the construction $\{1, 2\}, \{1, 3\}, \{1, 4\} ...$ in which case your sets have size two but all pairs intersect on exactly one element?


Continuous mathematics and formal language theory

Lamine commented on the connection to the Chomsky-Schützenberger enumeration theorem. Recently, a few research problems in formal language theory were solved using continuous mathematics via this connection. For example:

Hermann Gruber, Jonathan Lee, and Jeffrey Shallit. Enumerating Regular Expressions and their Languages. available online at arxiv.org as arXiv:1204.4982, 2012
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
A Hitchhiker's Guide to descriptional complexity through analytic combinatorics. Theor. Comput. Sci. 528: 85-100 (2014)
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
Average Size of Automata Constructions from Regular Expressions. Bulletin of the EATCS 116 (2015)
Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis:
On the Average Complexity of Partial Derivative Automata for Semi-extended Expressions. Journal of Automata, Languages and Combinatorics 22(1-3): 5-28 (2017)

The first two of the above references also give a survey of the mathematical and/or historical background.


How is DHT different than regular hash tables in context to data/node lookup?

Your question in the first sentence is a bit vague and open-ended. I'm guessing you want to know about routing and mutual node knowledge in the context of lookup.

Each node shouldn't have to know about every other node. Assuming a hash ring topology, the simplest approach is to have each node know about its two neighbors on the ring. This defines a circular linked list. Unfortunately, as with all linked lists, it only supports slow linear search. It's also very sensitive to node removal: if any two nodes go offline, it breaks the connectivity of the ring.

If you try to repair this idea by having nodes maintain knowledge of their longer-range relatives then you eventually wind up with the idea of a skip graph, a generalization of skip lists that can handle node disappearance robustly. Unlike skip lists they are not explicitly stratified, which is important due to the non-hierarchical peer-to-peer nature of the problem.


Small kernel (i.e. proof-verifier) for Agda?

It is true that Agda currently has a much shakier foundation than say Coq or Lean. It does have an internal term syntax that could be seen as a core language (https://github.com/agda/agda/blob/master/src/full/Agda/Syntax/Internal.hs). It even has an independent typechecker for internal syntax (https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/CheckInternal.hs).

However, this story is far from complete because it takes the signature of defined types and functions for granted. In particular, functions by dependent pattern matching are represented as case trees that need to pass coverage checking and termination checking, which means those checks are also part of Agda's 'trusted core'. In our ICFP paper last year (https://dl.acm.org/citation.cfm?doid=3243631.3236770) Andreas and I describe a potential core language for case trees, but so far there is no independent typechecker for case trees as we have for internal syntax (one day...).

Another important part of Agda's trusted core is the conversion checker, which in Agda shares most code with the constraint solver (https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/Conversion.hs), while in Coq it's two separate algorithms. Recently I added the possibility to run the conversion checker in 'pure' mode which is guarateed to be free of side-effects (https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/Conversion/Pure.hs).

As you can see, there is bits and pieces that could be part of a core language of Agda, but no real coherent story yet. In general, any attempt to build a core language will also be an exercise in selecting which features of Agda should be included and which ones should not (e.g. irrelevance, sized types, prop, rewrite rules, cubical, ...). Yet this selection of various features would've been much harder to implement if Agda already had a core language from the beginning, so not having a core language has advantages as well as disadvantages.


It's been a long time but I am pretty sure this problem is in P.

I wrote my PhD dissertation about this in 1995. See "Efficient Dynamic Network flow algorithms" by Bruce Hoppe submitted to Cornell CS dept. Online at http://dspace.library.cornell.edu/bitstream/1813/7181/1/95-1524.pdf

See Chapter 8 "Extensions" section 8.1 about "mortal edges"


How do I store data with a query that's a approximated ?

You should explain how F works ... however I try to give you some tips.

Suggestion 1

The standard information retrieval approach may help you:

split each "item" in small size words (for example 4 digits), and build an inverted index, i.e. a table that maps each word to the items that contains it:

word1 -> item1, item2, item5, ...
word2 -> item2, item3, item6, ...
...

Then if you must find items similar (closer) to item X:

split X in words w1 w2 w3 ... w4
easily (and quickly) retrieve items that contains those words
order the retrieved items according to your F (weighting each item using the number of  common words also contained in X)

You can also expand the inverted index to include the word positions if required by your function (w1#1 -> item1, item4; w1#2 -> item3, item6; ...).

Obviously, this approach works only if your F can be rearranged and calculated only using the word co-occurences.

The inverted index can be very large if the choosen word size is small.

Suggestion 2

Perhaps you can try to "fit" your data in a compressed prefix tree.

In the paper Prefix Tree Indexing for Similarity Search and
Similarity Joins on Genomic Data the authors combine several techniques and implement similarity searches (and joins) on a prefix tree.

We present PETER, a prefix tree based indexing algorithm supporting
approximate search and approximate joins. Our tool supports Hamming
and edit distance as similarity measure and is available as C++ library,
as Unix command line tool, and as cartridge for a commercial database.
It combines an efficient implementation of compressed prefix trees with
advanced pre-filltering techniques that exclude many candidate strings
early.

...Our experiments reveal that PETER is faster by orders of magnitudes compared to the command-line tools. Compared to RDBMS, it computes similarity joins in minutes for which UDFs did not finish within a day and outperforms the built-in join methods even
in the exact case.


The closest related family of languages seem to be the "bounded semilinear languages" defined in this paper.  But since the commutative image of each language in the family defined in the original post is a linear set, it might be appropriate to call such languages "bounded linear".


In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system model (Section 3.1). Then, they further illustrate how to map their spin system model to the problem of uniformly sampling from the order ideals of a poset which, in turn, is equivalent to sampling from the antichains of that poset (Section 3.2).

Propp, James Gary, and David Bruce Wilson. "Exact sampling with coupled Markov chains and applications to statistical mechanics." Random Structures & Algorithms 9.1‐2 (1996): 223-252.


What are the popular science books that inspire TCS?

I know of many theoretical computer scientists whose first inspiration came from reading Godel, Escher, Bach

Its becoming a bit dated at this point, but is still an excellent read.


What can we say about a fixed point for a provability predicate in deductively defined theory that satisfies diagonalisation lemma

The formula $A$ is provable, this is almost exactly the content of Löb's Theorem.

The proof (which can be found on the Wikipedia page) is a bit contorted, as it requires an additional application of diagonalization to build and analyze the formula:

$$ \Psi \equiv Pr(\lceil\Psi\rceil)\rightarrow A $$


You can solve the problem in a fixed number of dimensions by extending the linear time original solution of Bird from 1977 http://www.sciencedirect.com/science/article/pii/0020019077900175 (subscription needed sadly).

The general idea (in 2D) is in step 1 to build an Aho-Corasick automaton of the rows of the 2D pattern and then feed in the rows of the 2D text one by one. You will then find all the positions that the pattern rows match in the text.  To finish you now only need to do a 1D search for the (labels of) the rows of the pattern in the right order in a column in the output of step 1, using KMP say.  This all takes linear time.

Using the same method you can reduce from any dimension d exact matching problem to a dimension d-1 problem. In this way you get a linear time solution for any fixed dimension d.


How do you compute the fixed point of a best-response function efficiently?

A fixed point of a best response function is a Nash equilibrium -- the fact that you do not have the payoff matrix cannot make the problem easier (since if you know the payoff matrix, you also know the best response function, but not vice versa). Unfortunately, there are not in general good algorithms for computing approximate Nash equilibria in multi-player games. It is known that in general settings, computing a fixed point of a function is equivalent in difficulty to computing a Nash equilibrium -- see for instance http://homepages.inf.ed.ac.uk/kousha/nash_focs07_full_j_spec_issue_sub.pdf

There are not believed to be efficient algorithms for computing fixed points for general (best response) functions, and it is open whether they can be approximated well in general.


No, that's not what you thought!

The "K" in K-SAT is not related to the number of variables in the formula; rather, it limits the number of "literals" in each "clause".

Let's define the terms:

atom = the same thing you called variable; e.g. "x", "y", "z", etc.

literal = an atom or its negation; e.g "x" or "$\neg$x".

clause = a disjunction of literals; e.g. $(x \vee y \vee \neg z \vee w)$.

CNF: A formula is said to be in Conjunctive Normal Form (CNF) if it consists of AND's of several clause. For instance, $(x \vee y) \wedge (y \vee \neg z \vee w)$ is a CNF formula.

The followin problem is K-SAT:
Given a CNF formula $f$, in which each clause has exactly K literals, decide whether or not $f$ is satisfiable. That is, whether there is a an assignment to the atoms such that $f$ evaluates to TRUE.

See also Mike Jason B Punkt's answer in this post.


I emailed the PC and received the following answer:

  "Title  page" means a page that contains only the title and abstract.


What is the complexity of this covering problem?

Although this does not resolve the question you raise, some of the previous comments consider approximation algorithms.  FWIW, I think a PTAS (poly-time approximation scheme) is possible using dynamic programming.  Here's the idea.

Given any instance and $\epsilon > 0$, build a solution as follows.  Mark every $(1/\epsilon)$'th vertex.  For each marked vertex $i$, from all of the edges $(j,k)$ that "span" $i$ (i.e., that satisfy the constraint (1) for $i$), choose one edge that minimizes $j$ and one that minimizes maximizes $k$.  Add these $2 \epsilon n$ edges to the solution.

These edges satisfy the constraints of type (1) for many of the vertices.  Meanwhile they contribute $2n\epsilon$ edges to the solution, which is only $O(\epsilon \mbox{OPT})$.  To finish, we will find an optimal solution to the remaining problem of finding a set of edges that meets all remaining type (1) and type (2) constraints.

Define a "block" of vertices to be a set of consecutive vertices whose type (1) constraints are met by the edges added so far.  Between any two consecutive blocks, there is a sequence of vertices whose type (1) constraints are not met.  (Any such sequence has length at most $1/\epsilon$, because the marked vertices have their type (1) constraints met by the edges already added.)  Call any such sequence a "neighborhood" of the two adjacent blocks (so each block has a neighborhood to its left and a neighborhood to its right).

Within each neighborhood, for each vertex in the neighborhood, each edge leaving the vertex spans a distance of at most $1/\epsilon$ (because the edge doesn't span any marked vertex).  Thus, the vertex has degree at most $1/\epsilon$.  Thus, each neighborhood has at most $1/\epsilon$ vertices and touches at most $1/\epsilon^2$ edges.  Call any subset of those edges a "configuration" of the neighborhood.  If a configuration meets all of the type (1) and type (2) constraints for the vertices in the neighborhood, call the configuration "valid".

For each block $i$, for each pair $(C_i, C_{i+1})$ of valid configurations of the block's two neighborhoods, compute (in polynomial time, using maximum matching etc), the minimum size $F_i(C_i,C_{i+1})$ of any set $S$ of edges (if any exists) such that the edges in $C_i\cup S \cup C_{i+1}$ meet the type (2) constraints for the vertices in the block.  Since there are at most $2^{1/\epsilon^2} = O(1)$ configurations, this can be done in polynomial time (for fixed eps).

Now you can solve the original instance by finding a sequence $D_1, D_2, .., D_k$ of valid configurations, one for each neighborhood, that minimizes $\sum_i |D_i| + F_i(D_i, D_{i+1})$, where $F_i$ is as defined in the previous paragraph.  This can be done by finding a shortest path in the graph formed by all valid configurations, with an edge of cost $|D_i| + F_i(D_i, D_{i+1})$ from each configuration $D_i$ for neighborhood $i$ to each configuration $D_{i+1}$ for neighborhood $i+1$.  (This graph has size $O(2^{1/\epsilon^2} n)$, which is $O(n)$ for fixed $\epsilon$.)


There cannot be significantly better algorithms for graphs with $O(n\log n)$ edges than there are for general graphs. This is because the Benczur-Karger cut sparsifier can take an arbitrary graph, and output a graph with only $O(\frac{n\log n}{\epsilon})$ edges such that the value of any cut in the sparsified graph is within a $(1\pm\epsilon)$ factor of the cut value in the original graph. Therefore, a PTAS for sparse graphs would yield a PTAS for general graphs, by simply first running the cut sparsifier, and then approximating max-cut in the sparse graph. Since it is NP hard to approximate max cut in general graphs to within a factor of 16/17, this is also true for sparse graphs.

Note that there is no PTAS for max-cut even when all edge weights are non-negative. Things are even worse when negative edge weights are allowed, as in your question. See this question for the negative edge weight case: Max-cut with negative weight edges


Prime factorisation of decidable problems

I think a candidate for such a set $\mathbb{B}$, or something very much like it, could be produced by considering an infinite sequence of singleton languages: $L_1=\{w_1\},L_2=\{w_2\},\ldots$ --- where the $w_1\cdot w_2\cdot\ldots$ form an incompressible sequence. You might be able to shave off a bit here or there (this will strongly depend on the encoding -- which is why Kolmogorov complexity really only makes sense up to an additive constant). But modulo additive constants, this family of strings has the property where being given one of them as input does not in any way help in generating any other one.


What is First-Order Rewritable (and FO-Query)?

Part of the answer is in your question: if your language is FO-rewritable, query answering is in $\textrm{AC}_0$ in data complexity, which is almost as good as it gets. However, keep in mind that you have to pay the cost of computing $Q_\Sigma$, which might be expensive, though you have to do it only once.

Other good thing is that, for a FO-rewritable language, you reduce the problem of answering a query over a database with dependencies to answering a query over a database without dependencies. But again, the size of the new query ($Q_\Sigma$) might be exponential (or worse, but I'm not so sure) in the size of $Q$ and $\Sigma$ (because you have to encode the TGDs in $Q_\Sigma$ somehow). Anyways, roughly speaking it means you are reducing a problem to a simpler problem. I guess that's why it's very good.


2DFA to 1DFA - Converting two way deterministic finite automata to one way deterministic finite automata

Kozen presents a constructive proof of the equivalence of 1dfa and 2dfa in a chapter of his book titled "Automata and Computability". If I recall correctly,  it is a standard argument and the algrothim follows clearly from the proof. The chapter can be found at the following link.  https://link.springer.com/chapter/10.1007/978-1-4612-1844-9_22


Understanding the talks in Conferences and Workshops

This may seem strange at first, but one way I've found to understand an area better is to write in it.

Every area of any discipline has its own mini-language. It consists most obviously of specialized terminology---but there is also a certain structure and order to how people in that area prefer to give and receive information. There are also particular ways of understanding certain difficult concepts, especially abstract or nonobvious concepts.

Reading is obviously key, and it will help you understand the terminology. But to really climb into the heads of those who present in your area, you have to write. You'll then be forced to learn good ways to structure information and ways to understand difficult concepts---and discover how and why the other researchers in your area think and talk the way they do.


Are there any natural hard problems where it is required that the number of solutions are always more than one?

In a cubic graph, the number of Hamiltonian cycles containing a given edge is even.  Therefore, if a cubic graph has any Hamiltonian cycles, it has at least two.  (The same has been conjectured to be true for $k$-regular graphs with $k \ge 4$ as well; I don't know the status of that conjecture.)  So deciding whether a cubic graph contains a Hamiltonian cycle (which is still NP-hard) seems to meet the criteria.

However, showing that this (or any other) problem is not in UP seems difficult, since you would have to show that the multiplicity of solutions can't be eliminated by some clever non-parsimonious reduction.  It's not enough to show that the obvious NP machine that solves the problem has multiple accepting paths.


You may be working with rude elitists, but from my experience, being reluctant to explain technical details depends more on the context than on the person I am talking to. I would usually avoid giving technical details of a proof/algorithm over lunch or in the corridor even if my interlocutor were Alan Turing himself. The reason is that details heavily depend on the choice of notations and on hand-crafted concepts introduced to smooth a claim. Also, because everyone understands things differently and I do not have a generic way to explain a concept, I always have to adapt to my interlocutor (that is why giving technical details in a research presentation is so hard by the way).

One exception is if my interlocutor has worked closely with me on this kind of problem and then, I know that we can use this common gibberish that only we understand because we grow into it together after several white board sessions (or before an urgent deadline).

Another exception is if after giving a crude overall scheme of the proof without details, my interlocutor asks a precise question showing he has seen a particular hard part of the proof that I have been intentionally hiding from him in order to simplify the presentation. In that case, we would naturally open the Pandora box and go together into the heart of the proof, layer by layer... and usually end up on a white board because at some point, we again need this common gibberish that only fit us and this problem.

There are several morals with my already too long story:

Do not depreciate yourself because you are not actively working in theoretical computer science. Most people will not care about your precise background as long as you show that you are curious about their work.
When people are vague about a proof/concept, stay alert and try to guide the conversation by asking a precise question showing your understanding and thus helping your interlocutor to choose which part of the proof he should develop first. This is obviously quite hard and unpredictable because you may not be able to give relevant comments on the go (this happens to everyone even to "theorists"), but if you manage it, then you will likely end up with a very enlightening discussion.
Even "theorists" need time to reload the details of a proof in their head before being able to clearly explain it. Make an appointment by explicitly asking that you are interested in the technical details of X. This will allow for time for your interlocutor and you to prepare, and will ease the discussion. Make sure to have a white board or a piece of paper during the discussion so that you can really go into details.


Soundbite answer: DNA computing does not provide a magic wand to solve NP-complete problems, even though some respected researchers in the 1990s thought for a time it might.

The inaugural DNA computing experiment was performed in a laboratory headed by the renowned number theorist Len Adleman.  Adleman solved a small Traveling Salesman Problem -- a well-known NP-complete problem, and he and others thought for a while the method might scale up.  Adleman describes his approach in this short video, which I find fascinating.  The problem they encountered was that to solve a TSP problem of modest size, they would need more DNA than the size of the Earth.  They had figured out a way to save time by increasing the amount of work done in parallel, but this did not mean the TSP problem required less than exponential resources to solve. They had only shifted the exponential cost from amount-of-time to amount-of-physical material.

(There's an added question: if you require an exponential amount of machinery to solve a problem, do you automatically require an exponential amount of time, or at least preprocessing, to build the machinery in the first place?  I'll leave that issue to one side, though.)

This general problem -- reducing the time a computation requires at the expense of some other resource -- has shown up many times in biologically-inspired models of computing.  The Wikipedia page on membrane computing (an abstraction of a biological cell) says that a certain type of membrane system is able to solve NP-complete problems in polynomial time.  This works because that system allows for the creation of exponentially-many subobjects inside an overall membrane, in polynomial time.  Well... how does an exponential amount of raw material arrive from the outside world an enter through a membrane with constant surface area?  Answer: it's not considered.  They're not paying for a resource that the computation would otherwise require.

Finally, to respond to Anthony Labarre, who linked to a paper showing AHNEPs can solve NP-complete problems in polynomial time.  There's even a paper out showing AHNEPs can solve 3SAT in linear time.  AHNEP = Accepting Hybrid Network of Evolutionary Processors.  An evolutionary processor is a model inspired by DNA, whose core has a string that at each step can be changed by substitution, deletion, or (importantly) insertion.  Further, an arbitrarily large number of strings is available at every node, and at each communication step, all nodes send all their correct strings to all attached nodes.  So without time cost, it's possible to transfer exponential amounts of information, and because of the insertion rule, individual strings can become ever larger over the course of the computation, so it's a double whammy.

If you are interested in recent work in biocomputation, by researchers who focus on computations that are real-world practical, I can offer this book review I recently wrote for SIGACT News, which touches briefly on multiple areas.


As mentioned in the comments, if you allow some extra additive slack of $\varepsilon\in(0,1]$ (an input parameter) in the error guarantee, and relax the success probability from one to $1-\delta$ (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class $\mathcal{C}_n$ of $n$-state DFAs with membership queries.

Indeed, while you do not have accuracy queries $\mathrm{AQ}$, those can be easily simulated by sampling in the PAC setting (leading to the $\pm\varepsilon$ and $1-\delta$ relaxation).

However, this paper by Vitaly Feldman [Feldman09] shows that then, one may as well forget about the membership queries and focus on honest-to-goodness agnostic PAC learning:

  [...] we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries.

In this light, provided you are willing to proceed with the error slack and high-probability guarantee, then your question boils down to agnostic PAC learning of $n$-state DFAs.

[Feldman09] Vitaly Feldman. On The Power of Membership Queries in Agnostic Learning. Journal of Machine Learning Research (JMLR) 10(Feb):163--182, 2009.


If all XOR relationships between variables in CNF formulas could be detected in polynomial time, then this would allow the solution of UNAMBIGUOUS-SAT in polynomial time.  By the Valiant–Vazirani theorem this result would imply that NP = RP.

To solve UNAMBIGUOUS-SAT, recall that $a \oplus b$ implies $a \neq b$.  Find the XOR relationship between each pair of variables and use the results to divide the variables into two groups of equivalent variables.  Once this is done, only two test assignments are required to determine satisfiability.

In the limited case of recovering XOR relationships encoded in the usual way, i.e.

$a \oplus b \oplus c$

to

$
\lnot a \lor b \lor c \\
a \lor \lnot b \lor c \\
a \lor b \lor \lnot c \\
\lnot a \lor \lnot b \lor \lnot c
$

this can be done in polynomial time by sorting the clauses followed by a linear-time scan.


Average-case complexity open problems other than one-way functions

You can look at the survey paper by Bogdanov and Trevisan, and this survey talk by Luca. The main open question is whether $\mathsf{P} \neq \mathsf{NP}$ implies that there exist hard on average problems in $\mathsf{NP}$. There are also more concrete conjectures about specific problems, two of which were mentioned in the comments:

The planted clique problem: distinguish between a uniformly random graph on $n$ vertices, and a uniformly random graph in which we have planted a $k$-clique on a random $k$-subset of the vertices. Conjectured to be hard for $k = \omega(\log n)$, $k = o(\sqrt{n})$.
Feige's random SAT hypothesis: for every $\Delta$, any polynomial time algorithm which never refutes a satisfiable 3SAT formula will fail to refute most 3SAT formulas with $\Delta n$ clauses. It is consistent with current knowledge that this hypothesis may hold even up to $\Delta = o(\sqrt{n})$.


Mutual information and entropy to prove minimal Relevance Maximum Dependency

For the equations you are reporting, $J(S_m) = I(S_{m-1}; x_m)$, i.e. $J(S_m)$ is the mutual information between $S_{m-1}$ and $x_m$. Since for any two random variables $X$ and $Y$

$I(X; Y) = H(X) + H(Y) - H(X; Y)$

the equation follows directly from the definition of mutual information (the chain rule does not apply here, since there is no need to deal with conditional entropy):

$\begin{gathered}
  H({S_{m - 1}},{x_m}) = H({S_m})  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - J({S_m})  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - I({S_{m - 1}};{x_m})  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - (H({S_{m - 1}}) + H({x_i}) - H({S_{m - 1}},{x_m}))  \\
   = \sum\limits_{i = 1}^m {H({x_i})}  - (\sum\limits_{i = 1}^m {H({x_i})}  - H({S_{m - 1}},{x_m}))  \\
   = H({S_{m - 1}},{x_m})  \\
\end{gathered}$


Hardness of finding a graph coloring given the optimal number of colors

Knowing the exact value of the chromatic number $\chi$ cannot help by more than a factor of $n$.  Since there are only $n$ possible values of $\chi$, you can 'guess' its value, i.e., run processes $P_1,\dots,P_n$, where $P_i$ runs an algorithm assuming $\chi=i$.  This whole scheme can find an optimum colouring in time at most $n$ times the time that it takes $P_\chi$ to find an optimum colouring.

On the other hand, if you're talking about parameterizing the running time by $\chi$, then it's a much more interesting question.  It's in FPT if you parameterize by $n-\chi$ S. Khot and V. Raman, ‘Parameterized Complexity of Finding Subgraphs with
Hereditary properties’.  If you parameterize by $\chi$ I would assume it's W[1]-hard.


Complexity of the directed Steiner tree problem on special graph classes

This manuscript seems to prove exactly that. (It doesn't; the complexity parameter is $|T|$, not the treewidth.)

In general, most NP-hard optimisation problems have polynomial-time algorithms when the input is restricted to bounded-treewidth graphs. These algorithms use the rather well-known tree-decomposition machinery, which is also used in the linked paper.

EDIT: The undirected Steiner tree is, on the other hand, known to be fixed-parameter tractable with regards to parameter $w$ the treewidth of the underlying graph. My suggestion would be to try and adapt this algorithm to the directed case, which would in particular give a polynomial time algorithm for series-parallel graphs.


What happens if we improve the time hierarchy theorems?

About your second question. No, that would not imply $P \neq NP$. Hierarchy theorems are mostly useful to determine the amount of a single resource needed by a TM so that additional problems can be solved.

For example, we know that $DTIME(n) \neq NTIME(n)$. Let $f(n) = n$, $g(n)$, $h(n)$ such that $f(n+1) = o(g(n))$ and $f(n)log(f(n)) = o ( h(n) )$.

From the hierarchy theorems it follows that $ DTIME( f(n) ) \subsetneq DTIME( g(n) )$ and $NTIME ( f(n) ) \subsetneq NTIME( h(n) )$.
 Under those assumptions, $ NTIME( g(n) ) \subseteq DTIME( h(n) )$ is possible.

The hierarchy theorems can be used to determine relationships between resources, given an equality between them. For example , assume that
$ NTIME(2^{n}) = SPACE( n )$. We know that $NTIME( g(n) )$, for $g(n)$ such that $2^{n+1} = o(g(n))$, cannot be equal to $SPACE(n)$ , due to the NTIME hierarchy theorem.


A decomposition theorem for maximum weight matchings

Are you actually looking for a polynomial time algorithm solving maximum weight matching for general graphs, or a specific way to solve it using a kind of decomposition?

In the former case, the following paper gives an $\mathcal{O}\big(n(m + \log n)\big)$ exact algorithm:
H.N.Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors witk Linking. SODA'90 (1990)
And for a $(2/3 - \epsilon)$-approximation algorithm running in $\mathcal{O}(m \log 1/\epsilon)$:
S.Pettie, P.Sanders. A Simpler Linear $2/3 - \epsilon$ Approximation Algorithm for Maximum Weight Matching. Information Processing Letters, vol.91 (2004)


Continued Fraction Algorithm in Shor's Algorithm

Yes, that's exactly the idea.  It is inspired by the following fact:

Theorem. Let $\psi$ be an irrational number, and suppose $|\psi - s/r| \le 1/2r^2$.  Then $s/r$ is one of the convergents of the continued fraction expansion of $\psi$.

In other words, every "very good" approximation to $\psi$ can be obtained by computing the continued fraction representation of $\psi$ and looking at one of its convergents.

In the specific situation you mentioned, we know $\psi$, and we don't know $s$ or $r$.  However, we know that there exist $s,r$ such that $|\psi - s/r| \le 1/2r^2$.  It follows from the theorem that $s/r$ must be one of the convergents of the continued fraction of $\psi$.

Therefore, if we iterate through the convergents of the continued fraction for $\psi$, this is guaranteed to find $s,r$.  Moreover, this procedure is efficient: you'll only have to look at $O(\lg r)$ convergents, so the running time will be polynomial in $\lg N$.

See also https://math.stackexchange.com/q/1139381/14578.


How hard is deciding the existence of a polygonization with prescribed perimeter?

Your problem is NP-hard, since it contains the Hamiltonian cycle problem on grid graphs as special case: Given a set of lattice points in the plane, is there a cycle in which all edges have lengths $1$ (and hence connect two horizontally or vertically adjacent lattice points.
The grid graph has a Hamiltonian cycle, if and only if the corresponding $n$ lattice points (interpreted as geometric points) have a polygonization with perimeter $n$.

Alon Itai, Christos H. Papadimitriou, Jayme Luiz Szwarcfiter:
Hamilton Paths in Grid Graphs.
SIAM Journal on Computing 11, pp 676-686 (1982)


Limited number of variable occurrences in 1-in-3 SAT

Up to my knowledge the current "limits" have been settled in:

Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, Andreas Wotzlaw:
XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics 167: 1-14 (2014)

See also Schmidt's Thesis: Computational Complexity of SAT, XSAT and NAE-SAT for linear and mixed Horn CNF formulas

Theorem 29. XSAT remains NP-complete for $k$-$CNF^l_+$ and $k$-$CNF^l$, $k, l \geq 3$.

(XSAT for $3$-$CNF^3$ is exactly 1-in-3-SAT where each variable appears exactly $l=3$ times)

Note that the theorem also proves the NP-completeness of the stronger monotone case ($CNF_+$)


The class of regular languages that can be described by regular expressions without union (and without complementation) are known as union-free regular (also: star-dot regular) languages. This class of languages apparently has received some attention recently:

Benedek Nagy: "Union-free regular languages and 1-cycle-free-path-automata", Publicationes Mathematicae 68(1-2), 2006.

Sergey Afonin and Denis Golomazov: "Minimal Union-Free Decompositions of Regular Languages", Language and Automata Theory and Applications, Springer 2009.

Galina Jirásková and Tomás Masopust: "Complexity in Union-Free Regular Languages", Developments in Language Theory, Springer 2010.


For every finite, non-unary alphabet, the language of all palindromes is not in DCFL, but in the intersection of coCFL and CFL.


In what sense are Scala's Try[T] and Future[T] dual?

The short answer is: they are not dual.

The Try[T] type is basically the sum type $T + E$, where $E$ is the type of exceptions.

A typical way of rendering a future Future[T] is via temporal logic. Here, a future can be understood as a "weak eventually" operator, $\Diamond T$, saying that at some point in the future you may receive a $T$. This can be decomposed as the coinductive type $\nu \alpha.\;T + \bullet\alpha$, where $\bullet$ is the "next-step" modality.


Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST

If the weight of the MST is $W$, then the weight of all edges is $\le \binom n 2 \cdot W$, because every edge in the graph is bounded by the unique path in the MST connecting the two nodes of the edge by the triangle inequality.

This is tight: Consider a line with edge weights all being equal to $1$ and let the metric be the shortest path metric induced by this line. Then the MST is this line and has weight $n-1$, on the other hand there are $\Omega(n^2)$ pairs of nodes with a distance of $\Omega(n)$.


Where do sublinear time algorithms fit in the picture of complexity theory?

Sublinear time algorithms (as well as sublinear space algorithms) are indeed an active area of research. The field of property testing covers much of the sublinear time regime, and I'll point you to the property testing blog to learn about recent work in the area.

The question about complexity theory relating to this is very interesting, and is also an active area of research. P vs NP might not exactly be the right analogy here, but you're right that the boundary between computation and verification is something where sublinearity changes things.

In particular, you can look at a PCP as "kind of" doing something sublinear, in that it only inspects a few bits of a long proof in order to check the prover's claim. More generally, there's been recent work prover-verifier systems where the verifier runs in sublinear time. Some references that are worth perusing:

Interactive proofs of proximity: delegating computation in sublinear time
Non-Interactive Proofs of Proximity


PPAD is pretty "low" above P and not much would change in our understanding of complexity if it was shown equal to P (except that the few problems in PPAD would now be in P).  The main "evidence" that PPAD!=P is an oracle separation, which is essentially equivalent to the  combinatorial fact that no "black-box simulation" exists.


Special properties of bipartite expanders

Two things come to mind when I hear "bipartite expanders"

The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all graphs - that every graph has a Ramanujan $\mathbb{Z}_2$ signing. [http://arxiv.org/abs/1304.4132]
The work by Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson about how entropy can help understand the construction of optimal lossless expanders and zig-zag product seems to be essentially focussed on bipartite expanders. [ http://dash.harvard.edu/bitstream/handle/1/3330492/Vadhan_CondLosslessExpanders.pdf?sequence=2 ][ http://arxiv.org/abs/math/0406038  ]

Seems all optimality results about expanders are about when they are bipartite? May be this is because somehow our technologies are more tuned to control the upper edge of graph spectrum and only with bipartiteness does it imply something for the whole. (MSS result can in principle be generalized for a larger class of expanders but this larger class is not as conveniently describable)


De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers replace the complex numbers used by Fürer. Both algorithms give the best bit-complexity for integer multiplication.


Let $S_0=\{1\}$. For $i = 1,...,n$, set $S_i\gets \{xy\mod b : x\in S_{i-1},y\in L_i\}$. Then just check whether $a \in S_n$.

It's obviously correct, since $S_i$ contains the residues which can be expressed as a product of elements, one each from $L_1,\ldots,L_i$.

Just using the definition of $S_i$ to compute it, you get a running time of $O(m n b)$, which is significantly better than brute force when $b$ is smaller than $n^m$.

By replacing the linear sweep by divide and conquer, you might be able to improve the running time even more, though I didn't check. (It will still have a factor of $b$ though.)


On the properties of a family of submatrices

As @Steven Stadnicki points out in his comment, acording to your question, the contents of the matrices are not important here, but the number $k$ and $n$. Therefore, you can look at $\mathcal{F}$ as a family of intersecting $k$-subsets of $\{1,\dots,n\}$.

You can derive properties from something called a Sunflower.

Definition: A sunflower with $m$ petals and a core $Y$ is a collection of sets $S_1,\dots,S_m$ such that $S_i\cap S_j=Y$ for all $i\neq j$. Moreover, the sets $S_i\setminus Y\neq \emptyset$.

Sunflower Lemma: Let $\mathcal{F}$ be a family of sets each of cardinality $k$. If $|\mathcal{F}|>k!(k-1)^k$ then $\mathcal{F}$ contains a sunflower with $k$ petals.

You can make relaxations to the sunflower, like the petals not being intersected by a set of size smaller than $c$. In this case we have the following lemma.

Lemma: Let $\mathcal{F}$ be a family of sets each of cardinality $k$. If $|\mathcal{F}| > (c-1)^k$ then $\mathcal{F}$ contains a flower with $k$ petals.

There are more properties that you can look for in the book:

Extremal Combinatorics with Applications to Computer Science by Stasys Jukna.

The definitions and lemmas above are from chapter 7. Take a look at the excercises, and maybe also chapter 8 on Intersecting Families.


How high are the higher types that appear in practice?

Okasaki's Functional Pearl, "Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use a Sixth-Order Function?" answers this question with a type of order 6.


Difference lists in functional programming

Yes, the bounds depend on the assumption that function composition takes constant time.
Basically, if you have a join list:

datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join

It's obvious that concatenation is constant time, and that it's $O(n)$ to turn this into a cons-list. If you think about the usual representation of closures, you can see that this is basically the same pointer representation as the usual representation of datatypes. (Alternatively, you can view this type as a defunctionalized difference-list.)


What are the consequences of Parity-L = P?

parity-$L$ is in $NC^2$ and parity-$L=P$ would mean that $P$ can be simulated in parallel $\log^2$ time or in $\log^2$ space (since $NC^2$ is in $DSPACE(log^2 n)$)


Decidability of type inference and type checking in MLTT

Certainly the decision problem

  Given a (pre-)term $a$ Is there a type $A$ such that $\vdash a :A$ is derivable in MLTT?

Sometimes written $\vdash a\ :\ ?$ (and called the type inference problem) is decidable, which is to say it doesn't matter whether $a$ is well-typed or not to get an answer. Indeed, all proof checkers based on MLTT implement some version of this decision algorithm!

Obviously, the problem in a non-empty context ($\Gamma\vdash a\ :\ ?$) is decidable as well, usually you need to solve the latter to solve the former.

This should answer questions 1 and 2. The algorithm does not involve normalizing $a$, which in general would be bad news, since it is undecidable whether an untyped term normalizes to anything. However the type checking algorithm does involve normalizing types, which are by construction well-typed themselves.

As a result, normalization of well-typed terms is a necessary condition for the type inference problem to be decidable.

You might want to check Nordström, Petersson and Smith for an introduction.

I'm not aware of any generic description of a type inference algorithm for normalizing type theories, though Pollack gives a pretty good overview (though the state of the art has improved) in Typechecking in Pure Type Systems.


Is the knapsack variant with small profit and unlimited repetition of items NP-hard?

The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm.
Theorem 1. For unbounded Knapsack with integer profits $(p_1,\ldots,p_n)$, there is an algorithm running in time polynomial in $n$ and $\max_i p_i$.
Proof. We first observe that the problem reduces in polynomial time to  the "flipped" variant, where the profits are given a threshold, rather than the weights:
input: weights $w=(w_1,\ldots,w_n)$, positive integer profits $p=(p_1,\ldots, p_n)$, and desired profit $P$
output: the minimum sufficient weight $W^* = \min\big\{ w\cdot x : p\cdot x \ge P,\, x\in\mathbb N_0^n\big\}$.
Throughout "$\cdot$" denotes the dot product, $a\cdot b = \sum_{i=1}^n a_i b_i$.
Lemma 1. Knapsack with integer profits reduces in time polynomial in $n$ and $\log(\max_i p_i)$ to the "flipped" problem defined above.
The proof of Lemma 1 is straightforward.  I've appended it at the end.
Next we observe that the flipped problem has an algorithm whose run-time is polynomial in $n$ and the profit threshold $P$.
Lemma 2. There is an algorithm for the flipped problem that runs in time polynomial in $n$ and $P$.
The proof of Lemma 2 is a standard exercise in dynamic programming.  I've appended it at the end.
The theorem doesn't follow directly, because the desired profit $P$ is not, in general, polynomial in the maximum item profit $\max_i p_i$.
Next we develop an algorithm that runs in time polynomial in $n$ and $\max_i p_i$.
Fix any instance $(p, w, P)$ of the flipped variant.
Let $i^*=\arg\max_i p_i/w_i$ be the item with highest profit-to-weight ratio.
The key observation is the following:
Lemma 3. There is an optimal solution $x$ with $x_i < p_{i^*}$ for all $i\ne i^*$.
Proof. Consider any optimal solution $x$.  Suppose $x_i \ge p_{i^*}$ for some $i\ne i^*$.  Then replace $p_{i^*}$ copies of item $i$ with $p_i$ copies of item $i^*$.  This preserves the total profit, and cannot increase the weight.  Repeat as necessary with other items to obtain the claimed solution. $~~\Box$
In the optimal solution $x$ from Lemma 3, the total profit from items
other than $i^*$ is at most $\sum_{i\ne i^*} p_{i^*} p_i \le n(\max_i p_i)^2$.  That is, the total profit from items other than $i^*$ is polynomial in $n$ and $\max_i p_i$.  Intuitively, this means that we can greedily commit to taking most of the profit from $i^*$, and once we do, for the remaining problem (allocating the rest of the profit), the desired profit will be polynomial in $n$ and $\max_i p_i$. So we can solve that remaining problem using the algorithm from Lemma 2.  Here are the details.
Let optW$(p, w, P)$ denote the minimum weight needed to make profit $P$.
Lemma 4. Let $\delta = \max(0,\lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil)$ and $P'= P - \delta p_{i^*}$.  Then
$$\text{optW}(p, w, P) = \delta w_{i^*} + \text{optW}(p, w, P').$$
Proof. The optimal solution $x$ from Lemma 3 has $x_i < p_i$ for $i\ne i^*$. Since $\sum_i x_i p_i \ge P$, it follows that
$x_{i^*}p_{i^*} \ge P - \sum_{i\ne i^*} p_i p_{i^*}$,
i.e.,
$x_{i^*} \ge \lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil = \delta$.
So this optimal $x$ must consist of an optimal solution to $(p, w, P')$, plus $\delta$ units added to $x_{i^*}$. $~~~\Box$
(A technical remark to avoid confusion: the solution to $(p, w, P')$ in the proof above can still use item $i^*$.  However many copies of $i^*$ it takes, the optimal $x$ will take $\delta$ more.)
Lemma 4 gives the desired algorithm:

calculate $\delta$, and $P'$ as defined in Lemma 4:
$\delta = \max(0,\lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil)$ where     $i^* = \arg\max_i p_i/w_i$
$P'= P - \delta p_{i^*}$

return optW$(p, w, P') + \delta w_{i^*}$,
where optW$(p, w, P')$ is computed using the algorithm from Lemma 2

Correctness of the algorithm follows from Lemma 4. By inspection and Lemma 2 the run time is polynomial in $n$ and $P'$, with
$$\textstyle P' = P-\delta p_{i^*} \le P - (P - \sum_{i\ne i^*} p_i p_{i^*})
= \sum_{i\ne i^*} p_i p_{i^*} \le n(\max_i p_i)^2.$$
So the time is polynomial in $n$ and $\max_i p_i$. $~~~\Box$
Proof of Lemma 1 (reduction to flipped problem). Fix an instance $(p, w, W)$ of Knapsack with integer profits. The optimal solution has profit $P^*$ at most $\lambda^* = p_{i^*} W/w_{i^*}$, because no item has a profit per weight ratio larger than $p_{i^*}/w_{i^*}$.  On the other hand, using just item $i^*$, as many items as possible, yields a solution of profit $\lfloor W/w_{i^*}\rfloor p_{i^*} > \lambda^* - p_{i^*}$. So $\lambda^* - p_{i^*} \le P^* \le \lambda^*.$  Use binary search for $P$ in the range $\lambda^* - p_{i^*}$ to $\lambda^*$ (solving the flipped problem $(p, w, P)$ in each iteration) to find the maximum profit $P^*$ such that the minimum required weight to achieve profit $P^*$ is at most $W$.  This $P^*$ will be the maximum profit achievable with weight-budget of $W$.  The time for this reduction is polynomial in $n$ and $\log(\max_i p_i)$. $~~\Box$
Proof of Lemma 2 (standard dynamic-programming-algorithm for the flipped problem). Fix an input $(p, w, P)$.  For $i\in\{0,1,\ldots,n\}$ and $Q\in \{0,1,\ldots, P\}$, define $W(i, Q)$ to be the minimum sufficient weight for the subproblem formed by the first $i$ items and desired profit $Q$.
Then
$$W(i, Q) = \begin{cases}
0 & \text{if } Q = 0 \\
\infty & \text{if } Q>0, i=0 \\
\min\big\{ x_i w_i + W(i-1, Q-x_i p_i) : x_i\in\mathbb N_0,\, x_i p_i \le Q\big\} & \text{otherwise.}
\end{cases}$$
There are $O(n P)$ subproblems, and for each the right-hand side of the recurrence can be evaluated in time $O(P)$, so the dynamic-programming algorithm takes time $O(n P^2)$. $~~~\Box$
EDIT: Looking briefly over the literature, the same idea (but for weights instead of profits) has been used for unbounded Knapsack with small weights.  See e.g. Section 8.2.1 of https://doi.org/10.1007/978-3-540-24777-7_8 or Section 10.4 of  https://doi.org/10.1007/978-3-540-76796-1_10. I don't know whether it has also been used before for profits.


Is finding whether k different perfect matchings exist in a bipartite graph co-NP?

Yes, cause the problem lies in P. Look at paper Fukuda, Matsui ''Finding All The Perfect Matchings in Bipartite Graphs''


Algorithm for extensional equality in combinator calculus

Equality of terms in the combinator calculus is undecidable. We can encode the natural numbers as Church numerals and then show that every recursive function is represented, see for instance section 1.3.1 of Jaap van Oosten's book. I don't have any other books with me right now, but am sure almost any book on this topic will have the result, Barendregt's book surely does.

For your purposes it might be useful enough to apply a simple heuristic that will cover sufficiently many cases. You could do exactly what you suggest: see if two terms applied to a variable reduce to the same term (but you need to give up after a while).


Reference for Turing to many-one reductions

I'm pretty sure you can find this in the book Bounded Queries in Recursion Theory by Martin and Gasarch, but I don't have access to a copy now to check.

(Your statement gives an upper bound of $2^f$; most of that book is about lower bounding such quantities, so the upper bound must be in there somewhere, probably very near the beginning.)

PS - I agree with M. Blaser's comment: you're basically talking about truth-table reductions without using that terminology.


Cite a conference contribution as conference paper of book chapter

Converting/extending a comment to an answer:

I keep a list of talks/posters on my website. I do this to include links to slides, photos and video recordings. When I was applying for grad school I had them in my CV, too. I have the impression that it might have helped. However, once you have a lot of talks it becomes too much info. On some senior researchers' CVs I've seen very compact talk lists: they include their invited or conference talks as acronyms/university names and lists of years. For example, if they regularly present at STOC they might write "STOC 2003,2004,2007". I think this is mostly to show that they are involved with the community and go places regularly.
As Dave mentioned, it is usually standard to cite the paper as a conference. I think the exception is when conferences publish their proceedings, or selected papers, as a special issue of a journal. The only time this happened to me, I had to go through an extra layer of review (first conference, then the journal) for one paper, so I think is appropriate to cite those as journal papers.
A lot of time papers are first published in conferences, and then a year (or more!) later a longer version appears in a journal. The convention is to cite this as a journal paper with a note after: "preliminary version appeared in Conference X 2008".


Can we distinguish strictly syntactic and semantic methods in programming language?

No, you cannot strictly distinguish syntactic from semantic methods, but the distinction still ends up making sense.

Structural operational semantics is not denotational, because it is not a compositional method of giving semantics to a programming language.

However, you can build denotational models out of a structural operational semantics by using a realizability or logical relations method. As an example, see Robert Harper's Constructing Type Systems over Operational Semantics.

Term models are denotational, but generally semanticists are not satisfied with them. What they usually want is a category of models in which the term model is initial, which can be used to prove soundness and completeness results.  (The soundness and completeness of the typed lambda calculus for cartesian closed categories is the paradigmatic example; see Alex Simpson's Categorical Completeness Results for the Simply-Typed $\lambda$-calculus for some details.)

In the other direction, if you have a denotational semantics, you might want to figure out what the syntax for it is. Then you want to go and find a syntax and abstract machine whose term model can serve as an intitial object in a suitable category of models.
For instance, game semantics began its life as a purely semantic construction, and eventually led to work on operational game semantics --- a recent example of which is Alexis Goyet's The lambda lambda-bar calculus: A dual calculus for unconstrained strategies.

Overall, you can think of structural operational semantics as a way of specifying abstract machines, which we hope are easy to implement. A denotational semantics gives a compositional model of a language, which we hope is easy to reason about. If we have both, then we can both implement and reason about the language.

Normalization theorems are an interesting ambiguous case. Usually, to prove normalization, you need a semantic model (typically a logical relation). However, once you know that normalization holds, many properties can now be proved by induction on normal forms, which is a purely syntactic argument.
For weak logics (anything up to first-order logic without induction, roughly), you can prove normalization syntactically, using the technique of hereditary substitution. In these logics, the subformula property holds, and so you can prove normalization by induction on types. See Frank Pfenning's paper Structural Cut Elimination for an explanation of how this works.


Contradiction between Gödel's Second Incompleteness Theorem and the Church-Rosser's property of CIC?

First, you are confusing consistency of CIC as an equational theory with consistency of CIC as a logical theory. The first means that not all terms of CIC (of the same type) are $\beta\eta$-equivalent. The second means that the type $\bot$ is not inhabited. CR implies the first kind of consistency, not the second.  This, as has been pointed out in the comments, is implied instead by (weak) normalization. The prototypical example of this situation is the pure $\lambda$-calculus: it is equationally consistent (CR holds) but, if you consider it as a logical system (as Alonzo Church orginally intended) it is inconsistent (indeed, it does not normalize).

Second, as Emil pointed out, even if CIC has a given property (CR or normalization) it is perfectly possible that CIC cannot itself prove that property. In this case, I do not see any inconsistency in the fact that CIC is able to prove its own CR property, and I guess that this is indeed the case (elementary combinatorial arguments usually suffice for CR, and such arguments definitely fall within the huge logical power of CIC).  However, CIC certainly does not prove its own normalization property, precisely because of the second incompleteness theorem.


Benjamin Werner has proved the mutual interpretability of ZFC with countably many inaccessibles and the Calculus of Inductive Constructions, in his paper Sets in Types, Types in Sets.

This means, roughly, that any function which can be shown to be total in ZFC with countably many inaccessibles can be defined in Coq. So unless you are a set theorist working on large cardinals, it is unlikely that any computable function you have ever wanted cannot be defined in Coq.


This has been called "Discounted Reward." In my brutish opinion, steer toward the CS guys and away from the OR guys. I just like the lit better.

See: "Approximation Algorithms for Orienteering and Discounted-Reward TSP." FOCS 2003 Which I just stole from my colleague's desk.

They model reward as $\lambda^{-t}$, where $t$ is time, and $\lambda$ is constant, but otherwise it is the standard orienteering formulation: Maximize reward, subject to a budget, or minimize budget subject to a reward constraint.


Can we get a sorted list from a sorted matrix in $O(n^2)$

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order.

It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you just need to make them sufficiently large. In particular, sorting the matrix implies sorting each one of these diagonals. The $i$th diagonal has $i$ entries, and as such $i!$ possible ordering. As such, a sorted matrix could define at least $X = \prod_{i=1}^n i!$  different orderings. It is now easy to verify that $\log_2 X = \Omega(n^2 \log n)$,  implying that in the comparison model (and as Jeff points out below, in any binary decision tree model) at least this is a lower bound on the sorting time.


Check if graph stays connected after edge swap

Check this paper https://arxiv.org/pdf/1209.5608.pdf which uses cluster forest which support operations like:

connected(u, v) : if vertex u and v are connected ,
insert(u, v) : Insert edge (u, v)
delete(u, v) : delete edge (u, v)

It answers your query in O(log n / log log n) time with O(log2n / log log n) update time.


Example demonstrating the power of non-deterministic circuits

If this problem has no progress, I have an answer.

--

I also have considered this problem since my COCOON'15 paper (before your question).

Now, I have a proof strategy, and it immediately gives the following theorem:
There is a Boolean function $f$ such that the nondeterministic $U_2$-circuit complexity of $f$
is at most $2n + o(n)$ and the deterministic $U_2$-circuit complexity of $f$ is $3n - o(n)$.

I apologize that I haven't written the paper.
The proof sketch below might be enough to explain my proof strategy.
I aim to write the paper with more results by the STACS deadline (Oct. 1).

[Proof Sketch]

Let $f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$.

The deterministic lower bound proof is based on a standard gate elimination method with a little modification.

The nondeterministic upper bound proof is a construction of such nondeterministic circuit.

Construct a circuit computing $Parity_{\sqrt{n}}$. (The number of gates is $o(n)$.)
Construct a circuit selecting $\sqrt{n}$ inputs nondeterministically. (The number of gates is $2n + o(n)$.)
Combine the two circuits.


Implications of a problem being in XP when parameterized by diameter

I think Figure 1 (page 4) of the paper "New Races in Parameterized Algorithmics" of Komusiewicz and Niedermeier is what you are looking for.

In particular, being in XP for the parameter diameter implies being in XP for parameters: min dominating set, max independent set, minimum clique cover, distance to cograph, distance to co-cluster, distance to clique, distance to cluster, vertex cover, and cluster editing.