User domotorp

4

32

votes

1

answer

1k

views

Does LOGLOG = NLOGLOG?

Dec 4 '12 at 3:29 Hsien-Chih Chang 張顯之 6,113

11

30

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 at 23:20 Igor Pak 435

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

6

28

votes

4

answers

2k

views

What is simplest polynomial algorithm for PLANARITY?

graph-algorithms co.combinatorics planar-graphs

Jun 28 '14 at 13:23 domotorp 9,279

2

21

votes

2

answers

679

views

Are shift-chains two-colorable?

co.combinatorics graph-colouring hypergraphs

Jul 10 '18 at 8:52 domotorp 9,279

4

21

votes

4

answers

935

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 10.8k

7

20

votes

4

answers

1k

views

Positive topological ordering, take 3

ds.algorithms np-hardness open-problem matrices

Jan 14 at 17:04 ORILL_Code 1

4

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 Gamow 4,487

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

7

17

votes

2

answers

481

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 13.9k

1

17

votes

3

answers

651

views

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

cc.complexity-theory complexity-classes randomized-algorithms

Sep 11 '17 at 20:12 Dmytro Taranovsky 1,512

2

17

votes

2

answers

374

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

234

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 9,279

7

16

votes

1

answer

747

views

Can we decide whether a permanent has a unique term?

cc.complexity-theory ds.algorithms matrices matching permanent

Nov 22 '10 at 9:26 Community♦ 1

1

15

votes

1

answer

209

views

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

cc.complexity-theory circuit-complexity logspace ppad ac0

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

14

votes

3

answers

371

views

Separation of a preprocessed polyhedron and a plane

ds.algorithms cg.comp-geom

May 26 '16 at 16:05 Joseph Stack 825

4

14

votes

0

answers

357

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 9,279

3

14

votes

0

answers

322

views

Are there other proofs for Barrington's theorem?

circuit-complexity gr.group-theory formulas

Oct 4 '13 at 7:55 domotorp 9,279

13

votes

0

answers

228

views

Is it possible to make trapdoor board games?

cr.crypto-security board-games

Nov 18 '14 at 20:55 Community♦ 1

1

12

votes

4

answers

507

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

1

11

votes

0

answers

162

views

$\exists \mathbb R$ and IP

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

Apr 26 at 0:18 Kaveh 16.4k

2

11

votes

0

answers

136

views

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

cc.complexity-theory computability counter-automata

Nov 22 at 9:19 domotorp 9,279

3

11

votes

3

answers

306

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

11

votes

1

answer

485

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 10.8k

11

votes

1

answer

516

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

4

10

votes

3

answers

322

views

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

fl.formal-languages context-free

Feb 1 at 20:27 Marzio De Biasi 18.9k

2

10

votes

0

answers

142

views

Is RAMSEY COLORING in $NC$?

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

Aug 4 '14 at 17:56 Kaveh 16.4k

1

9

votes

1

answer

311

views

Is there an algorithm that finds the forbidden minors?

graph-theory decidability graph-minor

Nov 4 '18 at 19:46 domotorp 9,279

2

9

votes

5

answers

665

views

Can neural networks be used to devise algorithms?

cc.complexity-theory ds.algorithms machine-learning ne.neural-evol

Dec 13 '17 at 20:29 CinchBlue 172

1

9

votes

1

answer

194

views

What is known about the hardness of the chromatic index for restricted graph classes?

graph-theory np-hardness graph-colouring

Jul 7 '16 at 13:39 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

58 Questions

Does LOGLOG = NLOGLOG?

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

Can we not output the Kolmogorov complexity?

What is simplest polynomial algorithm for PLANARITY?

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?

Is it possible to encrypt a CNF?

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

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?

Can we decide whether a permanent has a unique term?

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

Separation of a preprocessed polyhedron and a plane

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

Are there other proofs for Barrington's theorem?

Is it possible to make trapdoor board games?

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

$\exists \mathbb R$ and IP

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

Is there a simple game with asymmetric complexity?

For what c is division by c in AC0?

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

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

Is RAMSEY COLORING in $NC$?

Is there an algorithm that finds the forbidden minors?

Can neural networks be used to devise algorithms?

What is known about the hardness of the chromatic index for restricted graph classes?