User Mohammad Al-Turkistany

10

41

votes

3

answers

3k

views

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

Jan 30 '17 at 12:42 Community♦ 1

8

36

votes

7

answers

1k

views

Formal notion for energy complexity of computational problems

cc.complexity-theory physics

Mar 2 '13 at 15:51 vzn 10.6k

19

34

votes

17

answers

2k

views

Hardness jumps in computational complexity?

cc.complexity-theory

Jan 3 '19 at 18:34 Community♦ 1

17

34

votes

2

answers

4k

views

Status of Impagliazzo's Worlds?

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

Feb 8 '11 at 19:17 Community♦ 1

10

29

votes

7

answers

2k

views

Proving lower bounds by proving upper bounds

cc.complexity-theory lower-bounds

Dec 8 '10 at 5:15 Community♦ 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,343

7

23

votes

4

answers

3k

views

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

cc.complexity-theory graph-isomorphism

Nov 22 at 10:53 Anna Tomskova 1

5

21

votes

2

answers

974

views

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

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

Sep 8 '16 at 7:46 Community♦ 1

2

21

votes

1

answer

952

views

Is finding Logspace reductions harder than P reductions?

cc.complexity-theory np-hardness

Aug 14 '13 at 15:12 Community♦ 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,261

2

17

votes

2

answers

911

views

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

cc.complexity-theory graph-theory

Feb 4 '14 at 11:40 Mohammad Al-Turkistany 19.8k

1

16

votes

1

answer

405

views

Natural candidates for the hierarchy inside NPI

cc.complexity-theory np-hardness np-intermediate

Feb 8 '13 at 16:26 Community♦ 1

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 Community♦ 1

8

16

votes

2

answers

863

views

Relationship between symmetry and computational intractability?

cc.complexity-theory graph-isomorphism automorphism symmetry

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

6

15

votes

2

answers

673

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 Community♦ 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

852

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

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

987

views

NP-hard problems on expander graphs?

cc.complexity-theory np-hardness expanders

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

4

15

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 Community♦ 1

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 Community♦ 1

5

13

votes

1

answer

272

views

Hard extendability problems

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

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

4

13

votes

1

answer

767

views

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

cc.complexity-theory np-hardness partition-problem

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

2

13

votes

1

answer

236

views

One-way functions with respect to various resource bounds

cc.complexity-theory one-way-function

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

4

12

votes

3

answers

472

views

Completeness under injective Karp reductions

cc.complexity-theory

Sep 7 '19 at 8:40 Vincenzo IOVINO 11

3

12

votes

1

answer

4k

views

How hard is binary Sudoku puzzle?

cc.complexity-theory np-hardness puzzles

Mar 19 '16 at 20:20 Community♦ 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 Community♦ 1

4

12

votes

3

answers

495

views

Hard gaps in maximum constraint satisfaction problems?

cc.complexity-theory pcp csp

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

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 at 10:31 Chris Jefferson 198

4

11

votes

0

answers

3k

views

Efficient recognition of sequences sortable by transpositions?

cc.complexity-theory sorting

Apr 3 '18 at 4:49 Mohammad Al-Turkistany 19.8k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

119 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

Subexponentially solvable hard graph problems

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

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

Is finding Logspace reductions harder than P reductions?

Super-polynomial time approximation algorithms for MAX 3SAT

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?

Relationship between symmetry and computational intractability?

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?

Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

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

Hard extendability problems

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

One-way functions with respect to various resource bounds

Completeness under injective Karp reductions

How hard is binary Sudoku puzzle?

Efficient algorithm for existence of permutation with differences sequence?

Hard gaps in maximum constraint satisfaction problems?

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

Efficient recognition of sequences sortable by transpositions?