User Tayfun Pay

590

votes

6

answers

120k

views

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

Jul 16 '20 at 22:57 dmbarbour 81

476

votes

72

answers

172k

views

What papers should everyone read?

big-list soft-question

Apr 13 at 8:00 Xi Li 21

78

votes

5

answers

4k

views

Techniques for Reversing the Order of Quantiﬁers

lo.logic big-picture proof-techniques

Jan 24 '11 at 12:25 Community♦ 1

67

votes

7

answers

4k

views

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

cc.complexity-theory np-hardness big-picture

Mar 9 '14 at 21:27 Sylvain 3,294

61

votes

12

answers

3k

views

Parameterized complexity from P to NP-hard and back again

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

Jul 20 '19 at 19:45 user13136 2,437

51

votes

6

answers

3k

views

Theoretical explanations for practical success of SAT solvers?

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

Jun 9 at 0:50 Andras Farago 10.4k

46

votes

0

answers

2k

views

Monotone complexity of s-t connectivity

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

Dec 14 at 22:54 monty 1

43

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

Nov 28 '17 at 18:34 Eric Allender 966

42

votes

5

answers

1k

views

The cozy neighborhoods of “P” and of “NP-hard”

cc.complexity-theory

Jan 3 '13 at 13:23 Gil Kalai 5,803

31

votes

1

answer

4k

views

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

soft-question sat terminology

Aug 8 '17 at 6:44 András Salamon 18.5k

30

votes

10

answers

2k

views

Great algorithms, machine learning and no linear algebra

ds.algorithms machine-learning teaching

Apr 25 '19 at 8:53 Aryeh 9,108

30

votes

1

answer

778

views

Can graph isomorphism be decided with square root bounded nondeterminism?

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

Apr 11 '14 at 2:33 Joshua Grochow 34.4k

27

votes

2

answers

1k

views

Ladner's Theorem vs. Schaefer's Theorem

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

Jan 9 '13 at 14:13 András Salamon 18.5k

25

votes

2

answers

822

views

Computational complexity of counting induced subgraphs which admit perfect matchings

cc.complexity-theory co.combinatorics counting-complexity

Nov 16 '13 at 3:28 Radu Curticapean 807

23

votes

3

answers

4k

views

Minimum Unsatisfiable 3-CNF Formulae

cc.complexity-theory sat

Jan 24 '20 at 2:59 ian.p.swift 41

23

votes

1

answer

555

views

Unification and Gaussian Elimination

reference-request lo.logic

Aug 25 '12 at 10:21 Community♦ 1

23

votes

1

answer

889

views

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

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

Mar 11 '11 at 22:56 Ryan Williams 25.8k

22

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

22

votes

1

answer

444

views

Are there natural separations in the nondeterministic time hierarchy?

cc.complexity-theory nondeterminism time-hierarchy

Sep 3 '10 at 8:00 András Salamon 18.5k

22

votes

2

answers

1k

views

Are AND&OR circuits P-complete?

cc.complexity-theory circuit-complexity

Sep 4 '12 at 14:57 vzn 10.8k

20

votes

2

answers

642

views

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

cc.complexity-theory

Mar 16 '15 at 8:54 Michael Wehar 4,830

19

votes

1

answer

2k

views

What are the limits of computation in this universe?

computability upper-bounds

Aug 17 at 13:08 Peter Morgan 145

19

votes

1

answer

1k

views

Consequences of UP equals NP

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

Apr 14 at 21:05 User2021 65

19

votes

3

answers

2k

views

Shortest Equivalent CNF Formula

cc.complexity-theory co.combinatorics sat formulas

Jan 25 '12 at 19:57 András Salamon 18.5k

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

May 22 '17 at 3:43 Tayfun Pay 2,549

16

votes

2

answers

520

views

Characterization of problems for which sublinear time algorithms exist

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

Mar 7 '12 at 22:14 Suresh Venkat 31.5k

16

votes

3

answers

456

views

Separating time classes

cc.complexity-theory

Mar 7 '17 at 6:45 Michael Wehar 4,830

15

votes

1

answer

886

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.8k

15

votes

2

answers

742

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

14

votes

1

answer

237

views

What is the minimum required depth of reductions for NP-hardness of SAT?

cc.complexity-theory reference-request np-hardness circuit-complexity reductions

Jun 11 '13 at 17:04 Robin Kothari 13.2k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

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

Great algorithms, machine learning and no linear algebra

Can graph isomorphism be decided with square root bounded nondeterminism?

Ladner's Theorem vs. Schaefer's Theorem

Computational complexity of counting induced subgraphs which admit perfect matchings

Minimum Unsatisfiable 3-CNF Formulae

Unification and Gaussian Elimination

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

Is finding Logspace reductions harder than P reductions?

Are there natural separations in the nondeterministic time hierarchy?

Are AND&OR circuits P-complete?

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

What are the limits of computation in this universe?

Consequences of UP equals NP

Shortest Equivalent CNF Formula

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

Characterization of problems for which sublinear time algorithms exist

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

What is the minimum required depth of reductions for NP-hardness of SAT?