Virtual Labs

Acceptance by Non-Deterministic Turing Machines

What is the main difference between a Deterministic Turing Machine (DTM) and a Non-Deterministic Turing Machine (NDTM)?

a: DTM has multiple tapes while NDTM has only one tape Explanation

Explanation

b: DTM follows a single computation path while NDTM can explore multiple paths simultaneously Explanation

Explanation

c: DTM is faster than NDTM in all cases Explanation

Explanation

d: DTM uses binary alphabet while NDTM uses any alphabet Explanation

Explanation

What does the 'non-deterministic' aspect of NDTM refer to?

a: The machine makes random choices Explanation

Explanation

b: The machine can be in multiple states at the same time Explanation

Explanation

c: The machine can have multiple possible transitions for the same state-symbol pair Explanation

Explanation

d: The machine cannot halt Explanation

Explanation

Which class of languages do Turing Machines (both DTM and NDTM) recognize?

a: Regular Languages Explanation

Explanation

b: Context-Free Languages Explanation

Explanation

c: Context-Sensitive Languages Explanation

Explanation

d: Recursively Enumerable Languages Explanation

Explanation

What is the relationship between DTM and NDTM in terms of computational power?

a: NDTM is more powerful than DTM Explanation

Explanation

b: DTM is more powerful than NDTM Explanation

Explanation

c: They have equivalent computational power Explanation

Explanation

d: Their power depends on the specific problem Explanation

Explanation

What does the complexity class P represent?

a: Problems solvable by NDTM in polynomial time Explanation

Explanation

b: Problems solvable by DTM in polynomial time Explanation

Explanation

c: Problems that are undecidable Explanation

Explanation

d: Problems solvable in exponential time Explanation

Explanation

What does the complexity class NP represent?

a: Problems that cannot be solved in polynomial time Explanation

Explanation

b: Problems solvable by NDTM in polynomial time Explanation

Explanation

c: Problems that are undecidable Explanation

Explanation

d: Problems solvable only in exponential time Explanation

Explanation

Which of the following is an equivalent definition of NP?

a: Problems that can be solved in polynomial time Explanation

Explanation

b: Problems whose solutions can be verified in polynomial time Explanation

Explanation

c: Problems that require exponential time to solve Explanation

Explanation

d: Problems that are undecidable Explanation

Explanation

The Traveling Salesman Problem (TSP) decision version is in which complexity class?

a: P Explanation

Explanation

b: NP Explanation

Explanation

c: NP-Hard Explanation

Explanation

d: Undecidable Explanation

Explanation

What is the main practical limitation of NDTMs?

a: They cannot solve any useful problems Explanation

Explanation

b: They are slower than DTMs Explanation

Explanation

c: They cannot be physically implemented Explanation

Explanation

d: They use too much memory Explanation

Explanation

In the context of NDTMs, what does 'guessing' refer to?

a: Making random choices Explanation

Explanation

b: Using probability to make decisions Explanation

Explanation

c: Exploring all possible computation paths simultaneously Explanation

Explanation

d: Using heuristics to find solutions Explanation

Explanation

Which of the following problems is typically used as an example of an NP problem?

a: Sorting an array Explanation

Explanation

b: Finding the shortest path in a graph Explanation

Explanation

c: Sudoku solving Explanation

Explanation

d: Binary search Explanation

Explanation

What is the significance of the P vs NP problem?

a: It determines which problems are solvable Explanation

Explanation

b: It asks whether every problem verifiable in polynomial time is also solvable in polynomial time Explanation

Explanation

c: It compares the speed of different algorithms Explanation

Explanation

d: It determines the memory requirements of algorithms Explanation

Explanation