User Andras Farago

15

54

votes

7

answers

4k

views

For which problems in P is it easier to verify the result than to find it?

Nov 20 '15 at 18:08 Yonatan N 1,550

13

45

votes

8

answers

5k

views

Obituaries of dead conjectures

cc.complexity-theory ds.algorithms

Oct 7 '15 at 16:04 Community♦ 1

9

38

votes

4

answers

1k

views

Examples where the uniqueness of the solution makes it easier to find

cc.complexity-theory ds.algorithms graph-algorithms complexity-classes unique-solution

Jun 20 '18 at 16:38 Mohammad Al-Turkistany 20.1k

5

36

votes

4

answers

3k

views

Hardness of approximation without the PCP theorem

cc.complexity-theory approximation-hardness pcp

Mar 14 '14 at 3:16 Artem Kaznatcheev♦ 9,993

7

36

votes

3

answers

916

views

Why does randomness have stronger effect on reductions than on algorithms?

cc.complexity-theory reductions derandomization

Jan 14 '14 at 10:12 Niel de Beaudrap 8,709

8

34

votes

3

answers

1k

views

Hardest known natural problem in P?

cc.complexity-theory ds.algorithms

Oct 2 '14 at 23:18 D.W. 9,606

9

33

votes

5

answers

4k

views

The unreasonable power of non-uniformity

cc.complexity-theory complexity-classes big-picture

May 2 '14 at 12:07 Thomas Klimpel 2,963

13

31

votes

6

answers

2k

views

Why are so few natural candidates for NP-intermediate status?

cc.complexity-theory p-vs-np np-intermediate

Mar 14 '14 at 10:09 Community♦ 1

16

29

votes

16

answers

5k

views

Hard-looking algorithmic problems made easy by theorems

cc.complexity-theory ds.algorithms graph-algorithms

Nov 12 '15 at 9:20 Emil Jeřábek 12.8k

5

25

votes

2

answers

1k

views

Is there an NP-complete language that contains precisely half of the n-bit instances?

cc.complexity-theory np np-complete

Nov 29 '16 at 4:42 Kaveh 21k

2

23

votes

2

answers

602

views

Which graph parameters are NOT concentrated on random graphs?

graph-theory pr.probability random-graphs

Jun 3 '19 at 8:02 Yuval Peres 336

3

23

votes

3

answers

1k

views

How much would a SAT oracle help speeding up polynomial time algorithms?

cc.complexity-theory np np-complete

Sep 29 '15 at 23:21 Joshua Grochow 34.1k

2

23

votes

10

answers

2k

views

Problems that are easy on unweighted graphs, but hard for weighted graphs

cc.complexity-theory graph-algorithms np-hardness

Jan 26 '15 at 14:09 Community♦ 1

3

23

votes

3

answers

982

views

Optimization problems with good characterization, but no polynomial-time algorithm

cc.complexity-theory graph-algorithms complexity-classes optimization linear-programming

Feb 16 '14 at 9:38 Rahul Savani 1,683

4

21

votes

1

answer

598

views

Is P equal to the intersection of all superpolynomial time classes?

cc.complexity-theory ds.algorithms complexity-classes

Sep 21 '14 at 23:05 Huck Bennett 4,412

8

20

votes

1

answer

758

views

“Almost easy” NP-complete problems

cc.complexity-theory ds.algorithms complexity-classes np-complete

Nov 18 '15 at 3:17 Andras Farago 10.4k

2

20

votes

1

answer

860

views

Time complexity with irrational exponent?

cc.complexity-theory time-complexity polynomial-time

Sep 27 '15 at 0:27 Joe Bebel 2,265

4

19

votes

2

answers

564

views

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

cc.complexity-theory circuit-complexity ho.history-overview

May 12 '14 at 1:54 Community♦ 1

3

18

votes

1

answer

491

views

Natural candidate against the Isomorphism Conjecture?

cc.complexity-theory complexity-classes p-vs-np np-complete

Feb 28 '14 at 13:06 Artem Kaznatcheev♦ 9,993

6

17

votes

3

answers

1k

views

How common is phase transition in NP-complete problems?

cc.complexity-theory phase-transition

Feb 11 '17 at 0:41 daniel pehoushek 115

5

16

votes

1

answer

441

views

What is the complexity of this graph problem?

graph-theory graph-algorithms np-hardness

Feb 21 '18 at 14:44 Marzio De Biasi 21.7k

2

16

votes

3

answers

470

views

Complexity class separations without hierarchy theorems

cc.complexity-theory complexity-classes hierarchy-theorems

Feb 28 '14 at 21:27 Community♦ 1

2

13

votes

3

answers

2k

views

What would be the consequences of PH=PSPACE?

cc.complexity-theory complexity-classes conditional-results

Feb 23 '14 at 21:51 Community♦ 1

1

12

votes

3

answers

737

views

Nontrivial problems solvable in constant time?

cc.complexity-theory ds.algorithms time-complexity

Oct 13 '15 at 22:50 David Eppstein 49.3k

12

votes

1

answer

273

views

Slowest many-one reduction?

cc.complexity-theory reductions np-complete

Oct 3 '15 at 12:07 Community♦ 1

2

12

votes

2

answers

682

views

What is the complexity of this path problem?

cc.complexity-theory graph-theory graph-algorithms

Mar 10 '14 at 3:39 Community♦ 1

1

12

votes

3

answers

408

views

NP-complete graph property that is hereditary, but not additive?

cc.complexity-theory graph-theory graph-algorithms np

Mar 2 '14 at 12:50 Super8 304

3

11

votes

1

answer

195

views

Natural candidates for NP-E and E-NP

cc.complexity-theory complexity-classes np-complete

Jan 26 '19 at 12:19 Lance Fortnow 8,351

1

11

votes

4

answers

859

views

Does NP-completeness/hardness have to be constructive?

cc.complexity-theory np-hardness reductions

Aug 29 '15 at 8:15 Mohammad Al-Turkistany 20.1k

2

11

votes

1

answer

259

views

Randomized Polynomial Hierarchy?

cc.complexity-theory randomized-algorithms randomness

Aug 28 '15 at 12:05 Emil Jeřábek 12.8k

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

61 Questions

For which problems in P is it easier to verify the result than to find it?

Obituaries of dead conjectures

Examples where the uniqueness of the solution makes it easier to find

Hardness of approximation without the PCP theorem

Why does randomness have stronger effect on reductions than on algorithms?

Hardest known natural problem in P?

The unreasonable power of non-uniformity

Why are so few natural candidates for NP-intermediate status?

Hard-looking algorithmic problems made easy by theorems

Is there an NP-complete language that contains precisely half of the n-bit instances?

Which graph parameters are NOT concentrated on random graphs?

How much would a SAT oracle help speeding up polynomial time algorithms?

Problems that are easy on unweighted graphs, but hard for weighted graphs

Optimization problems with good characterization, but no polynomial-time algorithm

Is P equal to the intersection of all superpolynomial time classes?

“Almost easy” NP-complete problems

Time complexity with irrational exponent?

Arguments for/against Kolmogorov's conjecture about the circuit complexity of P

Natural candidate against the Isomorphism Conjecture?

How common is phase transition in NP-complete problems?

What is the complexity of this graph problem?

Complexity class separations without hierarchy theorems

What would be the consequences of PH=PSPACE?

Nontrivial problems solvable in constant time?

Slowest many-one reduction?

What is the complexity of this path problem?

NP-complete graph property that is hereditary, but not additive?

Natural candidates for NP-E and E-NP

Does NP-completeness/hardness have to be constructive?

Randomized Polynomial Hierarchy?