Stack Exchange Network

Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Loading…
  1. 0
  2. +0
    • Tour Start here for a quick overview of the site
    • Help Center Detailed answers to any questions you might have
    • Meta Discuss the workings and policies of this site
    • About Us Learn more about Stack Overflow the company
    • Business Learn more about hiring developers or posting ads with us
  3. Log in Sign up
  4. current community

    • Theoretical Computer Science
      help chat
    • Theoretical Computer Science Meta

    your communities

    Sign up or log in to customize your list.

    more stack exchange communities

    company blog
Theoretical Computer Science
  1. Home
    1. Questions
    2. Tags
    3. Users
    4. Unanswered
    5. Jobs
Profile Activity
Meta user
Network profile
Mohammad Al-Turkistany

Reputation

20,154
  • 20.2k
  • 18.4k
  • 16.6k
  • 2018
  • 2019
  • 2020
  • 2021

Top tag

cc.complexity-theory

Next privilege

25,000 Rep.
Access to site analytics

Badges

4
55
138

Newest

 Convention

Next badge

94/100
Sportsmanship

Impact

~563k
people reached
38 posts edited
24 helpful flags
4,251 votes cast
Summary Answers Questions Tags Badges Bookmarks Bounties Reputation All actions

120 Questions

Votes Activity Newest Views
10
42
votes
3
answers
3k
views

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

cc.complexity-theory ds.algorithms graph-theory graph-isomorphism
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
1
2 3 4 Next
Theoretical Computer Science
  • Tour
  • Help
  • Chat
  • Contact
  • Feedback
  • Mobile
Company
  • Stack Overflow
  • For Teams
  • Advertise With Us
  • Hire a Developer
  • Developer Jobs
  • About
  • Press
  • Legal
  • Privacy Policy
  • Terms of Service
Stack Exchange
Network
  • Technology
  • Life / Arts
  • Culture / Recreation
  • Science
  • Other
  • Stack Overflow
  • Server Fault
  • Super User
  • Web Applications
  • Ask Ubuntu
  • Webmasters
  • Game Development
  • TeX - LaTeX
  • Software Engineering
  • Unix & Linux
  • Ask Different (Apple)
  • WordPress Development
  • Geographic Information Systems
  • Electrical Engineering
  • Android Enthusiasts
  • Information Security
  • Database Administrators
  • Drupal Answers
  • SharePoint
  • User Experience
  • Mathematica
  • Salesforce
  • ExpressionEngine® Answers
  • Stack Overflow em Português
  • Blender
  • Network Engineering
  • Cryptography
  • Code Review
  • Magento
  • Software Recommendations
  • Signal Processing
  • Emacs
  • Raspberry Pi
  • Stack Overflow на русском
  • Code Golf
  • Stack Overflow en español
  • Ethereum
  • Data Science
  • Arduino
  • Bitcoin
  • Software Quality Assurance & Testing
  • Sound Design
  • Windows Phone
  • more (28)
  • Photography
  • Science Fiction & Fantasy
  • Graphic Design
  • Movies & TV
  • Music: Practice & Theory
  • Worldbuilding
  • Video Production
  • Seasoned Advice (cooking)
  • Home Improvement
  • Personal Finance & Money
  • Academia
  • Law
  • Physical Fitness
  • Gardening & Landscaping
  • Parenting
  • more (10)
  • English Language & Usage
  • Skeptics
  • Mi Yodeya (Judaism)
  • Travel
  • Christianity
  • English Language Learners
  • Japanese Language
  • Chinese Language
  • French Language
  • German Language
  • Biblical Hermeneutics
  • History
  • Spanish Language
  • Islam
  • Русский язык
  • Russian Language
  • Arqade (gaming)
  • Bicycles
  • Role-playing Games
  • Anime & Manga
  • Puzzling
  • Motor Vehicle Maintenance & Repair
  • Board & Card Games
  • Bricks
  • Homebrewing
  • Martial Arts
  • The Great Outdoors
  • Poker
  • Chess
  • Sports
  • more (16)
  • MathOverflow
  • Mathematics
  • Cross Validated (stats)
  • Theoretical Computer Science
  • Physics
  • Chemistry
  • Biology
  • Computer Science
  • Philosophy
  • Linguistics
  • Psychology & Neuroscience
  • Computational Science
  • more (10)
  • Meta Stack Exchange
  • Stack Apps
  • API
  • Data
  • Blog
  • Facebook
  • Twitter
  • LinkedIn
  • Instagram

site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev 2021.1.21.38376