user avatar
user avatar
user avatar
Tayfun Pay
  • Member for 11 years, 10 months
  • Last seen this week
603 votes
6 answers
124k views

What's new in purely functional data structures since Okasaki?

  • 8,651
480 votes
72 answers
178k views

What papers should everyone read?

80 votes
5 answers
4k views

Techniques for Reversing the Order of Quantifiers

  • 16.4k
68 votes
7 answers
4k views

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

63 votes
12 answers
3k views

Parameterized complexity from P to NP-hard and back again

  • 2,789
57 votes
6 answers
3k views

Theoretical explanations for practical success of SAT solvers?

50 votes
0 answers
2k views

Monotone complexity of s-t connectivity

  • 6,635
44 votes
10 answers
16k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

  • 607
42 votes
5 answers
1k views

The cozy neighborhoods of "P" and of "NP-hard"

  • 5,983
33 votes
1 answer
4k views

Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming

  • 481
31 votes
1 answer
793 views

Can graph isomorphism be decided with square root bounded nondeterminism?

30 votes
10 answers
2k views

Great algorithms, machine learning and no linear algebra

  • 3,920
27 votes
2 answers
1k views

Ladner's Theorem vs. Schaefer's Theorem

  • 2,756
25 votes
2 answers
825 views

Computational complexity of counting induced subgraphs which admit perfect matchings

  • 523
24 votes
1 answer
596 views

Unification and Gaussian Elimination

24 votes
2 answers
2k views

Is finding Logspace reductions harder than P reductions?

23 votes
1 answer
913 views

Is there any justification to believe that $NL\neq L$?

  • 893
23 votes
3 answers
5k views

Minimum Unsatisfiable 3-CNF Formulae

  • 239
22 votes
2 answers
1k views

Are AND&OR circuits P-complete?

22 votes
1 answer
464 views

Are there natural separations in the nondeterministic time hierarchy?

20 votes
2 answers
664 views

How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?

  • 201
20 votes
1 answer
1k views

Consequences of UP equals NP

19 votes
3 answers
2k views

Shortest Equivalent CNF Formula

19 votes
1 answer
2k views

What are the limits of computation in this universe?

18 votes
4 answers
2k views

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

  • 2,579
16 votes
2 answers
534 views

Characterization of problems for which sublinear time algorithms exist

16 votes
0 answers
1k views

Phase Transitions in NP Hard Problems

  • 521
16 votes
3 answers
456 views

Separating time classes

  • 423
15 votes
1 answer
905 views

$NP$-complete problem with quasi-polynomial bound on the number of solutions

15 votes
2 answers
787 views

GI-hard graph problem not known to be $NP$-complete