User domotorp

34 votes

2 answers

1k views

Does LOGLOG = NLOGLOG?

asked Dec 24, 2010 at 7:47

31 votes

5 answers

3k views

Is there a natural problem on the naturals that is NP-complete?

asked Oct 30, 2012 at 15:19

31 votes

4 answers

2k views

What is simplest polynomial algorithm for PLANARITY?

asked Jun 22, 2014 at 10:36

27 votes

2 answers

1k views

Can we not output the Kolmogorov complexity?

asked Apr 26, 2015 at 11:37

23 votes

2 answers

836 views

Are shift-chains two-colorable?

asked Nov 12, 2010 at 7:02

23 votes

1 answer

907 views

FOCS virtual fee $600

asked Jan 3, 2022 at 7:40

21 votes

4 answers

1k views

What is the minimum size of a circuit that computes PARITY?

asked Oct 10, 2014 at 18:30

20 votes

4 answers

1k views

Positive topological ordering, take 3

asked Oct 1, 2010 at 10:07

20 votes

2 answers

1k views

Can any computational challenge be transformed to proof-of-work?

asked Dec 28, 2017 at 20:51

20 votes

1 answer

2k views

Number of words of length n in a context-free language

asked Nov 14, 2018 at 10:29

19 votes

2 answers

1k views

Can we decide whether a permanent has a unique term?

asked Oct 8, 2010 at 8:17

18 votes

3 answers

795 views

In what class are randomized algorithms that err with exactly 25% chance?

asked Nov 28, 2013 at 20:57

18 votes

2 answers

526 views

Is it possible to encrypt a CNF?

asked Dec 29, 2017 at 8:17

17 votes

2 answers

410 views

What are TCS conjectures that were proved for primes and small values but then turned out to be false?

asked Jan 6, 2013 at 12:46

16 votes

1 answer

263 views

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

asked Mar 1, 2015 at 21:23

15 votes

1 answer

259 views

Does ${\bf AC^0PAD} = {\bf PPAD}$?

asked Oct 15, 2014 at 19:38

15 votes

0 answers

375 views

Are there other proofs for Barrington's theorem?

asked Oct 4, 2013 at 7:55

14 votes

3 answers

396 views

Separation of a preprocessed polyhedron and a plane

asked Dec 4, 2011 at 15:45

14 votes

0 answers

243 views

Is it possible to make trapdoor board games?

asked Nov 17, 2014 at 21:59

14 votes

0 answers

495 views

Is it possible to find the median with a linear size sorting network?

asked Dec 9, 2014 at 14:40

13 votes

4 answers

631 views

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

asked Mar 15, 2017 at 18:22

12 votes

3 answers

483 views

Is the complement of { www | … } context-free?

asked Jan 12, 2019 at 20:37

12 votes

1 answer

615 views

Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

asked Mar 27, 2013 at 15:22

11 votes

1 answer

568 views

For what c is division by c in AC0?

asked Dec 2, 2014 at 22:23

11 votes

3 answers

353 views

Is there a simple game with asymmetric complexity?

asked Dec 4, 2014 at 22:05

11 votes

0 answers

146 views

Is RAMSEY COLORING in $NC$?

asked Aug 2, 2014 at 19:46

11 votes

0 answers

178 views

$\exists \mathbb R$ and IP

asked Apr 21, 2019 at 21:44

11 votes

0 answers

217 views

Can two-tape read-only Turing machines recognize any recursive language?

asked Nov 22, 2018 at 9:13

10 votes

6 answers

808 views

Can neural networks be used to devise algorithms?

asked Dec 9, 2017 at 12:36

10 votes

0 answers

182 views

Provable BPP Hierarchy

asked Dec 23, 2020 at 20:53

Stack Exchange Network

68 Questions

Does LOGLOG = NLOGLOG?

Is there a natural problem on the naturals that is NP-complete?

What is simplest polynomial algorithm for PLANARITY?

Can we not output the Kolmogorov complexity?

Are shift-chains two-colorable?

FOCS virtual fee $600

What is the minimum size of a circuit that computes PARITY?

Positive topological ordering, take 3

Can any computational challenge be transformed to proof-of-work?

Number of words of length n in a context-free language

Can we decide whether a permanent has a unique term?

In what class are randomized algorithms that err with exactly 25% chance?

Is it possible to encrypt a CNF?

What are TCS conjectures that were proved for primes and small values but then turned out to be false?

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

Does ${\bf AC^0PAD} = {\bf PPAD}$?

Are there other proofs for Barrington's theorem?

Separation of a preprocessed polyhedron and a plane

Is it possible to make trapdoor board games?

Is it possible to find the median with a linear size sorting network?

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

Is the complement of { www | … } context-free?

Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

For what c is division by c in AC0?

Is there a simple game with asymmetric complexity?

Is RAMSEY COLORING in $NC$?

$\exists \mathbb R$ and IP

Can two-tape read-only Turing machines recognize any recursive language?

Can neural networks be used to devise algorithms?

Provable BPP Hierarchy