What is the simplest computational model for which the emptiness problem is undecidable?

Probably you already got these in your bag :-)

Two way one counter machine over unary alphabet (Minsky61).
Two way weak counter machines (the counter has no effect on the computation but the machine halts if counter reaches zero) [1].
Quantum one counter automata [2].

With binary alphabets, the emptiness remains undecidable for:

One way machines with one unbounded counter and one pushdown store that makes at most one reversal [3].
Two-way machines deterministic finite automata with multiple reversal bounded counters (even over a bounded language) [3].
Stateless (the transitions depend only on the scanned symbol) 2-head 2-way deterministic finite automata even when each head makes only one reversal on the input tape [4].

Edit: on the boundary:

(Open problem) Is the emptiness problem decidable for two-way nondeterministic finite automata with one reversal bounded counter over non-bounded languages? (over bounded languages it is decidable [5])

[1] Tat-hung Chan. On Two-Way Weak Counter Machines. Mathematical Systems Theory 01/1987;
[2] Richard F. Bonner, Rusins Freivalds, and Maksim Kravtsev. 2001. Quantum versus Probabilistic One-Way Finite Automata with Counter. In Proceedings of the 28th Conference on Current Trends in Theory and Practice of Informatics Piestany: Theory and Practice of Informatics (SOFSEM '01), Leszek Pacholski and Peter Ruzicka (Eds.). Springer-Verlag, London, UK, UK, 181-190.
[3] Oscar H. Ibarra. 1978. Reversal-Bounded Multicounter Machines and Their Decision Problems. J. ACM 25, 1 (January 1978), 116-133.
[4] Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin, On stateless multihead automata: Hierarchies and the emptiness problem, Theoretical Computer Science, Volume 411, Issue 3, 6 January 2010, Pages 581-593, ISSN 0304-3975.
[5] Zhe Dang, Oscar H. Ibarra, Zhi-wei Sun. On the emptiness problems for two-way nfa with one reversal-bounded counter. In Proc. Thirteenth Int. Symp. on Algorithms and Computation (2002)


Finite automata that accept binary strings divisible by n

There is a known formula for minimum number of states for such a finite automaton. This depends on $n$ as well as the radix $R$ of the underlying positional representation.

If $n$ is coprime to $R$, then the minimal number of states is $n$. However, when $n$ shares a factor with the radix then the situation is rather complicated. See Mathematica Journal Vol 3 Issue 11. "Divisibility and State Complexity" by Klaus Sutner.


What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in

  H. Buhrman, L. Fortnow, T. Thierauf. Nonrelativizing separations. CCC '98. (freely available author's version)


Noether’s Normalization Lemma for finite fields

I believe the answer is yes. The only part I haven't checked carefully is:

The argument in the middle of Theorem 4.2 using the complex topology, and the fact that the Zariski closure = complex closure for Zariski-constructible sets over $\mathbb{C}$. This part of the argument should be replaceable by the standard algebraic technique of using Laurent series, though as I said, I haven't checked this carefully.

In Theorems 4.1 and 4.2, it seems the only other place characteristic zero is really used is the $\mathsf{EXPH}$ part of Theorem 4.1 (assuming GRH). This uses Koiran's result that, assuming GRH, Hilbert's Nullstellensatz is in $\mathsf{PH}$. Koiran's result relies pretty heavily on characteristic zero (since it considers the solutions of the system of equations modulo many different primes $p$). This is not needed to get the $\mathsf{EXPSPACE}$ part of Theorem 4.1, however, only the $\mathsf{EXPH}$ part (assuming GRH).


Ashish Sabharwal lists some software (e.g., SampleCount, ApproxCount, and more) for this on his web page.  I haven't tried any of these.


efficient diff algorithm for trees and Levenshtein distance

The following paper describes a slightly more efficient algorithm than Zhang-Shasha for computing tree edit distance, along with a proof that their algorithm is optimal (within a certain broad class of algorithms):

Erik Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann.  An Optimal Decomposition Algorithm for Tree Edit Distance.  ACM Transactions on Algorithms, 6(1), 2009.


Defining Mutually Recursive functions in Coq

As stated in Coq Reference Manual (2.3)

  in Fixpoint, the decreasing argument must be given (unless the
  function is not recursive), but it must not necessary be structurally
  decreasing.

Key word is structurally, Coq can't guess, which arguments is decreasing at each step of the recursion.

The reason for this is nicely described in Software Foundations

  Since Coq is not just a functional programming language, but also a
  consistent logic, any potentially non-terminating function needs to be
  rejected. Here is an (invalid!) Coq program showing what would go
  wrong if Coq allowed non-terminating recursive functions:

 Fixpoint loop_false (n : nat) : False := loop_false n.

  That is, propositions like False would become provable (e.g. loop_false 0 would
  be a proof of False), which would be a disaster for Coq's logical
  consistency.


Is there current research into the implemention of Randomness Extractors?

Much of extractor literature is about minimizing the seed length, which is important for derandomization application. However, it may not be crucial for yours. Also, often the literature focuses on relatively large error (e.g., 1/100), which is fine for derandomization but may be problematic in other settings, that require an exponentially small error.

In your setting, it may be OK to generate once and for all a long random seed (say by tossing coins), and then use it to extract. In this case you could use pairwise independent hash functions that have rather efficient implementations. I wrote a paper with Shaltiel and Tromer on this issue. You may also be able to use almost independent hash functions, that can be more efficient and have smaller seed. (Don't know offhand a good reference for their efficient implementation, though there have been several works on this.)

If you have multiple sources that are independent, then you can do better things. The classical Hadamard extractor works if the entropy rate is larger than 50% (this should be mentioned in the surveys above). If the entropy is smaller than 50% then we had one simple construction with Impagliazzo and Wigderson . The dependence between of number of sources and error achieved on the entropy rate is not ideal, though to really understand it you'll need to look at the exact bounds given by today's state of the art sum product theorems. (And if you're willing to assume certain number theoretic conjectures you can get even more efficient extractors.) This construction has been greatly improved in various ways, some of which could be relevant to your application. A great source for these is Anup Rao's Thesis.


Classes containing boolean closure of CFLs

This is not an answer to your question per se, but might explain why finding sensible classes of languages more or less fitting your requirements will be hard: recall that the emptiness of intersection of two context-free languages is undecidable, thus the full boolean closure of CFLs is not a very interesting class... (In fact, any R.E. language $L$ can be expressed as $h(L_1\cap L_2)$ for $L_1$ and $L_2$ deterministic context-free and $h$ an homomorphism.)

More in the scope of your question, you can look at Alexander Okhotin's work on conjunctive and boolean grammars, but I don't recall any pumping results.


Here are a few:

Max Cut: Can one color the vertices of an input graph $G$ black and white so that at least $k$ edges go from black to white?
Max Sat: Is there an assignment that satisfies at least $k$
clauses?
Max Leaf: Does $G$ have a spanning tree with at least $k$
leaves?
Longest Path / Cycle: Does $G$ contain a simple path / cycle on at least $k$
vertices?
3-Set Packing: Given a set family ${\cal F}$ of sets of
size $3$, are there $k$ pairwise disjoint sets in ${\cal F}$?


Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem?

Note that Gödel's Incompleteness Theorems are the following statements:

Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither provable nor disprovable) or inconsistent.
Any formal system which can be used to prove a statement equivalent to  its own consistency, is in fact inconsistent.

But assuming, for instance, that ZF set theory (or an essentially equivalent  foundation for mathematical subjects such as computer science) is consistent, we don't need Gödel's Theorems anymore to tell us that there are statements which are neither provable nor disprovable from our foundations: interesting specific examples, such as the Axiom of Choice have already been demonstrated. So even without Gödel's Theorem, it is certainly concievable that a statement such as "P = NP" is indepdendent of set theory.

For this question, Scott Aaronson has written a very accessible article on the subject, which also goes over the basics of formal logic, what it could mean to have a model of set theory which included an axiom which is equivalent to asserting its own inconsistency, and the subject of logical independence results in general.


Communication complexity of approximating the size of set intersection

I will give two upper bounds. Let $A$ and $B$ be the sets given to Alice and Bob, respectively, and put $a=|A|$, $b=|B|$, $c=|A\cap B|$.

First, there is a randomized protocol that, given $d>0$ and $\epsilon>0$, computes with probability $\ge1-\epsilon$ an approximation of $c$ up to additive error $d$, using $O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log n\log\epsilon^{-1}\Bigr)$ bits of communication, and $O\Bigl(\left(\frac{\min\{a,b\}}d\right)^2\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$ bits of randomness.

The protocol goes as follows:

If $d\ge\min\{a,b\}$, the party who sees it terminates the protocol and outputs $0$ as the estimate. Otherwise, Alice and Bob communicate $a$ and $b$ to each other, and determine which is smaller. I will assume below w.l.o.g. that $a\le b$.
Alice draws $t=\log(2\epsilon^{-1})a^2/(2d^2)$ independent uniformly random samples $a_i\in A$, $i<t$, and sends them to Bob.
Bob estimates $c$ as $\frac at|\{i<t:a_i\in B\}|$.

The protocol is correct by the Chernoff–Hoeffding bounds: if $X_i$ denotes the indicator random variable of the event $a_i\in B$, then $X_i$, $i<t$, are i.i.d. variables with mean $p=c/a$. Thus,
$$\Pr\left[a\overline X\le c-d\right]=\Pr\left[\overline X\le p-\tfrac da\right]\le\exp\left(-2\left(\tfrac da\right)^2t\right)\le\frac\epsilon2,$$
and similarly for $\Pr\bigl[a\overline X\ge c+d\bigr]$.

Now, these bounds are somewhat wasteful if $c\ll a$: there are also variant Chernoff bounds stating
$$\begin{align}
\Pr\left[\overline X\le p-\delta\right]&\le\exp\left(-\frac{\delta^2}{2p}t\right),\\
\Pr\left[\overline X\ge p+\delta\right]&\le\exp\left(-\frac{\delta^2}{3p}t\right),\qquad\delta\le p,
\end{align}$$
which would allow us to get by with the number of samples $t$ smaller by a factor of roughly $p$. The problem is that $p=c/a$ is the very quantity we want to approximate, hence we do not know it ahead. This can be remedied by making first a ball-park estimate of $c$.

So, the improved protocol computes with probability $\ge1-\epsilon$ an additive $d$-approximation of $c$ using $O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log n\log\epsilon^{-1}\Bigr)$ bits of communication, and $O\Bigl(\frac{\min\{a,b\}}d\left(1+\frac cd\right)\log \min\{a,b\}\log\epsilon^{-1}\Bigr)$ bits of randomness, and it goes as follows (the constants are not optimized):

Same as above.
Alice draws $r=10(\log\epsilon^{-1})a/d$ random samples from $A$, and sends them to Bob.
Bob counts how many of these samples belong to $B$, and sends this number, $s$, to Alice.
If $as/r\le d/2$, the protocol terminates with output $0$.
Alice draws $t=10sa/d$ random samples $a_i\in A$, $i<t$, and sends them to Bob.
Bob estimates $c$ as $\frac at|\{i<t:a_i\in B\}|$.

