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
1 vote
0 answers
103 views

On the borderline between natural and artificial problems

4 votes
1 answer
185 views

Finding a "typical" path

1 vote
0 answers
57 views

Minimum rank graph cut

2 votes
1 answer
74 views

Maximum subgraph problem with unknown complexity

6 votes
1 answer
492 views

Complexity of finding the largest induced subgraph with all even degrees

10 votes
1 answer
758 views

Relationship between two graph optimization problems

10 votes
2 answers
493 views

"Relatives" of the shortest path problem

1 vote
0 answers
118 views

Minimum cut with nonlinear objective function

5 votes
1 answer
255 views

Minimum cost cut with discount - what is the complexity?

11 votes
1 answer
221 views

Natural candidates for NP-E and E-NP

2 votes
0 answers
172 views

Best polynomial-time approximation factor for NP-optimization problems

3 votes
1 answer
124 views

Results/concepts that also proved useful outside of their "home areas"

17 votes
1 answer
467 views

What is the complexity of this graph problem?

25 votes
2 answers
1k views

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

9 votes
0 answers
362 views

What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

5 votes
0 answers
213 views

When will an NP-complete language remain hard if half of a witness is revealed with the instance?

5 votes
1 answer
188 views

Does p-isomorphism preserve phase transition?

6 votes
1 answer
242 views

Graph class with easy chromatic number, but NP-hard coloring

19 votes
3 answers
2k views

How common is phase transition in NP-complete problems?

5 votes
3 answers
505 views

Natural NP-complete problems with high density?

21 votes
1 answer
886 views

"Almost easy" NP-complete problems

23 votes
2 answers
698 views

Which graph parameters are NOT concentrated on random graphs?

55 votes
7 answers
4k views

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

12 votes
1 answer
264 views

What do dichotomy theorems feed on?

12 votes
3 answers
876 views

Nontrivial problems solvable in constant time?

46 votes
8 answers
6k views

Obituaries of dead conjectures

13 votes
1 answer
298 views

Slowest many-one reduction?

23 votes
3 answers
1k views

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

19 votes
1 answer
944 views

Time complexity with irrational exponent?

11 votes
1 answer
321 views

Randomized Polynomial Hierarchy?