13
$\begingroup$

Most classical computer science problems are still open concerning the exact asymptotic algorithmic worst-case complexity required to solve them.

Is there any online collaborative wiki (or other references, e.g. periodicals) specialized in aggregating the best upper (the best algorithm known so far) and lower bounds known for the worst-case complexity of computer science problems?

$\endgroup$

2 Answers 2

8
$\begingroup$

For job scheduling problems, there is this complexity wiki. I am not sure if it is actively being updated.

$\endgroup$
4
$\begingroup$

For fixed-parameter tractability, there is this wiki: http://fpt.wikidot.com/fpt-races/ (seems to be updated only until ~10 years ago.) The problem with most such resources is that it takes a lot of effort to curate them and keep them up to date.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.