6
$\begingroup$

I remember reading an article/paper (or perhaps a talk, most probably by Scott Arranson) where he lists the major open problems and their likelihood of being true or false in a table/graph. This is listed along with the 'surprise factor' of each result if its true/false.

I am unable to locate the article though. I wonder if someone remembers the article and can help. I am aware of a similar one by Ryan Williams but I am looking for the other one.

P.S. I know its a silly request. Apologies. But, still need it.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Probably not exactly what you're looking for, but Impagliazzo's 'complexity worlds' sounds similar. It may help your search. $\endgroup$
    – Discrete lizard ♦
    Commented May 29, 2019 at 15:17
  • $\begingroup$ Thank you. Yes its similar, but, that one is focused mainly on P vs NP not the generic domain. $\endgroup$
    – TheoryQuest1
    Commented May 29, 2019 at 17:24

2 Answers 2

Reset to default
4
$\begingroup$

Perhaps you are looking for the diagram on slide 12 of this talk by Scott Aaronson. Scott has given the talk many times, and not all versions contain the slide. Note that except for P vs NP, it does not contain any open problems, but apart from that, it appears to match your description.

Screenshot of slide 12 of the mentioned talk

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. Yes this is the one! The power of social media :) $\endgroup$
    – TheoryQuest1
    Commented Jun 6, 2019 at 11:12
5
$\begingroup$

What you are searching for could be Some Estimated Likelihoods For Computational Complexity by R. Ryan Williams, 2018.

Here are "Some Estimated Likelihoods for Some Major Open Problems" in that paper. Note that "The numerical values of my 'estimated likelihoods' are (obviously) nothing too rigorous. What is more important is the relative measure between problems."

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank a lot. I am aware of this one but there was another one similar to this where there was a 'surprise factor' or 'improbability factor' mentioned on a log scale regarding the problems (Scott most probably but not 100%). $\endgroup$
    – TheoryQuest1
    Commented May 29, 2019 at 17:21

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.