# Questions tagged [time-complexity]

Time complexity of decision problems or relations among time-bounded complexity classes. (Use the [analysis-of-algorithms] tag for the time taken by particular algorithms.)

411 questions
Filter by
Sorted by
Tagged with
66 views

### Complexity of a variation of edge cover for paths

Consider the following problem. Given a directed acyclic graph $G=(V,E)$ with a designated source vertex $s\in V$ and sink vertex $t\in V$, and natural number $k$. Find a smallest set $E'\subseteq E$ ...
1 vote
94 views

• 381
263 views

### Is parity of GI easy?

Given graphs $G,H$ let $N(G,H)$ be the number of isomorphisms between them. Is there polynomial time algorithm to compute $N(G,H)\bmod 2^t$ for every fixed $t\geq1$?
• 13.1k
1 vote
161 views

• 2,252
1 vote
138 views

### Complexity of analytic functions and integrals

There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this: To which class do analytic elementary functions, including trigonometric ones, ...
285 views

66 views

### computational complexity of sparse matrix powers

Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I ...
• 209