Without going into the details, the Chernoff bounds quoted above imply that with high probability, the value of $s/r$ is $\Theta(c/a)$, in which case the protocol does not exceed the stated cost, and it computes with high probability a good estimate of $c$ by another application of Chernoff bounds.


What kind of language is needed to recognize an ordered list? [multihead automata, apparently]

It sounds like what you are looking for are multihead automata (in your case, 1-way 2-head deterministic finite automata should suffice). I'm not really an expert on these, but google turns up some interesting surveys on this language hierarchy, such as

Marek Chrobak: Hierarchies of one-way multihead automata, http://www.sciencedirect.com/science/article/pii/0304397586900939

This also gives one answer to your second question: The hierarchy of n-head automata lies "across" the Chomsky hierarchy.


"Guarded" negative occurrences in definition of inductive types, always bad?

The reason for the ban on negative occurrences can be understood by analogy with the Knaster-Tarski theorem. This theorem says that

if $L$ is a complete lattice and $f : L \to L$ is a monotone function on $L$, then the set of fixed points of $f$ is also a complete lattice. In particular, there is a least fixed point $\mu{f}$ and a greatest fixed point $\nu f$.

In traditional model theory, lattices $L$ can be viewed as propositions, and the order relation $p \leq q$ can be understood as entailment (i.e., that $q$'s truth is entailed by $p$'s truth).
When we move from model theory to proof theory, lattices generalize to categories. Types can be seen as the objects of a category $\mathbb{C}$, and a map $e : P \to Q$ represents a proof that $Q$ can be derived from $Q$.
When we try to interpret types defined by recursive equations, e.e., $\mathbb{N} = \mu \alpha.\;1 + \alpha$, the obvious thing to do is to look for a generalization of the Knaster-Tarski theorem. So instead of a monotone function on a lattice, we know want a functor $F : \mathbb{C} \to \mathbb{C}$, which sends objects to objects, but generalizes the monotonicity condition so that every map $e : P \to Q$ gets a map $F(e) : F(P) \to F(Q)$ (with the coherence conditions that $F$ sends identities to identities and preserves compositions so that $F(g \circ f) = F(g) \circ F(f)$).
So if you want an inductive datatype $\mu \alpha.\;F(\alpha)$, you also need to supply a functorial action on terms for the type operator $F$ in order to be assured that the fixed point you want exists. The strict positivity condition in Agda and Coq is a syntactic condition that implies this semantic constraint. Loosely speaking, it says that if you build a type operator from sums and products, then you can always cook up the functorial action, and so any type formed in this way should have a fixed point.
In dependently-typed languages, you also have indexed and parameterized types, so your real task is more complicated. Bob Atkey (who has blogged about this here and here) tells me that a good place to look for the story is:

Structural Induction and Coinduction in a Fibrational Setting,  Claudio Hermida and Bart Jacobs 1997.
Fibrational Induction Rules for Initial Algebras, Neil Ghani, Patricia Johann, and Clement Fumex 2010.

As Andrej notes, fundamentally whether or not a negative occurence is okay or not depends on what your model of type theory. Basically, when you have a recursive definition, you are looking for a fixed point, and there are a lot of fixed-point theorems in mathematics.
One which I, personally, have made a lot of use of is Banach's fixed point theorem, which says that if you have a strictly contractive function on a metric space, then it has a unique fixed point. This idea was introduced into semantics by (IIRC) Maurice Nivat, and was extensively studied by America and Rutten, and was recently connected by Birkedal and his collaborators to a popular operational technique called "step-indexing".

Solving Reflexive Domain Equations in a Category of Complete Metric Spaces, Pierre America and Jan J. M. M. Rutten 1989.
The Category-Theoretic Solution of Recursive Metric-space Equations, Lars Birkedal, Kristian Støvring, and Jacob Thamsborg. 2010.

This gives rise to type theories where negative occurences in recursive types are permitted, but only when the negative occurences occur under a special "guardedness" type constructor. This idea was introduced by Hiroshi Nakano, and the connection to Banach's theorem was made both by myself and Nick Benton, as well as Lars Birkedal and his coauthors.

A Modality for Recursion, Hiroshi Nakano, 2000.
Ultrametric Semantics of Reactive Programs, Nick Benton and Neel Krishnaswami, 2011.
A metric model of guarded recursion, Lars Birkedal, Jan Schwinghammer, and Kristian Støvring, 2010.


Integrality gaps essentially represent the inherent limits of a particular linear or convex relaxation in approximating an integer program.  Generally, if the integrality gap of a particular relaxation is $x$, then any approximation algorithm based on that relaxation cannot hope to do better than an $x$-approximation.  So at the very least, integrality gaps are of interest to algorithm designers since they suggest limitations in certain techniques.

So why not just come up with another LP relaxation or switch to other techniques and move on?  Linear and convex programming have proven to be central to approximation algorithms; for many problems the integrality gap of a natural LP or SDP formulation is equal to the approximation ratio of the best algorithm as well as the hardness of approximation ratio.  This is just an empirical observation, but it means that proving an integrality gap may suggest much stronger consequences of an improved algorithm or lower bound.

There may be deeper and more rigorous reasons for this phenomenon.  For instance, assuming the unique games conjecture, it is known that the approximation ratio and inapproximability ratio for constraint satisfaction problems is equal to the integrality gap of a simple SDP relaxation (see Optimal Algorithms and Inapproximability Results for Every CSP? by Prasad Raghavendra)

Finally, integrality gaps represent unconditional lower bounds.  Usually, we need to rely on unproven assumptions (e.g. $P \neq NP$) if we want to make any progress in lower bounds, but for restricted models of computation, we can sometimes get away without it (see lecture notes by Luca Trevisan).  Integrality gaps, being purely geometric rather than computational, are one way of getting fairly powerful lower bounds without the baggage of extra assumptions.


That problem is strongly NP-hard by reduction from 3-SAT:

Each ai is 0, each bi is 1, each negative literal is represented by its propositional variable,

each positive literal is represented by 1 minus that, each clause is represented by the product

of the representations of its literals, and f is the sum of the representations of the clauses.

I don't have any evidence regarding possible ∃ℝ-completeness or membership in NP.


Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT.
Proof. Call the given problem Positive Discrepancy Cut (PDC).  Define weighted PDC to be the generalization where the input is a graph $G=(V,E)$ with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut.  To prove the theorem we prove two lemmas:
Lemma 1. Weighted PDC reduces in polynomial time to (unweighted) PDC.
Lemma 2. MAX-CUT reduces in polynomial time to Weighted PDC.
Proof of Lemma 1. Given an $n$-vertex instance $G=(V,E)$ of weighted PDC with weights in $[-M, M]$, where $M$ is polynomial in $|G|$, the reduction outputs the graph $G'$ obtained from $G$ as follows.  Replace each vertex $v$ in $G$ by a clique $C_v$ of $|E|+1$ vertices, with all edges white.  For each edge $(u, v)$ of weight $w$ in $G$, add $|w|$ edges between $C_u$ and $C_v$, making them white if $w<0$ and red if $w>0$.  Given any positive-weight cut $(A, B)$ in $G$, the corresponding cut in $G'$ is $(A', B')$ where $A'= \bigcup_{v\in A} C_v$ and $B'=\bigcup_{v\in B} C_v$.  The number of red edges minus white edges crossing $(A', B')$ is the weight of the cut $(A, B)$.  So, if $G$ has a positive-weight cut, then $G'$ has a cut with more red than white edges.  Conversely, suppose $G'$ has a cut with more red than white edges.  The total number of red edges in $G'$ is at most $|E|M$, so each clique $C_v$ must be entirely contained in one side of the cut or the other.  So the cut corresponds to a cut in $G$ that has positive weight.  This proves Lemma 1. $~~\Box$
Proof of Lemma 2.  Given a MAX-CUT instance $(G=(V,E), k)$, the reduction outputs the instance $G'$ of Weighted PDC defined as follows.  Obtain $G'$ from $G$ by giving every edge in $G$ weight 1, then adding two vertex $a$ and $b$, each with edges to all other vertices.  Give each edge from $a$ or $b$ to a vertex in $G$ weight $-M$ where $M=|E|+1$.  Give the edge $(a, b)$ weight $M|V|-k+1$.  This completes the reduction.
Suppose there is a cut $(A, B)$ in $G$ with at least $k$ edges.  Then the cut $(A', B')$ in $G'$ where $A'=A \cup \{a\}$ and $B'=B\cup\{b\}$ has weight at least $k-|V|M + M|V|-k+1 = 1$.  Conversely, suppose there is a positive-weight cut $(A', B')$ in $G'$.  Vertices $a$ and $b$ cannot be on the same side of the cut, because if they are, the edge $(a, b)$ is not cut, while at least one edge out of $a$ or $b$ is cut, contributing $-M=-|E|-1$ to the cut weight, and each of the remaining edges (in $E$) contributes at most 1.  So $a$ and $b$ are on different sides of the cut $(A', B')$.  WLOG assume $a\in A'$ and $b\in B'$.  Then (accounting for the edges out of $a$ and $b$) the cut $(A, B)$ in $G$ where $A=A'\setminus \{a\}$ and $B=B'\setminus \{b\}$ must have at least $k$ edges.  So the reduction is correct. $~~\Box$
This reduction is similar to one by Peter Shor in this answer to a question about approximating MAX-CUT with negative edge weights.


Constraint Satisfaction Problem: Choosing real numbers with certain characteristics

This problem is clearly NP-Complete, so finding an efficient solution is almost surely out of the question.  Since you've put no real constraints on $f_i$, the best general solution is probably a brute force search.  If you knew something more about the $f_i$ then maybe you could exploit that to cull the search space or even come up with an efficient algorithm, but in general, even for simple functions this problem is difficult.

For example, choose just one function, $f( { r_0, r_1, \dots , r_{k-1} } ) = \sum_{i=0}^{k-1} r_i $, with the constraint $ -\epsilon < f( { r_0, r_1, \dots, r_{k-1} } ) < \epsilon$, then this is essentially the number partition problem.


$\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$

Your proof must be wrong. All your techniques (including VV) relativize and Beigel has an oracle where $P^{NP}$ is not contained in $PP$. I'm guessing you aren't using VV properly.

Also UPH=PH because you can make an existential unique by requiring the lexicographical least witness (using an extra universal quantifier to eliminate the others).


Dynamic programming  and shortest path problem

