7
I don't know whether this problem has been studied but I think its #P-hardness should follow directly from the #CSP dichotomy established by Bulatov (Bulatov JACM'13), later simplified by Dyer and Richerby (Dyer and Richerby SICOMP'13). In particular, your problem is equivalent to a CSP with a constraint language on the domain D := {1,2,3} with a single ...
5
Non-termination can be considered an algebraic effect up to a point. It's an exception that cannot be handled. More precisely, we may introduce a nullary operation (constant) $\bot$ which signifies non-termination, but then we disallow handling it, as that would allow us to implement the Halting oracle.
Such treatment of non-termination is a bit naive. A ...
2
You may be interested in this paper. It describes things in terms of monads, but the idea is that you define an 'effect' of making a recursive call. Then appropriately typed functions can be interpreted as recursive definitions. Note for instance on page two where he refers to the, "generic effect," which is something you'll see in work on algebraic effects. ...
2
Theorem: The special case of 1-in-3-SAT where each variable
appears an even number of times is NP-hard.
Proof: Consider an instance $I$ of 1-in-3-SAT, and let $a_1,\ldots,a_n$
be an enumeration of the variables in $I$.
Assume that variables $a_1,\ldots,a_m$ occur an odd number of times,
whereas $a_{m+1},\ldots,a_n$ occur an even number of times.
...
2
From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the graph of their DFA may be embedded. It is shown in [1] that there exist languages of arbitrarily large genus and that this hierarchy is proper.
Bonfante, ...
Only top voted, non community-wiki answers of a minimum length are eligible
