Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago
  • Member for 11 years, 6 months
  • Last seen more than a month ago
46 votes
8 answers
6k views

Obituaries of dead conjectures

31 votes
16 answers
5k views

Hard-looking algorithmic problems made easy by theorems

55 votes
7 answers
4k views

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

17 votes
4 answers
4k views

What would be the consequences of PH=PSPACE?

34 votes
5 answers
4k views

The unreasonable power of non-uniformity

37 votes
4 answers
4k views

Hardness of approximation without the PCP theorem

34 votes
6 answers
3k views

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

23 votes
10 answers
2k views

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

34 votes
3 answers
2k views

Hardest known natural problem in P?

19 votes
3 answers
2k views

How common is phase transition in NP-complete problems?

38 votes
4 answers
2k views

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

23 votes
3 answers
1k views

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

25 votes
2 answers
1k views

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

26 votes
3 answers
1k views

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

38 votes
3 answers
1k views

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

3 votes
1 answer
965 views

Partitioning the edges of a complete graph into smaller complete graphs

19 votes
1 answer
944 views

Time complexity with irrational exponent?

24 votes
1 answer
939 views

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

11 votes
4 answers
908 views

Does NP-completeness/hardness have to be constructive?

21 votes
1 answer
886 views

"Almost easy" NP-complete problems

12 votes
3 answers
876 views

Nontrivial problems solvable in constant time?

12 votes
2 answers
820 views

What is the complexity of this path problem?

10 votes
1 answer
758 views

Relationship between two graph optimization problems

23 votes
2 answers
698 views

Which graph parameters are NOT concentrated on random graphs?

20 votes
2 answers
690 views

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

7 votes
0 answers
637 views

Narrowing the gap between BPP and RP

17 votes
3 answers
580 views

Complexity class separations without hierarchy theorems

19 votes
1 answer
569 views

Natural candidate against the Isomorphism Conjecture?

9 votes
1 answer
514 views

Is the complexity of this path problem known?

5 votes
3 answers
505 views

Natural NP-complete problems with high density?