One standard view of dynamic programming is the following. Start with a recursive algorithm and then memoize it. By memoization we mean that solutions for intermediate problem instances/sub-problems are stored and not recomputed. If one can argue that the number of sub problems generated in the recursive algorithm for an instance of size $n$ is polynomial in $n$ then memoization leads to a polynomial time algorithm. A recursive algorithm for a problem instance $I$ generates, naturally, an associated DAG $G(I)$ whose nodes are the sub-problem instances and the arcs are the dependencies generated by the recursive algorithm on $I$. It is possible to interpret several different computational problems as solving some kind of shortest path problem on this DAG $G(I)$ (not all though). In these cases it is possible to take out the scaffolding of the recursive algorithm and memoization and directly use a shortest path algorithm in an associated graph. This should not lead one to conclude that all of dynamic programming can be reduced to shortest path computation.


Can all linear lambda calculi be linearity checked syntactically?

I don't want to make a statement about "all linear lambda calculi" since it's hard to make that precise, but for pure linear lambda-calculus the answer is yes.  One way to enforce linearity in pure lambda calculus is by trying to type application and abstraction using the linear implication $A \multimap B$,
$$
\frac{\Gamma \vdash t:A\multimap B\quad \Delta\vdash u:A}{\Gamma,\Delta\vdash t(u):B}
 \qquad
\frac{x:A,\Gamma \vdash t:B}{\Gamma\vdash \lambda x.t:A\multimap B}
$$
together with the linear identity and exchange rules:
$$
\frac{}{x:A\vdash x:A}
 \qquad
\frac{\Gamma,y:B,x:A,\Delta \vdash t:C}{\Gamma,x:A,y:B,\Delta \vdash t:C}
$$

But if you just want to check that a lambda term is linear, types are overkill, and it suffices to check syntactically that every free or $\lambda$-bound variable is used exactly once.

A way to make that a bit more precise is to define the set of linear lambda terms $\Lambda_1(\gamma)$ with a given list $\gamma = x_i,\dots,x_1$ of distinct free variables.  This is really a family of sets (indexed by $\gamma$) generated by the following rules (which can be seen as an abstraction of the typing rules above):
$$
\frac{}{x \in \Lambda_1(x)}
 \qquad
\frac{t \in \Lambda_1(\gamma,y,x,\delta)}{t \in \Lambda_1(\gamma,x,y,\delta)}
 \qquad
\frac{t\in \Lambda_1(\gamma)\quad u \in \Lambda_1(\delta)}{t(u) \in \Lambda_1(\gamma,\delta)}
 \qquad
\frac{t \in \Lambda_1(x,\gamma)}{\lambda x.t \in \Lambda_1(\gamma)}
$$
Then a term $t$ of pure lambda calculus with free variables $\gamma$ is linear just in case $t \in \Lambda_1(\gamma)$.  Note that these rules (like the typing rules) also have the effect of performing scope checking, and thus ruling out certain syntactic expressions which might look linear but violate scoping (e.g., an expression like "$\lambda x.x(y)(\lambda y.\lambda z.z)$", where the variable $y$ is used before it is bound).

Finally, pure linear lambda calculus has the remarkable property that every term is typable (which is related to the fact that it is strongly normalizing).  So, once we know that a lambda term is linear it is always possible to go back and give it a type.  Even more remarkably, the principal type of a term uniquely identifies its $\beta$-normal form, so type inference is in fact equivalent to normalization.  Harry Mairson had a nice paper discussing some aspects of these remarkable properties in Linear lambda calculus and PTIME-completeness (JFP 14:6, 2004).


NP-Completeness of the decision problem for the generalized 15-puzzle

I think that I found a partial (although quite disappointing) answer to my problem:

I stumbled across this paper (2007):

"The Complexity of Three-Dimensional Channel Routing" by     Satoshi Tayu and Shuichi Ueno

They show (Theorem 4) that the "3d-channel routing problem" with "2-nets" and dimension $p,q$ can be solved if and only if the corresponding (check article for more details) $p \times q-1$ puzzle can be solved.

Below Theorem 1 they propose some problem they call "2.5-D CHANNEL ROUTING", which is basically "3d-channel routing" with fixed depth $k$. They also say "the complexity of
the following problem [2.5-D Channel Routing] is open for any fxed integer $k \geq 2$".

If we knew that the decision version of the $p \times q-1$ puzzle is NP-Complete for some fixed $k \geq 2$ we would also know that 2.5-D Channel Routing is difficult for that $k$, therefore it seems the question can be reduced to some open problem.

It could of course be that the answer to my question would be that $p \times q-1$ puzzle is in P for all fixed $k$, which would still leave their question open (as the general routing doesn't only handle $2$-Nets). Therefore this is no complete answer, it is also rather disappointing that they include no references when claiming that the problem is still open.


Which subproblems of 3SAT are still NP complete?

I asked a similar question on cs.stackexchange.com, perhaps Juho's answer can help you; it contains references to: MONOTONE NAE-3SAT, MONOTONE 1-in-3-SAT, PLANAR 3SAT, k-COLOURABLE MONOTONE NAE-3SAT.

You can find other variants also in this cstheory question: 4-BOUNDED PLANAR 3-CONNECTED 3SAT, POSITIVE PLANAR 1-in-3 SAT.


We wrote a paper related to that. Perfect packing theorems and the average-case behavior of optimal and on-line packing, by Coffman, Courcoubetis, Garey, Johson, Shor, Weber, and Yannakakis.  See Theorem 1:

  Perfect Packing Theorem: For positive integers k, j, and r, with k ≥ j, one can perfectly pack a list L consisting of rj items, r each of sizes 1 through j, into bins of size k if and only if the sum of the rj item sizes is a multiple of k.

You should note that this only solves the question when (for the OPs definition of $k$ and $n$) $k$ divides $\frac{1}{2}n(n+1)$. If anybody knows how to solve it for all $k$, they should definitely submit another answer.


Is there a definitive reference for Turing machines with multiple oracle tapes?

Here is a more recent paper giving a difference between single vs. multiple oracles motivated by cryptography:

Donald Beaver and Joan Feigenbaum.  Hiding instances in multioracle queries.  STACS 1990.  Springer Lecture Notes in Computer Science, 1990, Volume 415/1990, 37-48, DOI: 10.1007/3-540-52282-4_30


Counting the Number of Simple Paths in Undirected Graph

There are several algorithms that count the simple paths of length $k$ in $f(k)n^{k/2+O(1)}$ time, which is a whole lot better than brute force ($O(n^k)$ time). See e.g. Vassilevska and Williams, 2009.


Is there an official name for a notion of "reusably universal"?

There has been work in the PL/systems community on the semantics and modelling of operating systems.  As you point out, what you are talking about is much like an OS: it does something, but is guaranteed (well, in the case of an OS, guaranteed-ish) to return to a "ground state."  The PL people may not have formalized your notion of reusably universal, but you might find some inspiration there.

Your formalization will have to capture the difference between "a universal machine that, after it runs with one input, if you replace the input with another input it is ready to go" and "a universal machine that, given a sequence of input programs, runs them in succession."  And of course, all reasonable notions of universal machine probably satisfy the latter requirement.  So it seems quite tricky...


Is the half-filled magic square problem NP-complete?

Filling a partially-filled Latin square is NP-Complete. "The complexity of completing partial Latin squares" Charles J. Colbourn. Discrete Applied Mathematics, Volume 8, Issue 1, April 1984, Pages 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

Can a Latin square problem be turned into a magic square problem via modular arithmetic? My intuition says yes, but the rest of my brain says "Get back to grading!"


This is an answer for the first problem:
Consider a new weighted graph $G'=(V,E')$, where $E'=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$ (weights of all edges that are in $G$ are 0, and weights of 'reversed' edges are 1). Now You just have to find the shortest path from $s$ to $t$.


What is the "right" definition of upper and lower bounds?

The right definition of $f(n)=\Omega(n^2)$ is that there exists some $k>0$ such that for infinitely many $n$, $f(n)\geq kn^2$. The infinitely-often definition for lower bounds handles your issues and is how we use it in practice.

I did a post on this back in 2005.

Some textbooks get this definition right, some don't.


How are real numbers specified in computation?

I disagree with your accepted answer by Kaveh. For linear programming and Nash equilibria, floating point may be acceptable. But floating point numbers and computational geometry mix very badly: the roundoff error invalidates the combinatorial assumptions of the algorithms, frequently causing them to crash. More specifically, a lot of computational geometry algorithms depend on primitive tests that check whether a given value is positive, negative, or zero. If that value is very close to zero and floating point roundoff causes it to have the wrong sign, bad things can happen.

Instead, inputs are often assumed to have integer coordinates, and intermediate results are often represented exactly, either as rational numbers with sufficiently high precision to avoid overflow or as algebraic numbers. Floating point approximations to these numbers may be used to speed up the computations, but only in situations where the numbers can be guaranteed to be far enough away from zero that the sign tests will give the right answers.

In most theoretical algorithms papers in computational geometry, this issue is sidestepped by assuming that the inputs are exact real numbers and that the primitives are exact tests of the signs of roots of low-degree polynomials in the input values. But if you are implementing geometric algorithms then this all becomes very important.


Rewrite relations - proof of correctness

To simplify, let $D$ be the domain of $T$ and let $R = \{\epsilon\} \cup (\Sigma^* \setminus \Sigma^*D\Sigma^*)$. Then by definition
$$
N(T) = Id_R \quad \text{and} \quad R^{obl}(T) = N(T)(TN(T))^*.
$$
Here is a formal way to justify your idea.
Let $(u,v) \in \Sigma^* \times \Sigma^*$. By definition, $(u,v) \in R^{obl}(T)$ if and only if $(u,v)$ can be written as
$$
(u, v) = (r_0, r_0)(u_1, v_1)(r_1, r_1)(u_2,v_2) \dotsm  (r_{k-1}, r_{k-1})(u_k,v_k)(r_k, r_k)
$$
where $r_0, r_1, \ldots, r_k \in R$ and $(u_1, v_1), \ldots, (u_k,v_k) \in T$, which is exactly what you describe in your sentence starting by "The idea is the following".


There are several output-sensitive algorithms to enumerate all maximal cliques in polynomial time per output.  One of the earliest algorithms was developed by Tsukiyama, Ide, Ariyoshi, and Shirakawa (1977).

Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa: A New Algorithm for Generating All the Maximal Independent Sets. SIAM J. Comput. 6(3): 505-517 (1977)

This means that if you know your graph has at most polynomially many maximal cliques, then the total running time of their algorithm will be polynomial in the input size.


Evidence that Graph Isomorphism problem is not $NP$-complete

Due to Babai's recent result (see the paper) $GI$ is in quasi-polynomial time ($QP$). If $GI$ is $NP$-complete, then it implies $NP\subseteq  QP=DTIME(n^{polylog\, n})$. This, in turn, implies $EXP=NEXP$, see
here. Therefore, if the commonly accepted conjecture $EXP\neq NEXP$ holds, then $GI$ cannot be $NP$-complete.


The role of symmetry in geometric complexity theory?

As for what invariant properties are being used, and what transformations are being applied to the permanent and determinant, see the answer to a related question.

As for how the symmetry is used to explain computational hardness: it's not. First, it's not just symmetry that is being used, but characterization by symmetries.  As discussed in another question of yours, symmetry can very well make a function easier to compute.

