# Tagged Questions

Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

17 views

25 views

### Algorithmic complexity of testing whether a permutation belongs to a subgroup generated by a set of permutations

Let $S=\{S_1,S_2,S_3,\ldots,S_m\}$ be a set of permutations on $n$ symbols (in other words $S$ is a subset of a symmetric group on $n$ symbols) and $P$ be a permutation on $n$ symbols. What is the ...
56 views

### How quickly can this function be computed?

I can show that $\lambda (n)=i^{\tau(n^{2})-1}$, where $\lambda (n)$ is the Liouville function, $\tau(n)$ is the divisor function, and $i$ is the imaginary unit. My question is as stated, and what is ...
16 views

### Is there any example of real-life decidable problem that is not in EXP?

In order to illustrate an introduction on computational complexity, I am trying to find examples of real-life problems for every one of the main complexity classes: $P$, $NP$, $EXP$, $R$ and ...
Let $\varphi$ be a boolean formula of $n$ variables and $(t_1, t_2,\ldots,t_n) \in \{0, 1\}$ be an assignment. How to describe a polynomial-time algorithm to compute $\varphi(t_1,t_2,\dots, t_n)$?