Jump to content

If there's a proof that creating tallies or any sparse language in poly-time is impossible, then what's the significance of this decision problem?


Recommended Posts

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

 

 

 

image.thumb.png.ead3cc67c489fcb974993d702b5dc092.png

 

Link to comment
Share on other sites

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 by fiveworlds
Link to comment
Share on other sites

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 account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.