Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active Hot Week Month

-1

votes

1

answer

64

views

Time complexity for multiplying two lower triangular matrices

cc.complexity-theory ds.algorithms time-complexity matrices recursion

answered 9 hours ago Pranav Bisht 1

11

votes

3

answers

355

views

Applications of sunflower lemma in theoretical computer science

cc.complexity-theory co.combinatorics set-system

modified Mar 29 at 20:48 Emil Jeřábek 11.4k

7

votes

5

answers

337

views

NP-complete decision problems on deterministic automata

cc.complexity-theory np-hardness fl.formal-languages automata-theory np-complete

modified Mar 24 at 21:25 Hermann Gruber 4,359

2

votes

0

answers

99

views

Proof systems induced by NP-complete problems

cc.complexity-theory reference-request proof-complexity

modified Mar 24 at 17:13 Mohammad Al-Turkistany 19.6k

7

votes

1

answer

307

views

Technical lemma about curves used in original proof of PCP theorem

cc.complexity-theory algebra pcp

modified Mar 20 at 21:49 A.2 331

45

votes

9

answers

7k

views

Best Upper Bounds on SAT

cc.complexity-theory ds.algorithms sat upper-bounds

modified Mar 20 at 20:16 Hermann Gruber 4,359

-2

votes

0

answers

39

views

performance vs complexity given an optimization problem

cc.complexity-theory complexity-classes

asked Mar 18 at 18:26 Deniz Sargun 1

5

votes

0

answers

127

views

What research is being done in classical complexity theory?

cc.complexity-theory soft-question

asked Mar 17 at 16:44 exfret 593

2

votes

0

answers

94

views

Is PP invariant under changing its cut-off from 1/2 to another number?

cc.complexity-theory complexity-classes time-complexity

modified Mar 11 at 17:47 user138901 347

5

votes

2

answers

1k

views

Attempted proofs of P vs NP

cc.complexity-theory

modified Mar 11 at 14:59 Yasunori Ohto 1

-2

votes

1

answer

159

views

Is it possible to sort by only knowing the sign of pairwise sums?

cc.complexity-theory ds.algorithms sorting

modified Mar 10 at 15:00 Community♦ 1

3

votes

1

answer

469

views

Time complexity of d-dimensional convex hull

cc.complexity-theory cg.comp-geom time-complexity lower-bounds convex-hull

modified Mar 10 at 6:01 Inuyasha yagami 3

4

votes

1

answer

114

views

Is $L \subset 1NL$ when $L \neq NL$?

cc.complexity-theory complexity-classes turing-machines nondeterminism space-complexity

answered Mar 9 at 10:17 domotorp 12.7k

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled