All Questions

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i). I guess complexity of its volume calculate is higher than linear in "N", am I right ? (Is the complexity ...

What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...

I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight. Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to ...

Hello, Let T be a Turing machine such that 1) it operates on the alphabet {0,1}, 2) its set of states is A 3) the language it accepts is $L$ . Does there exists a Turing machine S which also ...