User Andras Farago

15

52

votes

7

answers

3k

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,435

12

44

votes

8

answers

5k

views

Obituaries of dead conjectures

cc.complexity-theory ds.algorithms

Oct 7 '15 at 16:04 Community♦ 1

9

37

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 19.8k

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,913

7

36

votes

3

answers

900

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,619

8

33

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,103

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,868

13

29

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

15

28

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 11.5k

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 20.8k

2

23

votes

2

answers

543

views

Which graph parameters are NOT concentrated on random graphs?

graph-theory pr.probability random-graphs

Jun 3 '19 at 8:02 Yuval Peres 236

2

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 32.8k

3

23

votes

3

answers

960

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,673

2

22

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

8

21

votes

1

answer

732

views

“Almost easy” NP-complete problems

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

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

2

21

votes

1

answer

834

views

Time complexity with irrational exponent?

cc.complexity-theory time-complexity polynomial-time

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

4

21

votes

1

answer

596

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,333

4

19

votes

2

answers

551

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

480

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,913

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

435

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

2

16

votes

3

answers

459

views

Complexity class separations without hierarchy theorems

cc.complexity-theory complexity-classes hierarchy-theorems

Feb 28 '14 at 21:27 Community♦ 1

1

14

votes

3

answers

687

views

Nontrivial problems solvable in constant time?

cc.complexity-theory ds.algorithms time-complexity

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

13

votes

1

answer

269

views

Slowest many-one reduction?

cc.complexity-theory reductions np-complete

Oct 3 '15 at 12:07 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

2

12

votes

1

answer

249

views

Randomized Polynomial Hierarchy?

cc.complexity-theory randomized-algorithms randomness

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

2

12

votes

2

answers

659

views

What is the complexity of this path problem?

cc.complexity-theory graph-theory graph-algorithms

Mar 10 '14 at 3:39 Rupei Xu 2,329

1

12

votes

3

answers

404

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

1

11

votes

4

answers

825

views

Does NP-completeness/hardness have to be constructive?

cc.complexity-theory np-hardness reductions

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

2

10

votes

1

answer

713

views

Relationship between two graph optimization problems

graph-algorithms np-hardness np-complete

Nov 18 at 10:51 Antti Röyskö 551

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?

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

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

“Almost easy” NP-complete problems

Time complexity with irrational exponent?

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

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

Nontrivial problems solvable in constant time?

Slowest many-one reduction?

What would be the consequences of PH=PSPACE?

Randomized Polynomial Hierarchy?

What is the complexity of this path problem?

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

Does NP-completeness/hardness have to be constructive?

Relationship between two graph optimization problems