People who code: we want your input. Take the Survey

Network profile

Dan Brumleve

Reputation

560

581
481
381

2018
2019
2020
2021

Top tag

cc.complexity-theory

Next privilege

1,000 Rep.

See votes

Badges

5

17

Newest

Caucus

Next badge

0/1

Impact

1 post edited

0 helpful flags

114 votes cast

5 Questions

Votes Activity Newest Views

2

7

votes

2

answers

368

views

Most general setting for fine-grained exponential-time complexity classes?

reference-request time-complexity exp-time-algorithms machine-models

Jul 2 '20 at 22:26 Ryan Williams 25.8k

2

7

votes

1

answer

321

views

Examples of quasilinear vs. essentially linear time translatable models

reference-request time-complexity machine-models

Nov 25 '17 at 15:01 Dmytro Taranovsky 2,092

1

4

votes

0

answers

66

views

Complexity of comparing polygon perimeters

cc.complexity-theory tsp

Mar 18 '18 at 18:55 Dan Brumleve 560

4

4

votes

0

answers

263

views

The problem of whether or not every function computable in time $T(n)$ is computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously

reference-request time-complexity space-complexity

Dec 3 '17 at 17:04 Dan Brumleve 560

1

vote

2

answers

189

views

What is the time complexity of base conversion on a multi-tape Turing machine?

reference-request time-complexity turing-machines

Nov 21 '17 at 15:12 Emil Jeřábek 13.2k

Theoretical Computer Science Stack Exchange works best with JavaScript enabled