Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?

$\let\mr\mathrm\def\xx{\mr{FP^{NP[wit,\log]}}}\xx$ is not defined as a class of functions, but of potentially multivalued search problems. It is not difficult to construct $\xx$-complete search problems by variating the usual Cook–Levin theorem. Here is one, somewhat simplified from what I suggested in the comment above.

First, as should be mentioned somewhere in the BKT paper, the class $\xx$ does not change if all the oracle queries are made to ordinary, nonwitnessing NP oracles, except for the final query, which is guaranteed to succeed, and returns a witness $(u,v)$ such that $u$ is the output of the algorithm. Moreover, since $\mr{P^{NP[\log]}}=\mr{P^{\|NP}}$, we can simulate the initial $O(\log n)$ nonwitnessing queries with polynomially many nonadaptive (parallel) NP queries.

Now, if $A(x)$ is a polynomial-time algorithm making $n^c$ nonadaptive queries to an NP-oracle, and one witnessing query in the fashion described above, then

$\qquad B(x,1^j)\iff{}$ “the $j$th parallel query made by $A$ on input $x$ is true”

is an NP-predicate, hence by the Cook–Levin theorem, it is equivalent to the satisfiability of a poly-time (or log-space) constructible 3-CNF. Likewise,

$\qquad C(x,a_1,\dots,a_{n^c})\iff{}$ “the final query is true in the run of $A$ on input $x$ such that the $j$th parallel query is answered with $a_j\in\{0,1\}$ for each $j$”

is an NP-predicate, and the output of $A(x)$ can be read off from a witness to $C(x,\vec a)$ if supplied with the correct $\vec a$. Again, it can be expressed as a 3-CNF. Thus, the following search problem is $\xx$-complete:

  Input: A sequence of 3-CNFs $(\phi_1,\dots,\phi_n)$ (in whatever variables), and a 3-CNF $\psi(x_1,\dots,x_n,y_1,\dots,y_m)$

  Output: A satisfying assignment $(b_1,\dots,b_m)$ to $\psi(a_1,\dots,a_n,y_1,\dots,y_m)$, where
  $$a_j=\begin{cases}1&\text{if $\phi_j$ is satisfiable,}\\
0&\text{otherwise.}\end{cases}$$

Perhaps a more compelling $\xx$-complete problem is the following search variant of MAX-3SAT:

  Input: A 3-CNF $\phi$.

  Output: An assignment that satisfies the maximum possible number of clauses in $\phi$.

To see that this works, let $(\phi_1,\dots,\phi_n)$ and $\psi$ be as in the previous problem, where due to the way the reduction works, we may assume that $\psi(a_1,\dots,a_n,\vec y)$ is satisfiable for every $\vec a\in\{0,1\}^n$. We may also assume that variables used by the $\phi_j$ are pairwise disjoint, and disjoint from $\vec x,\vec y$. Then let $\phi$ be the conjunction of all clauses of $\phi_1,\dots,\phi_n,\psi$, together with a handful additional clauses that express that $x_j$ is true iff all clauses of $\phi_j$ are true.

Given any assignment to variables of $\phi_1,\dots,\phi_n$, we can find an assignment of the remaining variables that satisfies all clauses of $\psi$, and the additional clauses. Moreover, we can change an assignment of the variables of $\phi_j$ without affecting $\phi_k$ for $k\ne j$.

Thus, an assignment satisfying the maximal number of clauses of $\phi$ will also individually maximize the number of satisfied clauses of each $\phi_j$, and in particular, it will satisfy the whole $\phi_j$ iff $\phi_j$ is satisfiable, and its restriction to the $\vec y$ variables will be a correct solution to the original problem.

The above are multivalued search problems. As far as I am aware, it is an open problem whether there are $\xx$-complete functions.

As should also be mentioned in the BKT paper, predicates (i.e., $\{0,1\}$-valued functions) in $\xx$ are computable using nonwitnessing oracles: they are exactly the predicates in the class
$$\Theta_2^{\mr P}=\mr{P^{NP[\log]}}=\mr{P^{\|NP}}=\mr{L^{NP}}.$$
Consequently, a function $f$ is in $\xx$ if and only if

$|f(x)|$ is polynomially bounded in $|x|$, and
the bit-graph of $f$ is in $\Theta_2^\mr P$.

Thus, we could call the class of such functions $\mr{F\Theta_2^P}$. A similar reasoning as above shows that the following is an $\mr{F\Theta_2^P}$-complete function:

  Input: A sequence of 3-CNFs $(\phi_1,\dots,\phi_n)$

  Output: The sequence $(a_1,\dots,a_n)$, where
  $$a_j=\begin{cases}1&\text{if $\phi_j$ is satisfiable,}\\
0&\text{otherwise.}\end{cases}$$

Since $\mr{F\Theta_2^P}$ is closed under composition, an inspection of the two complete problems shows:

  Proposition: The following are equivalent.

  There exists an $\xx$-complete function.
  For every $\xx$-search problem $S(x,y)$, there is an $\mr{F\Theta_2^P}$-function $f$ such that $S(x,f(x))$.
  There is an $\mr{F\Theta_2^P}$-function that computes a satisfying assignment to any given satisfiable 3-CNF.


Damas-Milner-like subset of the calculus of constructions with global type inference

As far as I can tell, there is no prime candidate for an analogue of Damas-Milner for CoC. Certainly there is no definitive answer.

Arguably, Damas-Milner isn't even a perfect inference system for $\mathrm{F}_\omega$, as in general it can't infer types with higher kinds in them (though it is an open question as to whether higher kinds are really necessary, see this problem).

At any rate, here's a rather simple argument against a definitive system for the CoC: unification modulo $\beta$ conversion is undecidable in general, even for terms with simple types. But for a given unification problem $t\approx u$ it is rather easy to set up a term which can be typed if and only if $t$ unifies with $u$:

$$ A : \Pi \vec{x}.C\ t\rightarrow \mathrm{nat},\ B:\Pi\vec{x}.C\ u\vdash A\ B$$

where the $\vec{x}$ are the free (unification) variables in $t$ and $u$, as well as the "implicit arguments" which are the analogue of the polymorphic type variables in Damas-Milner.

That being said, there are restrictions of the unification problem which are decidable, most notably Miller patterns which have good properties (uniqueness of solutions), so it's common to restrict implicit argument resolution to Miller patterns and reject the term otherwise.

In practice every dependently typed language does have to solve this problem, if only because giving every single type annotation is unworkably tedious. However, that inference is usually designed to fail in which case the user is asked to supply additional annotations, something which is absent from usual programing language type inference systems.

More background in this cs.stackexchange answer: https://cs.stackexchange.com/questions/12691/what-makes-type-inference-for-dependent-types-undecidable

and this one, more centered on the unification problem:

https://stackoverflow.com/questions/1936432/higher-order-unification

And (tooting my own horn further, I guess), I recommend the article Elaboration in Dependent Type Theory by de Moura et al, as a discussion of the issues involved.


Computed circuit complexity of decision problems

Yes, this is a natural idea and people have thought about it. In short, the problem is that even the state-of-the-art SAT/QBF-solvers allow to find very small circuits only (with about 10–12 gates), not to say about proving that there is no small circuit. Some references:

Ryan Williams, Applying practice to theory (2008):

  Our knowledge of Boolean circuit complexity is quite poor. <…>  One good reason why we don’t know much about the true power of circuits is that we don’t have many examples of minimum circuits. We don’t know, for example, what an optimal circuit for $3 \times 3$ Boolean matrix multiplication looks like.

  One good reason why we don’t know much about the true power of circuits is that we don’t have many examples of minimum circuits. We don’t know, for example, what an optimal circuit for $3 \times 3$ Boolean matrix multiplication looks like. <…> Might we benefit from an Encyclopedia of Minimum Circuits? For example, what do the smallest Boolean circuits for $10 \times 10$ Boolean matrix multiplication look like? Are they regular in structure? It is likely that the answers would give valuable insight into the complexity of the problem. The best algorithms we know of reduce the problem to matrix multiplication over a ring, which is then solved by a highly regular, recursive construction (such as Strassen’s [Str69]). Even if the cataloged circuits are not truly minimal but close to that, concrete examples for small inputs could be useful for theoreticians to mine for inspiration, or perhaps for computers to mine for patterns via machine learning techniques. The power of small examples cannot be underestimated.

  Experiments with QBF solvers have not yet revealed significant new insight. So far, they have discovered one fact: the optimal size circuit for $2 \times 2$ Boolean matrix multiplication is the obvious one. Well, duh. What about the $3 \times 3$ case? This is already difficult! The sKizzo QBF solver [Ben05] can prove that there is no circuit for $3
\times 3$ that has 10 gates, but nothing beyond that. Even when we restrict the gates to have fan-in two, the solver crashes on larger instances.

Together with Evgeny Demenkov, Arist Kojevnikov, and Grigory Yaroslavtsev we managed to use SAT-solvers to improve upper bounds on the circuit size of symmetric functions. Details can be found in the following two papers: Finding Efficient Circuits Using SAT-solvers (2009), New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions (2010). Still, we do not know the exact circuit complexity for many elementary functions: for example, $2.5n \le C(MOD_3) \le 3n$, $2n \le C(AND,OR,XOR) \le 2.5n$.

Exercises 477–481 in Section 7.2.2.2: Satisfiability of TAOCP Volume 4 by Don Knuth (2015) discuss ways of finding optimal circuits with the help of SAT solvers. From the solution to exercise 481:

  It’s true for $n \le 5$. Here’s a 12-step computation when $n=6$ and $a=0$, found in 2014 by Armin Biere: <…> The case $n=6$ and $a \neq 0$, which lies tantalizingly close to the limits of today’s solvers, is still unknown.


Directed multigraphs as minimal automata

Any absorbing node $n$ will have to be either accepting or not (so that either everything or nothing is accepted once $n$ is entered). If the graph has more than two absorbing nodes, then some of them will end up equivalent for any choice of labeling and accepting set.

More generally, for any strongly connected graph $H$ there is only a finite number $n(H)$ of different possible labelings and accepting subsets; if your graph has more than $n(H)$ terminal strongly connected components equivalent to $H$ (attached at the leaves of a tree, say), it cannot correspond to any minimal automaton.

EDIT, regarding the follow-up question: This sounds tricky. One approach suggested by my argument might look like this:

Partition $G$ into SCCs. This is cheap; $O(|V|+|E|)$ using Tarjan's algorithm.
Sort the SCCs into isomorphism classes. Unfortunately graph isomorphism is not known to be in $P$.
For each terminal isomorphism class, determine the number of permissible corresponding sub-automata, and fail if there are not enough of them. Note that not every combination of accepting subset and edge labeling is permissible: for example, suppose our alphabet is $\{a,b\}$, and a component has two nodes, each with a self-loop and an edge to the other node. Making both nodes accepting and labeling both loops with $a$ (and the other edges with $b$) gives an automaton which is bisimilar to a single absorbing state, violating minimality.
Treat the remaining SCCs in the DAG similarly, taking into account the lower ones; I'm a bit fuzzy on the details of this part.

