3 ms·
>> complete absence of progress in proving P != NP We've ruled out a number of techniques and also have shown that any solution must fall into a category avoid
by anandkulkarni 10y ago
>> complete absence of progress in proving P != NP
We've ruled out a number of techniques and also have shown that any solution must fall into a category avoiding a number of conditions (natural proof, algebrization barrier). Note also Ryan Williams' result separating ACC0 and NEXP. All of that is progress as I see it.
It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes.
- lotsoflumens 10y ago>> It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes. I agree, but the search for better algorithms is also more principled. At some point, separating complexity classes looks like counting the number of angels on a pinhead. It's probably interesting in an abstract way for some people - but it's not my cup of tea, as they say.