Q.1 Which of the following best describes a non-deterministic Turing machine (NDTM)?
A Turing machine that can write multiple symbols simultaneously
A Turing machine that can choose between multiple transitions at each step
A Turing machine that can only read input without moving the tape
A Turing machine that always halts in polynomial time
Explanation - A non-deterministic Turing machine can have multiple possible next moves for a given state and tape symbol, allowing it to 'branch' into different computational paths simultaneously.
Correct answer is: A Turing machine that can choose between multiple transitions at each step
Q.2 In alternating Turing machines, states are divided into which types?
Deterministic and non-deterministic states
Existential and universal states
Start and accepting states
Read and write states
Explanation - Alternating Turing machines generalize non-deterministic Turing machines by having existential states (where acceptance requires some path to accept) and universal states (where all paths must accept).
Correct answer is: Existential and universal states
Q.3 The class AP of problems solvable by an alternating Turing machine in polynomial time is equal to which classical complexity class?
NP
PSPACE
P
EXPTIME
Explanation - It is known that polynomial-time alternating Turing machines (AP) can solve exactly the problems in PSPACE.
Correct answer is: PSPACE
Q.4 Which of the following statements is true about non-deterministic computation?
Every non-deterministic machine can be simulated deterministically with exponential slowdown
Non-deterministic machines always halt faster than deterministic ones
Non-deterministic computation cannot solve NP-complete problems
Non-deterministic machines do not use states
Explanation - A deterministic simulation of a non-deterministic Turing machine requires exploring all computation branches, leading to potentially exponential time.
Correct answer is: Every non-deterministic machine can be simulated deterministically with exponential slowdown
Q.5 In an alternating Turing machine, acceptance from a universal state requires:
At least one computation branch accepts
All computation branches accept
Exactly half of the computation branches accept
The machine to halt immediately
Explanation - Universal states in an alternating Turing machine require that every possible branch of computation leads to acceptance for the state to be accepting.
Correct answer is: All computation branches accept
Q.6 Which complexity class is characterized by problems solvable in polynomial time by a non-deterministic Turing machine?
P
NP
PSPACE
EXPTIME
Explanation - NP (nondeterministic polynomial time) consists of decision problems solvable by a non-deterministic Turing machine in polynomial time.
Correct answer is: NP
Q.7 Alternating Turing machines are a generalization of which computational model?
Deterministic Turing machines
Non-deterministic Turing machines
Pushdown automata
Finite state machines
Explanation - Alternating Turing machines extend non-deterministic Turing machines by introducing both existential and universal states.
Correct answer is: Non-deterministic Turing machines
Q.8 Which statement is true about the relationship between P, NP, and AP?
P ⊆ NP ⊆ AP = PSPACE
AP ⊆ NP ⊆ P
NP = AP ⊆ P
P = NP = AP
Explanation - Deterministic polynomial-time problems are a subset of non-deterministic polynomial-time problems, and polynomial-time alternating Turing machines characterize PSPACE.
Correct answer is: P ⊆ NP ⊆ AP = PSPACE
Q.9 Which of the following is a key advantage of alternating Turing machines over non-deterministic ones?
They can solve PSPACE-complete problems in polynomial time
They require less memory than deterministic machines
They are always faster than non-deterministic machines
They do not require a tape
Explanation - Alternating Turing machines running in polynomial time can solve any problem in PSPACE efficiently, whereas non-deterministic machines in polynomial time cannot.
Correct answer is: They can solve PSPACE-complete problems in polynomial time
Q.10 A non-deterministic Turing machine accepts an input if:
All computation paths reject
At least one computation path accepts
No computation path accepts
The tape becomes blank
Explanation - Acceptance in non-deterministic computation requires that at least one branch of computation leads to an accepting state.
Correct answer is: At least one computation path accepts
Q.11 Which class of problems is known to be solvable by alternating Turing machines in logarithmic space?
L
NL
APSPACE
ALOGSPACE
Explanation - ALOGSPACE refers to the class of problems solvable by alternating Turing machines using logarithmic space.
Correct answer is: ALOGSPACE
Q.12 Which of the following is true about existential states in alternating Turing machines?
The machine accepts if all branches accept
The machine accepts if at least one branch accepts
The machine rejects if one branch rejects
Existential states always lead to rejection
Explanation - Existential states accept if at least one of the possible transitions from that state leads to an accepting configuration.
Correct answer is: The machine accepts if at least one branch accepts
Q.13 Non-deterministic polynomial-time computation can be verified deterministically in:
Polynomial time
Exponential time
Logarithmic time
Constant time
Explanation - A solution guessed by a non-deterministic Turing machine can be verified by a deterministic machine in polynomial time, which is the essence of NP.
Correct answer is: Polynomial time
Q.14 Which type of computation is more powerful in the sense of space complexity?
Deterministic polynomial time
Non-deterministic polynomial time
Alternating polynomial time
Deterministic logarithmic space
Explanation - Polynomial-time alternating Turing machines can solve all problems in PSPACE, making them more powerful in terms of space usage than standard polynomial-time machines.
Correct answer is: Alternating polynomial time
Q.15 In the context of alternating Turing machines, which operation corresponds to 'AND' branching?
Existential state
Universal state
Non-deterministic choice
Deterministic step
Explanation - Universal states require that all branches lead to acceptance, functioning like a logical AND across the branches.
Correct answer is: Universal state
Q.16 Which of the following statements about NDTMs and ATMs is correct?
Every ATM can be simulated by a polynomial-time NDTM with no slowdown
Every NDTM is a special case of an ATM
NDTMs require exponential space
ATMs cannot solve NP-complete problems
Explanation - Alternating Turing machines generalize non-deterministic Turing machines; NDTMs can be seen as ATMs with only existential states.
Correct answer is: Every NDTM is a special case of an ATM
Q.17 Which statement about the acceptance of alternating Turing machines is true?
Only the first computation path is considered
Acceptance depends on a combination of existential and universal state rules
All computations are rejected by default
They accept only empty input
Explanation - Alternating Turing machines combine existential and universal states, so acceptance requires considering both types of states according to their rules.
Correct answer is: Acceptance depends on a combination of existential and universal state rules
Q.18 Simulating a non-deterministic machine deterministically requires which of the following?
Only following one path
Exploring all computational branches
Ignoring some states
Writing symbols in parallel
Explanation - To simulate a non-deterministic Turing machine deterministically, we must explore every branch of the computation tree, which may require exponential time.
Correct answer is: Exploring all computational branches
Q.19 In terms of acceptance conditions, universal states are similar to which logical operator?
OR
AND
XOR
NOT
Explanation - Universal states require that all branches accept, mirroring the behavior of the logical AND operator.
Correct answer is: AND
Q.20 Which is a key characteristic of non-deterministic computation?
It allows branching into multiple computation paths simultaneously
It always runs in logarithmic time
It cannot be verified deterministically
It uses no states
Explanation - Non-deterministic machines can branch into several paths for a given input and state, representing all possible choices simultaneously.
Correct answer is: It allows branching into multiple computation paths simultaneously
Q.21 Which of the following is true about the relationship between ATM polynomial time and PSPACE?
ATM polynomial time = PSPACE
ATM polynomial time ⊂ NP
ATM polynomial time = P
ATM polynomial time = EXPTIME
Explanation - Polynomial-time alternating Turing machines can solve exactly the problems in PSPACE.
Correct answer is: ATM polynomial time = PSPACE
Q.22 Non-deterministic Turing machines differ from deterministic ones primarily in:
Tape length
Multiple possible next moves for a given configuration
Input alphabet
Tape alphabet
Explanation - NDTMs allow more than one transition from a given state and symbol, while deterministic machines allow exactly one.
Correct answer is: Multiple possible next moves for a given configuration
Q.23 Which statement correctly describes the power of ATMs over NDTMs?
ATMs can solve PSPACE-complete problems in polynomial time, NDTMs cannot
ATMs are weaker than NDTMs
ATMs are equivalent to deterministic machines
ATMs cannot simulate NDTMs
Explanation - Alternating Turing machines running in polynomial time can solve all PSPACE-complete problems efficiently, while NDTMs in polynomial time cannot reach full PSPACE power.
Correct answer is: ATMs can solve PSPACE-complete problems in polynomial time, NDTMs cannot
Q.24 Existential and universal states in ATMs correspond to which type of branching?
Existential = OR, Universal = AND
Existential = AND, Universal = OR
Existential = XOR, Universal = NOT
Existential = NOT, Universal = XOR
Explanation - Existential states require at least one branch to accept (OR), and universal states require all branches to accept (AND).
Correct answer is: Existential = OR, Universal = AND
Q.25 Which of the following is true about simulation of ATMs by deterministic machines?
Requires exponential time
Can be done in linear time
Does not require exploring all branches
Cannot be done at all
Explanation - Simulating an alternating Turing machine deterministically requires exploring all computational branches recursively, which may take exponential time.
Correct answer is: Requires exponential time