29 + Interview Questions in Intractable Problems in Automata Theory Page 1 InterviewSolution

1.	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
Answer» Right option is (a) Statement: Hamiltonian cycles through any fixed edge is always even, so if one such CYCLE is given, the SECOND one must also exists. The best explanation: Handshaking lemma states that ‘Every finite undirected graph has an even number of verticeswith ODD DEGREE.

Discussion

2.	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
Answer» Right choice is (d) None of the mentioned The explanation: This is a list of some PROBLEMS which are in NP: a) All problems in P b) Decision version of INTEGER FACTORIZATION method c) Graph Isomorphism Problem d) All NP COMPLETE problems, etc.

Discussion

3.	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
Answer» The correct choice is (d) all of the mentioned The best I can explain: A problem X belongs to P COMPLEXITY class if there exist ATLEAST 1 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. Thus, all the OPTIONS are correct.

Discussion

4.	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
Answer» Correct CHOICE is (c) Both (a) and (b) The best explanation: NP can be defined USING DETERMINISTIC TURING machines as verifiers.

Discussion

5.	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
Answer» CORRECT answer is (B) Non-deterministic polynomial Explanation: NP is said to be one of the most fundamental complexity classes. NP is an acronym forNon deterministic polynomial TIME.

Discussion

6.	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
Answer» The correct ANSWER is (d) Deterministic TURING machine The best I can explain: All the decision problems that can be SOLVED USING a Deterministic turing machine using polynomial time to compute, all belong to the complexity class P.

Discussion

7.	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
Answer» Right option is (d) All of the mentioned The explanation: GIVEN a context free grammar and a string, can the string be GENERATED by the grammar? Such PROBLEMS FALL in the CATEGORY of P-complete.

Discussion

8.	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
Answer»

Discussion

9.	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
Answer» Right option is (b) polynomial time The explanation is: Most of the operations like addition, SUBTRACTION, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the INPUT and k is some NON negative integer.

Discussion

10.	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
Answer»

Discussion

11.	Which of the given problems are NP-complete?(a) Node cover problems(b) Directed Hamilton Circuit Problem(c) Both (a) and (b)(d) None of the mentionedThe question was asked in exam.Enquiry is from Node-Cover Problem, Hamilton Circuit Problem topic in division Intractable Problems of Automata Theory
Answer» CORRECT OPTION is (c) Both (a) and (b) The explanation is: VERTEX cover or Node cover PROBLEM, and HAMILTON Circuit problem, both are NP complete type of problems.

Discussion

12.	For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?(a) tree graphs(b) bipartite graphs(c) both (a) and (b)(d) none of the mentionedI got this question at a job interview.This question is from Node-Cover Problem, Hamilton Circuit Problem topic in section Intractable Problems of Automata Theory
Answer» CORRECT ANSWER is (a) TREE graphs The best explanation: For bipartite graphs, Konigs theorem ALLOWS the bipartite vertex problem to be SOLVED in polynomial time.

Discussion

13.	A problem which is both _______ and _________ is said to be NP complete.(a) NP, P(b) NP, NP hard(c) P, P complete(d) None of the mentionedI had been asked this question during an internship interview.Question is taken from Non Deterministic Polynomial Time in portion Intractable Problems of Automata Theory
Answer» Right CHOICE is (a) NP, P To explain: A PROBLEM is said to be NP Hard if an algorithm for solving the problem can be TRANSLATED from for solving any other problem. It is EASIER to show a problem NP than showing it Np Hard.

Discussion

14.	In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.(a) O(n)(b) O(n^1/2)(c) O(n^k), k∈N(d) None of the mentionedThis question was addressed to me in an interview.This is a very interesting question from Non Deterministic Polynomial Time topic in division Intractable Problems of Automata Theory
Answer» The CORRECT answer is (c) O(n^k), k∈N Explanation: The complexity class NP can be DEFINED in TERMS of NTIME as: NP=O(n^k) for k ∈N.

Discussion

15.	The hardest of NP problems can be:(a) NP-complete(b) NP-hard(c) P(d) None of the mentionedThis question was posed to me during an internship interview.My question is based upon Non Deterministic Polynomial Time topic in portion Intractable Problems of Automata Theory
Answer» Correct OPTION is (a) NP-complete To explain I would say: NP class contains MANY IMPORTANT problems, the hardest of which is NP-complete, whose solution is sufficient to deal with any other NP problem in polynomial TIME.

