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
26 votes
3 answers
1k views

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

1 vote
0 answers
103 views

On the borderline between natural and artificial problems

4 votes
1 answer
185 views

Finding a "typical" path

17 votes
4 answers
4k views

What would be the consequences of PH=PSPACE?

55 votes
7 answers
4k views

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

10 votes
1 answer
283 views

Complexity of unique coloring of graphs

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
481 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
488 views

"Relatives" of the shortest path problem

23 votes
2 answers
698 views

Which graph parameters are NOT concentrated on random graphs?

1 vote
0 answers
116 views

Minimum cut with nonlinear objective function

5 votes
1 answer
253 views

Minimum cost cut with discount - what is the complexity?

11 votes
1 answer
220 views

Natural candidates for NP-E and E-NP

2 votes
0 answers
172 views

Best polynomial-time approximation factor for NP-optimization problems

38 votes
4 answers
2k views

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

3 votes
1 answer
124 views

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

17 votes
1 answer
466 views

What is the complexity of this graph problem?

19 votes
3 answers
2k views

How common is phase transition in NP-complete problems?

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
361 views

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

5 votes
0 answers
209 views

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

5 votes
1 answer
187 views

Does p-isomorphism preserve phase transition?

6 votes
1 answer
242 views

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

5 votes
3 answers
505 views

Natural NP-complete problems with high density?

21 votes
1 answer
881 views

"Almost easy" NP-complete problems

31 votes
16 answers
5k views

Hard-looking algorithmic problems made easy by theorems

12 votes
3 answers
874 views

Nontrivial problems solvable in constant time?

12 votes
1 answer
263 views

What do dichotomy theorems feed on?