User Mohammad Al-Turkistany

10

43

votes

3

answers

3k

views

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

Jan 30 '17 at 12:42 CommunityBot 1

8

39

votes

8

answers

2k

views

Formal notion for energy complexity of computational problems

cc.complexity-theory physics

Sep 10 '20 at 17:05 user3483902 1,053

19

35

votes

17

answers

2k

views

Hardness jumps in computational complexity?

cc.complexity-theory

Jan 3 '19 at 18:34 CommunityBot 1

20

35

votes

2

answers

4k

views

Status of Impagliazzo's Worlds?

cc.complexity-theory conditional-results average-case-complexity

Feb 8 '11 at 19:17 CommunityBot 1

11

30

votes

7

answers

2k

views

Proving lower bounds by proving upper bounds

cc.complexity-theory lower-bounds

Dec 8 '10 at 5:15 CommunityBot 1

7

26

votes

4

answers

4k

views

What evidence is there that Graph Isomorphism is not in $P$?

cc.complexity-theory graph-isomorphism

Nov 22 '19 at 10:53 Anna Tomskova 1

13

25

votes

5

answers

2k

views

Subexponentially solvable hard graph problems

cc.complexity-theory reference-request

Oct 17 '13 at 12:13 Saeed 3,410

2

22

votes

1

answer

1k

views

Is finding Logspace reductions harder than P reductions?

cc.complexity-theory np-hardness

Aug 14 '13 at 15:12 CommunityBot 1

5

21

votes

2

answers

1k

views

$NP$-completeness of recognizing the difference of two permutations

cc.complexity-theory co.combinatorics np-hardness permutations

Sep 8 '16 at 7:46 CommunityBot 1

20

votes

2

answers

1k

views

Super-polynomial time approximation algorithms for MAX 3SAT

cc.complexity-theory pcp

Dec 10 '11 at 21:52 Opt 1,281

9

20

votes

2

answers

903

views

Relationship between symmetry and computational intractability?

cc.complexity-theory graph-isomorphism automorphism symmetry

Nov 5 '10 at 11:04 Giorgio Camerani 6,575

3

18

votes

3

answers

1k

views

Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

cc.complexity-theory graph-theory

Sep 14 '20 at 18:25 JimN 1,227

1

16

votes

1

answer

464

views

Natural candidates for the hierarchy inside NPI

cc.complexity-theory np-hardness np-intermediate

Nov 19 at 8:10 Joshua Grochow 34.9k

2

16

votes

1

answer

1k

views

NP-hardness of a graph partition problem?

cc.complexity-theory graph-theory graph-isomorphism

Mar 5 '12 at 18:34 CommunityBot 1

4

16

votes

3

answers

2k

views

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

cc.complexity-theory counting-complexity

Oct 24 '10 at 17:42 CommunityBot 1

6

15

votes

2

answers

764

views

GI-hard graph problem not known to be $NP$-complete

cc.complexity-theory graph-theory graph-isomorphism np-intermediate

Jun 5 '18 at 19:35 CommunityBot 1

5

15

votes

3

answers

2k

views

Complexity of edge coloring in planar graphs

cc.complexity-theory graph-theory np-hardness graph-colouring

Jul 20 '16 at 20:29 draks ... 155

4

15

votes

1

answer

892

views

$NP$-complete problem with quasi-polynomial bound on the number of solutions

cc.complexity-theory np

Nov 17 '14 at 4:29 Ryan Williams 26.1k

8

15

votes

10

answers

3k

views

Intractability of NP-complete problems as a principle of physics?

cc.complexity-theory soft-question big-picture experimental

Jul 24 '13 at 0:17 James McIntosh 9

4

15

votes

2

answers

1k

views

NP-hard problems on expander graphs?

cc.complexity-theory np-hardness expanders

Nov 22 '10 at 22:47 Boaz Barak 3,711

6

14

votes

1

answer

278

views

Hard extendability problems

cc.complexity-theory reference-request graph-theory np-hardness

Apr 12 '17 at 18:30 Mohammad Al-Turkistany 20.5k

15

14

votes

3

answers

1k

views

Is there a complexity theory analogue of Rice's theorem in computability theory?

cc.complexity-theory computability np

Jan 18 '14 at 13:19 CommunityBot 1

4

13

votes

1

answer

787

views

Intermediate $\mathsf{NP}$-complete problems?

cc.complexity-theory np-hardness partition-problem

Jan 28 '15 at 21:24 Mohammad Al-Turkistany 20.5k

2

13

votes

1

answer

246

views

One-way functions with respect to various resource bounds

cc.complexity-theory one-way-function

Sep 1 '13 at 23:14 Manu 7,439

3

12

votes

1

answer

5k

views

How hard is binary Sudoku puzzle?

cc.complexity-theory np-hardness puzzles

Mar 19 '16 at 20:20 CommunityBot 1

6

12

votes

1

answer

2k

views

Efficient algorithm for existence of permutation with differences sequence?

cc.complexity-theory co.combinatorics np-hardness permutations

Oct 26 '14 at 23:55 CommunityBot 1

4

12

votes

3

answers

509

views

Hard gaps in maximum constraint satisfaction problems?

cc.complexity-theory pcp csp

Dec 16 '10 at 8:57 Mohammad Al-Turkistany 20.5k

3

12

votes

1

answer

654

views

Using Kolmogorov complexity to establish proof complexity lower bounds?

lower-bounds proof-complexity kolmogorov-complexity

Oct 15 '10 at 10:42 CommunityBot 1

5

11

votes

2

answers

1k

views

Does “Second X is NP-complete” imply “X is NP-complete”?

cc.complexity-theory unique-solution

Oct 8 '19 at 10:31 Chris Jefferson 208

4

11

votes

3

answers

544

views

Completeness under injective Karp reductions

cc.complexity-theory

Sep 7 '19 at 8:40 Vincenzo IOVINO 11

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

121 Questions

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

Formal notion for energy complexity of computational problems

Hardness jumps in computational complexity?

Status of Impagliazzo's Worlds?

Proving lower bounds by proving upper bounds

What evidence is there that Graph Isomorphism is not in $P$?

Subexponentially solvable hard graph problems

Is finding Logspace reductions harder than P reductions?

$NP$-completeness of recognizing the difference of two permutations

Super-polynomial time approximation algorithms for MAX 3SAT

Relationship between symmetry and computational intractability?

Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

Natural candidates for the hierarchy inside NPI

NP-hardness of a graph partition problem?

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

GI-hard graph problem not known to be $NP$-complete

Complexity of edge coloring in planar graphs

$NP$-complete problem with quasi-polynomial bound on the number of solutions

Intractability of NP-complete problems as a principle of physics?

NP-hard problems on expander graphs?

Hard extendability problems

Is there a complexity theory analogue of Rice's theorem in computability theory?

Intermediate $\mathsf{NP}$-complete problems?

One-way functions with respect to various resource bounds

How hard is binary Sudoku puzzle?

Efficient algorithm for existence of permutation with differences sequence?

Hard gaps in maximum constraint satisfaction problems?

Using Kolmogorov complexity to establish proof complexity lower bounds?

Does “Second X is NP-complete” imply “X is NP-complete”?

Completeness under injective Karp reductions