User András Salamon

13

54

votes

2

answers

4k

views

Can one amplify P=NP beyond P=PH?

May 18 '17 at 12:42 András Salamon 18.5k

23

52

votes

21

answers

4k

views

Dinner-table description of theoretical computer science?

big-list soft-question

Jul 21 '12 at 17:26 CommunityBot 1

15

46

votes

4

answers

4k

views

Generalized Ladner's Theorem

cc.complexity-theory reference-request np-intermediate

Mar 12 '12 at 10:22 CommunityBot 1

31

42

votes

8

answers

3k

views

Rigour leading to insight

big-list soft-question proofs

May 25 '11 at 19:56 CommunityBot 1

2

41

votes

1

answer

616

views

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

ho.history-overview communication-complexity

Apr 19 '17 at 9:11 András Salamon 18.5k

16

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

Sep 25 '13 at 9:37 Sebastian Siebertz 1,106

11

36

votes

3

answers

2k

views

NC = P consequences?

cc.complexity-theory conditional-results

Nov 23 '14 at 6:28 CommunityBot 1

5

30

votes

1

answer

785

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

10

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

Oct 1 '14 at 2:17 CommunityBot 1

6

26

votes

4

answers

2k

views

What specific evidence is there for P = RP?

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

Sep 7 '15 at 11:41 R B 9,214

2

22

votes

2

answers

875

views

Best current space lower bound for SAT?

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

Dec 30 '14 at 10:00 András Salamon 18.5k

3

22

votes

1

answer

2k

views

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

cc.complexity-theory quantum-computing

Nov 13 '10 at 17:12 Scott Aaronson 13.3k

8

22

votes

1

answer

452

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

2

20

votes

1

answer

868

views

How to prove that USTCONN requires logarithmic space?

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

Jun 7 at 5:25 Mr. 11.8k

7

20

votes

1

answer

481

views

Are there efficient general Bonferroni-style bounds known?

reference-request pr.probability

Jan 15 '15 at 14:03 Aryeh 9,692

4

20

votes

0

answers

497

views

Model-checking for three-variable logics and restricted structures

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

Jan 12 '15 at 11:35 András Salamon 18.5k

11

20

votes

5

answers

2k

views

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

soft-question research-practice software writing

Feb 19 '13 at 3:07 CommunityBot 1

4

20

votes

5

answers

450

views

Reducing space usage of st-connectivity with multiple passes?

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

Nov 9 '11 at 20:43 Martin Pál 591

4

18

votes

3

answers

2k

views

How do models of hypercomputation overcome the Halting Problem?

computability hypercomputation

Mar 8 '20 at 10:42 domotorp 13.2k

2

18

votes

1

answer

838

views

Context-sensitive grammar for SAT?

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

Jan 30 '12 at 11:46 kinaba 106

3

17

votes

1

answer

947

views

Quadratic relationship between nondeterministic and deterministic space?

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

Apr 13 '17 at 20:29 Richard Wilson 1

8

17

votes

2

answers

693

views

Hardness of parameterized CLIQUE?

cc.complexity-theory np parameterized-complexity clique

Sep 20 '10 at 0:48 Tsuyoshi Ito 16.1k

5

16

votes

0

answers

807

views

Deeper look at Algorithmica?

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

Feb 25 '16 at 3:59 CommunityBot 1

2

16

votes

1

answer

816

views

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

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

Jul 10 '12 at 6:25 CommunityBot 1

3

15

votes

1

answer

240

views

2FA state complexity of k-Clique?

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

Apr 16 '17 at 10:20 András Salamon 18.5k

4

15

votes

6

answers

492

views

Global properties of hereditary classes?

cc.complexity-theory graph-theory relational-structures

Oct 28 '10 at 4:42 David Eppstein 50k

1

14

votes

0

answers

262

views

AC0 many-one reduction of Mod_3 to PRIMES?

cc.complexity-theory reference-request circuit-complexity

Sep 8 '11 at 9:01 CommunityBot 1

4

14

votes

1

answer

666

views

What are the historical roots of Milner's bigraphs?

process-algebra ho.history-overview

Aug 27 '10 at 21:51 András Salamon 18.5k

2

13

votes

0

answers

335

views

Consequences of bipartite perfect matching not in NL?

cc.complexity-theory space-bounded matching conditional-results

May 16 '18 at 8:52 András Salamon 18.5k

13

votes

3

answers

338

views

Can limit of hard languages be easy?

cc.complexity-theory complexity-classes reductions

Feb 1 '14 at 2:01 Joshua Grochow 34.8k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

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

Best current space lower bound for SAT?

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

Are there natural separations in the nondeterministic time hierarchy?

How to prove that USTCONN requires logarithmic space?

Are there efficient general Bonferroni-style bounds known?

Model-checking for three-variable logics and restricted structures

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

Reducing space usage of st-connectivity with multiple passes?

How do models of hypercomputation overcome the Halting Problem?

Context-sensitive grammar for SAT?

Quadratic relationship between nondeterministic and deterministic space?

Hardness of parameterized CLIQUE?

Deeper look at Algorithmica?

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

2FA state complexity of k-Clique?

Global properties of hereditary classes?

AC0 many-one reduction of Mod_3 to PRIMES?

What are the historical roots of Milner's bigraphs?

Consequences of bipartite perfect matching not in NL?

Can limit of hard languages be easy?