User Mohammad Al-Turkistany

54

votes

13

answers

3k

views

For which algorithms is there a large gap between the theoretical analysis and reality?

Oct 17 '13 at 11:20 Bodo Manthey 355

54

votes

2

answers

3k

views

Can one amplify P=NP beyond P=PH?

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy

May 18 '17 at 12:42 András Salamon 18.3k

53

votes

1

answer

2k

views

Is there a gap amplification type of result for the Graph Isomorphism Problem?

cc.complexity-theory graph-isomorphism pcp

Dec 24 '15 at 7:50 Joe Bebel 2,245

52

votes

7

answers

4k

views

For which problems in P is it easier to verify the result than to find it?

cc.complexity-theory ds.algorithms reference-request

Nov 20 '15 at 18:08 Yonatan N 1,435

50

votes

4

answers

3k

views

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

cc.complexity-theory space-bounded big-picture

Dec 2 '10 at 13:54 Michael Blondin 2,492

47

votes

6

answers

2k

views

Ways for a mathematician to stay informed of current research in complexity theory

cc.complexity-theory soft-question research-practice

Jan 27 '11 at 5:53 Oleksandr Bondarenko 4,165

47

votes

20

answers

7k

views

NP-hard problems on trees

cc.complexity-theory np-hardness tree

Jul 14 '19 at 21:52 Mohammad Al-Turkistany 19.8k

46

votes

5

answers

1k

views

Are there Conservation Laws in Complexity Theory?

cc.complexity-theory big-picture

Jun 28 '14 at 18:18 Mohammad Al-Turkistany 19.8k

45

votes

4

answers

3k

views

Generalized Ladner's Theorem

cc.complexity-theory reference-request np-intermediate

Mar 12 '12 at 10:22 Community♦ 1

45

votes

3

answers

4k

views

An NP-complete variant of factoring.

cc.complexity-theory np-hardness factoring

Apr 8 '17 at 18:39 Mohammad Al-Turkistany 19.8k

45

votes

4

answers

10k

views

Is finding the minimum regular expression an NP-complete problem?

np-hardness fl.formal-languages lg.learning regular-expressions

Nov 10 at 19:31 Hermann Gruber 4,839

44

votes

10

answers

4k

views

Kolmogorov complexity applications in computational complexity

cc.complexity-theory big-list co.combinatorics it.information-theory

Feb 21 '13 at 10:25 András Salamon 18.3k

43

votes

0

answers

953

views

Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

cc.complexity-theory sat planar-graphs succinct

Jan 21 '13 at 13:44 Colin McQuillan 3,446

43

votes

3

answers

5k

views

Wikipedia-style explanation of Geometric Complexity Theory

cc.complexity-theory gct

Sep 3 '17 at 18:00 Abdelmalek Abdesselam 141

43

votes

12

answers

4k

views

Applications of representation theory of the symmetric group

co.combinatorics permutations fourier-analysis gr.group-theory

Mar 22 '14 at 20:57 Community♦ 1

42

votes

22

answers

4k

views

What hierarchies and/or hierarchy theorems do you know?

cc.complexity-theory reference-request big-list survey hierarchy-theorems

Dec 16 at 7:02 Hermann Gruber 4,839

42

votes

8

answers

3k

views

Rigour leading to insight

big-list soft-question proofs

May 25 '11 at 19:56 Community♦ 1

42

votes

4

answers

2k

views

Why have we not been able to develop a unified complexity theory of distributed computing?

big-picture dc.distributed-comp

Jun 14 '17 at 17:11 lamba 131

42

votes

16

answers

4k

views

Physics results in TCS?

soft-question quantum-computing statistical-physics physics

Apr 25 '14 at 22:17 Community♦ 1

42

votes

4

answers

3k

views

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

computability lo.logic proofs

Jul 18 '11 at 18:58 Community♦ 1

41

votes

3

answers

3k

views

What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

cc.complexity-theory cg.comp-geom computing-over-reals computable-analysis

Mar 17 '13 at 16:02 Community♦ 1

41

votes

7

answers

5k

views

Truly random number generator: Turing computable?

reference-request computability turing-machines randomness

Sep 17 '10 at 17:05 Community♦ 1

41

votes

3

answers

3k

views

Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

cc.complexity-theory ds.algorithms graph-theory graph-isomorphism

Jan 30 '17 at 12:42 Community♦ 1

39

votes

5

answers

1k

views

Is there a logic without induction that captures much of P?

cc.complexity-theory lo.logic descriptive-complexity finite-model-theory

Sep 25 '13 at 9:37 Sebastian Siebertz 1,106

39

votes

9

answers

21k

views

What is the difference between non-determinism and randomness?

automata-theory randomness computability

Oct 6 '15 at 9:00 Nikos M. 563

39

votes

13

answers

2k

views

Using error-correcting codes in theory

co.combinatorics big-list coding-theory

Sep 8 '17 at 13:07 Clement C. 3,714

39

votes

9

answers

5k

views

References for TCS proof techniques

reference-request proof-techniques

Sep 30 '14 at 20:43 Community♦ 1

39

votes

3

answers

3k

views

Is the integer factorization problem harder than RSA factorization: $n = pq$?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring

Jun 16 at 8:39 Community♦ 1

38

votes

17

answers

4k

views

Conjectures implying Four Color Theorem

graph-theory co.combinatorics big-list graph-colouring

Aug 6 '14 at 3:42 Jordan Longstaff 11

38

votes

7

answers

5k

views

Many-one reductions vs. Turing reductions to define NPC

cc.complexity-theory np-hardness reductions

Oct 10 '14 at 16:02 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

455 Bookmarks

For which algorithms is there a large gap between the theoretical analysis and reality?

Can one amplify P=NP beyond P=PH?

Is there a gap amplification type of result for the Graph Isomorphism Problem?

For which problems in P is it easier to verify the result than to find it?

Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?

Ways for a mathematician to stay informed of current research in complexity theory

NP-hard problems on trees

Are there Conservation Laws in Complexity Theory?

Generalized Ladner's Theorem

An NP-complete variant of factoring.

Is finding the minimum regular expression an NP-complete problem?

Kolmogorov complexity applications in computational complexity

Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

Wikipedia-style explanation of Geometric Complexity Theory

Applications of representation theory of the symmetric group

What hierarchies and/or hierarchy theorems do you know?

Rigour leading to insight

Why have we not been able to develop a unified complexity theory of distributed computing?

Physics results in TCS?

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

Truly random number generator: Turing computable?

Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

Is there a logic without induction that captures much of P?

What is the difference between non-determinism and randomness?

Using error-correcting codes in theory

References for TCS proof techniques

Is the integer factorization problem harder than RSA factorization: $n = pq$?

Conjectures implying Four Color Theorem

Many-one reductions vs. Turing reductions to define NPC