That is one step whose complexity is famously open, and another one which looks like it may require exponential time (since there may be exponentially many partitions into bisimilarity classes to be excluded when determining permissible automata). Can we do better?


As Sasho and Huck mentioned in their comments, "shattering means that you have to be able to separate all +/- labelings of the same set of points, given the function class."

Therefore, since the set of points on a line is never separable by the class of triangles, it is not a valid set of points to decide the VC-dimension this class.


The oracle you ask for has $P=NP\ne BQP=NEXP$, and therefore it has $BQP\ne PH$. Finding any oracle relative to which $BQP\ne PH$ was an open problem for twenty years until Raz and Tal [1] found such an oracle last year. In summary, the oracle you ask for currently is not known to exist, but people are looking. There are oracles relative to which $P\ne BPP=PH=BQP=NEXP$, but these lack your constraint $P=NP$. [3]*

(The second oracle you ask for exists, namely take $O=PSPACE$, then $P=NP=BQP=PSPACE\ne NEXP$).

There is currently no quantum PCP Theorem, though again, people are looking. Aharonov et al. [2] provide a readable introduction to the Quantum PCP Conjecture. In this context, as in the classical PCP, there are two equivalent versions, one talking about verifying a quantum proof, the other talking about hardness-of-approximation. One major step that has been accomplished is that we know that the two versions are equivalent, that is, they imply each other. Many other questions remain open.

[1] Raz, Ran, and Avishay Tal. "Oracle Separation of BQP and PH." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. ACM, 2019.

[2] Aharonov, Dorit, Itai Arad, and Thomas Vidick. "Guest column: the quantum PCP conjecture." Acm sigact news 44.2 (2013): 47-79.

[3] Williams, Ryan. "Towards NEXP versus BPP?." International Computer Science Symposium in Russia. Springer, Berlin, Heidelberg, 2013. (Section 4, Conclusion)

[4] Kitaev, Alexei Yu, et al. Classical and quantum computation. No. 47. American Mathematical Soc., 2002.

(*) (Actually I cannot find a reference for such an oracle, but [3] mentions such an oracle)


Automata : Language Containment, Minimality & Graph Homomorphism

For inclusion, using your condition that non-final states can be mapped to final states does not work. Consider for instance that $A$ is a rejecting sink $p_0$, and $B$ is the minimal automaton for any non-trivial language with a transition $q_0\to q$. Then no such morphism can exist, because we must have $h(p_0)=q_0$, but also $h(p_0)=q$ because of the second condition, although $L(A)\subseteq L(B)$.

If you add the condition that nonfinal states are mapped to nonfinal states, it corresponds to language equality.
You actually just need $B$ to be minimal for the equivalence to hold, assuming all states of $A$ are reachable.

First, notice that the morphism is indeed unique, as you must map the initial state of $A$ to the initial state of $B$, and then the whole morphism (if it exists) is induced by your second condition, since all states of $A$ are reachable.

We can now prove the equivalence. First it is clear that if the morphism exists, then $L(A)=L(B)$, since accepting runs of $A$ are mapped to accepting runs of $B$ and vice-versa.

Conversely, assume that $L(A)=L(B)$, we have to show that the morphism $h$ exists. The only problem we could have when building $h$ in the forced way, is if two words $u,v$ lead to the same state in $A$ but two different states in $B$.
Since $B$ is minimal this means $u^{-1}L(B)\neq v^{-1}L(B)$. But  $u^{-1}L(A)=v^{-1}L(A)$ since both words reach the same state of $A$, we reach a contradiction with $L(A)=L(B)$.

As Andras Salamon mentioned, the minimal automaton is indeed defined as the DFA $B$ such that for any DFA $A$ for the same language, such a morphism $A\to B$ exists.


Isomorphism Problems with Unknown Single-Exponential Algorithms

A. Permutational isomorphism (aka conjugacy) of permutation groups. Input: Two lists of permutations $\pi_1, \dotsc, \pi_k, \rho_1, \dotsc, \rho_l$ Decide: Is there a permutation $\gamma$ such that $\gamma\langle \pi_1, \dotsc, \pi_k \rangle \gamma^{-1} = \langle \rho_1, \dotsc, \rho_\ell\rangle$, where $\langle \dotsc \rangle$ denotes the subgroup generated by $\dotsc$. The best known running time is $2^{O(n)}|G|$ (Babai-Codenotti-Qiao, freely available version), where the permutations are permutations on $n$ elements and $G = \langle \pi_1, \dotsc, \pi_k \rangle$. Note that $|G|$ can be as large as $n!$, so in the worst case this is $2^{O(n \log n)}$ time. Running time $2^{O(n)}$ (independent of $|G|$) is still open.

