17

TL;DR. The metamathematics of binding are subtle: they seem trivial but aren't — whether you deal with (higher-order) logics or 𝜆-calculus. They're so subtle that binding representations form an open research field, with a competition (the POPLmark challenge) some years ago. There are even jokes by people in the field about the complexity of approaches to ...


5

On Closure Properties of #P in the Context of PF ∘ #P Note that FP and PF are the same complexity class. It is stated in proposition 2.1 on page 3 that FP ∘ #P = FP $^{\# P{ [1]}}$


4

There is an article from Alan Selman: A taxonomy of complexity classes of functions Please note, that i found this reference in an Answer (by Joshua Grochow) for this Question: Complexity class when reducing decision problem to function problem Note also the Comments from Kaveh: If you have a function you can look at the bit graph of the function which ...


4

Indeed there is a Wikipedia entry on metaprogramming. The question "What are staged functions?" on cs.stackexchange is also relevant.


3

(2.) implies (1.) by a standard compactness argument. First note that it suffices to exhibit a Cook-reduction $M$ from $R$ to $S'$ for any relation $S'$ such that $S(x,y)\iff S'(x,y)$ for all but finitely many values of $x$. This is because we can then give a Cook-reduction from $R$ to $S$ by simulating $S'$ using $S$. Suppose for contradiction that there ...


2

I already answered how to construct such terms in a related question, so let me just amend that answer with some equations. A standard type constructor which has constructors and eliminators, for instance $A \times B$ has pairing and projections, will have: $\beta$-rules which says how destructors operate on constructors, for instance: $\pi_1 (a,b) \equiv ...


1

Consider the function $f(x, y) = 1 - e^{-(x + y)}$. Now $f(0, 0) = 0$, $f$ is increasing and concave, since $g(t) = -e^{-t}$ is concave. But $f(1, 0) + f(0, 1) = 2(1 - e^{-1}) > 1 - e^{-2} = f(1, 1)$, hence the claim doesn't hold even when $n = 2$. The claim doesn't hold for convex functions either. $f(x, y) = 2(x + y) + |x - y|$ is one counterexample: $...


1

Let $n=1$. Let $\mu$ be the usual Lebesgue length measure on $[1/2,1]$, and let $\mu$ be the negative of the usual Lebesgue length measure on $[0,1/2]$. In particular, Lebesgue measure is $|\mu|$. Let $\mathcal U\subseteq [0,1]$ be a set of Lebesgue measure 0. (For instance, $\mathcal U$ could be the set of all numbers whose binary expansion does not ...


Only top voted, non community-wiki answers of a minimum length are eligible