Discussion

16.	A generalization of P class can be:(a) PTIME(b) DTIME(c) NP(d) None of the mentionedThis question was posed to me during an online interview.The question is from Problem Solvable in Polynomial Time topic in chapter Intractable Problems of Automata Theory
Answer» The correct choice is (C) NP Best explanation: P is a specific CASE of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in POLYNOMIAL TIME.

Discussion

17.	An exact cover problem can be represented using:(a) incidence matrix(b) bipartite graph(c) both (a) and (b)(d) none of the mentionedI got this question in an interview for internship.My question is based upon Node-Cover Problem, Hamilton Circuit Problem topic in chapter Intractable Problems of Automata Theory
Answer» Correct choice is (c) both (a) and (b) Easiest explanation: The relation ‘contains’ can be represented using a bipartite GRAPH. The vertices of the graph can be divided into two DISJOINT sets, one representing the subset S and the other representing the ELEMENTS of P and one edge for each subset in S;each node is included in EXACTLY one of the edges forming the COVER.

Discussion

18.	Which of the following problems do not belong to Karp’s 21 NP-complete problems?(a) Vertex Cover problems(b) Knapsack(c) 0-1 integer programming(d) None of the mentionedThis question was addressed to me at a job interview.Query is from Node-Cover Problem, Hamilton Circuit Problem topic in chapter Intractable Problems of Automata Theory
Answer» Right CHOICE is (d) None of the mentioned The best EXPLANATION: There EXISTS a set of 21 problems that are NP-complete and the set is CALLED Karp’s 21 NP-complete problems.

Discussion

19.	State true or false?(a) Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.(b) true(c) falseThis question was addressed to me in an interview.Question is taken from Non Deterministic Polynomial Time topic in portion Intractable Problems of Automata Theory
Answer» Right option is (a) STATEMENT: If a PROBLEM X is in NP and a polynomial TIME algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP. The explanation: This is just a commutative property of NP complexity class where a problem is SAID to be in NP if it can be solved USING an algorithm which was used to solve another NP problem in polynomial amount of time.

Discussion

20.	Hamilton Circuit problem is a special case of ____________(a) travelling salesman problem(b) halting problem(c) hitting set(d) none of the mentionedI had been asked this question during an online interview.This intriguing question comes from Node-Cover Problem, Hamilton Circuit Problem topic in section Intractable Problems of Automata Theory
Answer» RIGHT option is (a) TRAVELLING SALESMAN problem Explanation: Hamilton circuit problem is a special case of travelling salesman problem, OBTAINED by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is EQUAL to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).

Discussion

21.	Which of the following problems were reduced to Knapsack?(a) Exact Cover(b) Max Cut(c) 0-1 integer programming(d) None of the mentionedThis question was posed to me during a job interview.Asked question is from Node-Cover Problem, Hamilton Circuit Problem topic in division Intractable Problems of Automata Theory
Answer» Right option is (a) Exact Cover The best I can EXPLAIN: Exact cover is a DECISION PROBLEM in computer SCIENCE to DETERMINE if an exact cover exists.

Discussion

22.	Which of the following cannot be solved using polynomial time?(a) Linear Programming(b) Greatest common divisor(c) Maximum matching(d) None of the mentionedI had been asked this question in homework.This interesting question is from Problem Solvable in Polynomial Time in division Intractable Problems of Automata Theory
Answer» RIGHT ANSWER is (d) None of the mentioned The best explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges WITHOUT common vertices. Given a graph (V, E), a matchingM in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.

Discussion

23.	The value of constants like p and e can be calculated in:(a) polynomial time(b) non-polynomial time(c) cannot be calculated(d) none of the mentionedThe question was asked during an interview.Question is from Problem Solvable in Polynomial Time topic in division Intractable Problems of Automata Theory
Answer» Right CHOICE is (a) polynomial time Explanation: The value of such constants can be CALCULATED using algorithms which have time COMPLEXITY in terms if O(n^k) i.e polynomial time.

Discussion

