User András Salamon

55 votes

2 answers

4k views

Can one amplify P=NP beyond P=PH?

asked Mar 13, 2011 at 16:55

53 votes

21 answers

4k views

Dinner-table description of theoretical computer science?

big-list soft-question

asked Sep 19, 2010 at 23:25

46 votes

4 answers

4k views

Generalized Ladner's Theorem

cc.complexity-theory reference-request np-intermediate

asked Aug 31, 2010 at 14:52

42 votes

8 answers

3k views

Rigour leading to insight

big-list soft-question proofs

asked Oct 12, 2010 at 16:16

41 votes

1 answer

633 views

Does Rabin/Yao exist (at least in a form that can be cited)?

ho.history-overview communication-complexity

asked Jan 3, 2015 at 12:43

39 votes

5 answers

1k views

Is there a logic without induction that captures much of P?

cc.complexity-theory lo.logic descriptive-complexity finite-model-theory

asked Sep 2, 2010 at 11:25

36 votes

3 answers

2k views

NC = P consequences?

cc.complexity-theory conditional-results

asked Sep 24, 2010 at 15:48

31 votes

1 answer

791 views

Can graph isomorphism be decided with square root bounded nondeterminism?

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

asked Apr 4, 2014 at 7:50

28 votes

4 answers

1k views

Maximal classes for which largest independent set can be found in polynomial time?

ds.algorithms graph-theory co.combinatorics graph-classes

asked Oct 27, 2010 at 9:12

27 votes

4 answers

2k views

What specific evidence is there for P = RP?

cc.complexity-theory derandomization conditional-results randomized-algorithms

asked Aug 16, 2010 at 23:27

24 votes

1 answer

2k views

How does the BosonSampling paper avoid easy classes of complex matrices?

cc.complexity-theory quantum-computing

asked Nov 11, 2010 at 19:37

23 votes

2 answers

952 views

Best current space lower bound for SAT?

cc.complexity-theory sat lower-bounds space-bounded space-complexity

asked Nov 13, 2014 at 17:27

22 votes

1 answer

464 views

Are there natural separations in the nondeterministic time hierarchy?

cc.complexity-theory nondeterminism time-hierarchy

asked Sep 1, 2010 at 15:39

20 votes

1 answer

486 views

Are there efficient general Bonferroni-style bounds known?

reference-request pr.probability

asked Oct 22, 2010 at 17:27

20 votes

5 answers

457 views

Reducing space usage of st-connectivity with multiple passes?

reference-request graph-algorithms ds.data-structures lower-bounds data-streams

asked Sep 26, 2011 at 16:37

20 votes

5 answers

2k views

Version control for collaboration (with word-level diffs)?

soft-question research-practice software writing

asked Nov 12, 2010 at 17:54

20 votes

0 answers

499 views

Model-checking for three-variable logics and restricted structures

cc.complexity-theory co.combinatorics lo.logic descriptive-complexity

asked Nov 3, 2010 at 18:47

20 votes

1 answer

914 views

How to prove that USTCONN requires logarithmic space?

cc.complexity-theory lower-bounds reductions space-bounded

asked Jun 23, 2015 at 20:08

19 votes

1 answer

892 views

Context-sensitive grammar for SAT?

cc.complexity-theory fl.formal-languages sat space-bounded

asked Jan 29, 2012 at 23:16

18 votes

3 answers

3k views

How do models of hypercomputation overcome the Halting Problem?

computability hypercomputation

asked Apr 8, 2011 at 8:28

17 votes

2 answers

699 views

Hardness of parameterized CLIQUE?

cc.complexity-theory np parameterized-complexity clique

asked Sep 18, 2010 at 20:30

17 votes

0 answers

864 views

Deeper look at Algorithmica?

cc.complexity-theory reference-request np-hardness soft-question

asked Feb 17, 2016 at 16:29

17 votes

1 answer

954 views

Quadratic relationship between nondeterministic and deterministic space?

cc.complexity-theory automata-theory space-bounded space-complexity

asked Apr 13, 2017 at 12:51

16 votes

1 answer

830 views

Reference for (odd-hole,antihole)-free graphs?

reference-request graph-theory co.combinatorics graph-classes

asked Oct 28, 2010 at 14:46

15 votes

6 answers

498 views

Global properties of hereditary classes?

cc.complexity-theory graph-theory relational-structures

asked Sep 5, 2010 at 21:22

15 votes

1 answer

244 views

2FA state complexity of k-Clique?

cc.complexity-theory ds.algorithms graph-algorithms clique

asked Nov 12, 2015 at 15:57

14 votes

1 answer

684 views

What are the historical roots of Milner's bigraphs?

process-algebra ho.history-overview

asked Aug 17, 2010 at 0:47

14 votes

0 answers

264 views

AC0 many-one reduction of Mod_3 to PRIMES?

cc.complexity-theory reference-request circuit-complexity

asked Sep 7, 2011 at 18:08

13 votes

1 answer

268 views

Elementary bounds on parameter in fixed-parameter tractability?

cc.complexity-theory reference-request fixed-parameter-tractable

asked Nov 17, 2011 at 15:15

13 votes

3 answers

339 views

Can limit of hard languages be easy?

cc.complexity-theory complexity-classes reductions

asked Jan 31, 2014 at 17:13

Stack Exchange Network

current community

your communities

more stack exchange communities

54 Questions

Can one amplify P=NP beyond P=PH?

Dinner-table description of theoretical computer science?

Generalized Ladner's Theorem

Rigour leading to insight

Does Rabin/Yao exist (at least in a form that can be cited)?

Is there a logic without induction that captures much of P?

NC = P consequences?

Can graph isomorphism be decided with square root bounded nondeterminism?

Maximal classes for which largest independent set can be found in polynomial time?

What specific evidence is there for P = RP?

How does the BosonSampling paper avoid easy classes of complex matrices?

Best current space lower bound for SAT?

Are there natural separations in the nondeterministic time hierarchy?

Are there efficient general Bonferroni-style bounds known?

Reducing space usage of st-connectivity with multiple passes?

Version control for collaboration (with word-level diffs)?

Model-checking for three-variable logics and restricted structures

How to prove that USTCONN requires logarithmic space?

Context-sensitive grammar for SAT?

How do models of hypercomputation overcome the Halting Problem?

Hardness of parameterized CLIQUE?

Deeper look at Algorithmica?

Quadratic relationship between nondeterministic and deterministic space?

Reference for (odd-hole,antihole)-free graphs?

Global properties of hereditary classes?

2FA state complexity of k-Clique?

What are the historical roots of Milner's bigraphs?

AC0 many-one reduction of Mod_3 to PRIMES?

Elementary bounds on parameter in fixed-parameter tractability?

Can limit of hard languages be easy?