Kummer's cardinality theorem states that a language is recursive
if a Turing machine can exclude for any n words one of the
n + 1 possibilities for the number of words in the language. It
is known that this theorem does not hold for polynomial-time
computations, but there ... more >>>

We study approximation hardness and satisfiability of bounded
occurrence uniform instances of SAT. Among other things, we prove
the inapproximability for SAT instances in which every clause has
exactly 3 literals and each variable occurs exactly 4 times,
and display an explicit ... more >>>

We consider possible equality QMA=PP and give an argument
against it. Namely, this equality implies that PP contains PH. The argument is based on the strong form of Toda's theorem and
the strengthening of the proof for inclusion $QMA\subseteq PP$ due to Kitaev and Watrous.

more >>>