Question

State true or false?

(a) , does that machine halt on that input within the first T-steps?

(b) The given problem is P-complete.

(c) true

(d) false

I have been asked this question in class test.

This question is from Problem Solvable in Polynomial Time topic in division Intractable Problems of Automata Theory

Answer 1

Correct answer is (a) , does that machine halt on that input within the first T-steps?

Explanation: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.