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) falseI 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

State true or false?(a) , does that machine halt on that input within

1.	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) falseI 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» 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.

Discussion

No Comment Found

Related InterviewSolutions

State true or false:Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.(a) Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.(b) true(c) falseThe question was posed to me in an internship interview.My doubt is from Node-Cover Problem, Hamilton Circuit Problem in portion Intractable Problems of Automata Theory
Which of the following are not in NP?(a) All problems in P(b) Boolean Satisfiability problems(c) Integer factorization problem(d) None of the mentionedThis question was posed to me in semester exam.Question is from Non Deterministic Polynomial Time in portion Intractable Problems of Automata Theory
A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.(a) 1(b) 2(c) 3(d) all of the mentionedThe question was posed to me during an interview for a job.The query is from Problem Solvable in Polynomial Time topic in chapter Intractable Problems of Automata Theory
Which of the following can be used to define NP complexity class?(a) Verifier(b) Polynomial time(c) Both (a) and (b)(d) None of the mentionedThe question was asked during an internship interview.This interesting question is from Non Deterministic Polynomial Time topic in chapter Intractable Problems of Automata Theory
What does NP stands for in complexity classes theory?(a) Non polynomial(b) Non-deterministic polynomial(c) Both (a) and (b)(d) None of the mentionedThis question was addressed to me in class test.My question is from Non Deterministic Polynomial Time in section Intractable Problems of Automata Theory
The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.(a) Push Down automata(b) DFA(c) NDFA(d) Deterministic Turing machineI had been asked this question by my school teacher while I was bunking the class.Asked question is from Problem Solvable in Polynomial Time topic in division Intractable Problems of Automata Theory
Which of the following is a P-complete type of problem?(a) Circuit Value problem(b) Linear programming(c) Context free grammar membership(d) All of the mentionedThe question was posed to me in an interview.Enquiry is from Problem Solvable in Polynomial Time in chapter Intractable Problems of Automata Theory
The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.(a) Push Down automata(b) DFA(c) NDFA(d) Deterministic Turing machineThe question was asked during an interview.This is a very interesting question from Problem Solvable in Polynomial Time topic in section Intractable Problems of Automata Theory
If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:(a) non-polynomial time(b) polynomial time(c) infinite time(d) none of the mentionedI got this question in a national level competition.Enquiry is from Problem Solvable in Polynomial Time in section Intractable Problems of Automata Theory
If the number of steps required to solve a problem is O(n^k), then the problem is said to be solved in:(a) non-polynomial time(b) polynomial time(c) infinite time(d) none of the mentionedI had been asked this question in a national level competition.My doubt is from Problem Solvable in Polynomial Time in division Intractable Problems of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment