fiveworlds Posted March 23, 2019 Share Posted March 23, 2019 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? Link to comment Share on other sites More sharing options...
Strange Posted March 23, 2019 Share Posted March 23, 2019 This doesn't answer your question, but you might find it interesting: https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/ 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