Skip to main content
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago
  • Member for 11 years, 7 months
  • Last seen more than a month ago
55 votes
7 answers
5k views

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

46 votes
8 answers
6k views

Obituaries of dead conjectures

38 votes
4 answers
2k views

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

38 votes
3 answers
1k views

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

37 votes
4 answers
4k views

Hardness of approximation without the PCP theorem

34 votes
3 answers
2k views

Hardest known natural problem in P?

34 votes
6 answers
3k views

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

34 votes
5 answers
4k views

The unreasonable power of non-uniformity

31 votes
16 answers
5k views

Hard-looking algorithmic problems made easy by theorems

26 votes
3 answers
1k views

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

25 votes
2 answers
1k views

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

24 votes
1 answer
944 views

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

23 votes
3 answers
1k views

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

23 votes
10 answers
2k views

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

23 votes
2 answers
701 views

Which graph parameters are NOT concentrated on random graphs?

21 votes
1 answer
888 views

"Almost easy" NP-complete problems

20 votes
2 answers
702 views

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

19 votes
1 answer
570 views

Natural candidate against the Isomorphism Conjecture?

19 votes
3 answers
2k views

How common is phase transition in NP-complete problems?

19 votes
1 answer
949 views

Time complexity with irrational exponent?

17 votes
1 answer
467 views

What is the complexity of this graph problem?

17 votes
4 answers
4k views

What would be the consequences of PH=PSPACE?

17 votes
3 answers
583 views

Complexity class separations without hierarchy theorems

13 votes
1 answer
300 views

Slowest many-one reduction?

12 votes
3 answers
878 views

Nontrivial problems solvable in constant time?

12 votes
1 answer
265 views

What do dichotomy theorems feed on?

12 votes
3 answers
450 views

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

12 votes
2 answers
822 views

What is the complexity of this path problem?

11 votes
4 answers
909 views

Does NP-completeness/hardness have to be constructive?

11 votes
1 answer
321 views

Randomized Polynomial Hierarchy?