In Classic Computational Complexity, we say this algorithm is in NP, so kick it out. It's rubbish.
But Parametrized Computational Complexity says:
keep calm classic! The algorithm maybe is in NP but it's nature is p some damn parameters made it NP. So we can control these bad parameters(source of intractability), keeping them small and have a nice p algorithm.
The cognitive models I talked about in last post and I said they are considered rubbish, they may be acceptable by parametrized Complexity. The FPT(Fixed parameter Tractable) which hopefully I'll talk about in next posts is a tool for checking tractability in the view of parametrized Computational Complexity.
Hope to see you soon guys ;)
No comments:
Post a Comment