Second, even characterization by symmetries does not explain hardness - since both $det$ and $perm$ are characterized by their symmetries, but $det$ is easy. The idea instead is this: it should be easier to understand the algebro-geometric and representation-theoretic properties of functions that are characterized by their symmetries, and hence to carry out the GCT plan of attack.

Since most functions are not characterized by their symmetries, using characterization by symmetries in a crucial way also gives some hope of bypassing the natural proofs barrier, as discussed here.

(That characterization by symmetries should make understanding easier can be formalized a  tiny bit more as follows. Since GCT is studying the orbits of $det$ and $perm$, and there is a sort of duality between orbits and stabilizers, functions that are characterized by their stabilizers should have "special" orbits in some sense. I guess this alone doesn't actually say anything about how difficult it should be to understand these orbits. But understanding "generic" orbits can be very hard; having a nice property like characterization by symmetries at least gives us something to grab on to that we can try to use to gain more understanding.)


Is it considered OK to email authors to inquire about their paper while subreviewing their paper for a conference?

Usually any such ex-parte communication needs to go through the relevant PC. For example I was once on a PC where a subreviewer identified a bug in a paper they were reviewing for me. They relayed it to me, I discussed it with the other PC members assigned to the paper, and then we presented our conclusions to the PC chair who initiated contact with the authors.

This is for conferences without a rebuttal process (typically true for theory confs). If the conference has a rebuttal process then there's a formal mechanism for discussing this with the authors.

Finally, if you're not sure if there's a bug, then merely raise your doubt with the PC.

Update: a secondary issue that comes to mind after seeing Jeff's comment is a matter of fairness. Suppose ex-parte communications are not officially sanctioned, but are not frowned on. Then an author who happens to know people on the PC gets a slight advantage, because PC members might be more likely to contact the author. However, an official policy on how to handle such communication that does not depend on "knowing the author" implicitly or explicitly seems fairer.


Smallest set not included in a collection of sets

Let $[n] = \{ 1, 2, \dotsc, n \}$, and let $\mathcal{F} = \{S_1, S_2, \dotsc, S_m \} \subseteq 2^{[n]}$ be the input set family. Unless I misunderstood your problem formulation, we want to find a minimum-size set $T \subseteq [n]$ such that $T \not\subseteq S_i$ for all $i = 1, 2, \dotsc, m$.

To answer your question, note that $T \not\subseteq S_i$ if and only if $T \cap ([n] \setminus S_i) \not= \emptyset$. That is, $T$ has to intersect the complement of each $S_i$. But this means that your problem is, essentially, equivalent to the hitting set problem (consider hitting set with input $\mathcal{G} = \{ [n] \setminus S_i \  \colon \  i = 1, 2, \dotsc, m  \}$):

  Hitting Set.
  Given a set family $\mathcal{F} \subseteq 2^{[n]}$ and integer $k$, does there exists a set $T \subseteq [n]$ with $|T| \le k$ and $T \cap S \not= \emptyset$ for all $S \in \mathcal{F}$?

Hitting set is known to be NP-complete and cannot be, loosely speaking, solved faster than in time $O(2^n)$ unless the Strong Exponential-time Hypothesis fails.


This is almost a duplicate (see my comment above) but I'll give a quick answer before it (likely) gets closed. The first inequality in the OP has a superfluous $\log(n/d)$, which may be removed via chaining, as discussed here:
Tight VC bound for agnostic learning

Once that log-factor is removed from the VC bound, it becomes optimal up to constants (i.e., essentially unimprovable). See Section 5 in the Anthony-Bartlett book:
http://www.cambridge.org/gb/academic/subjects/computer-science/pattern-recognition-and-machine-learning/neural-network-learning-theoretical-foundations?format=HB&isbn=9780521573535#JEHXi1lP4I6Gl8dg.97

Regarding the optimality of the Rademacher bound, see the discussion and links here concerning Sudakov's inequality:Rademacher complexity beyond the agnostic setting


Though not directly constructing a context sensitive grammar for SAT, the following paper might shed some light.

W. C. Rounds, Complexity of recognition in intermediate Level languages, Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5

The paper by Rounds gives a one-way nondeterministic stack automaton (1-NSA) recognizing SAT, and then shows the membership problem of 1-NSA (and its proper superset, Aho's Indexed Grammar) is in general in NP. In other words, SAT as a CSL/linear-bounded-automata is special in the sense that it uses its memory only as a stack.


In domain theory, what can the extra structure present in metric spaces be used for?

Relative to domain structure, metric structure gives you extra data on the carrier set. Basically, you can compare any two elements of a metric space and furthermore you know how much two elements are different, whereas in domains the order structure is partial, and you don't have a quantitative measure of how much elements differ.

Pragmatically, this extra structure is useful in that it makes solving domain equations hugely easier. Back in the 80s there were a lot of Dutch computer scientists using metric space equations to model concurrency, but it's also of current interest.

If you've been following the usual places (POPL/ICFP/ESOP/etc), you'll have noticed that so-called step-indexed models are big business these days, since they let you give models of languages with combinations of features (such as impredicative polymorphism and higher-order state) that are difficult to treat with classical domain-theoretic models. However, the constructions used in these models are hauntingly similar to solving domain equations, and it's natural to wonder what the heck the connection is. Lars Birkedal and his collaborators have had the general idea that solving domain equations on bisected (ie, distances between any two points are all of the form $2^{-n}$ for some $n$) ultrametric spaces is the secret denotational life of step-indexed models. See Birkedal, Stovring and Thamsborg's paper "The Category-Theoretic Solution of Recursive Metric Space Equations" for some recent work in this area.

Now, all this work has been focused on getting models at all, but that's not the only thing we're interested in -- we can't just replace partial orders with metric structure in a denotational model and expect it to mean exactly the same thing. So you might wonder what the impact of metric models on properties like full abstraction, for example.

Escardo showed in his 1999 paper "A Metric Model of PCF" that a straightforward metric model of PCF was adequate but not fully abstract -- the extra metric structure could be used to model timeout constants. Concretely, you could model a constant $\mathrm{timeout}\;n\;e$ which would raise an error if $e$ did not return in $n$ steps or fewer. This is information that a metric model can see, because it has distance information, but it's information a domain model can't, since the information order doesn't tell you "how evaluated" a value is.

This extra resolving power is both the strength and the weakness of metric techniques. In their note "Step Indexing: the Good, the Bad, and the Ugly", Benton and Hur show that the extra structure of step-indexed models is very useful for them give to give realizability-style correctness proofs of programming languages implemented in terms of bad low-level languages. However, the extra structure also keeps them from performing optimizations that are in some sense "too effective", because it might mess up the distance information. So it both helps and hurts them.

EDIT: I should also give an example of when Banach's fixed point theorem of metric spaces can be useful. In domains, we find fixed points by, basically, Kleene's fixed point theorem. This says that if we have a pointed domain $D$, and a continuous function $f$ on it, then iterating from $\bot$ gives us the least fixed point. This theorem makes no claims about the uniqueness of fixed points in general -- iterating from something other than $\bot$ can give us other fixed points. So if you want to consider recursion definitions on a domain, you have no choice but to admit nontermination into it.

However, you might not want to do that. For example, in my own recent research (with Nick Benton), I've been working on higher-order synchronous dataflow programming. Here, the idea is that we can model interactive programs through time as stream functions. Naturally, we want to consider recursive definitions (for example, imagine writing a function which receives a stream of numbers as inputs, and outputs a stream of numbers corresponding to the sum of the stream elements seen so far).

But an explicit goal of this work is to ensure that only well-founded definitions are allowed, while still allowing recursive definitions. So, I model streams as ultrametric spaces and functions on them as nonexpansive maps (as an aside, this generalizes the causality condition of reactive programming). Under the metric I use, a guarded definition on stream functions corresponds to a contractive function on streams, and so by Banach's fixed point theorem, a unique fixed point exists. Intuitively, the uniqueness property means that computing fixed points works the same no matter what element of the space we start with, so as a result we can compute fixed points of contractive functions on a space, even if the space doesn't have a minimal element in the sense of domain theory.


Published as:

Scott, D. A Type-Theoretical Alternative to ISWIM, CUCH, OWHY.
   Theoretical Computer Science, vol. 121 (1993), pp. 411 - 440.

See also:

Scott, D. Some Reflections on Strachey and his Work. in: A Special Issue
   Dedicated to Christopher Strachey, edited by O. Danvy and
   C. Talcott.  Higer-Order and Symbolic Computation, vol. 13 (2000),
   pp. 103-114.

and:

Gordon D. Plotkin, Set-theoretical and other elementary models of the λ-calculus,
   Theoretical Computer Science, vol. 121 (1993), pp. 351-409.


Where is the proof that Coq + Excluded Middle is consistent

Actually, in section 4.5.3, he doesn't quite say that EM+impredicativity is inconsistent. He says that when you assume it, the model must becomes degenerately proof-irrelevant (the interpretation of all types other than Prop can  have at most one element). Andy Pitts describes a similar phenomenon "Non-trivial Power Types Can't Be Subtypes of Polymorphic Types".

For predicative versions of type theory, it's probably easier to just do the consistency proof than to Google for it -- universe stratification gives you everything you need for the simple-minded set-theoretic model of types (i.e., types are sets, terms are maps) to work out. Just observe that sets are closed under indexed sums and products, and get cozy with the axiom of replacement when interpreting universes. This is academic bad practice, of course, but the proof is still worth doing for yourself.


The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers

There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.


Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?

A special case of DNF equivalence is DNF tautology: Given a DNF formula $F$, is it satisfied for all assignments? This can be seen by setting $F_1 = F$ and $F_2$ to be a trivial tautology. CNF non-satisfiability is co-NP-complete. Negating the input formula turns a CNF formula into a DNF formula and vice versa and non-satisfiability into tautology. Thus, DNF tautology is co-NP-complete.


Dynamic transitive closure with immediate new reachability facts

Most research regarding time complexity of dynamic reachability looks at an index structure which is updated and then queried.  It would be useful to know why you want an immediate query?  The link studies this idea from a descriptive complexity approach although time complexities aren't given for the queries.
https://arxiv.org/pdf/1512.05511.pdf


Dissecting tetrahedra into similar tetrahedra

Hi Herman — since you asked me this at GD, I've found an answer to version (ii) of your question. Jiří Matoušek and Zuzana Safernová have shown that subdivision of a tetrahedron into $k$ tetrahedra that are similar to the original and congruent to each other is possible only when $k$ is a cube (and it is conjectured more strongly that this is possible exactly when $k$ is a power of eight, the case you already know about). See their paper "On the nonexistence of k-reptile tetrahedra", arXiv:1006.1807.


I've asked Dick personally out of curiosity a few years back. He said that as far as he knows Rabin-Karp was a random switch many years after the paper was first published. He also indicated that it is his understanding that Michael would say the same thing if asked, since at some point they had talked about it.


Does “Second X is NP-complete” imply “X is NP-complete”?

No,

Consider the problem "Find a subset of a set of integers S which sums to 0".

This problem is trivial, as one can return the empty set.

However, finding a second solution after returning the empty set is the well-known subset sum problem, which is known to be NP-complete.


You probably want

Manna, Pnueli, Axiomatic Approach to Total Correctness of Programs, 1973


I believe the answer to original question is probably yes, but unfortunately, I can't say that definitively.  I can help answer Peter's extended question, however.

In math/0001038, by Nebe, Rains, and Sloane, they show that the Clifford group is a maximal finite subgroup of U(2^n).  Solovay has also shown this in unpublished work that "uses essentially the classification of finite simple groups."  The Nebe et al. paper also shows that the qudit Clifford group is a maximal finite subgroup for prime p, also using the classification of finite groups.  This means that the Clifford group plus any gate is an infinite group, which makes one of the assumptions of the original question redundant.

Now, both Rains and Solovay told me that the next step, showing that an infinite group containing the Clifford group is universal, is relatively straightforward. However, I don't know how that step actually works.  And more importantly for the original question, I don't know if they were only considering the qubit case or also the qudit case.

Actually, I might add that I don't understand the Nebe, Rains, and Sloane proof either, but would like to.


Some such problems are considered here
https://eccc.weizmann.ac.il/report/2014/098/
under the name "simultaneous approximation".

See Theorems 1.1 and 1.3.


Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions

Doesn't $F + V \le 2I$ hold trivially for every system of incidences between things called vertices and things called faces? Under some reasonable assumptions, every vertex has at least one incidence, and every face has at least one incidence. If you add those incidences together you count each incidence at most twice.

To get from there to your desired $F + V \le I/2 + O(1)$ you'd need to use some actual geometry show that the vertices and faces each have at least four incidences on average. This is obvious for convex subdivisions but maybe needs more assumptions in general (e.g. consider a system of bubbles in 3d space, linked one to the next in a chain: each face has no vertex-face incidences, because there are no vertices).


Number of rounds of iterative one-round distributed color reduction

A friend helped me, the equation I wrote was correct. I simply didn't develop the result enough to bring it to the desired form. I will post more details when I have time.
Edit: what I needed to achieve the desired result is:

$log(a/b)/log(c/d) = log(b/a)/log(d/c)$

And that we should use Taylor expansion to say $log(1+1/d+1) =~ d+1$ as 1/x+1 -> 0.

If anybody needs help contact me.


Theoretical computer science self-study resources for programmers

There are several ways to learn about type theory. For a working programmer,
   Types and Programming Languages by B. Pierce is a good start.
Practical Foundations for Programming Languages by R. Harper might also be good. If you want a bit of easy to read background on operational semantics,
I recommend G. Winskel's, The Formal Semantics of Programming Languages: An Introduction. With T. Nipkow, G. Klein, Concrete Semantics, a variant of Winskel's book has been formalised for the Isabelle/HOL interactive proof assistant. I suspect it's really difficult to get to grips with a prover just from this (or any) book, you'd want an expert nearby to ask questions.
If you want a more mathematical approach to type-theory, you could look at
J. R. Hindley, J. P. Seldin, Lambda-Calculus and Combinators: An Introduction, or
H. Barendregt's, Lambda Calculi with Types. Although I wouldn't recommend starting from Barendregt.

If you want a single recommendation, I'd say read all of Pierce except Part VI (Higher-Order Systems), and implement the toy languages the book discusses. You'll end up with a strong grounding in type theory, and probably a better programmer too.


How much larger than the relaxation time can the mixing time be?

This paper shows that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}}\log t_{\mathrm{rel}})$ for all Markov chains and that $t_{\mathrm{mix}} = O(kt_{\mathrm{rel}})$ for reversible chains. The conjecture in the question is false since it's shown that $t_{\mathrm{mix}}$ can be as large as $kt_{\mathrm{rel}}.$

