= 27d567bc2d48d9f40e9ccc20ea370b15)
IlyaShpitser comments on AI cooperation is already studied in academia as "program equilibrium" - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (42)
One simple heuristic formula for approximate problem difficulty I heard is this:
D = log(T)*N
D is difficulty, T is length of time the problem stayed open after being posed, N is the average number of people working on it.
Rationalle:
Since we expect P != NP, finding proofs is an exponential search problem. That means in time T we can only cover problems that have about log(T) shortest proof length. Assuming linear scaling with adding more processing, we have a factor of N (in reality, scaling is sublinear, but this is a heuristic..).
The point is that just because a field has open problems, doesn't mean those problems are necessarily very hard. It could be that either they haven't been open very long, or not enough people care.
If D is the proof length, surely your reasoning should lead to something like log(T*N) rather than log(T)*N? It seems to me that N people working for T days is T*N person-days, so the two variables should be mostly exchangeable, it's weird to see only one of them under the logarithm...
P != NP does not imply that one can't do better than an exponential search for finding proofs. For instance an O(n^log(n)) algorithm for finding proofs would not contradict P != NP.