User Mohammad Al-Turkistany

10

40

votes

3

answers

2k

views

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

Jan 30 '17 at 12:42 Community♦ 1

8

35

votes

7

answers

1k

views

Formal notion for energy complexity of computational problems

cc.complexity-theory physics

Mar 2 '13 at 15:51 vzn 8,480

19

33

votes

17

answers

2k

views

Hardness jumps in computational complexity?

cc.complexity-theory

Jan 3 at 18:34 Andras Farago 5,641

16

32

votes

2

answers

3k

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 2,739

7

22

votes

4

answers

2k

views

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

cc.complexity-theory graph-isomorphism

Dec 20 '15 at 18:18 Community♦ 1

5

21

votes

2

answers

926

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

20

votes

1

answer

828

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 851

2

17

votes

2

answers

811

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

1

16

votes

1

answer

375

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

803

views

Relationship between symmetry and computational intractability?

cc.complexity-theory graph-isomorphism automorphism symmetry

Nov 5 '10 at 11:04 Giorgio Camerani 3,892

6

15

votes

2

answers

608

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

4

15

votes

3

answers

1k

views

Complexity of edge coloring in planar graphs

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

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

4

15

votes

1

answer

810

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

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

935

views

NP-hard problems on expander graphs?

cc.complexity-theory np-hardness expanders

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

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

13

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 Mohammad Al-Turkistany 13.9k

5

13

votes

1

answer

821

views

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

cc.complexity-theory unique-solution

Jun 20 '18 at 15:34 Mohammad Al-Turkistany 13.9k

4

13

votes

1

answer

731

views

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

cc.complexity-theory np-hardness partition-problem

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

1

13

votes

1

answer

212

views

One-way functions with respect to various resource bounds

cc.complexity-theory one-way-function

Sep 1 '13 at 23:14 Manu 5,274

4

12

votes

1

answer

249

views

Hard extendability problems

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

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

3

12

votes

1

answer

3k

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

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

3

11

votes

1

answer

354

views

Redundancy and Structure of computational problems

cc.complexity-theory graph-isomorphism

Sep 6 '13 at 16:32 Community♦ 1

3

11

votes

3

answers

453

views

Hard gaps in maximum constraint satisfaction problems?

cc.complexity-theory pcp csp

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

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

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

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

One-way functions with respect to various resource bounds

Hard extendability problems

How hard is binary Sudoku puzzle?

Efficient algorithm for existence of permutation with differences sequence?

Efficient recognition of sequences sortable by transpositions?

Redundancy and Structure of computational problems

Hard gaps in maximum constraint satisfaction problems?