http://arxiv.org/abs/1310.8021


Finding self-similar homomorphisms of a FSM transducer

I guess I'm a few years late with this answer but here goes:

Every homomorphism $h:\Sigma\rightarrow\Sigma^{*}$ has a corresponding deterministic transducer with a single state $q$ (which is accepting) such that on each transition $\delta(q,\sigma)=q$, the machine outputs $h(\sigma)$. In this case the machine $F$ implements the total function $h:\Sigma^{*}\rightarrow\Sigma^{*}$.

The other direction does not hold since $F$ may define a partial function $f:\Sigma^{*}\rightharpoonup\Sigma^{*}$. While the set of regular languages is closed under homomorphism, a single language is not necessarily closed under an arbitrary homomorphism, so there is no gaurantee that $h(x)\in L$. Additionally the function $f$ should really be defined as taking two arguments $f(x,q)$ since the output is dependent on the combination of symbol and state. As such, I think $F$ must define a homomorphism for there to exist an $h$ such that $h(f(x))=f(h(x))$ holds, in which case $L=\Sigma^{*}$, or $L$ must be closed under both $h$ and $f$. In the latter case $L$ would have to be captured by some regular expression that is a concatention of some number of sub-expressions of the form $e_{1}^{*}\cdot...\cdot e_{n}^{*}$, where each $e$ is either a single symbol or a disjunction or a concatenation of kleene star terms similar to the top level expression, otherwise the language would not be closed under the given functions.


Graph theoretic restriction to Proofs in Proof Complexity Theory

The most natural restriction on the proof DAG is that it be a tree – that is, any "lemma" (intermediate conclusion) is not used more than once. This property is called being "tree-like". General resolution is exponentially more powerful than tree-like resolution, as shown for example by Ben-Sasson, Impagliazzo and Wigderson. The concept has also been considered for other proof systems – just search for "tree-like X", where X is a proof system interesting you. In the particular case of resolution, there are other restrictions that can be considered. See for example a paper of Alekhnovich, Johannsen, Pitassi and Urquhart regarding regular resolution.

Tree-like resolution is especially important since traditional implementations of DPLL correspond to tree-like resolution refutations. The technique of clause learning, which is important in practice, corresponds to allowing general DAGs. Hence the structure of the proof DAG is also strongly dependent on the algorithm generating it.


Does the isomorphism conjecture imply exponential lower bounds on witnesses density?

I don't see how that would immediately follow: the isomorphism conjecture is about languages, and doesn't seem to have any implications about the witness structure of NP verifiers. (Every language has infinitely many different verifiers for it, and you could potentially rig those verifiers to do odd things.)

But your question reveals another very natural intriguing question, about the following strengthening of the Isomorphism Conjecture:

"Are all verifiers for NP-complete sets poly-time isomorphic?"

I.e., we want not only a poly-time isomorphism $\phi_{L,L'}$ between any two NP-complete languages $L,L'$ defined by verifiers $V,V'$, but also isomorphisms $\psi_{V,V'}$ between their sets of input-witness pairs which respect the isomorphism $\phi_{L,L'}$. (Note: There are multiple ways one might formally define this.) All $NP$-hardness proofs I can think of give you a one-to-one correspondence of this kind, as well. This stronger "Witness Isomorphism Conjecture" would imply some sort of yes-answer to your question.

A quick Google search (typing 'witness isomorphism conjecture') found a survey of some approaches to this kind of question:

Eric Allender. Investigations Concerning the Structure of Complete Sets. Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, Springer, 2014


Good text on introduction to circuit complexity

To start off, there is of course Arora and Barak's book Computational Complexity: A Modern Approach. From there, parts 3 and 4 of Jukna's book Boolean Function Complexity: Advances and Frontiers make excellent reading material. Also, Ryan Williams teaches a nice course on circuit complexity whose course notes might hopefully be put up online :)


Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

In general, it seems that you cannot get the concentration you want without  more constraints on the probabilities.

Consider the following graph on $n$ vertices. Let vertices $C = \{2,\ldots,n\}$ form a clique such that for all $i,j \in C$, $p_{ij} = 1$. Let vertex $1$ be connected to this clique via only one edge, with $p_{1,2} = 1/\log(n)$, and $p_{1,j} = 0$ for all $j \in C$ with $j \neq 2$. Then with probability $1/\log(n)$, all $n$ vertices are reachable from $1$ with 2 hops, and with probability $1 - 1/\log(n)$ none are. So the expected number of reachable vertices is $n/\log(n)$, but with probability $1/\log(n) \gg n^{-1}$, it is $n$, larger than its expectation by a $\log(n)$ factor.

In fact, since you are interested in paths of length $\log n$, all that we require is that the realized edges in $C$ form an expander, not a clique, with high probability. This can be accomplished with $p_{ij} = o(1)$ as well, so this condition does not save you.

The essence of the problem is this: since you can have a group of vertices $C$ that are highly connected with high probability, how many vertices vertex $1$ is connected to can depend only on whether it is connected to $C$ or not, which can depend on only a single edge. You can't expect something depending on only a single Bernouli random variable to be well concentrated.


Reference for the undefinability of modulus of continuity functional in PCF?

The proof is hidden somewhere in Troelstra and van Dalen, Constructivism in mathematics, volume 2, I suppose. More likely, it can be found in Troelstra's investigations, if you can lay your hands on it.

It goes like this. Suppose we could define the modulus of continuity in typed $\lambda$-calculus with fixpoint operators. Then we could interpret it in a domain-theoretic realizaiblity model, for example in $\mathsf{PER}(\mathcal{P}\omega)$ where $\mathcal{P}\omega$ is Scott's graph model. In this model the choice principle $AC_{2,0}$ is valid. But it is known that $AC_{2,0}$ together with extensionality of functions (which holds in every realizability model) is incompatible with existence of modulus of continuity. If I get a moment, I will fill in the details later.

See also M. Escardo, T. Streicher: In domain-realizability not all functionals are continuous, published in Mathematical Logic Quarterly, volume 48, issue Supplement 1, pages 41-44, 2002.


Optimal algorithm for finding the girth of a sparse graph?

Here's what I know about the girth problem in undirected unweighted graphs.
First of all, if the girth is even, you can determine it in $O(n^2)$ time- this is an old result of Itai and Rodeh (A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413–423, 1978.). The idea there is: for each vertex in the graph, start a BFS until the first cycle is closed (then stop and move on to the next vertex); return the shortest cycle found. If the girth is even the shortest cycle found will be the shortest cycle. In particular if your graph is bipartite this will always compute the girth. If the girth $g$ is odd, however, you'll find a cycle of length $g$ or $g+1$, so you may be off by $1$.

