Problem Solvable in Polynomial Time Online Exam Quiz
Problem Solvable in Polynomial Time GK Quiz. Question and Answers related to Problem Solvable in Polynomial Time. MCQ (Multiple Choice Questions with answers about Problem Solvable in Polynomial Time
'a' in a-machine is :
Options
A : Alan
B : arbitrary
C : automatic
D : None of the mentioned
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.
Options
A : 1
B : 2
C : 3
D : all of the mentioned
A turing machine is a
Options
A : real machine
B : abstract machine
C : hypothetical machine
D : more than one option is correct
A turing machine operates over:
Options
A : finite memory tape
B : infinite memory tape
C : depends on the algorithm
D : none of the mentioned
In the above problem, if the input is binary, the class the problem belongs?
Options
A : EXPSPACE
B : DLOGTIME
C : EXPTIME-complete
D : All of the mentioned
State true or false?^ Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?^ The given problem is P-complete.
Options
A : TRUE
B : FALSE
C : -
D : -
Which of the following is a P-complete type of problem?
Options
A : Circuit Value problem
B : Linear programming
C : Context free grammar membership
D : All of the mentioned
Which of the following options are correct with reference to P-complete problems?
Options
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 mentioned
Which of the functions are not performed by the turing machine after reading a symbol?
Options
A : writes the symbol
B : moves the tape one cell left/right
C : proceeds with next instruction or halts
D : none of the mentioned
Which of the problems were not answered when the turing machine was invented?
Options
A : Does a machine exists that can determine whether any arbitrary machine on its tape is circular.
B : Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol
C : Hilbert Entscheidungs problem
D : None of the mentioned
Ambiguous Grammar more Online Exam Quiz
CFG-Eliminating Useless Symbols
Deterministic Finite Automata-Introduction and Definition
Finding Patterns in Text,Algebric Laws and Derivatives
From Grammars to Push Down Automata
Node-Cover Problem, Hamilton Circuit Problem
Properties-Non Regular Languages
Regular Language & Expression - 1
Turing Machine-Notation and Transition Diagrams