In this note we study the computational complexity of feedback arc set counting problems in directed graphs, highlighting some subtle yet common properties of counting classes. Counting the number of feedback arc sets of cardinality $k$ and the total number of feedback arc sets are $\#P$-complete problems, while counting the number of minimum feedback arc sets is only proven to be $\#P$-hard. Indeed, this latter problem is $\#OptP[\log n]$-complete, hence if it belongs to $\#P$ then $P=NP$.

A $t$-dimensional orthogonal representation of a hypergraph is an assignment of nonzero vectors in $R^t$ to its vertices, such that every hyperedge contains two vertices whose vectors are orthogonal. The orthogonality dimension of a hypergraph $H$, denoted by ${\overline{\xi}}(H)$, is the smallest integer $t$ for which there exists a $t$-dimensional \ orthogonal representation of $H$. In this paper we study computational aspects of the orthogonality dimension of graphs and hypergraphs. We prove that for every $k \geq 4$, it is $NP$-hard (resp. quasi-$NP$-hard) to distinguish $n$-vertex $k$-uniform hypergraphs $H$ with ${\overline{\xi}}(H) \leq 2$ from those satisfying ${\overline{\xi}}(H) \geq \Omega(\log^\delta n)$ for some constant $\delta>0$ (resp. ${\overline{\xi}}(H) \geq \Omega(\log^{1-o(1)} n)$). For graphs, we relate the $NP$-hardness of approximating the orthogonality dimension to a variant of a long-standing conjecture of Stahl on the multichromatic numbers of Kneser graphs. We also consider the algorithmic problem in which given a graph $G$ with ${\overline{\xi}}(G) \leq 3$ the goal is to find an orthogonal representation of $G$ of as low dimension as possible, and provide a polynomial time approximation algorithm based on semidefinite programming.