User Mohammad Al-Turkistany - Theoretical Computer Science Stack Exchange

Mohammad Al-Turkistany

Member for 13 years, 8 months
Last seen this week

turkistany.blogspot.com
Makkah, Saudi Arabia

172 Answers

Score Activity Newest

102 votes

What Books Should Everyone Read?

answered Nov 22, 2010 at 16:17

27 votes

Accepted

Did "Where the really hard problems are" hold up? What are current ideas on the subject?

answered Jan 23, 2017 at 14:16

25 votes

NP-hard problems on trees

answered Sep 12, 2010 at 23:07

24 votes

Techniques for showing that problem is in hardness "limbo"

answered Feb 6, 2014 at 8:04

24 votes

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

answered Nov 14, 2015 at 17:08

22 votes

Accepted

Curious about computer-assisted NP-completeness proofs

answered Jan 31, 2015 at 16:19

22 votes

A simple decision problem whose decidability is not known

answered Sep 6, 2013 at 8:41

22 votes

Data for testing graph algorithms

answered Aug 29, 2010 at 14:25

20 votes

Accepted

Can you identify the sum of two permutations in polynomial time?

answered Jun 17, 2013 at 10:29

18 votes

Accepted

Counterexample for Corneil's efficient algorithm for Graph Isomorphism

answered Aug 27, 2013 at 13:53

15 votes

Easy decision problem, hard search problem

answered Oct 2, 2010 at 17:20

15 votes

Major unsolved problems in theoretical computer science?

answered Oct 29, 2011 at 21:11

14 votes

Accepted

Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

answered Nov 5, 2013 at 13:55

13 votes

Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?

answered Jun 9, 2011 at 6:26

12 votes

Problems that are NP-complete under randomized or P/poly reductions.

answered Feb 9, 2011 at 7:08

12 votes

"Natural" decidable problems known not to be in NP.

answered Apr 11, 2011 at 20:30

12 votes

How hard is unshuffling a string?

answered Jun 24, 2013 at 17:06

12 votes

Accepted

NP-complete problem with polynomially many certificates?

answered Jul 16, 2014 at 13:17

12 votes

Accepted

NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

answered Feb 14, 2017 at 13:21

11 votes

In the neutral zone between polynomial and sub-exponential

answered Jun 20, 2020 at 16:26

11 votes

Problems that are easy on unweighted graphs, but hard for weighted graphs

answered Feb 18, 2014 at 4:47

11 votes

List of theorems stating that P does not equal NP if and only if

answered Mar 7, 2014 at 14:36

11 votes

Accepted

What is the proof that the existence of one-way-functions implies $P \neq NP$?

answered Oct 2, 2015 at 20:01

11 votes

Accepted

Reference for Levin's optimal factoring algorithm ?

answered Apr 28, 2011 at 14:13

11 votes

List of theorems stating that P does not equal NP if and only if

answered Jan 20, 2012 at 15:08

11 votes

Beautiful results in TCS

answered Feb 27, 2012 at 19:36

11 votes

Problems Between P and NPC

answered Dec 23, 2010 at 16:39

10 votes

NP-hard problems on cographs

answered Feb 7, 2011 at 14:15

10 votes

The significance of NP-Hard Problems in Cryptography

answered Oct 25, 2011 at 11:52

10 votes

Models of random graphs, for real computer networks

answered Apr 28, 2011 at 23:04

1