Explore Our Questions

more tags

Active 2 Featured Hot Week Month

5

votes

1

answer

36

views

Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?

complexity-theory time-complexity

modified 2 days ago dkaeae 1,768

0

votes

0

answers

7

views

Time complexity of well know constraint satisfaction problem algorithms with heuristics

time-complexity space-complexity constraint-satisfaction constraint-programming

asked Feb 21 at 0:29 Thuriya Thwin 4

2

votes

2

answers

26

views

An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$

time-complexity number-theory multiplication modular-arithmetic computer-algebra

answered Feb 20 at 20:11 D.W.♦ 99.4k

1

vote

2

answers

24

views

Calculating the number of assignments satisfying a general propositional formula

time-complexity satisfiability polynomial-time

modified Feb 20 at 16:21 dkaeae 1,768

2

votes

4

answers

382

views

Why aren't primality tests easily linear in time complexity?

algorithm-analysis time-complexity runtime-analysis

modified Feb 20 at 15:38 Bilal Hayat Butt 1

0

votes

0

answers

22

views

Is there a known lower bound on the time/space complexity of DFA minimization?

time-complexity automata finite-automata space-complexity

asked Feb 20 at 15:03 Reed Oei 143

0

votes

1

answer

34

views

Merge sort: sorting and merging complexity $\Theta(n)$

algorithms time-complexity master-theorem mergesort

answered Feb 20 at 14:26 Nathan 57

3

votes

3

answers

95

views

Complexity of forming a min heap out of a given array with k inversions

time-complexity heaps

modified Feb 20 at 9:43 Amir H 81

1

vote

1

answer

27

views

Max number of configurations of a Turing Machine

turing-machines time-complexity space-complexity

answered Feb 19 at 20:51 D.W.♦ 99.4k

3

votes

0

answers

17

views

Is the definition of $\textbf{BPP}$ robust for doubly exponential small (or even smaller) error?

complexity-theory time-complexity probabilistic-algorithms

modified Feb 19 at 10:44 dkaeae 1,768

1

vote

2

answers

73

views

What's the worst case complexity of Robert W. Floyd's cycle detection algorithm?

time-complexity

answered Feb 19 at 4:07 rici 4,485

1

vote

1

answer

35

views

Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$

complexity-theory turing-machines time-complexity

modified Feb 18 at 22:23 Jazz 177

2

votes

2

answers

132

views

Decidability of equivalence to existential formulas

formal-languages time-complexity logic first-order-logic

modified Feb 18 at 8:00 F.D.C. 13

0

votes

0

answers

27

views

Time complexity of quicksort for arrays in increasing or descreasing order

algorithms time-complexity sorting quicksort

modified Feb 17 at 10:46 Discrete lizard♦ 4,214

Browse More Questions

Computer Science Stack Exchange works best with JavaScript enabled