2
votes
1answer
35 views

Complexity class of generating all permutations

What is the complexity of the following problem (i.e. to what complexity class does it belong)? Given a positive integer $n$, provide all permutations of the sequence $\{1, 2, \ldots, n\}$.
0
votes
1answer
849 views

Proof that computing composition of permutations is in P

Consider the following problem: A permutation on the set ${1,…,k}$ is a one-to-one, onto function on this set. When $p$ is a permutation, $p^t$ means the composition of $p$ with itself $t$ times. ...
0
votes
0answers
129 views

Maximum number of truths in an optimized truth table.

I have a math-related question: I have a set of predicates that need to be evaluated. These predicates can have two kinds of operators; AND/OR. When such an expression is constructed my code builds ...