Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago's user avatar
Andras Farago
  • Member for 11 years, 4 months
  • Last seen more than a month ago
55 votes
7 answers
4k 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
933 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
698 views

Which graph parameters are NOT concentrated on random graphs?

21 votes
1 answer
881 views

"Almost easy" NP-complete problems

20 votes
2 answers
679 views

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

19 votes
1 answer
567 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
942 views

Time complexity with irrational exponent?

17 votes
1 answer
466 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
572 views

Complexity class separations without hierarchy theorems

12 votes
3 answers
450 views

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

12 votes
2 answers
817 views

What is the complexity of this path problem?

12 votes
1 answer
295 views

Slowest many-one reduction?

12 votes
3 answers
874 views

Nontrivial problems solvable in constant time?

12 votes
1 answer
263 views

What do dichotomy theorems feed on?

11 votes
1 answer
318 views

Randomized Polynomial Hierarchy?

11 votes
4 answers
907 views

Does NP-completeness/hardness have to be constructive?