B. Group code equivalence for any group other than prime cyclic. For a group $G$, a $G$-code of length $n$ is a subgroup of $G^n$, specified by a generating set. Two such $G$-codes are equivalent if they become equal (as subgroups) after applying a permutation on the $n$ coordinates. For $G = \mathbb{Z}/p\mathbb{Z}$, this is the same as linear code equivalence and can be solved in $2^{O(n)}$ time (Babai; see Babai-Codenotti-G.-Qiao or Codenotti's freely available thesis). However, it is still open even if $G$ is a cyclic $p$-group of non-prime order, such as $\mathbb{Z}/p^2\mathbb{Z}$. Also, even doing the case of cyclic $p$-groups in time $2^{O(n)}$ (with operations in $G$ at unit cost) would have an application (see Observation 7.8 G.-Qiao).


Are there temporal logics linear time properties that only have counterexamples that are more complex than a lasso?

Pierre Wolper defined in 1983 extended temporal logic (ETL, in Information and Computation 56, 72–99, doi:10.1016/S0019-9958(83)80051-5), where a temporal operator $\mathcal A(\varphi_1,\dots,\varphi_n)$ can be introduced for a finite-state automaton $\mathcal A$.  The formula is satisfied in an infinite word $u$ at position $i$, i.e. $u,i\models\mathcal A(\varphi_1,\dots,\varphi_n)$, if there exists a finite word $a_{i_1}\cdots a_{i_n}$ in the language of the automaton $\mathcal A$, such that for every $1\leq j\leq n$, $u, i+(j-1)\models\varphi_{i_j}$.  Extended temporal logic has the same expressive power as the linear-time $\mu$-calculus or MSO on infinite words, so it does not answer your question.

One can however go further and allow other languages instead of regular ones in the operator $\mathcal A(\dots)$.  Paul Gastin and Stéphane Demri consider the case of context-free languages at the end of their chapter Specification and Verification using Temporal Logics of Modern applications of automata theory (IISc Research Monographs 2, chapter 15, pages 457–494, World Scientific, 2012, http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-iis09.pdf).  You can certainly express non-lasso properties in such a logic.  It is shown by Gastin and Demri to have (highly) undecidable satisfiability and model-checking problems.


As stated, the answer to this question is NO.

References :
A polynomial time algorithm http://dl.acm.org/citation.cfm?id=101343 [courtesy: vzn]

Another much simpler technique : http://dl.acm.org/citation.cfm?id=122322 [courtesy: Jeffe]


What is the advantage of designing deterministic distributed algorithms?

I will answer this from the perspective of distributed graph algorithms (distributed algorithms that solve a graph problem related to the structure of the communication network).

Here are some non-obvious reasons for designing deterministic distributed algorithms in this setting:

Subroutines in randomised algorithms. On p. 12–13 of these slides, Elkin outlines an algorithm design technique in which you can use a fast deterministic distributed algorithms as a subroutine in order to construct a fast randomised distributed algorithm. Interestingly, it is not possible to use a typical randomised algorithm as a subroutine in the same context (the error probability would be too high).
Fault tolerance. There is a mechanical translation that allows you to convert a fast deterministic distributed algorithm into a fast self-stabilising distributed algorithm (see e.g. Section 2.4 of this survey). A similar conversion is not known for randomised algorithms (and I think it is unlikely to exist in the general case).


See

Sariel Har-Peled and Soham Mazumdar (2005), "Fast algorithms for computing the smallest $k$-enclosing circle", Algorithmica 41 (3): 147–157, doi:10.1007/s00453-004-1123-0.


Size of complement of context-free language

From the proof that determining if a CFL ${L}$ = $\Sigma^*$ is undecidable, the set of strings $ID_0\#ID_1^R\#ID_2\#ID_3^R\#\ldots\#ID_t$ where $ID_0,ID_1,\ldots,ID_t$ is a list of the configurations of an accepting nondeterministic TM, is the complement of a context-free language. So $|\overline{L}_n|$ can basically be any computable function less than exponential.


Can complexities differ w.r.t. different computational models?

Niel De Beaudrap's point is an important one: a complexity class is defined with respect to a machine model. But if I were to re-interpret your question as:

  Can the complexity of a problem differ greatly in different computational models ?

Then the answer is yes. JeffE's answer to my earlier question about decision tree complexity presents an example of an NP-hard problem (SUBSET SUM) that has polynomial decision tree complexity.


What are the complexities of the following SAT subsets ?

I think both are NPI under the stronger assumption (but obviously true) that NP is not in "infinitely often P" - i.e., every polynomial time algorithm A and every sufficiently large n, A fails to solve SAT on inputs of length n.

In this case, such languages are not in P, but they also cannot be NP complete, since otherwise a reduction from SAT to a language L with large holes will give an algorithm for SAT that succeeds on these holes.

Such an assumption is also necessary, since otherwise the languages can be in P, or NP-complete, depending on where the "easy input lengths" are located.


Pattern matching with don't cares: multiple patterns

For the multiple pattern case, it seems that simply scanning for each of the might be the best possible solution, at least unless the strong exponential-time hypothesis fails.

Recall that given sets $S_1, S_2, \dotsc, S_n$ and $T_1, T_2, \dotsc, T_n$ over universe $[m]$, if we could decide if there are $S_i$ and $T_j$ such that $S_i \cup T_j = [m]$ in time $O(n^{2-\varepsilon}\operatorname{poly}(m))$, then SETH fails, i.e. we have a CNF-SAT algorithm with running time $O^*\bigl(2^{(1-\varepsilon/2)n}\bigr)$.

Given sets $S_1, S_2, \dotsc, S_n$ and $T_1, T_2, \dotsc, T_n$, we encode the above problem as multi-pattern matching with don't cares over binary alphabet as follows:

The text is $$1[T_1]10^{m+2}1[T_2]10^{m+2}\dots0^{m+2}1[T_n]1\,,$$ where $[T_i]$ is the natural encoding of $T_i$ as a binary string.
We have $n$ patterns of form $1\langle S_i \rangle 1$, where $\langle S_i \rangle$ is a string $y = y_1y_2\dots y_m$ such that $y_j = 1$ if $j \notin S_i$ and $y_j = * $ if $j \in S_i$ (here $*$ is the don't care symbol).

Now it's clear that a pattern $1\langle S_i \rangle 1$ can match the text at an occurrence of $1[T_j]1$, and only when $S_i \cup T_j = [m]$. The total length of patterns and the length of the text are both $O(nm)$, for instance so a near-linear single-pass algorithm for multiple patterns would give substantial improvements over best known CNF-SAT algorithms...

(Note that this does not say anything about algorithms that use lots of time preprocessing the patterns, say, quadratic in the total length of the patterns.)


Enumerating all simply typed lambda terms of a given type

This question has been considered several times in the academic community, from the practical:

Yakushev & Jeuring, Enumerating Well-Typed Terms Generically

Fetsher & al, Making Random Judgments: Automatically Generating
Well-Typed Terms from the Definition of a Type-System

to the more theoretical

Grygiel & Lescanne, Counting and generating lambda terms

Implementations can pretty easily be found online. I didn't find any that addressed a system with iterators per se, but it shouldn't be a stretch from what already exists.


I'm not answering the full question but only part of it (I have no interest in branching time).

Your definition of $\mathit{even}$ would better read $\mathit{even}(p) \equiv \exists q.(q \land \Box ( q \leftrightarrow \mathsf{X} \lnot q ) \land \Box ( q \rightarrow p ))$.  You are introducing $q$ only to remember if you are on an odd or even position, but this $q$ information is not on your system so it should not be a free variable of your formula (otherwise your system and your formula are defined on different alphabets).  Such a formula is an Existentially-Quantified LTL formula (EQLTL for short).

EQLTL formula can only have $\exists$ quantifiers at the top-level.  And they are as expressive as Büchi automata.  For instance to translate
the EQLTL formula $\exists q.(q \land \Box ( q \leftrightarrow \mathsf{X} \lnot q ) \land \Box ( q \rightarrow p ))$ as a Büchi automaton, you would simply translate the LTL formula $q \land \Box ( q \leftrightarrow \mathsf{X} \lnot q ) \land \Box ( q \rightarrow p )$, and then erase the $q$ variable from everywhere in the automaton.   Conversely any Büchi automaton can be converted into an EQLTL formula easily: declare an existential variables for all the states $\exists s_1.\exists s_2\ldots$, and use these to encode transitions and acceptance states (e.g. $\exists s_1.\exists s_2.(s_1\land\Box(s_1\rightarrow a\land \mathsf{X}s_2)\land\Box(s_2)\rightarrow b\land\mathsf{X}(s_1))\land\Box\Diamond s_2\land\Box(\bigwedge_i (s_i\rightarrow\bigwedge_{j\ne i}\neg s_j)))$ if $s_1$ can go to $s_2$ with $a$, $s_2$ can go to $s_1$ with $b$, and $s_2$ is Büchi-accepting; the last conjunction of implications make sure you cannot be in two states at once).  You might want to read Stutter-Invariant Languages, ω-Automata, and Temporal-Logic on this subject.

Basically the $\exists q$ is used here like some second-order quantifier (there exist a set of states where $q$ hold and such that...).  EQLTL and Büchi automata are equalivent to S1S, and LTL is equalivent to F1S.  $even$ is the typical S1S formula that cannot be expressed by F1S.

QPTL, which you mentioned, adds $\exists$, $\forall$ (not only at the top-level), and past operators.  It contains EQLTL but is not more expressive (since QPTL can be converted to Büchi automata and Büchi automata can be converted to EQLTL).

CTL is about branching time, so it's a different world.  A CTL formula like $\mathsf{EF}\mathsf{AG}p$ which is reasoning on the tree of all possible futures have now equivalent in LTL which is reasoning on all possible scenarios.


Is deterministic pseudorandomness possibly stronger than randomness in parallel?

They are the same: BPNC = DBPNC.

Say a BPNC machine is given as input a DBPNC program to simulate.  Execute the program in lock step.  First assume that the indices between different steps are distinct, so that we do not need to remember old random bits.  At each step, each processor asks for a random bit at a specific index into the shared stream.  Compute and distribute the random bits as follows:

Sort the indices among the processors and remember the origin of each bit.
Coordinate among adjacent processors to compute the ranges of identical indices.
Compute each random bit on the first processor that owns it after sorting.
Scatter throughout the identical ranges.
Send back to the origin process (if necessary by reversing the sorting algorithm).

To allow processors to ask for old indices, have each processor remember the (results) of all previous sorting epochs.  To check whether newly requested indices occurred in a given previous epoch, do

Sort the new indices.
Merge the lists of old and new indices (e.g., with Cole 1988).
Scatter appropriately.


Partition of $\{(i, j)\ |\ i \neq j \leq n\}$

A slightly different way of arguing for the upper bound of $\log n$ is as follows:

Observe that by mirroring across the line $x = y$, we can ignore all points in the upper triangle of the grid (at the cost of increasing the partition size by a factor of 2).
Now consider the lower triangle. If we draw the vertical line $x = n/2$, and "reflect it" off the diagonal $x = y$, we get a square with endpoints $(n/2, 0)$ and $(n, n/2-1)$. all of these points can be placed in a single set.
This leaves two similar  copies of the lower triangle with half its size. Any construction for these two triangles can be "paired up" since sets in these partitions don't conflict.

This yields the recurrence
$$ S(n) = 1 + S(n/2) $$
and hence $S(n) = \Theta(\log n)$


Closure properties of deterministic context-sensitive languages

Some  results

Unless I am very mistaken, some of these questions are not hard. But I did not yet look at all of them.

I assume that a deterministic context-sensitive language (DCSL) is
defined as one recognized by a deterministic linear bounded automaton
(DLBA). We note $n$ the size of the input string $w$. We restrict the
problem, w.l.o.g, to DLBAs that use a tape that has the size of the
input string, plus the two end markers. We also assume that acceptance
is by terminating (no transition) accepting state, and rejection is by
terminating non-accepting state or non-termination.

The constructions below will use multi-track finite tapes. That is
only a presentation of a single tape that is the cross-product of
several tapes, i.e. where each cell can contain a tuple of symbols,
one component of the tuple for each track.

Since the tape contain initially just the input string, a first
deterministic pass of any DLBA we build will consiste in
transforming the input tape into a multitrack tape, that will have the
initial string in one or several of its tracks.

For every DLBA $A$, there is a DLBA $A'$ that always halt and accepts the same language.

The problem here is to detect looping computation. That is done with
the pigeon-hole principle, using the fact that computation is deterministic.

A first point is to note that a DLBA has $O(nk^n)$ configuration,
where $k$ is the number of tape symbols of the DLBA, the factor $n$ is
for the head position, and the constant number of states is just a
constant factor.  Hence, using a constant $h$ large enough (usually
$k+1$, but it may not be enough for small values of $n$, though that
is just a finite number of cases), a tape track of size $n$ with an
alphabet of size $h$ is enough to count beyong the number of
configurations of $A$ for the given input.

Hence we can build a DLBA $A'$ that has three tracks, two to simulate
the original DLBA $A$, and the other to simulate the counter. The
roles of the two simulation track are to hold the tape configuration
for the first, and to memorize the head position and the associated
state for the second.

The finite control, simulates steps of the automaton $A$ one at a
time, and  increment the counter by one for each simulated transition.
If the counter overflow the tape, then the number of steps simulated
exceeds the number of possible configurations of $A$, which indicates
that $A$ went at least twice through the same configuration, hence
that it is looping for ever since computation is deterministic.

In such a case, the DLBA $A'$ stops in a rejecting state.

Otherwise, the DLBA $A'$ accepts or rejects as $A$ would have.

*So, W.l.o.g., we can now consider only DLBA that always terminate.

Complementation of (the language of) a DLBA $A$

Given a terminating DLBA accepting a language $L$, we can construct a
DLBA accepting its complement $\bar L$ by exchanging accepting and
non-accepting states.

Thus DCSLs are closed under complementation.

Intersection, union, and difference of (languages of) two DLBA $A$ and $B$.

We assume wlog that both DLBA always terminate. Hence it is easy to
build a DLBA $C$ with two track, each containing initially a copy of
the input (after the initialization pass, as indicated above). The
DLBA $C$ will first simulate $A$ until it terminates, then simulate
$B$ until it terminates. Then it can examine the terminating states of
both, and mimic any bolean function on the results, particularly and
for intersection and or for union.

This gives closure of DCSLs under union, intersection, and set difference.

Closure of DCSLs under intersection with regular set is just a special case, as
any DFA is a DLBA.

Concatenation of (languages of) two DLBA $A$ and $B$.

It is easy to check whether a string $w$ is accepted as the
concatenation of two strings $u\in\mathcal L(A)$ and $v\in\mathcal
L(B)$. Knowing where the boundary between $u$ and $v$ is placed, a
DLBA $C$ can simulate $A$ on $u$, then $B$ on $v$ and decides on
acceptance iff both simulations accept.

The remaining difficulty is that given a string $w$, we do not know
how it should be decomposed as $w=uv$ such that $u\in\mathcal L(A)$
and $v\in\mathcal L(B)$. The solution is to try successively all
possible decompositions, until one succeeds, which is followed by an
acceptance. If none succeed, the input string $w$ is rejected.

Hence DCSLs are closed under concatenation.

Kleene star of (the language of) a DLBA A

This problem is nearly the same as concatenation. But instead of
trying all decompositions of the input string $w$ into two strings, we
have to try all possible decomposition into the concatenation of an
arbitrary number of  non-empty substrings. To do this, the simplest
way is to use a track to keep a clean copy of the input string, a
track to have a working copy on which we test a decomposition in
substring, and a third track with a $\{0,1\}$ alphabet that defines
the decomposition into substrings. To list all the possible
decompositions, we only have to use the third track as a counter from
$0$ to $2^{n-1}-1$, incrementing it by one after every unsuccesful
try, until one succeeds thus accepting the input string, or until the
counter reaches the value $2^{n-1}$ in which case the input string is
not accepted.

Thus DCSLs are closed under Kleene star

Note: Closure of DCSLs under reversal is just obvious


Can NP-hard statements be proved by PCPs that only involve reading 2 bits?

Such a characterization of NP follows from the NP-hardness of any gap problem for a binary CSP with constraints of arity 2.

A binary CSP with arity 2 constraints is given by a family $\Pi$ of arity 2 relations on $\{0, 1\}^n$. An instance is given by a set of constraints. The GapCSP$_\Pi$($c$,$s$) problem for the CSP is the promise problem of distinguishing between CSP instances where at least a fraction $c$ of the constraints can be satisfied and instances where at most a fraction $s$ of the constraints can be satisfied. If such a GapCSP$_\Pi$($c$, $s$) problem is NP-hard for constants $c > s$, then we get a 2-bit PCP for NP in the usual way: the proof is a variable assignment, and can be verified by sampling a constraint and checking if it is satisfied.

In Some Optimal Inapproximability Results, Håstad shows that the GapCSP$_\Pi$($\frac{3}{4} - \delta$, $\frac{11}{16} + \delta$) problem is NP-hard for any constant $\delta$ when $\Pi$ is the family of constraints of the type $x_i + x_j = c \pmod 2$. There are two components to the reduction:

the famous optimal hardness of 3-variable linear equations mod 2: $\text{GapCSP}{_\Pi}$($1 - \delta'$, $\frac{1}{2} + \delta'$) is NP-hard for any constant $\delta'$ and $\Pi$ the family of constraints of the type $x_i + x_j + x_k = c \pmod 2$ (equivalently, this is a result about optimal 3-bit PCP for NP)
a gadget reduction from 3-variable linear equations to 2-variable linear equation; each 3-variable equation is replaced by sixteen 2-variable equations over the original variables and some auxiliary ones, so that if the original equation is satisfied, then 12 of the new equations can be satisfied by some assignment of the auxiliary variables, and if the original equation is not satisfied, then no assignment of the auxiliary variables satisfies more than 10 of the new equations (Theorem 5.14 in the paper)

You can get a better ratio between $c$ and $s$ if you assume the Unique Games conjecture: Khot, Kindler, O'Donnel, and Mossel showed that for $\Pi$ the max cut constraints $x_i \neq x_j$, solving GapCSP$_\Pi$($\frac{1}{2}(1 - \rho)$, $\frac{1}{\pi}\arccos(\rho) - \delta$) is as hard as Unique Games for any $\rho \in (-1, 1)$ and any constant $\delta > 0$. Optimizing over $\rho$ gives $\frac{s}{c}$ arbitrarily close to the Goemans-Williamson constant.


Recent progress in permutation groups algorithms?

Certainly there has been tons of progress! (And if you really meant to ask about the last 50 years, then that includes the algorithms of Schreier-Sims and Butler that you already mentioned...)

For example, see Seress's book [1], which includes many algorithms that upgrade standard tasks into $\mathsf{NC}$ and/or quasi-linear (sometimes Las Vegas) time, such as membership testing, computing the order, and even computing the entire composition series! The finite simple groups can be recognized in the black-box model [2] (more general/stronger than permutation groups or matrix groups), and permutational isomorphism of permutation groups of degree $n$ can be decided in $O(2^{n} |G|)$ time [3] (prior to that, the best known was the trivial $n! \cdot poly(n)$ algorithm). Many of these results were in the last 20 years, and the latter is even from 2012.

[1] Seress, Ákos
Permutation group algorithms. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003

[2] Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theory 5 (2002), no. 4, 383–401.

[3] László Babai, Paolo Codenotti, Youming Qiao: Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups (Extended Abstract). In: Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP'12), Springer LNCS 7391, 2012, pp. 51-62.


Terminology for complete k-partite graph where k is not fixed

I believe the most standard term is complete multipartite graph.


Classes and types in object-oriented languages

Core calculi for Java typically take the classes-as-types approach.  Two well-known examples are Featherweight Java and Classic Java.


Clarification of leftmost maximal periodicities

Main explicitly states that his algorithm may output some nonleftmost or nonmaximal occurrences of periodicities. Indeed, theorem 3.4 only guarantees that every leftmost maximal periodicity will be reported at least once and that total size of the output is linear in size of input string. Namely,

It may report some nonmaximal periodicity, which is suffix of $t_h u_h$ and still can be extended to the right.
There might be several occurrences of the same substring such that none of them fit into a single s-factor.

Kolpakov and Kucherov slightly modify Main's algorithm to exclude suffixes of $t_h u_h$ but allow either $t_h$ or $u_h$ to be empty. This way the algorithm never reports nonmaximal periodicities and at the same time finds every occurrence of maximal periodicity that either spans several s-factors or touches their boundaries.

So, Kolpakov and Kucherov don't rely on the notion of leftmost occurrences at all. They only need to find every periodicity that is not strictly inside single factor of s-factorization. (And prove that there will be only linear number of occurrences in total, of course.)


Complexity of the $(3,2)_s$ SAT problem?

This problem is NP-complete.

Let $\varphi$ be an arbitrary CNF formula (an instance of SAT).  Consider $\varphi \lor y$, where $y$ is a fresh variable; obviously, this formula is satisfiable (you can simply set $y$ to true).  Now convert $\varphi \lor y$ to 3-CNF, using any standard method, and let $\psi$ denote the result.  Note that $\psi$ is a satisfiable 3-CNF formula, so we can let $F_3 = \psi$.  Now, let $F_2 = \neg y$.  Notice that $F_3 \land F_2$ is satisfiable if and only if $\varphi$ is.  Therefore, the $(3,2)_s$ SAT problem is at least as hard as SAT.  Also, it is clearly no harder than SAT.  Therefore, it is exactly as difficult as SAT.


Primitive Recursive Definition : Binary numbers

The concept of primitive recursion function easily generalizes to any inductive data structure. For example, you can define the primitive recursive functions on binary strings as the smallest class of functions containing $\epsilon$ (the constant "empty string"), $S_0,S_1$ (append $0$ or $1$), projections and closed under composition and the scheme allowing to define a function $f$ by
$$
\begin{align*}
f(\epsilon,\vec x) &= g(\vec x), \\
f(zi,\vec x) &= h_i(z,\vec x,f(z,\vec x)), & i\in\{0,1\}
\end{align*}
$$
as soon as $g$ and $h_0,h_1$ are already in the class.

In the above setting, the usual numerical functions may be encoded either by considering only unary strings (i.e., $n$ is represented by $1^n$), in which case you can mimick the usual primitive recursive functions, or, more interestingly, by representing integers in binary. In that case, the successor function is not part of the basic functions but must be defined (and this is not immediate).

As you point out, traditional recursion theory considers primitive recursion on unary strings (or tally integers) because in that setting complexity is not a main concern.  On the other hand, whenever complexity classes are defined in terms of recursive functions, primitive recursion on binary strings (or binary integers) is routinely used. See for example the seminal paper by Bellantoni and Cook "A New Recursion-Theoretic Characterization of the Polytime Functions", Computational Complexity 2(2):97-110.


Generalization bound for parameters rather than loss functions

See our recent paper:
"Non-parametric Binary regression in metric spaces with KL loss"
https://arxiv.org/abs/2010.09886
The setting is actually non-parametric and quite general. Our loss measures the expected log-likelihood -- which is more natural in the context of logistic regression than distance in parameter space. Notice that our loss is unbounded, as would be the $\ell_1$ or $\ell_2$ loss in parameter space.


Is there any programming language in which any equivalent program has a unique, decidable normal representation?

What you are asking for does not exist for a general-purpose programming language (by which we mean that the language can simulate Turing machines, and that Turing machines can simulate the language). Let me first recall the proof, and then turn the question around to discover something interesting.

We have to make your question just a bit more precise. Let us suppose that when you speak of inputs and outputs you mean strings, and that your programs are total (defined on all inputs). Now suppose there were an algorithm $Z$ which maps programs to programs (that is, strings to strings) such that, given any two valid programs $A$ and $B$ which map strings to strings, $Z(A)$ and $Z(B)$ are defined and
$$Z(A) = Z(B) \iff \forall x \in \mathtt{string} . A(x) = B(x).$$
Notice that I did not even require that $Z(A)$ be a program equivalent to $A$, it can be any string whatsoever, the important thing is that it maps $A$ and $B$ to the same string if, and only if, they represent equivalent programs. We can now solve the halting oracle as follows.

Let $A$ be a program which always outputs the string 0, i.e., $A(x) = 0$ for all $x \in \mathtt{string}$, and let $x_0 = Z(A)$. Consider any Turing machine $M$ and an input $y$. Because we assumed our language is Turing-complete, from a description of $M$ and a given input $y$ we can construct a program $B_{M,y}$, which computes as
$$B_{M,y}(n) = \begin{cases}
1 & \text{if $M(y)$ halts in fewer than $n$ steps of simulation}\\\\
0 & \text{otherwise}
\end{cases}$$
Notice that $B_M$ and $A$ are equivalent if, and only if, $M(y)$ diverges. But now we can decide whether $M(y)$ halts: if $Z(B_{M,y}) = x_0$ then $M(y)$ does not halt, otherwise it halts.

The above argument shows that programs of type $\mathtt{string} \to \mathtt{string}$ do not have canonical codes. How about other kinds of programs? Well, in some cases we obviously can produce canonical codes. For instance, a program $A$ of type $\mathtt{bool} \to \mathtt{bool}$ can be represnted canonically by the list $[A(\mathtt{false}), A(\mathtt{true})]$, from which the corresponding $Z$ can be easily constructed. If we replace $\mathbb{bool}$ with some other finite datatype, we also obtain canonical codes by simply listing the values of $A$.

But did you know that there are canonical codes for programs of type $(\mathtt{nat} \to \mathtt{bool}) \to \mathtt{bool}$? That is, given a program $A$ which takes as input infinite binary streams and outputs a bit, we can compute a corresponding canonical code $Z(A)$. See my blog post on juggling double exponentials where I explicitly construct $Z$.

We could also ask whether it is possible to make Turing machines somehow more powerful so that we can compute canonical code, and thereby solve the Halting problem. Well, adding an oracle will not help because exactly the same reasoning goes through. But we use infinite-time Turing machines (ITTM), then canonical codes for maps $\mathtt{string} \to \mathtt{string}$ are computable. The ITTM's therefore can solve the Halting problem for ordinary Turing machines, but they still cannot solve their own halting problem (which is not reducible to comparison of two functions $$mathtt{string} \to \mathtt{string}$). See my paper on embedding $\mathbb{N}^{\mathbb{N}}$ into $\mathbb{N}$ for details.

P.S. Apologies for blatant self-propaganda.


Can a result of (any) hash algorithm contain the hash result itself?

For the first question, about the last line, it surely depends on the hash function. For example, suppose each line is a single bit (0 or 1). If the hash function is the xor of the bits, then the answer is yes -- take 240 lines with total parity 0. But the answer is no if the hash function is defined by
$$f(x_1, x_2, \ldots, c_n) = \neg (x_n \oplus f(x_1, \ldots, x_{n-1})),$$
with $f()=0$, where $\oplus$ is xor.

For the second question (about any line), I think @Yonatan's point in his comment was that if the hash function has finitely many possible outputs (as e.g. MD5 does), then, for a file that already contains every possible hash output (one per line), no matter what the hash outputs it will be in the file already.


Do graphs with large number of paths contain large chain minor?

Seems this is a FPT algorithm for a fixed $k$. First of all we can just consider a block which contains $s,t$. If we have a $k\times k$ grid minor which contains $s,t$ then we can find the corresponding chain. As otherwise, as Chekuri et al. shown, the graph has tree width at most $O(k^{1/\delta})$ where $\delta > 0$ is some constant. So we can compute the tree decomposition of graph then check whether that chain exists or not. I'm not sure if with usual dynamic programming on graphs of bounded tree width is possible to find the chain. Also if is not bounded tree width, their algorithm can find the corresponding grid in polynomial time.

P.S: Note that I didn't use the fact that there are $n^k$ s-t paths, may be by some trick inside this fact is possible to obtain better algorithm.


A course for learning algebraic complexity

The massive tome of Burgisser-Clausen-Shokrollahi is the standard reference for algebraic complexity theory (and I'm not really sure there are others from the complexity point of view, though there are definitely others about algebraic algorithms), but doesn't do much of PIT.

The surveys of Chen-Kayal-Wigderson (freely available from Wigderon's webpage) and Shpilka-Yehudayoff (freely available from Shpilka's webpage) cover much more of the recent results on lower bounds and derandomizing PIT for small algebraic circuit classes.

Agrawal's 2006 ICM address gives a good overview of the permanent versus determinant problem, and despite being 8 years old is still fairly up to date. (I think the only more recent lower bound is Landsberg-Manivel-Ressayre, which gets the same lower bound but for approximative determinantal complexity instead of just determinantal complexity.)


What does the contention-free communication assumption really mean in the context of DAG scheduling?

Not my field of expertise, but I think this is a relaxation in comparison with real-life scenarios. In actual systems, once a connection has been established and a "packet" has been sent (what packet here means depends on the context of the problem being solved), it is possible that an unscheduled interrupt occurs  that pauses this communication and allows a new communication with a different processor to occur.

I believe this relaxation means that once a "packet" is sent, we assume that the other processors do not interrupt this connection until this quantum of information has been sent. Essentially, it makes the processors being collaborators instead of antagonizers and it simplifies the analysis, while still keeping it reasonable, since all processors stick to the schedule and do not monopolize the connection (i.e. they will stop transmitting once this quantum of information has been sent, instead of maintaining their connection and sending their entire message in the expense of others, thus ignoring the schedule given).


NP-complete problem with polynomially many certificates?

No, there is no known sparsely certified $NP$-complete languages. The class that you are describing is known as $fewP$. It is widely believed that $fewP \ne NP$, So, No $NP$-complete problem is known to be in fewP. (It is impossible unless $fewP=NP$).


Simulate a process of state change with transition probability dependent on proportion in state in previous time

The principle of your voting system makes me think of Instant Run off, which forces the participants to vote X number of time when there's X+1 candidates on the poll. For Instant Runoff it is the choice that gather the less votes which is out of the competition, but i think you can easily adapt this system to your situation. (Inverting the max and min condition to get the right state out of the game)

I think you can figure it out in R, but you can also try to do it in Python. Take a look at this post : List sorting/modify problem if you want to see how IR can be implemented in Python. You might have to try and post what you've done (even not working) or to ask more specific questions if you want further help from the community.

You can also try other voting systems if it matches with your expectations, i would strongly recommand you the Condorcet voting method if you don't want to bother with multiple round processus : http://short.open-agora.com/m0ZQMPjMQV


This problem is solved in the following paper, where more general problems are mostly addressed: http://valis.cs.uiuc.edu/~sariel/papers/06/integrate/ .


I believe this is an open question.

Lee and Schraibman in "An approximation algorithm for approximation rank" show that the approximation rank can be approximated to a constant factor by a polynomial time algorithm.  To do so, they relate a semidefinite programming quantity $\gamma_2^\alpha$ to the approximation rank, where the $\alpha$ is some finite parameter greater than 1.  Taking $\alpha$ to the limit of infinity yields the sign-rank but their result does not give anything in this setting.


How many induced subgraphs does $G$ have of specific size

Consider a star graph, if we take a center of star union with $l-1$ arbitrary vertices then the corresponding subgraph is induced connected subgraph. So the maximum number is about $n-1\choose l-1$. We can extend this class of graphs by connecting arbitrary vertices together to have more edges. It's also possible to achieve closer to $n \choose l$ if $l$ is much smaller than $k$, or $k$ is big enough.


Unique Identifier Creation and Invalidation

Looks like some Data integrity check stuff.
For example adding something like CRC16 (4hex digits) will allow filter ID with typos


How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

Diagonal Hamiltonians are easy to simulate with 2 queries. It's very well explained (with a circuit diagram!) in Andrew Childs' PhD thesis on page 18, Rule 1.6.

The main idea is to observe that if H is the Hamiltonian with diagonal entries d(j), then simulating H for time t maps the basis state $|j\rangle$ to $e^{-id(j)t}|j\rangle$. This is performed as follows: $|j, 0\rangle \rightarrow |j, d(j)\rangle$ (this uses 1 query), then $|j, d(j)\rangle \rightarrow e^{-id(j)t}|j, d(j)\rangle$ (this is a controlled phase flip on the first register controlled by the second), and then $e^{-id(j)t}|j, d(j)\rangle \rightarrow e^{-id(j)t}|j, 0\rangle$ (this uncomputes the answer using another query).

Indeed, all 1-sparse Hamiltonians can be simulated with 2 queries. This is also explained in Andrew's thesis, towards the end of page 20. It might be a bit hard to understand since it's explained in the context of simulating a d-sparse Hamiltonian using edge coloring. But the essential idea is to reduce a d-sparse Hamiltonian to a sum of 1-sparse Hamiltonians and then simulate the 1-sparse Hamiltonian.


Meaning of program as solution of a recursive equation

"Meaning", or "semantics" to use the more technical term, is only the understanding you wish to associate with the
text of the program.  It can be a mathematical function that specifies
abstractedly what the program computes (denotational semantics), or it
can be a formal description of how the computation is conducted by a
formally defined machinery (operational semantics). It is really a
matter of what you are interested in expressing. The program is a big
formula, and there are many way in which you may want to interpret it.

You may even be interested in so-called non-standard interpretation
that may express specific properties of the program, such as well
typedness.  Even a prettyprinter, that gives you a string of
characters corresponding to a nicely presented version of the program
text can be seen as an interpretation, a meaning for it (however trivial). It is much in
the eyes of the beholder.

However, the definition of a meaning cannot be arbitrary. It is
expected to obey some rules so that it can be used constructively. In
particular, a program or formula is produced by composition, by using
formal operators to build larger formulae from smaller parts. A
meaning, or semantics is expected to follow these compositional rules,
so that you can somehow define the meaning of the whole from the
meaning of the components. The use high order functions makes the
constraint more manageable than appears.

The concept is applicable to other formal structures. For example, the
syntax of a programming language is usually defined by a grammar. The
grammar can have a meaning that is the set of program (strings) that
can be written according to that grammar. It could also be the set of
parse-trees for those programs.

Now a standard meaning of program is what it computes, or how it does
it (again, partly for consistency reasons, the distinction is often
in the eyes of the beholder, depending somewhat on what you do with
that formal meaning).

Coming back to your example:

The function $next$ defines what it is to execute one step of
the program. Its meaning is a function (on a mathematical
domain of states) that gives you the next state after a step of
computation given the current state. By applying this function
repeatedly,  starting from the initial state of your computation, you
will ultimately get to a final state that gives you the result ... or
computes indefinitely (depending on whether that computation is
supposed to terminate).

This means that the effect of running your program is to apply the
function :  $ next \circ  next \circ next \circ next \circ ...$
this composition being as long as necessary for all steps of the
calculation at hand, possibly infinitely many.

This is better expressed by the fixed-point equation:  $P = next \circ P$
since from it you can derive :

$P = next \circ next \circ P$
$P = next \circ next \circ next \circ P$
$P = next \circ next \circ next \circ next \circ P$
and so on

It shows that any function $P$ satisfying this equation will provide as
many steps as needed, applying the function $next$, to get the
computation you want to describe.

Now, this requires a minimum of mathematical apparatus to work
properly, for the equation to have a mathematical meaning.  The mathematical domains used are supposed to allow you to talk about
approximating a function. For example a finite composition of $n$
application of the function $next$ is an approximation of $P$ for when the
program needs no more than $n$ steps to do its work. Typically, a
lattice of ever better approximations will do that (this is what
monotonicity is about: getting ever better approximations, as you
increase the number of applications). Furthermore, you need this
lattice to be continuous, so that the monotonically increasing infinite sequence of
approximations of $P$ will have a limit, which is actually the meaning
of $P$.

In practice, all this is usually described in a more formal mathematical way,
as done for example in the answer of @tathanhdinh.

This technique of approximations can be used as well to describe data structures that contain loops, actually implemented with pointers, though the semantics may not want to know about pointers.


With respect to Problem II, it is coNP-hard (under Karp reductions) to tell if the number of unreachable strings is 0 or at least $1 - 2^{-\text{poly}(|x|)}$ fraction of all strings. I suspect there is a way to boost this and show that the gap problem is PSPACE-hard, maybe by using IP as a robust characterization of PSPACE.

Let $L$ be a coNP-complete language. There exists a polynomial time Turing machine $M$ and a polynomial $p$ such that $x \in L$ if and only if for all $w$, $|w| = p(|x|)$, we have $M(x, w) = 0$.

Construct $P$ to be the following program. It takes $z$ where $|z| = p(|x|) + i$ and maps it to

itself if $z = (w, 0^{i})$ and $M(x, w) = 1$
to $z'$, where $z'$ is the successor of $z$ in the lexicographic order, otherwise

Notice that if $x \in L$, then starting from $0^{p(|x|) + i}$ and repeatedly applying $P$ we run through all strings $z$ of size $p(|x|) + i$. Otherwise, there is some $w$ such that $M(x, w) = 1$ and the repeated applications of $P$ reach at most $2^{p(|x|)}$ strings. Taking $i$ to be a large enough polynomial in $|x|$ finishes the proof.


Is $LL(k)$ for large $k$ considered harmful? If so, why?

The parsing table of a $LL(k)$ grammar grows exponentially in $k$.
This is however the worst-case scenario, which is not typical, as Niel pointed out:
For an $LL(k)$ grammar $G$, $k$ is the size of the maximal lookahead needed across $L(G)$.
But it appears that in practice, the need for a $k$ lookahead is restricted to a small portion to the language, so that the size of the parsing table remains reasonable.

We face here a quite common problem of theoretical complexity not reflecting the practical experience.
Beyond $LL(k)$ are $LL(*)$ grammars, whose lookahead is adaptative, so as to keep the parsing table no larger than necessary.
$LL(*)$ technique is examplified by ANTLR, and described in this paper by Terence Parr.

Finally, I would say that many teachers focus on $LL(1)$ to emphasize that $LL(1)$ suffices to parse most languages in practice.
Philosophically, our programming languages lie somewhere between Deterministic and Non-Deterministic Pushdown Automata, but in fact way closer to DPA than to the full NPA.
A similar observation can be done for natural languages: context-free is not enough, yet context-sensitive is way too powerful.


This was a comment first, but Suresh asked me to turn it into an answer:

Maybe you want to take a look at timed automata. These are finite automata equipped with clocks; time can pass, clocks can be reset, transitions can be restricted to occur within a given time by clock guards etc. Here are some nice introductory slides: lsv.ens-cachan.fr/~bouyer/files/bouyer_chennai.pdf

(This is actually the framework that Vor is using in his answer. His solution makes use of a clock that is reset and a guard for the epsilon transition.)


graph isomorphism given a partial isomorphism

Only an extended comment: Lipton et al. proved [1] that if we have access to an oracle that given two graphs on $n$ vertices, reveals a partial map on at least $(3+\epsilon)\log n$ vertices (for some constant $\epsilon > 0$) which is part of an isomorpshism between the two graphs, then we can find the isomorphism in polynomial time.

The theorem deals with finding the isomorphism (the two graphs must  be  isomorphic), and the oracle is obviously called multiple times.

[1] Anna Gál, Shai Halevi, Erez Petrank, and Richard Lipton. 1999. Computing From Partial Solutions. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (COCO '99). IEEE Computer Society, Washington, DC, USA, 34-.


For a constant $d$ the $(k,d)$-hitting set problem is not harder than the original $d$-hitting set (i.e. $k=1$) in view of both approximation and parametrized complexity.
There is a simple reduction from $kd$-HS to $d$-HS. For an instance $(U,\mathcal{F},d,k)$ of the first problem we get an instance of $(U',\mathcal{F'},d)$ of the second one in which every element $e \in U'$ corresponds to a $k$-element subset of $U$, and each set in $\mathcal{F'}$ corresponds to a set in $\mathcal{F}$ in the same way (i.e. mapping all $k$-element subsets of $U$ to elements in $U'$). Since $k$ is a constant the size of new instance is a polynomial function of the size of the first instance ($O(n^k)$).
A hitting set for the first problem corresponds to a hitting set of same cardinality for the second problem and vice versa, hence the reduction is approximation preserving.


Level $k$ bounds in Analysis of Boolean functions

Just posting an answer in order to close the question.

See the helpful comments to the question which contain all the info;

Yes it is vacuous, but if you use the stronger bound you get something nontrivial for large $\epsilon$, of course for fixed $k$ you also have interesting things, it's just the estimates in the book lose too much.
Better bounds are known (thanks ot Yuval) : http://drops.dagstuhl.de/opus/volltexte/2019/10829/pdf/LIPIcs-CCC-2019-7.pdf


$NotTooManyP^{cc}$ class in communication complexity

When the inputs are the indicator functions, set non-disjointness is in NPcc with witnesses

from {0,1,2,3,...,n-2,n-1} $\big(\hspace{-0.04 in}$so in particular is in NotTooManyPcc$\hspace{-0.03 in}\big)$,  but by this paper,

the coUSBP (and thus also P) communication complexity of that problem is $\Theta$(n).

By padding, that means we leave coUSBPcc $\big(\hspace{-0.04 in}$and thus also Pcc$\hspace{-0.03 in}\big)$  as soon

as the number of witnesses is no longer polylogarithmically-bounded.

Also, for all functions  f : {0,1,2,3,...} $\to$ (0,1] ,  if the version with at most

nf(n) correct witnesses equals NPcc then f has a positive lower bound.

Proof:

Let f be any function from {0,1,2,3,...} to (0,1] such that the problem at

the start of this answer can be solved with at most nf(n) correct witnesses.

Let  g : {0,1,2,3,...} $\to$ {0,1,2,3,...}  be given by

g(0) = 0 = g(1)  and otherwise  g(n) = (log(n))1/(f(n))  .

g(0) = 0  and  g(1) = 0 < 1  and  for all other inputs n,

g(n) = (log(n))1/(f(n)) < n1/(f(n)) ≤ n1/1 = n1 = n  .

Accordingly, consider the problem   non-disjointness of subsets of  {0,1,2,3,...,(g(n))-2,(g(n))-1}  whose inputs are padded indicator functions.

By removing the padding, that problem can be solved with at most (g(n))f(n) correct witnesses.

For all integers n such that  1 < n ,  (g(n))f(n) = $\big(\hspace{-0.05 in}$(log(n))1/(f(n))$\hspace{-0.03 in}\big)^{\hspace{.02 in}f\hspace{.02 in}(n)}$ = (log(n))(1/(f(n)))$\cdot$f(n) = (log(n))1 .

Thus the problem is in FewPcc, so by the result you mentioned, it's also in Pcc.

By the communication lower bound in this answer's starting sentence, that means g is

at most polylogarithmic, so 1/(f(n)) is bounded above, so f has a positive lower bound.

I'm not aware of any other results about limited-ambiguity versions of NPcc,

although with inputs as in the rest of this answer, (paddings of, if necessary) the problems

"  Does the intersection have at least _ elements?  "

seem like natural candidates for separating those classes.

$\big(\hspace{-0.04 in}$On the other hand, I wasn't even aware of  unambiguousPcc = Pcc ,

and still know neither a proof of that nor a reference for that.$\hspace{-0.03 in}\big)$


Intuitively, why is the complementary slackness condition true?

As you have noted, complementary slackness follows immediately from strong duality, i.e., equality of the primal and dual objective functions at an optimum.
Complementarity slackness can be thought of as a combinatorial optimality condition, where a zero duality gap (equality of the primal and dual objective functions) can be thought of as a numerical optimality condition.

In order to understand what complementary slackness means, the concept of dual variables as "shadow prices" is useful. The dual variable associated with a primal constraint is called the constraint's shadow price because it can be thought of as how much the objective function would increase if the constraint was relaxed (meaning e.g. the right hand side of a $\le$ constraint was increased).

Complementary slackness says that at an optimal solution, if a shadow price (dual variable) is positive, meaning that the objective function could be increased if the corresponding primal constraint was relaxed, then this primal constraint must be tight. If not, the primal objective function value could be improved (by changing the primal variables in order to make this non-binding primal constraint binding).


Another reason is that this is often without loss of generality, since frequently (though not always - see below) complexity of functions and decision problems are equivalent. Every decision problem can be viewed as a function whose only values are 0 and 1. Conversely, given a function $f$, there are several associated decision problems which usually have the same complexity as $f$, for example:

$\{(x,i) : $ the $i$-th bit of $f(x)$ is 1$\}$.
$\{(x,k) : f(x) \leq k\}$ (or $\geq$)

Here is an example where the complexity of function classes and their associated language classes seem to differ: $\mathsf{P}^{\mathsf{NP}[\log ]} = \mathsf{P}^{\mathsf{NP}}_{tt}$ [Wagner 1987 "Log Query Classes", Hemaspaandra's 1987 thesis, Buss & Hay 1991],  but if $\mathsf{FP}^{\mathsf{NP}[\log ]} = \mathsf{FP}^{\mathsf{NP}}_{tt}$ then $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{P} = \mathsf{UP}$ [Selman 1994].

(Here the oracle $^{\mathsf{NP}[\log]}$ means the machine gets to make $O(\log n)$ queries to any problem in $\mathsf{NP}$ (say, SAT). The notation $\mathsf{P}^{\mathsf{NP}}_{tt}$ means $\mathsf{P}$ with an $\mathsf{NP}$ oracle, but in which the oracle queries are non-adaptive: on input $x$, the if $y_i$ is the $i$-th string queried to the oracle, then $y_i$ does not depend on the answers to any previous oracle calls. Equivalently, on input $x$ the machine builds a list $y_1, \dotsc, y_m$ without querying the oracle, queries the oracle about all of the $y_i$ and gets the answers, then proceeds to compute without querying the oracle again.)


Alan Turing's Contributions to Computer Science

I did not know of these until recently.

1) The LU decomposition of a matrix is due to Turing! Considering how fundamental LU decomposition is, this is one contribution that deserves to be highlighted and known more widely (1948).

2) Turing was the first to come up with a "paper algorithm" for chess. At that point, the first digital computers were still being built (1952).

Chess programming has had an illustrious set of people associated with it, with Shannon, Turing, Herb Simon, Ken Thompson, etc. The last two won the Turing Award. And Simom, of course, won the Nobel as well. (Shannon came up with a way to evaluate a chess position in 1948.)


What would signify hierarchy collapse to first level?

It is perhaps reasonable to think that circuits that people would come up with would come along with easily verifiable proofs of their correctness. (This was indirectly inspired by Dietrich & Wilson's notion of "groups of black box type", and is in the spirit of Hartmanis's "provable complexity.") Towards this end, we consider:

Definition: "Certified $\mathsf{P/poly}$" or "$\mathsf{Cert}$-$\mathsf{P/poly}$" consists of those languages $L$ such that $L$ is in $\mathsf{P/poly}$ and there is a poly-bounded certification of this fact. More precisely, $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$ if there exists a poly-time $V$, and for all $n$, there exists $C_n, \pi_n$ with $\max\{|C_n|,|\pi_n|\} \leq poly(n)$ such that

$V$ is a Cook-Reckhow proof system for the language $\{C : C \text{ correctly computes } L \text{ at length } \ell=\text{# inputs to C}\}$, that is (a) If $C(x) = L(x)$ for all $x \in \Sigma^\ell$, where $\ell$ is the number of inputs to $C$, then there exists a $\pi$ such that $V(C,\pi)=1$ and (b) If there is $x \in \Sigma^\ell$ such that $C(x) \neq L(x)$, then there is no $\pi$ such that $V(C,\pi)=1$.

For all $n$, $C_n$ has $n$ inputs and $V(C_n,\pi_n)=1$.

Then $\mathsf{Cert}\text{-}\mathsf{P/poly}$ contains $\mathsf{NPSV}_t$-uniform $\mathsf{P/poly}$, so it is probably not just $\mathsf{P}$. And we have the desired statement:

Proposition: $\mathsf{NP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longleftrightarrow \mathsf{coNP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longrightarrow \mathsf{PH} = \mathsf{\Sigma_1 P} = \mathsf{\Pi_1 P}$.

Proof: First we show that $\mathsf{Cert}\text{-}\mathsf{P/poly} \subseteq \mathsf{NP}$, giving the final "$\Longrightarrow$" in the statement. Suppose $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$ with verifier $V$ and $V$-verified circuit family $\{(C_n,\pi_n)\}_{n=1,2,3,...}$. The following is a nondeterministic poly-time algorithm for $L$: on input $x$ of length $n$, guess $C_n,\pi_n$, and run $V(C_n,\pi_n)$; if it accepts, then output $C_n(x)$.
Next, we show that Certified $\mathsf{P/poly}$ is closed under complement, giving the first "$\Longleftrightarrow$" in the statement. Suppose $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$, with verifier $V$ as in the above definition. Since $L \in \mathsf{NP}$ by the preceding paragraph, there is some $c$ such that $L \in \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(2^{n^c})$. Let $V'(C',\pi)$ compute as follows: if $C'$ has a negation gate as its output gate, then write $C' = \neg C$, and define $V'(C',\pi) = V(C,\pi)$. Otherwise, $V'(C',\pi)$ checks whether $|\pi|=2^{\ell + \ell^c}$ (where $\ell$ is the number of inputs to $C'$); if not, then $V'$ rejects, and if so, then $V'$ simply enumerates all strings $y$ of length $\ell$, and checks whether $C'(y)=L(y)$, using the $2^{\ell^c}$ deterministic algorithm for $L$, which takes time $poly(|\pi|)$. (This latter yoga was needed to make sure that $V'$ satisfies property 1 in the definition.) If $\{(C_n,\pi_n)\}$ is a certified family of circuits for $L$ with verifier $V$, then $\{(\neg C_n, \pi_n)\}$ is a certified family of circuits for $L^c$ with verifier $V'$. QED


Packing rectangles into convex polygons but without rotations

The problem can be reformulated as picking a maximum number of points inside a convex polygon, such that the every pair of them is in distance (under the $L_\infty$ metric) at least $1$ from each other (just think about the centers of the squares). This in turn is related to the same problem where one uses the regular Euclidean distance. This is in turn related to meshing, where one is interested in breaking a polygon into nicely behaved regions (i.e., you take the Voronoi diagram of the centers [see Centroidal Voronoi tessellations]).

Anyway, a $(1-\epsilon)$-approximation is quite easy. You randomly slide a grid of sidelength $O(1/\epsilon)$. Clip the polygon into the grid, and solve the problem inside each piece of intersection of the polygon with the grid using brute force. An algorithm with running time $O(M*noise(\epsilon))$ should easily follow, where $M$ is the number of points (i.e., rectangles), and $noise(\epsilon)$ is some horrendous function that depends only on $\epsilon$.


How can I find the second cheapest spanning tree?

The second-smallest spanning tree differs from the minimum spanning tree by a single edge swap. That is, to get the second-smallest tree, you need to add one edge that's not already in the minimum spanning tree, and then remove the heaviest edge on the cycle that the added edge forms.

If you already have the minimum spanning tree, this can all be done in linear time. See e.g. V. King, "A simpler minimum spanning tree verification algorithm", Algorithmica 1997, doi:10.1007/BF02526037.


The semantics of computer programs can be understood geometrically in three distinct (and apparently incompatible) ways.

The oldest approach is via domain theory. The intuition behind domain theory arises from the asymmetry behind termination and nontermination.

When treating programs extensionally (ie, only looking at their I/O behavior, and not their internal structure), it is always possible to confirm in finite time that a program halts -- you just wait until it stops. However, it's not possible to confirm that a program doesn't halt, because no matter how long you wait, there is always a halting program that will run for a few more steps than you waited.

As a result, halting and looping can be viewed as forming a topological space (the  Sierpiński space). This lifts to richer notions of observation (via the Scott topology), and you can thereby interpret programs as elements of  topological spaces. These spaces are generally quite surprising from a traditional point of view -- domains are generally not Hausdorff.

The best topological introduction I know to these ideas is Steve Vickers' short and extremely accessible Topology via Logic. It can be understood as a sort of warm-up for Peter Johnstone's significantly more formidable Stone Spaces.

If you are looking for online lecture notes, let me suggest Martin Escardo's Synthetic Topology of Data Types and Classical Spaces.
Another view arises from concurrency theory. A concurrent program can be understood as having multiple valid executions (sequences of states), depending on how races are resolved. Then, the set of executions can be viewed as a space, with each possible sequence of states understood as a path through this space. Then, methods from algebraic topology and homotopy theory can be applied to derive invariants about the program execution.

Nir Shavit and Maurice Herlihy uses this idea to prove the impossibility of certain distributed algorithms, for which they won the 2004 Gödel prize. (See The Topological Structure of Asynchronous Computation.) Eric Goubault has a survey paper explaining the relevant ideas in Some Geometric Perspectives in Concurrency Theory.
Most recently, it has been observed that the structure of the identity type in dependent type theory corresponds very closely with the notion of homotopy type in homotopy theory -- so closely, in fact, that dependent type theory can actually be seen as a sort of "synthetic homotopty theory"! (Vladimir Voevodsky has joked that he spent several years developing a new calculus for homotopy theory, only to discover that his colleagues in the CS department were already teaching it to undergraduates.)

See cody's link above to the homotopy type theory book.

Interestingly, these three views seem incompatible with each other, or at least very difficult to reconcile. Dependent type theory is a total language, so nontermination (and the Scott topology) does not arise in it. It is also confluent, so the view of computations-as-spaces doesn't arise either. Similarly, formulating concurrency in terms of domain theory has proved ferociously difficult, and a completely satisfactory account is still an open problem.


Are there Petri net models with "checking" rather than "taking" transitions?

What you are looking for with "checking edges" are known as Petri nets with read arcs.  In your question you also mention nets with a single read edge, those are called communication-free.  It would be difficult (for me) to point to the original author(s) for these notions, but they are fairly standard.  Relationships between communication-free Petri nets and Parikh images of context-free languages are investigated for instance by Javier Esparza, Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes, FCT 1995, LNCS 965, pp. 221--232, and Fundamenta Informatica 31(1):13--25, 1997.


Examples of successful derandomization from BPP to P

$SL = L$.

$RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace") that $SL = L$, where $S$ stands for "symmetric" and $SL$ is an intermediate class between $RL$ and $L$.

The idea is that you can think of a randomized logspace Turing machine as an polynomial-sized directed graph, where nodes are states of the machine, and an RL algorithm takes a random walk that has good properties. SL corresponds to undirected graphs of this form. Reingold's proof built on work on expander graphs, particularly Reingold, Vadhan, and Wigderson's "zig-zag product", to take any random walk on an undirected graph with good properties and turn it into a psuedorandom walk retaining those properties.

edit this question was posted before the question was explicitly changed to focus exclusively on P vs BPP ... I am leaving it up because it seems to be of interest.


Graphs whose maximal clique intersection graph has bounded chromatic number

For (2), any maximal clique $C$ of $G$ has size at most $\Delta+1$ and each vertex $v \in C$ participates in at most $2^{|N(v)|} \leq 2^\Delta$ maximal cliques. So the degree of $C$ in the clique intersection graph is at most $|C| \cdot 2^{|N(v)|} \leq (\Delta + 1) \cdot 2^\Delta$. Thus the clique intersection graph can be $(\Delta + 1) \cdot 2^\Delta+1$ colored.

The bound can be tightened to  $(\Delta + 1) \cdot 3^{\Delta/3}+1$ by using the Moon Moser bound for the number of maximal cliques.


What is the quantum computational model?

I'll echo Martin Schwartz's recommendation of Nielsen & Chaung as the standard reference; there are many others as well.

Research in the field prefers to consider uniform families of quantum circuits, which (ironically) are directed acyclic networks describing how the state of one or more registers transforms with time, in a way similar to classical boolean circuits. If you wish to learn more, I recommend learning in terms of this model.

I would like to give some qualitative answers to complement Martin's response.

Quantum computation does not actually consider "multiple possibilities at once" --- or more precisely, whether or not you consider them to consider multiple possibilities at once is a matter of your choice of interpretation of quantum mechanics, i.e. a philosophical choice which has no bearing on the ability or predictions of the computational model. ("Considering multiple possibilities at once" corresponds to the "many worlds interpretation" of QM.)
At the very least, one can say that a quantum computer considers multiple possibilities at the same time only to the extent that a randomized computation using coin-flips considers multiple possibilities at the same time. This is because:
Quantum states are generalizations of "the usual" probability distributions --- with some simple but important differences. A probability distribution can be represented as a non-negative real vector whose entries sum to 1: that is, a unit vector in the ℓ1 norm. Probabilistic computations must map ℓ1-unit vectors to other such vectors, and so they are described by stochastic maps. One can describe quantum computation in a similar way, except using ℓ2-unit vectors over ℂ (not restricted to be real or non-negative); transformations are by those maps which preserve the ℓ2-norm, i.e. unitary operations. This difference is not trivial, of course, nor does it explain yet what the coefficients of the quantum state vectors mean. But it may help to explain what is going on with Hilbert spaces and tensor products in quantum computation: to wit, exactly the same things as happen in probabilistic computation. The configuration space of a random bit is a vector in ℝ+2 (where ℝ+ are the non-negative reals); but because random bits can be correlated, we combine the configuration spaces of one or more random bits by taking the tensor product. So the configuration space of two random bits is ℝ+2 ⊗ ℝ+2 ≅ ℝ+4 , or the fully-general space of probability distributions over the four distinct two-bit strings. An operation A on the first of these random bits which does not act on the second is represented by the operator A ⊗ I2 . And so on. The same constructions apply to quantum bits; and we can consider quantum registers over sets of distinguishable elements the same way we consider probability distributions over such sets, again using ℓ2-norm vectors over ℂ. This description actually describes the "pure" quantum states --- the ones for which you can in principle transform in an information-preserving way to a delta-distribution over the bit-string 00...0 (or more precisely, to a state arbitrarily close to this in the ℓ2 norm). On top of the quantum-randomness (of which I have not yet mentioned anything explicit), you can consider vanilla-convexity-randomness corresponding to probabilistic mixtures of quantum states: these are represented by density operators, which can be represented by positive definite matrices with trace 1 (again generalizing "classical" probability distributions, which may be represented by the special case of positive diagonal matrices with trace 1). What is important about this is that, while quantum states are often described as being "exponentially large", this is because they are usually described using the same mathematical structures as probability distributions; why probability distributions are not described as "exponentially large" in the same way is unclear (but ultimately unimportant). The difficulty of simulating quantum states come from this fact, together with the fact that the complex coefficients of these ℓ2-distributions (or the complex off-diagonal terms of the density operators, if you prefer) may cancel in a way that probabilities cannot, rendering estimation of them more difficult.
Entanglement is just another form of correlation. For probabilistic computation on e.g. boolean strings, the only "pure" states (which can be mapped by information-preserving transformations to a delta-peaked distribution on 000...0) are the "standard basis" of delta-peaked distributions on the different boolean strings. Thus, this basis of ℝ+2n is distinguished. But there is no such distinguished basis in quantum mechanics, as far as we can tell --- this is clearest for quantum bits (look up spin 1/2 particles, if you want to know why). As a consequence, there are more information-preserving transformations than just the permutations: a continuous group of them, in fact. This allows would-be quantum computers to transform states in ways which are not possible for probabilistic computers, possibly obtaining an asymptotic advantage over them. But what about entanglement, which many people find mysterious, and claim to be the cause of the speed-up of quantum computers over classical? "Entanglement" here is really just a form of correlation: just as two random variables are correlated if their distribution is a convex combination of more than one product distribution (with different marginals on each variable), two "quantum variables" are entangled if their distribution is a linear combination (with unit ℓ2-norm) of two valid product distributions; it is the same concept under a different norm, and plays a similar role in communication tasks. (For example: "quantum teleportation" in quantum communication corresponds to encoding and decoding a message using a one-time pad classically.) This is a form of correlation which is more general than just classically correlated bits; but the only way to show this is that the correlations encoded in the entangled state apply to more than just one privileged basis. In a manner of speaking, entanglement is a consequence of the absence of a privileged basis.  People like to invoke entanglement as the key element of quantum computation, but this simply doesn't seem to hold water: there have been results showing that entanglement is not quantitatively important for Shor's algorithm to factor large integers, and that indeed a quantum system can have too much entanglement to be useful for a computation. In fact, everywhere that I am aware of that entanglement plays an important role in a quantum protocol is essentially one of communication (where correlations would be expected to play an important role for a classical protocol).

At this point, I begin wading into the domain of personal opinion, so I'll stop here. But hopefully, these remarks might de-mystify some of what is obscure about quantum computation and how it is described.


Which models of computation can be expressed through grammars?

There is a one-to-one correspondence between Chomsky Type-0 grammars and Turing machines.

This is exploied in the Thue programing language which allows you to write Turing-complete programs specified by an initial string and a set of string-rewriting rules (a semi-Thue grammar, which is equivalent to a type-0 grammar).

UPDATE:

Other than esoteric "Turing tar-pit" languages like Thue, various general purpose languages that allow the programmer to extend their own syntax can be used to perform Turing-complete computation during the parsing-compilation stage.

Languages in the Lisp family, in particular Common Lisp, are probably the most obvious examples, but also, broadly speaking, languages with static type checking that doesn't always need to halt, such as C++ with templates, Scala and Qi.


Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?

No, homogeneity is not required when applying this theorem to monotone circuits, and in fact homogeneity is a quite technical restriction that can be removed even in the general case by weakening the theorem a bit. I'll try to explain some things that made this more clear to me. (and hopefully being wrong in the internet will be more provocative than asking a question)
For completeness, the definition of monotonicity is that the subset of field elements used by the circuit cannot produce $0$ by additions and multiplications. The definition of homogeneity is that all gates of the circuit compute a homogeneus polynomial, i.e., a polynomial whose all monomials have the same degree.
The reason why homogeneity is quite technical restriction is that if $f$ is a polynomial that can be computed by an arithmetic circuit of size $t$, then the polynomial $f_d$ consisting of degree $d$ monomials of $f$ can be computed by a homogeneous arithmetic circuit of size $O(d^2 t)$. (This is for example stated as Lemma 2 in the Hyafil's paper.) This means that we can remove the homogeneity requirement from the theorem if we allow a blow up of a factor $O(d^3)$ in the number of terms.
Now, let's see what we need to assume so that the proof works:
First, given a circuit computing a polynomial $f$ with degree $deg(f)$, we need to find a gate $v$ computing a polynomial $f_v$ with degree $deg(f)/3 \le deg(f_v) \le 2deg(f)/3$. We need to assume fan-in 2 for this, but no other assumptions are required, as for any polynomials $g,h$ it holds that $deg(g) + deg(h) \ge deg(g \diamond h)$, where $\diamond$ is either the sum or the product.
Now that we have found the gate $v$, we write the polynomial $f$ as $f = f_v \cdot h + f_{v=0}$, where $f_{v=0}$ is the polynomial obtained from the circuit by setting $v$ to zero. No assumptions are required to see that the polynomial $f_{v=0}$ can be computed with one gate less than $f$, and any assumptions we made about the original circuit that are closed under setting a gate to zero also hold for the circuit computing $f_{v=0}$ (in particular, monotonicity or homogeneity).
One more important thing is that we have to guarantee that the degree of $f_{v=0}$ is at most $deg(f)$.
This holds if we cannot remove $v$ from the circuit without affecting the output and if for all gates in the circuit it holds that $deg(g \diamond h) \ge \max(deg(g), deg(h))$, where $\diamond$ is the operation computed by the gate and $g$ and $h$ the inputs.
This inequality holds for monotone polynomials and for homogeneous polynomials whenever $g \diamond h$ is non-zero, and here we indeed need to assume either monotonicity or homogeneity in order to make the proof work.
What is left is to show that there is such polynomial $h$ with $deg(h) \le 2deg(f)/3$.
The existence of $h$ follows by the observation that the polynomial $f_{v=0}$ is the same as the polynomial $f$, except that some monomials with a factor $f_v$ are missing. This can be proved by induction by separating the polynomials computed by each gate to two parts, the part coming from $v$ and the other part.
The degree of $h \cdot f_v$ is at most $deg(f)$ because the degrees of $f_{v=0}$ and $f$ are at most $deg(f)$.
Now, $deg(h) \le 2deg(f)/3$ follows from the facts that $deg(f_v) \ge deg(f)/3$ and $deg(h \cdot f_v) = deg(h) + deg(f_v)$, which is because the polynomials are over a field, which is a standard assumption in arithmetic circuits [1].
This would complete the proof of the version of the theorem that I stated in the question, but that version is missing an important property: if we assume either homogeneity or monotonicity, can we assume homogeneity or monotonicity of $f_v$ and $h$? For monotonicity, we see that the process of separating $h$ from $f$ by induction is closed under monotone arithmetic. For homogeneity, we have that $f_v$ and $f_{v=0}$ are homogeneous, so $h$ cannot be non-homogeneous because then $f$ would be non-homogeneous.
To summarize, the assumptions of this theorem are:

The polynomials are over a field. This is a standard assumption in arithmetic circuits [1].
The gates of the circuit have fan-in 2.
The circuit is homogeneous or monotone, or we have some other argument to guarantee that $deg(f + g) = \max(deg(f), deg(g))$ for $+$ gates with inputs $f$ and $g$.

[1] Shpilka, Amir, and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Now Publishers Inc, 2010.


Here's a proof (sketch) that doesn't explicitly use duality.  More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below.
EDIT: But, per the comment, the proof applies only to polytopes, not (unbounded) polyhedra!
Let $P\subset \mathbb R^n$ be any polyhedron polytope such that, for all $c\in \mathbb Z^n$, the (optimal) value of the LP $\max\{cx : x\in P\}$ is an integer.
Lemma 1. $P$ is integral.  That is, every extreme point (vertex) of $P$ has integer coordinates.
Proof sketch.

Suppose otherwise for contradiction.  That is, there exists a vertex $x'$ of $P$ with a coordinate $x'_k$ that is not an integer.

Given any cost vector $c\in \mathbb R^n$ such that $x'$ is an optimal solution to the linear program $\max\{c\cdot x : x\in P\}$, say that ``$c\cdot x$ is maximized by $x'$.''

We will use the following, hopefully intuitive, geometric fact: the set of vectors $c$ such that $c\cdot x$ is maximized by $x'$ contains a ball of positive volume in $\mathbb R^n$. (Draw some pictures for intuition.)

Equivalently, there is a vector $c'\in \mathbb R^n$ and an $\epsilon>0$ such that, for all $d\in \mathbb R^n$, if $\max_i |d_i - c'_i| \le \epsilon$, then $d\cdot x$ is maximized by $x'$.

Now define $d' = c'/\epsilon$ (scaling up $c'$ by $1/\epsilon$).

Then, for all $d\in \mathbb R^n$, if $\max_i |d_i - d'_i| \le 1$, then $d\cdot x$ is maximized by $x'$. (Here we use Line 4 above, and that $d\cdot x$ is maximized by $x'$ iff $(\alpha d)\cdot x$ is, provided $\alpha > 0$.  We take $\alpha=1/\epsilon$.)

Define $b$ and $b'$ in $\mathbb Z^n$
by taking $b_i = \lfloor d'_i \rfloor$ for all $i$,
and obtaining $b'$ from $b$ by increasing $b_k$ by 1.  (Recall that $k$ is such that $x'_k$ is not an integer.)

Then $b\cdot x$ is maximized by $x'$ (using $\max_i |b_i-d'_i| \le 1$),
and $b\in\mathbb Z^n$, so (by our assumption on $P$) $b\cdot x'$ is an integer.

By the same reasoning, $b'\cdot x'$ is an integer.  So $(b'-b)\cdot x'$ is an integer.

But $(b'-b)\cdot x'$ equals $x'_k$, which is not an integer. $~~~\Box$


Edge-weight updates in all pair shortest path problem

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

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

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

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

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

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


Here are some upper bounds.

By repeated squaring, the problem is in PSPACE.

There is a slightly better upper bound.  The problem is a special case of the BitSLP problem: Given a straight-line program starting from 0 and 1 with addition, subtraction and multiplication representing an integer N, and given i∈ℕ, decide whether the i-th bit (counting from the least significant bit) of the binary representation of N is 1.  The BitSLP problem is in the counting hierarchy (CH) [ABKM09].  (It is stated in [ABKM09] that it can be shown that the BitSLP problem is in PHPPPPPPPP.)

The membership to CH is often considered as an evidence that the problem is unlikely to be PSPACE-hard, because the equality CH=PSPACE implies that the counting hierarchy collapses.  However, I do not know how strong this evidence is considered to be.

As for the hardness, BitSLP is shown to be #P-hard in the same paper [ABKM09].  However, the proof there does not seem to imply any hardness of the language X in the question.

References

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM Journal on Computing, 38(5):1987–2006, Jan. 2009.  http://dx.doi.org/10.1137/070697926


Complexity theory when an oracle is part of the input

It's called Type-2 Complexity Theory. There's a paper by Cook, Impagliazzo and Yamakami that ties it nicely to the theory of generic oracles.


Deciding bound on Tensor Rank for a fixed value

Testing for constant border-rank can be done in polynomial-time, I'm pretty sure, if you're talking about tensors of fixed arity. More precisely, testing for border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ can be done in something like $k(d_1 d_2 \dotsb d_k)^{2(r+1)}$ evaluations of $(r+1) \times (r+1)$ determinants plus some additional constant work (constant depending on $r$).

Theorem 3.7.1.1 of Landsberg's tensor book ("Inheritance") says that the equations for the variety of tensors of border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \mathbb{C}^{d_2} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ are given by the equations for border-rank $r$ in $\mathbb{C}^r \otimes \mathbb{C}^r \otimes \dotsb \otimes \mathbb{C}^r$ together with all $(r+1) \times (r+1)$ minors of flattenings. Since $r = O(1)$, there are only finitely many equations of the former type.

Border-rank 1 = rank 1, and more generally rank $\leq r$ implies border-rank $\leq r$. But border-rank 2 can have rank anywhere from $2$ to the arity $k$, and border-rank $3$ in arity 3 can have ranks 3, 4, or 5. Beyond that I don't know about testing for rank.


Ordering sequences containing bitvectors for size-change termination

Surely, you want $s_1 < s_2$ if there is a $t$ such that $s_1.t < s_2.t$ and $s_1.u \leq s_2.u$ for every other field $u$. That, at least, gives you a well-founded order.

But there are many other well-founded orders on tuples, e.g. lexicographical order for some order of the fields (though you might need a heuristic to find the order), and various arithmetic combinations of the sizes of each field.

Modern termination checkers will actually simultaneously search for some order that works among a large family of such orders, by generating constraints of the form "There is some lexicographic order, or some polynomial order that shows termination" and trying to satisfy this constraint all at once.

A couple of papers that address termination analysis for bit-vectors and Java, respectively, are:

Termination and Complexity Analysis for Programs with Bitvector Arithmetic by Symbolic Execution

and

Automated Termination Proofs for Java Programs with Cyclic Data

by Giesl & al.


Measuring the connectedness of a graph, and applying it to NP problems

A standard measure of "interconnectedness" is how expanding the graph is. There are several ways to define expansion that are all related. The algebraic way is by measuring the second largest eigenvalue (in absolute value) of the adjacency matrix. The largest eigenvalue is a graph in which all vertices have degree D is always D. If the second largest eigenvalue is much smaller than D, then every two sets of vertices in the graph have roughly as many edges between them as if the edges were chosen at random (this is the expanding mixing lemma).
For more info about graph expansion, see this course:
http://www.math.ias.edu/~boaz/ExpanderCourse/

If the graph is an expander, the entire graph is one big, very interconnected, component.
This is the case with random SAT instances that are believed to be hard (for the appropriate clauses ratio).


Complexity results about locally bipartite graphs

Locally bipartite graphs obviously contain the locally independent (= triangle-free) graphs. According to graphclasses.org, most of the standard graph problems are already NP-complete for triangle-free graphs, and therefore also NP-complete for locally bipartite graphs. The two exceptions are clique (which is obviously polynomial for locally bipartite graphs because the maximum clique is a triangle) and clique cover, which is polynomial for triangle-free graphs but might be harder for locally bipartite graphs.