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
