Secret_Very_Secret Posted October 4, 2019 Share Posted October 4, 2019 Is there a legit proof that creating tallies or any other sparse language in poly-time is impossible? Or is this just a conjecture widely believed? Please read the picture below before going to the links. I have a paste-bin for an algorithm that solves my decision problem. https://pastebin.com/kuj2sZys I have a repl link as well. https://repl.it/repls/WiryGrandioseSearch Link to comment Share on other sites More sharing options...
fiveworlds Posted October 5, 2019 Share Posted October 5, 2019 (edited) If you want to show that, you'd have to start by disproving that a universal Turing machine with no internal states need only be slower by a logarithmic time factor compared to the machine it simulates. Since logarithmic time < polynomial time it holds that since a then b. Their is a draft of the book where that was shown here http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=EE1010E9E59F8CAA143C55745A49BD9A?doi=10.1.1.297.6224&rep=rep1&type=pdf Edited October 5, 2019 by fiveworlds Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now