User domotorp

4

33

votes

2

answers

1k

views

Does LOGLOG = NLOGLOG?

Mar 8 at 20:33 Frank Vega 119

12

31

votes

6

answers

2k

views

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

cc.complexity-theory np-hardness nt.number-theory combinatorial-game-theory

May 23 '19 at 23:20 Igor Pak 720

6

31

votes

4

answers

2k

views

What is simplest polynomial algorithm for PLANARITY?

graph-algorithms co.combinatorics planar-graphs

Jun 28 '14 at 13:23 Community♦ 1

10

28

votes

2

answers

1k

views

Can we not output the Kolmogorov complexity?

cc.complexity-theory kolmogorov-complexity universal-computation universal-turing-machines

Feb 18 '16 at 4:24 Community♦ 1

3

23

votes

2

answers

829

views

Are shift-chains two-colorable?

co.combinatorics graph-colouring hypergraphs

Nov 14 '19 at 8:40 domotorp 13.2k

4

21

votes

4

answers

1k

views

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

cc.complexity-theory circuit-complexity parity

Jan 25 '16 at 17:15 Emil Jeřábek 12.6k

7

20

votes

4

answers

1k

views

Positive topological ordering, take 3

ds.algorithms np-hardness matrices open-problem topological-sorting

May 15 at 15:59 a3nm 6,946

5

20

votes

1

answer

1k

views

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

fl.formal-languages context-free

Nov 14 '18 at 13:00 Community♦ 1

9

20

votes

2

answers

1k

views

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

cc.complexity-theory cr.crypto-security cryptojacking

Mar 5 '18 at 5:40 Joseph Van Name 1

9

19

votes

2

answers

1k

views

Can we decide whether a permanent has a unique term?

cc.complexity-theory ds.algorithms matrices matching permanent

Feb 14 '20 at 2:58 Neal Young 6,528

3

18

votes

3

answers

757

views

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

cc.complexity-theory complexity-classes randomized-algorithms

Dec 13 at 16:17 Dmytro Taranovsky 2,092

7

18

votes

2

answers

513

views

Is it possible to encrypt a CNF?

cc.complexity-theory cr.crypto-security one-way-function cryptojacking

Feb 10 '18 at 19:26 Mohammad Al-Turkistany 20.1k

2

17

votes

2

answers

402

views

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

big-list primes

Jan 8 '13 at 5:59 Community♦ 1

16

votes

1

answer

253

views

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

ds.algorithms sorting sorting-network

Mar 3 '15 at 22:37 domotorp 13.2k

4

15

votes

0

answers

406

views

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

ds.algorithms sorting sorting-network selection

Dec 9 '14 at 14:40 domotorp 13.2k

1

15

votes

1

answer

231

views

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

cc.complexity-theory circuit-complexity logspace ppad ac0

Oct 17 '14 at 19:34 Emil Jeřábek 12.6k

3

15

votes

0

answers

331

views

Are there other proofs for Barrington's theorem?

circuit-complexity gr.group-theory formulas

Oct 4 '13 at 7:55 domotorp 13.2k

14

votes

3

answers

389

views

Separation of a preprocessed polyhedron and a plane

ds.algorithms cg.comp-geom

May 26 '16 at 16:05 Joseph Stack 1,095

14

votes

0

answers

236

views

Is it possible to make trapdoor board games?

cr.crypto-security board-games

Nov 18 '14 at 20:55 Community♦ 1

2

13

votes

4

answers

557

views

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

cc.complexity-theory np-hardness randomized-algorithms

Mar 21 '17 at 20:27 Community♦ 1

5

12

votes

3

answers

419

views

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

fl.formal-languages context-free

Nov 24 '19 at 21:46 Jeffrey Shallit 6,808

3

12

votes

3

answers

335

views

Is there a simple game with asymmetric complexity?

cc.complexity-theory np board-games pspace

Dec 8 '14 at 8:42 Andras Pluhar 21

1

12

votes

1

answer

563

views

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

cc.complexity-theory time-complexity turing-machines time-hierarchy

Oct 25 '13 at 2:14 zZzZzZ 1

1

11

votes

0

answers

170

views

$\exists \mathbb R$ and IP

cc.complexity-theory interactive-proofs existential-theory-of-the-reals

Apr 26 '19 at 0:18 Kaveh 21k

2

11

votes

0

answers

171

views

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

cc.complexity-theory computability counter-automata

Nov 22 '18 at 9:19 domotorp 13.2k

11

votes

1

answer

533

views

For what c is division by c in AC0?

cc.complexity-theory circuit-complexity ac0

Dec 3 '14 at 15:30 Emil Jeřábek 12.6k

2

11

votes

0

answers

145

views

Is RAMSEY COLORING in $NC$?

cc.complexity-theory graph-theory co.combinatorics ramsey-theory

Aug 4 '14 at 17:56 Kaveh 21k

1

10

votes

0

answers

129

views

Provable BPP Hierarchy

cc.complexity-theory randomness time-hierarchy

Dec 24 at 8:49 domotorp 13.2k

3

10

votes

2

answers

326

views

Are non-deterministic tree-walking automata stronger than deterministic ones?

cc.complexity-theory automata-theory space-bounded dfa

May 9 '11 at 13:49 Community♦ 1

1

9

votes

1

answer

380

views

Is there an algorithm that finds the forbidden minors?

graph-theory decidability graph-minor

Nov 4 '18 at 19:46 domotorp 13.2k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

64 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?

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

Positive topological ordering, take 3

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

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

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?

Is it possible to find the median with a linear size 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?

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

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

Is there a simple game with asymmetric complexity?

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

$\exists \mathbb R$ and IP

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

For what c is division by c in AC0?

Is RAMSEY COLORING in $NC$?

Provable BPP Hierarchy

Are non-deterministic tree-walking automata stronger than deterministic ones?

Is there an algorithm that finds the forbidden minors?