User Mohammad Al-Turkistany

10

42

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

37

votes

8

answers

2k

views

Formal notion for energy complexity of computational problems

cc.complexity-theory physics

Sep 10 at 17:05 user3483902 903

19

34

votes

17

answers

2k

views

Hardness jumps in computational complexity?

cc.complexity-theory

Jan 3 '19 at 18:34 Community♦ 1

18

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

26

votes

5

answers

2k

views

Subexponentially solvable hard graph problems

cc.complexity-theory reference-request

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

7

24

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

5

21

votes

2

answers

992

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

1k

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

8

19

votes

2

answers

879

views

Relationship between symmetry and computational intractability?

cc.complexity-theory graph-isomorphism automorphism symmetry

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

2

17

votes

3

answers

960

views

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

cc.complexity-theory graph-theory

Sep 14 at 18:25 JimN 1,227

1

16

votes

1

answer

408

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

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

6

15

votes

2

answers

728

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

873

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

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,701

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

4

13

votes

1

answer

771

views

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

cc.complexity-theory np-hardness partition-problem

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

2

13

votes

1

answer

237

views

One-way functions with respect to various resource bounds

cc.complexity-theory one-way-function

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

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

3

12

votes

1

answer

385

views

Redundancy and Structure of computational problems

cc.complexity-theory graph-isomorphism

Sep 6 '13 at 16:32 Community♦ 1

4

12

votes

3

answers

497

views

Hard gaps in maximum constraint satisfaction problems?

cc.complexity-theory pcp csp

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

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

490

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

120 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

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?

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

How hard is binary Sudoku puzzle?

Efficient algorithm for existence of permutation with differences sequence?

Redundancy and Structure of computational problems

Hard gaps in maximum constraint satisfaction problems?

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

Completeness under injective Karp reductions