HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

List of major Open Problems in Computational Complexity and their Likelihood?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
majoropencomputationallikelihoodandlistproblemscomplexitytheir

Problem

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.

Solution

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."

Context

StackExchange Computer Science Q#110004, answer score: 5

Revisions (0)

No revisions yet.