24.	Which of the following contains NP?(a) PSPACE(b) EXPSPACE(c) Both (a) and (b)(d) None of the mentionedThe question was posed to me in class test.This intriguing question comes from Non Deterministic Polynomial Time in portion Intractable Problems of Automata Theory
Answer» Right option is (C) Both (a) and (b) To elaborate: It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, SINCE the same algorithm operates in EXPONENTIAL time.

Discussion

25.	Hamilton circuit problem can have the following version/s as per the input graph:(a) directed(b) undirected(c) both (a) and (b)(d) none of the mentionedThis question was posed to me in an internship interview.This interesting question is from Node-Cover Problem, Hamilton Circuit Problem in division Intractable Problems of Automata Theory
Answer» The correct option is (c) both (a) and (b) The BEST I can explain: Hamilton circuit problem is a problem DETERMINING whether a Hamiltonian path(a path in an undirected or directed graph that visits each VERTEX EXACTLY once) exists in a graph(directed or undirected).

Discussion

26.	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

27.	Which of the following options are correct with reference to P-complete problems?(a) used for the problems which are difficult to solve in limited space(b) every problem in P can be reduced to it using proper reductions(c) complete problem for complexity class P(d) all of the mentionedI have been asked this question in quiz.The question is from Problem Solvable in Polynomial Time in section Intractable Problems of Automata Theory
Answer» The correct choice is (d) all of the mentioned Explanation: The NOTION of P-complete DECISION problems is useful in the analysis of: a) which problems are tough to parallelize effectively b) which problems are difficult to solve in limited SPACE

Discussion

28.	Which of the following cannot solve Hamilton Circuit problem?(a) DNA Computer(b) Monte Carlo algorithm(c) Dynamic programming(d) None of the mentionedI had been asked this question at a job interview.Question is from Node-Cover Problem, Hamilton Circuit Problem in division Intractable Problems of Automata Theory
Answer» Correct CHOICE is (d) None of the mentioned For explanation I would say: Using Inclusion-exclusion PRINCIPLE, Andreas showed how to solve Hamilton Circuit PROBLEM in arbitrary n-vertex graphs by a Monte Carlo ALGORITHM in time O(1.657n).

Discussion

29.	Travelling sales man problem belongs to which of the class?(a) P(b) NP(c) Linear(d) None of the mentionedThe question was asked in an online quiz.I'd like to ask this question from Non Deterministic Polynomial Time topic in division Intractable Problems of Automata Theory
Answer» RIGHT answer is (b) NP For explanation: Travelling Salesman Problem: GIVEN an input matrix of DISTANCES between N CITIES, this problem is to determine if there is a route visiting all cities with total distance less than k.

Discussion

Explore topic-wise InterviewSolutions in .

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

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

Which of the given problems are NP-complete?(a) Node cover problems(b) Directed Hamilton Circuit Problem(c) Both (a) and (b)(d) None of the mentionedThe question was asked in exam.Enquiry is from Node-Cover Problem, Hamilton Circuit Problem topic in division Intractable Problems of Automata Theory

A problem which is both _ and ___ is said to be NP complete.(a) NP, P(b) NP, NP hard(c) P, P complete(d) None of the mentionedI had been asked this question during an internship interview.Question is taken from Non Deterministic Polynomial Time in portion Intractable Problems of Automata Theory

The hardest of NP problems can be:(a) NP-complete(b) NP-hard(c) P(d) None of the mentionedThis question was posed to me during an internship interview.My question is based upon Non Deterministic Polynomial Time topic in portion Intractable Problems of Automata Theory

A generalization of P class can be:(a) PTIME(b) DTIME(c) NP(d) None of the mentionedThis question was posed to me during an online interview.The question is from Problem Solvable in Polynomial Time topic in chapter Intractable Problems of Automata Theory

Which of the following contains NP?(a) PSPACE(b) EXPSPACE(c) Both (a) and (b)(d) None of the mentionedThe question was posed to me in class test.This intriguing question comes from Non Deterministic Polynomial Time in portion Intractable Problems of Automata Theory

Travelling sales man problem belongs to which of the class?(a) P(b) NP(c) Linear(d) None of the mentionedThe question was asked in an online quiz.I'd like to ask this question from Non Deterministic Polynomial Time topic in division Intractable Problems of Automata Theory