tag:blogger.com,1999:blog-3722233.post8037830445610090135..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: There is now a Bounded Discrete Envy Free Cake Cutting Protocol!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-59724563143217557362016-11-08T17:51:12.269-06:002016-11-08T17:51:12.269-06:00I believe I've found a problem with this resul...I believe I've found a problem with this result please let me know what you think: https://justincarcher.wordpress.com/2016/10/05/problems-cake-cutting-aziz-mackenzie-2016/Justin Archerhttps://www.blogger.com/profile/02417547954183994873noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84938974657267738632016-06-28T15:30:06.171-05:002016-06-28T15:30:06.171-05:00Bill accidentally deleted some comments. I've ...Bill accidentally deleted some comments. I've recovered a few of them.<br /><br />n^O(n) seems fairly HUGE as a bound. not Ackermann function huge, but it feels like if someone said “Hey, I’ve got a 3-SAT solver that runs in n^1,000,000 time; something to establish it can be bounded, but not in any useful way. <br /><br />-> A 3-SAT solver that runs in n^1,000,000 time would be a pretty huge result.<br /><br />The general result has a huge and impractical bound. The result for 4 agents still seems nice because it requires around 200 cuts whereas the previous algorithms had no bound on the cuts. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.com