User Tayfun Pay

603 votes

6 answers

124k views

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

jkff

8,651

asked Sep 21, 2010 at 8:04

480 votes

72 answers

178k views

What papers should everyone read?

big-list soft-question

Ryan Williams

26.5k

asked Sep 12, 2010 at 0:43

80 votes

5 answers

4k views

Techniques for Reversing the Order of Quantiﬁers

lo.logic big-picture proof-techniques

M.S. Dousti

16.4k

asked Jan 21, 2011 at 22:58

68 votes

7 answers

4k views

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

cc.complexity-theory np-hardness big-picture

Alex ten Brink

4,610

asked Mar 7, 2011 at 13:52

63 votes

12 answers

3k views

Parameterized complexity from P to NP-hard and back again

cc.complexity-theory np-hardness big-list phase-transition

mikero

2,789

asked Dec 2, 2010 at 19:12

57 votes

6 answers

3k views

Theoretical explanations for practical success of SAT solvers?

cc.complexity-theory ds.algorithms sat big-picture heuristics

Joshua Grochow

35.8k

asked Mar 30, 2017 at 21:02

50 votes

0 answers

2k views

Monotone complexity of s-t connectivity

cc.complexity-theory circuit-complexity lower-bounds dynamic-programming monotone

Stasys

6,635

asked Oct 6, 2012 at 12:45

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?

soft-question fl.formal-languages automata-theory big-picture turing-machines

Rahul

607

asked Apr 19, 2016 at 4:47

42 votes

5 answers

1k views

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

cc.complexity-theory

Gil Kalai

5,983

asked Dec 22, 2012 at 16:58

33 votes

1 answer

4k views

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

soft-question sat terminology

Fizz

481

asked Feb 7, 2015 at 7:56

31 votes

1 answer

793 views

Can graph isomorphism be decided with square root bounded nondeterminism?

cc.complexity-theory graph-theory graph-isomorphism nondeterminism

András Salamon

18.7k

asked Apr 4, 2014 at 7:50

30 votes

10 answers

2k views

Great algorithms, machine learning and no linear algebra

ds.algorithms machine-learning teaching

graffe

3,920

asked Nov 15, 2010 at 13:45

27 votes

2 answers

1k views

Ladner's Theorem vs. Schaefer's Theorem

cc.complexity-theory np-hardness complexity-classes sat csp

user834

2,756

asked Jan 23, 2012 at 9:59

25 votes

2 answers

825 views

Computational complexity of counting induced subgraphs which admit perfect matchings

cc.complexity-theory co.combinatorics counting-complexity

h.a

523

asked Mar 21, 2012 at 9:36

24 votes

1 answer

596 views

Unification and Gaussian Elimination

reference-request lo.logic

Neel Krishnaswami

31.7k

asked Aug 16, 2012 at 5:37

24 votes

2 answers

2k views

Is finding Logspace reductions harder than P reductions?

cc.complexity-theory np-hardness

Mohammad Al-Turkistany

20.6k

asked Aug 8, 2013 at 18:28

23 votes

1 answer

913 views

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

cc.complexity-theory reference-request complexity-classes space-bounded

Klim

893

asked Mar 11, 2011 at 8:13

23 votes

3 answers

5k views

Minimum Unsatisfiable 3-CNF Formulae

cc.complexity-theory sat

MAF

239

asked Sep 7, 2011 at 8:28

22 votes

2 answers

1k views

Are AND&OR circuits P-complete?

cc.complexity-theory circuit-complexity

Itai Bar-Natan

537

asked Mar 25, 2012 at 12:28

22 votes

1 answer

464 views

Are there natural separations in the nondeterministic time hierarchy?

cc.complexity-theory nondeterminism time-hierarchy

András Salamon

18.7k

asked Sep 1, 2010 at 15:39

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

cc.complexity-theory

Anonymous

201

asked Mar 13, 2015 at 0:36

20 votes

1 answer

1k views

Consequences of UP equals NP

cc.complexity-theory complexity-classes conditional-results unique-solution

Hsien-Chih Chang 張顯之

7,588

asked Dec 20, 2010 at 7:08

19 votes

3 answers

2k views

Shortest Equivalent CNF Formula

cc.complexity-theory co.combinatorics sat formulas

Giorgio Camerani

6,615

asked Jan 21, 2012 at 13:40

19 votes

1 answer

2k views

What are the limits of computation in this universe?

computability upper-bounds

Good Person

393

asked Feb 26, 2011 at 8:11

18 votes

4 answers

2k views

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

cc.complexity-theory big-list p-vs-np

Tayfun Pay

2,579

asked Jan 19, 2012 at 19:00

16 votes

2 answers

534 views

Characterization of problems for which sublinear time algorithms exist

cc.complexity-theory ds.algorithms complexity-classes approximation-algorithms

Massimo Cafaro

2,186

asked Mar 6, 2012 at 18:26

16 votes

0 answers

1k views

Phase Transitions in NP Hard Problems

cc.complexity-theory np-hardness phase-transition

Ganesh

521

asked Dec 17, 2010 at 4:03

16 votes

3 answers

456 views

Separating time classes

cc.complexity-theory

S. Pek

423

asked Feb 27, 2017 at 7:36

15 votes

1 answer

905 views

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

cc.complexity-theory np

Mohammad Al-Turkistany

20.6k

asked Nov 2, 2014 at 8:37

15 votes

2 answers

787 views

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

cc.complexity-theory graph-theory graph-isomorphism np-intermediate

Mohammad Al-Turkistany

20.6k

asked Dec 6, 2013 at 9:13

Stack Exchange Network

current community

your communities

more stack exchange communities

72 Bookmarks

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

What papers should everyone read?

Techniques for Reversing the Order of Quantiﬁers

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

Parameterized complexity from P to NP-hard and back again

Theoretical explanations for practical success of SAT solvers?

Monotone complexity of s-t connectivity

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

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

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

Can graph isomorphism be decided with square root bounded nondeterminism?

Great algorithms, machine learning and no linear algebra

Ladner's Theorem vs. Schaefer's Theorem

Computational complexity of counting induced subgraphs which admit perfect matchings

Unification and Gaussian Elimination

Is finding Logspace reductions harder than P reductions?

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

Minimum Unsatisfiable 3-CNF Formulae

Are AND&OR circuits P-complete?

Are there natural separations in the nondeterministic time hierarchy?

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

Consequences of UP equals NP

Shortest Equivalent CNF Formula

What are the limits of computation in this universe?

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

Characterization of problems for which sublinear time algorithms exist

Phase Transitions in NP Hard Problems

Separating time classes

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

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