Sign in to follow this  

Are deterministic Multi-track turing machines in P

Recommended Posts

If an algorithm runs say SAT runs in polynomial time on a deterministic multi-track Turing machine through the use of parallelization with 2^n tapes is the algorithm in P?

Share this post

Link to post
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
Sign in to follow this