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?

Secret_Very_Secret
in Computer Science

Featured Replies

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

 

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

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

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.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.