Now, the real problem with odd girth is that inevitably your algorithm would have to be able to detect if the graph has a triangle. The best algorithms for that use matrix multiplication: $O($ min{$n^{2.38}, m^{1.41})$ time for graphs on $n$ nodes and $m$ edges.
Itai and Rodeh also showed that any algorithm that can find a triangle in dense graphs can also compute the girth, so we have an $O(n^{2.38})$ time girth algorithm. However, the runtime for the girth in sparse graphs is not as good as that for finding triangles. The best we know in general is $O(mn)$. In particular, what seems to be the hardest is to find a $o(n^2)$ time algorithm for graphs with $m=O(n)$.

If you happen to care about approximation algorithms, Liam Roditty and I have a recent paper in SODA'12 on that: Liam Roditty, V. Vassilevska Williams: Subquadratic time approximation algorithms for the girth. SODA 2012: 833-845.
There we show that a $2$-approximation can be found in subquadratic time, and some other results concerning additive approximations and extensions. Generally speaking, because of a theorem of Bondy and Simonovits, when you have densish graphs, say on $n^{1+1/k}$ edges, they already contain short even cycles, say roughly $2k$. So the denser the graph is, the easier it is to find a good approximation to the girth. When the graph is very sparse, the girth can be essentially arbitrarily large.


What kind of string is produced by successive application of argmax M

It is computable.
Although $M$ is incomputable, since $M(x)\sim 2^{-K(x)}$, the sequence $\omega$ generated by $argmax M$ would have quite low Kolmogorov complexity.
If the sequence is generated by $argmin M$, then it would be Martin-lof random.


Exact formula for the number of spanning trees of a rectangle

According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known.

According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ both large) to
$$\exp (z_{\mathrm{sq}}mn)$$
where
$$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$
but I'm not sure whether this is a rigorous bound or the result of heuristic physics-based reasoning. The same paper also gives asymptotic formulas of similar type when $m$ is fixed to a small constant and $n$ is large.


compact context free expression for permutation

Using the method in this answer one can show that the smallest context-free grammar for all permutation of $n$ symbols has exponential size in $n$.


Lemma. The problem is NP-hard.

Proof sketch.  We disregard the constraints $|F_i| \ll n = |U|$ in the posted problem, because, for any instance $(F,U,k)$ of the problem, the instance $(F'=F^n,U'=U^n,k)$ obtained by taking the union of $n$ independent copies of $(F,U,k)$ (where the $i$th copy of $F$ uses the $i$th copy of $U$ as its base set) is equivalent, and satisfies the constraint (it has $|F'_i| \le n \ll n^2 = |U'|$).

We give a reduction from 3-SAT.  For presentation, in the first stage of the reduction, we disregard the constraints $e_i \in F_i$ in the posted problem.  In the second stage we describe how to meet those constraints while maintaining correctness of the reduction.

First stage. Fix any 3-SAT formula $\phi$.  Assume WLOG that each clause has exactly three literals (each using a different variable). Produce the following instance $(F,U,k)$ of the posted problem, with $k=3$.

Let $n$ be the number of variables in $\phi$.
There are $3n+1$ elements in $U$: one element $t$ (for "true"), and, for each variable $x_i$ in $\phi$, three elements $x_i$, $\overline x_i$, and $f_i$ (for "false").

For each element in $U$ there is a singleton set containing just that element in $F$.  Any solution $C$ therefore includes each of these sets, which contribute their total size $3n+1$ to the cost of $C$.

In addition, for each variable $x_i$ in $\phi$ there is a "variable" set $\{x_i, \overline x_i, f_i, t\}$ in $F$.  For each clause in $\phi$ there is a "clause" set in $F$ consisting of the literals in the clause, and $t$.  For example, the clause $x_1\wedge \overline x_2 \wedge x_3$ yields the set $\{x_1, \overline x_2, x_3, t\}$ in $F$.

Claim 1. The reduction is correct: $\phi$ is satisfiable iff some solution $C$ has cost $\sum_j |C_j| = 5n+1$.

(only if) Suppose $\phi$ is satisfiable. Construct a solution $C$ consisting of the $3n+1$ singleton sets, plus, for each variable $x_i$, the pair consisting of the true literal and $t$.  (E.g., $\{\overline x_i, t\}$ if $x_i$ is false.)  The cost of $C$ is then $5n+1$.

Each variable set $\{x_i, \overline x_i, f_i, t\}$ is the union of three sets: the pair consisting of the true literal and $t$, plus two singleton sets, one for each of the other two elements.  (E.g., $\{\overline x_i, t\}, \{x_i\}, \{f_i\}$.)

Each clause set (e.g. $\{x_1, \overline x_2, x_3, t\}$) is the union of three sets: a pair consisting of $t$ and a true literal, plus two singleton sets, one for each of the other two literals.  (E.g., $\{x_1, t\}, \{\overline x_2\}, \{x_3\}$.)

(if) Suppose there is a solution $C$ of size $5n+1$.  The solution must contain the $3n+1$ singleton sets, plus other sets of total size $2n$.

Consider first the $n$ "variable" sets, each of the form $\{x_i, \overline x_i, f_i, t\}$.  The set is the disjoint union of at most three sets in $C$.  Without loss of generality, it is the disjoint union of two singletons and a pair (otherwise, splitting sets in $C$ achieves this without increasing the cost).  Denote the pair $P_i$.  The pairs $P_i$ and $P_j$ for different variables $x_i$ and $x_j$ are distinct, because $P_i$ contains $x_i$, $\overline x_i$, or $f_i$ but $P_j$ does not.  Hence, the sum of the sizes of these pairs is $2n$.  So these pairs are the only non-singleton sets in the solution.

Next consider the "clause" sets, e.g, $\{x_i, \overline x_j, x_k, t\}$.  Each such set must be the union of at most three sets in $C$, that is, up to two singleton sets and at least one pair $P_i$, $P_j$, or $P_k$.  By inspection of the pairs and the clause set, it must be the union of two singletons and one pair, and that pair must be of the form $\{x_i, t\}$ or $\{\overline x_j, t\}$ (a literal and $t$).

Hence, the following assignment satisfies $\phi$: assign true to each variable $x_i$ such that $P_i=\{x_i, t\}$, assign false to each variable $x_i$ such that $P_i=\{\overline x_i, t\}$, and assign the remaining variables arbitrarily.

Stage 2. The instance $(F,U,k=3)$ produced above does not satisfy the  constraint $e_i \in F_i$ stated in the problem description.  Fix that shortcoming as follows.  Order the sets $F_i$ and elements $e_i$ in $U$ so that each singleton set corresponds to its element $e_i$.  Let $m$ be the number of clauses in $\phi$, so $|F|=1+4n+m$ and $|U|=1+3n$.

Let $(F', U', k'=4)$ denote the instance obtained as follows. Let $A$ be a set of $2n+2m$ new artificial elements, two for each non-singleton set in $F$. Let $U'=U\cup A$. Let $F'$ contain the singleton sets from $F$, plus, for each non-singleton set $F_i$ in $F$, two sets $F_i\cup \{a_i, a_i'\}$ and $\{a_i,a_i'\}$, where $a_i$ and $a_i'$ are two elements in $A$ chosen uniquely for $F_i$.  Now $|F'|=|U'|=1+5n+2m$ and (with the proper ordering of $F'$ and $U'$) the constraint $e'_i\in F'_i$ is met for each set $F'_i$.

To finish, note that $(F',U',k'=4)$ has a solution of cost $|A|+5n+1$ iff the original instance $(F, U, k=3)$ has a solution of cost $5n+1$.

(if)  Given any solution $C$ of cost $5n+1$ for $(F,U,k=3)$, adding the $n+m$ sets $\{a_i, a'_i\}$ (one for each non-singleton $F_i$, so these partition $A$) to $C$ gives a solution to $(F', U', k'=4)$ of cost $|A|+cost(C)=|A|+5n+1$.

(only if) Consider any solution $C'$ for $(F', U',k=4)$ of cost $|A|+5n+1$.  Consider any pair of non-singleton sets $F_i\cup\{a_i, a_i'\}$ and $\{a_i, a_i'\}$ in $F'$.  Each is the disjoint union of at most 4 sets in $C'$. By a local-exchange argument, one of these sets is $\{a_i, a_i'\}$ and the rest don't contain $a_i$ or $a_i'$ --- otherwise this property can be achieved by a local modification to the sets, without increasing the cost... (lack of detail here is why I'm calling this a proof sketch). So removing the $\{a_i, a_i'\}$ sets from $C'$ gives a solution $C$ for $(F,U,k=3)$ of cost $5n+1$.  $\diamond$


For a Planar Graph, Find the Algorithm that Constructs A Cycle Basis, with each Edge Shared by At Most 2 Cycles

Construct a planar embedding and use all but one of the faces of the embedding as cycles in the cycle basis. (It doesn't matter which one you leave out.)

Note that there are actually two different subproblems in planar embedding: determining the cyclic ordering of the edges around each vertex, and computing explicit coordinates. But for the cycle basis, you only need the cyclic ordering, since that's what determines the structure of the faces; you don't need any kind of "nice" coordinates.

Finding planar embeddings is linear time but complicated; there are several standard algorithms.


Justification for the Hungarian method (Kuhn-Munkres)

(Moved from a comment.)

Of course you can solve any LP by using a general-purpose LP solver, but specialised algorithms typically have a much better performance.

It is not only about theoretical asymptotic performance guarantees, it is also about practical real-world performance. Algorithms such as the Hungarian method can be extremely streamlined and they are relatively easy to implement correctly and efficiently.

You can also often avoid issues like using exact rational numbers vs. floating point numbers; everything can be done easily with integers.


Breaking cycles in network graph by adding nodes and rerouting edges

This problem is Feedback Vertex Set in disguise, and hence NP-Hard, but I'd imagine there are good heuristics out there (I don't know the references myself, maybe someone can help me out here).

More specifically, for an input graph $G = (V, E)$ with minimal FVS $S \subseteq V$, there is a solution to your problem that copies each member of $S$ once (and no other nodes are copied at all), and this is best possible.  That solution is as follows.  Define the nodes of $G'$ in the following order: first we put all the nodes in $S$ (in any order), then we put the nodes of $V \setminus S$ in topological order in the DAG $G \setminus S$, and finally we put another identical copy of the nodes of $S$ (again in any order).  The edges $(u, v) \in E$ are placed in $G'$ in the natural way: if either endpoint $u, v \notin S$ then there is only one way to place the edge in $G'$, and if both $u, v \in S$ then in $G'$ the corresponding edge goes from the first copy of $u$ to the last copy of $v$.

This graph $G'$ will have the following property: you can map the nodes of $G'$ to the nodes of $G$ in a way that bijects the edges of $G'$ with the edges of $G$.  I believe this is the right way to formalize the node-splitting process you are describing (in the node-splitting view, you would iteratively split each node $s \in S$ into the two corresponding nodes in $G'$, rerouting edges such that the incoming edges all go to one new copy $s_1$ and the outgoing edges all go to the other new copy $s_2$).

Additionally, if $G$ has $n$ nodes then $G'$ has $n + |S|$ nodes, but there is no graph $G''$ on $n + |S| - 1$ nodes with the above property.
That is because, if one can split a set of nodes $S$ to reach a DAG, then surely one also has a DAG by deleting $S$ entirely.  So the size of a minimal FVS is no more than the number of extra nodes required in $G'$.


