( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but: Question: Is there a reformul …

It is stated throughout the computational complexity literature that the Dominating Set problem is NP-hard to approximate within a factor of $\Omega(\log n)$. To my knowledge, the …

I want to try my hand at designing quantum algorithms to solve certain problems. I feel like I understand (for example) how Grover's algorithm and Shor's algorithm work, and I'm e …

In one of my complexity analysis, I came up with $O(n^k/2^n)$, where $k$ is a fixed number and $n$ is the size of the data. However I rarely see a big-O written as this. Is there a …

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hun …

1s and 0s that are separated by a single blank and with the tape blank elsewhere? That is, starting with a tape that contains ▭ ▭ ▭ xxxxxxxx▭ yyyyyyyyy▭ ▭ with the Head

I apologize as this question is not really mathematical, and therefore perhaps not well-suited for this site. Please feel free to close it if you think it is not. My reason for ask …

Consider $n$ independent tosses of a fair coin; the sample space has $2^n$ elements. Let $R_n(x)$ be the length of the longest run of heads in outcome $x$. We know that $$E[R_n]=\T …

Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this? To be more specific the cost function I …

I failed to get an answer at http://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here. I …

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of w …

I am reading Landsberg's "Tensors: Geometry and Applications". Here he mentions tensor formulation of Strassen's algorithm and shows that the rank of Strassen's matrix multiplicati …

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent. An induced subgraph $H$ of $G$ is ca …

what is the computational complexity of resolution of singularities of varieties over fields with characteristics 0?

I am a novice with K-theory trying to understand what is and what is not possible. Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the co …