Not necessary. Imagine the following Fake-#SAT problem: possible solutions are extended by one bit, and all vectors with this bit set are solutions. That is, the number of satisfying assignments for the new problem is $2^n+f$, where $f$ is the number of satisfying assignments for the original #SAT problem ($0\le f\le 2^n$).

The problem remains #P-complete; however, the corresponding "majority" problem (formulates as $\ge$ vs $<$) has always the answer "yes".


Agnostic learning over arbitrary distributions

If no class is too simple, then here are some agnostically PAC learnable classes.  In response to the comments, the classes with polynomially many hypotheses are crossed out:

constant depth decision trees (and other classes having only poly many hypotheses)
hyperplanes in $R^2$ (only $O(n^2)$ hypotheses producing distinct labelings)
unions of intervals (dynamic programming)
parity on some of the first $\log(k)\log\log(k)$ of $n$ bits (see this and this)
other hypothesis classes in low dimensional settings.

Pretty much everything else is NP-Hard to (at least properly) agnostically PAC learn.

Adam Kalai's tutorial on agnostic learning may also interest you.


Find negative cycle with vertex constraints

If you don't require the cycle to be simple, then break the (directed) graph into its strongly connected components, and for each component containing one of the given vertices $V_i$, check whether the component contains a negative cycle.  If no component does, there is no negative cycle containing any $V_i$.  But if some component does, you can find a (non-simple) negative cycle containing $V_i$ by taking many copies of the negative cycle, and adding to that paths to and from some vertex in the cycle to $V_i$.  (The total time to find an implicit representation of the desired cycle will be the same as the time to find a negative cycle in a directed graph, e.g. $O(nm)$, if I recall.)

If you do require the cycle to be simple, then the problem becomes NP-complete, even if only a single vertex $V_1$ is given.  (You can reduce Hamiltonian Path to the problem: to find a Hamiltonian path from a given source $S$ to a given sink $T$ in a given graph $G$, give the existing edges weight -1, then add an artificial vertex $V_1$ with two edges of cost $N/2-0.01$ each, one from $V_1$ to $S$ and one from $T$ to $V_1$.)

If you allow the cycle to repeat vertices but not edges, I believe it is still NP-complete (by a similar reduction, but splitting each vertex $v$ into a directed edge $(v,v')$ in a standard way).


Locating a set of 5 geometrically constrained points within a cloud of points

Upper bound:

Make three sorted lists of point pointers, one for each dimension O(nlogn)

Pick a point in your reference template to be the "origin" and make 4 vectors to the other points O(1)

For each vector

Scan the list of all points to see if a sister point exists at this vector, if not throw it out as not an origin candidate.  O(n)

If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries; but after the first few are matched to the template it will be oriented allowing you to go back to vector lookups.


Proof for ACYCLIC PARTITION being NP-complete

In the current formulation, your problem can be proved to be NP-complete by a direct reduction from PARTITION.

Given $n$ positive integers, $S = \{a_1,a_2,...,a_n\}$ the PARTITION problem asks to find two disjoint subsets $S_1 \cup S_2 = S$ such that $\sum_{i\in S_1} a_i = \sum_{j \in S_2} a_j$.

So, just pick: $G = \{ V, \emptyset \}$ with $|V| = n$, set $m = 2$ and assign weight $a_i$ to node $u_i$ for all $i = 1,...,n$; set $B = \frac{1}{2} \sum a_i$, and set $K=0$ (arc costs and the acyclic constraints are irrelevant).

NOTE: my old answer was related to a different ACYCLIC PARTITION problem, and you can find it in the edits history below.


Name the graph class: Disjoint union of a clique and an independent set

The edge-complement of graphs in your class are complete split graphs: they can be partitioned into an independent set and a clique, such that every vertex in the independent set is adjacent to every vertex in the clique (see, for example, http://www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Hence you could call your graph class co-complete split graphs.


Sequences of colored graphs under the operations of disjoint union (a form of graph addition), recoloring, and adding edges between all vertices with some color combination form the basis for the definition of clique-width. However, the quantity of interest for measuring the complexity of such a sequence is not the number of operations needed, but the number of colors.


Count $k$-hop neighborhood for every vertex

There is this quasi-linear time approximation algorithm based on HyperLogLog: https://papers-gamma.link/paper/187


“Overflow” in Extended Euclidean Algorithm

This is called the Bézout's identity/lemma (not to be confused with Bézout's theorem in algebraic geometry), which states:

  Lemma. For every integers $a,b \neq 0$, $\gcd(a,b) = ax + by$ for some integers $x,y$. Also, we may assume $|x| \leq |b|$ and $|y| \leq |a|$.

Proofs can be founded in standard algebra textbooks. Also you can prove it yourself by induction on the iterations of gcd process.

In general this is true in every Euclidean domain $R$ with a multiplicative Euclidean function $f$. In the case here when $R = \mathbf{Z}$, we have $f(x) = |x|$ which is multiplicative.


A question on linear extensions of partial orders

If every sequence has length 3, the problem is known as Betweenness. Even the Betweenness problem is NP-hard. In this problem, we are given a set of vertices and a set of constraints of the form $u$ lies between $v$ and $w$. Our goal is to order all vertices so as to maximize the number of satisfied constraints. Opantry [1] proved that the decision version of this problem is NP-hard. Chor and Sudan [2] proved that it is SNP-hard.

The best known approximation algorithm for the problem, by Chor and Sudan, satisfies 1/2 of all constraints if the instance is completely satisfiable.

[1] J. Opantry. Total Ordering Problem, SIAM Journal on Computing, 8(1):111—114, Feb. 1979.

[2] B. Chor and M. Sudan. A geometric approach to betweenness, SIAM Journal on Discrete
Mathematics, 11(4):511-523, Nov. 1998.

Edits: clarified that the decision version of the problem is NP-hard.


converse relationship between the cut rule and the identity axiom

Girard is talking about intuitionistic sequents, in which sequences to the right of the turnstile have length at most 1. So in the premiss of the cut rule, the sequence of formulas $\vec{B}$ is empty. We can rewrite the cut rule as follows, writing $B^?$ for a sequence which is either empty or contains a single formula.

$$
\frac{\vec{A} \vdash C \qquad \vec{A'},C \vdash B^?}
     {\vec{A}, \vec{A'} \vdash B^?}
$$

Now, it's easy to see why Girard says $C$ on the right is stronger -- it is the only formula that occurs to the right in the first premiss.


Complexity of finding the maximal number of pair-wise disjoint sets

This is a special case of the Maximum Set Packing Problem and both problem A and B are NP-Complete. Note that the problem is simply a matching problem if $n=2$ and is also easy if $n=1$. So I'll assume $n \ge 3$.

Instead of asking the question,

  Are there $M$ disjoint sets among the $P$ sets?

Let's ask the following question

  What is the maximum number of disjoint sets we can obtain from the $P$ sets?

It is clear that if the second question is answerable in polynomial time, then so is the first since all we have to do is compare this maximum value to $M$ and output YES if $M$ is less than or equal to this maximum and NO otherwise.

Also, if the first question is answerable in polynomial time, then the second is too since we can use binary search on $M$ and obtain the answer to the second question and only add a factor of $O(\log{M})$

So we can conclude that both questions are equivalent. i.e. Question 1 is polylomial time solvable if and only if Question 2 is too.

It is also clear that the problems are in NP since we can easily verify that the $M$ sets outputed are disjoint.

So the question now is how do we reduce a known NP-Hard problem to this? To do this we reduce from the maximum set packing problem. I'll simply focus on problem A since problem B can easily be shown to be hard by setting $k=n-1$

Consider an arbitrary instance of the maximum set packing problem $T$. Note that the only difference between problem A and the original maximum set packing problem is that in problem A, the size of the sets have to be equal. Let $t$ be the maximum cardinality among all sets in $T$. If every set in $T$ have the same cardinality, we are done and the set cover problem is exactlly problem A. Now suppose that for some set $S_i \in T$, we have $|S_i| < t$. We simply add $(t-|S_i|)$ elements to $S_i$ which are not elements of any set in $T$. We repeat this process until all sets $S_i \in T$ have the same size. It is clear that adding new elements in this way does not change the size of the maximum number of disjoint sets.

So, if we can solve problem $A$ in polynomial time, we can solve the maximum set packing problem in polynomial time since all we have to do is remove the extra elements that we have added, and doing this doesn't change the size of the maximum number of disjoint sets in $T$.

EDIT - Some Additional information about problem B

Suppose problem B has a polynomial time solution, now consider an arbitrary instance $T$ of problem A with $n$ elements per set. Now we add a dummy element $d$ to each set in $T$. We now ask the following question.

  What is the maximum number of disjoint sets we can obtain by taking
  $n$ elements from each set?

Now we know that among the sets in the maximum, at most one of them can contain the dummy element, hence if the answer we get as the maximum is $M$, then the actual maximum number of sets in instance $T$ (our original problem A) is either $M$ or $(M-1)$, but this gives a constant factor approximation for maximum set packing. And such an approximation is only possible if $P=NP$. So problem B is also hard.


Are Shannon entropy and Boltzmann entropy mutually convertible?

In practice the only difference is that Boltzmann entropy deals with a thermodynamical constant $K_B$:

$
H = -K_B\sum_{i=1}^{N} P_i log_e\ P_i
$

i assume you already know that if $K_B=1$ you have Shannon entropy in a different base.
However the conceptual backgrounds are important; probability of events (Shannon) and probability of a particle being in one of $N$ states (Boltzmann) under a thermodynamical context.

There is theoretical work in making the formal link between the two notions of entropy. Take a look at the work of Edwin Jaynes.

http://en.wikipedia.org/wiki/Edwin_Jaynes


Pavlovic et al. view Turing machines over a binary alphabet as coalgebras for the functor $\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$. The symbols $\lhd$ and $\rhd$ represent thereby the tape moves.

Bart Jacobs has presented in "Coalgebraic walks, in quantum and Turing computation" an approach by using a monad. He present a Turing machine with $n$ states as a coalgebra for functor $\mathcal{P}_{\mathrm{fin}}[n]$ on sets. Alternatively, consider the type $\mathbb{T} = 2^\mathbb{Z} \times \mathbb{Z}$ that represents the tape and the position of the head on the tape. A Turing machine with $n$ states is then also an endomorphism   on $2^n \otimes \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$ in the category of join-semilattices, or an $n \times n$-matrix of coalgebras $\mathbb{T} \to \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$.

The most advanced approach to Turing machines (and also push-down automata) is given by Goncharov et al. The authors give presentations of monads for these types of machines by generators and equations, they show how represent rational behaviour by means of fixed point expressions and prove various other properties. In particular, they also study the language semantics of such machines.

I hope this helps.


Your definition seems to extend the notion of "convolution products" in groups; this can be seen as follows. Consider a finite group $G$ with generating set $\Sigma$, with the corresponding map $i_G : \Sigma^* \rightarrow G$. Construct the corresponding automaton $\cal{A}(G,\Sigma)$ with state set $G$ and which contains a transition $x \rightarrow_a a.x$ for every $x \in G, a \in \Sigma$.

Let $H$ be a normal subgroup of $G$, and consider the quotient $Q = G / H$; we can view $Q$ as a finite group with generating set $\Sigma$, up to identifying each $a \in \Sigma$ with its class $aH$. By the factor theorem, there is a projection $j : G \rightarrow Q$ (mapping $x$ to $xH$) and an homomorphism $i_Q : \Sigma^* \rightarrow Q$ such that $i_Q = j \circ i_G$.

Consider the corresponding automata $A = \cal{A}(G,\Sigma)$ and $B = \cal{A}(Q,\Sigma)$. Define the relation $R$ by: $R(a,bH) \Leftrightarrow a \in bH$. This defines an automata relation: for every $u,v \in \Sigma^*$ such that $u.a = v.a$, we have $i_G(u) = i_G(v)$ and thus $i_Q(u) = i_Q(v)$, implying that $u.(bH) = v.(bH)$.

Consider the tuple $T = (A,B,R)$. For every coset $k = tH \in Q$, it is easy to see that the set $R^{-1}(k)$ consists exactly of the elements of $k$, and that given an element $s \in G$, the operation $s^{-1} k$ gives the coset $(s^{-1} t) H$. As $H$ is a normal subgroup of $G$, we have $(s^{-1} t) H = (s^{-1} H) (t H)$, and in this case we obtain a "convolution product" over $Q$: given two weight functions $f,g$ over $Q(B)$, we obtain $\Theta_{T,f,g}(s) = \sum_{t \in Q} f(t) g(s^{-1} t)$. In particular, the function is stabilized by $H$, as for $r \in H$ the function $t \rightarrow (s^{-1} r s) t$ is a bijection over $Q$.

This suggests a possible connection with Fourier analysis and with the theta functions of integer lattices; there might be also a relation with the notion of harmonic functions over group actions. I'm not sure though if this is the kind of questions you are interested in.


It is important to remark that a specific boolean circuit only treats inputs of a given size, unlike a Turing Machine that can take inputs of any size.

So a language with inputs of arbitrary size is usually treated by a family of circuits, one for each size of input.
The problem with this definition is that it allows circuit to solve uncomputable problems, since we could for instance answer 1 if $|x|\in H$ and $0$ if $|x|\notin H$, where $H\subseteq \mathbb N$ is any set. Take for instance $H$ to be an enconding of the halting problem.

To circumvent this problem, we usually look at uniform families of circuits, where there is a fixed Turing Machine $M$ which on input $n$ outputs the circuit for size $n$ inputs.

There is now a hope that circuits are equivalent to Turing machines.

Unfortunately, the model of circuits have computations that always halt (or you can define circuits with loops that never halt but they are useless). This limitation alone suffices to prove that they cannot be Turing complete, because any Turing-complete model must allow infinite computation.

However notice that you have a uniform family of circuits for any language that is decided by a total Turing machine: on input $n$ you can build your circuit for size $n$ by listing all inputs of size $n$ accepted by your machine.
The things that you miss are recursively enumerable languages, such as the Halting problem.


Renyi entropy is analogous, in some sense, to $\ell_p$-norms, so let's first recall why those norms are useful.

Suppose we have a vector of numbers $a \in \mathbb{R}^n$. We want to have a single number that represents, in some sense, how does the typical element of $a$ look like.

One way to do so is to take the average of the numbers in $a$, which roughly corresponds to the $\ell_1$ norm: $\mathbb{E}_{1 \le i \le n}[|a_i|]$. This is often useful, but for some applications it has the following problems: First, the $\ell_1$ norm does not give us a good upper bound on the largest element of $a$, because if there is a single large element and many zeroes, the $\ell_1$ norm will be significantly smaller than the largest element. On the other hand, the $\ell_1$ norm also does not give us a good bound on how small the elements of $a$ are, for example, how many zeroes $a$ has - this problem occurs in exactly the same scenario as before.

Of course, when the elements of $a$ have a lot of variance, such as in the extreme scenario as above, no single number can give solve both problems above. We have a tradeoff. For example, if we only want to know the largest element, we can use the $\ell_\infty$ norm, but then we will lose all information about the smaller elements. If we want the number of zeroes, we can look at the $\ell_0$ norm, which is just the size of the support of $a$.

Now, the reason for considering $\ell_p$ norms is that they give us the whole continuous tradeoff between the two extremes. If we want more information on the large elements we take $p$ to be larger, and vice versa.

Same goes for Renyi entropies: Shanon's entropy is like $\ell_1$ norm - it tells us something about the "typical" probability of an element, but nothing about the variance or the extremes. The min-entropy gives us information on the element with the largest probability, but loses all information about the rest. The support size gives the other extreme. The Renyi entropies give us a continuous tradeoff between the two extremes.

For example, many times the Renyi-2 entropy is useful because it is on the one hand close to Shanon's entropy, and thus contains information on all the elements on the distribution, and on the other hand gives more information on the elements with the largest probability. In particular, it is known that bounds on the Renyi-2 entropy gives bounds on the min-entropy, see, e.g., Appendix A here: http://people.seas.harvard.edu/~salil/research/conductors-prelim.ps


Does Karp reducibility yield a total order?

Far from it. Indeed, any countable distributive lattice embeds as a sub-partial-order of $\leq_p$, even if we only consider those degrees in between two given fixed languages (K. Ambos-Spies, Sublattices of the polynomial time degrees, Inform. & Control 65(1):63-84, 1985).


Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

1) Depending on exactly what was meant, the conclusion in Kaveh's observation can be strengthened from $\mathsf{NP} \subseteq \mathsf{P/poly}$ to $\mathsf{P} = \mathsf{NP}$, essentially using Mahaney's Theorem. That is, if there is an algorithm which solves SAT and runs in time $\leq p(n)$ on all instances of length $n$ except for possibly $q(n)$ such instances, where $p$ and $q$ are both polynomials, then in fact $\mathsf{P} = \mathsf{NP}$. See, e.g. Meyer and Paterson and references therein, or Schoning's monograph "Complexity and Structure". So if this captures your notion of "hard instances" then there must be more than $poly(n)$ many hard instances for each $n$, assuming $\mathsf{P} \neq \mathsf{NP}$.

FYI, such algorithms are sometimes referred to as "apt" or "APT" algorithms, for "almost polynomial time" (not to be confused with the more modern complexity class $\mathsf{almostP}$, which happens to equal $\mathsf{BPP}$).

2) The above can be strengthened even further, as follows. Assume $\mathsf{P} \neq \mathsf{NP}$. Then the above says that for any algorithm solving SAT and any polynomial $p$, there is a set of instances of super-polynomial size on which the algorithm takes more than $p(n)$ time. But the set can depend on the algorithm.

The stronger result switches the quantifiers, and concludes: there is a super-polynomial size set H (for "hard") such that for any algorithm A solving SAT and any polynomial p, A takes more than $p(n)$ time on all but finitely many elements of H. Such an H is called a complexity core (the size assumption is not part of the definition of complexity core). The definition and existence of complexity cores was given by Lynch. The result I just quoted is proved by Orponen and Schoning.


Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity

As commenters @Lwins and @SashaNikolov have already stated, it is non-computably hard to compute a function as slow-growing as $f$. (So no really humanly comprehensible rate can be given.)

Namely, suppose we just have one direction of your equality: $f(c)\le\min_{x\ge c} K(x)$, but suppose $f$ does goes to infinity monotonically.

Then $x\ge c$ implies $K(x)\ge f(c)$. So given $n$, if we find $c$ with $f(c)\ge n$ then $K(c)\ge n$. So letting $F(n)=c$ we have a function $F$ with $K(F(n))\ge n$ for all $n$.

But according to Theorem 4.1 of my paper with Merkle and Stephan, this allows us to compute a diagonally non-computable function with finite range, i.e., it allows us to compute a complete extension of Peano arithmetic.


Finding the closest point to a sets of discrete points

It is called p-Median and is known to be NP-hard.
Refer to the following paper for more info:

  O. Kariv and S. Hakimi, “An Algorithmic Approach to Network Location
  Problems. II: The p-MEDIANS,” SIAM Journal on Applied Mathematics,
  vol. 37, no. 3, pp. 539–560, December 1979.


For what regards point 3:  the problem remains NP-complete:

if $m$ is a parameter, then it is simply a generalization of SUBSET SUM;
if $m$ is fixed, then given an instance of SUBSET SUM, simply multiply every $a_i$ and the target sum $B$ by $p = 2^k$ s.t. $2^k>m(m+1)/2$ and set $m$ target integers in this way:

$G = \{ b_1=B,b_2=a_1+1,b_3=a_1+2,...,b_m=a_1+(m−1)\}$.

In both cases the problem remains solvable in pseudo-polynomial time.

For what regards point 2) you can find some information related to the density analysis for the ("simpler") SUBSET-SUM problem (it is usually defined in terms of $n/m$ where  $n$ is the number of elements of the input set and $m$ is its maximum);  e.g.: O'Neil, Thomas E. "On Clustering in the Subset Sum Problem." Proceedings of the 44th Midwest Instruction and Computing Symposium (Duluth, MN, 2011).


Is optimally solving the n×n×n Rubik's Cube NP-hard?

A new paper by Demaine, Demaine, Eisenstat, Lubiw, and Winslow makes partial progress on this question---it gives a polynomial-time algorithm for optimally solving $n \times O(1) \times O(1)$ cubes, and shows $\mathsf{NP}$-hardness for optimally solving what you might call "partially-colored" cubes.
It also shows that the $n \times n \times n$ cube's configuration space has diameter $\Theta(n^2/\log n)$.

Sweet!

One possible next question that their work seems to suggest: is there a fixed family of partially-colored $n \times n \times n$ cubes, one for each value of $n$, such that optimally solving from a given configuration is $\mathsf{NP}$-hard?


Quantum PCP and hardness of simulating of Hamiltonians

As Shor said, there is no QPCP theorem (yet!).  One conjecture (let us call it the QPCP conjecture) is this: consider a graph of N vertices, of degree O(1).  Associate a qudit with each vertex, with Hilbert space dimension O(1).  Let the Hamiltonian be a sum of terms for each edge, each such term acting just on the qudits on the vertices, with operator norm of each such term bounded by O(1), so that the operator norm of the Hamiltonian is O(N).  Then, the conjecture is that there is some epsilon>0 such that it is QMA-hard to approximate the ground state energy of the problem to an accuracy epsilon N.

A slightly stronger conjecture is to consider the case in which each such term acting on an edge is a projector so that the ground state energy is non-negative, and the conjecture is that it is QMA-hard to determine whether the ground state energy is 0 given a promise that if it is not zero then it is at least epsilon N.

There are other versions of the conjecture too, but those are two interesting ones with the most natural relation to physics.  An even stronger conjecture (hence probably an easier one to disprove if you believe that these conjectures are false) is to consider the case in which the Hamiltonian is a sum of commuting projectors.