9: Past Paper Stuff

Question 1

What is co-NP?

Answer 1

The set of problems whose complement is in NP.

Question 2

What is PSPACE?

Answer 2

The set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

Question 3

What is QSAT?

Answer 3

Quantified SAT, aka Quantified Boolean Formula, are problems finding the satisfiability of formulae defined in quantified propositional logic, where every variable is quantified (or bound), using either existential or universal quantifiers, at the beginning of the sentence.

Question 4

How do you determine if a problem is NP-complete?

Answer 4

Prove that the problem is in NP, and then that any problem in NP can be reduced/transformed to it (in practice only need to show 1 problem can be transformed into it since, in turn, all others must be able to transform into that 1 problem).

Question 5

How do you determine if a language can be recognised by an FSA?

Answer 5

??

Question 6

How do you determine if a language can be recognised by a PDA?

Answer 6

??

Question 7

What is Turing-completeness?

Answer 7

A programming language is said to be Turing-complete if we can simulate every Turing machine in it, or equivalently that you can simulate the Universal Turing Machine on it.

Question 8

How do you determine if an algorithm falls within the Master Theorem?

Answer 8

If it is of the general form of 𝑇(𝑛) = 𝑎 ⋅ 𝑇 (𝑛 / 𝑏) + 𝑓 (𝑛)

where 𝑎 ≥ 1 and 𝑏 > 1 are constants, and 𝑓 (𝑛) is asymptotically positive

Question 9

How can you use the master Theorem to find the time complexity of an algorithm to which it applies?

Answer 9

??

Question 10

How can you determine the best, average, and worst-case time complexities of an algorithm?

Answer 10

??

Question 11

What does it mean for a problem to be decidable, and semi-decidable?

Answer 11

A language L is Turing-decidable if there exists a decider TM, M with L = L(M). A decider TM is one that always halts and never infinitely loops. So, equivalently, a decidable problem is one that has an algorithm to resolve it to a yes/no answer.

A semi-decidable language is one which accepts all inputs of words in the language and either rejects or infinitely loops on input words not in the language. So the difference between semi and fully decidable languages is the absence of guaranteed halting found with fully decidable languages, since TMs running for semi-decidable words may infinitely loop when the input is a word no in the language.

Question 12

How can you determine if a problem is decidable, semi-decidable, or undecidable?

Answer 12

??

Question 13

How can you design a DFA to recognise a specific language?

Answer 13

??

Question 14

How can you convert from a DFA to a regular expression?

Answer 14

??

Question 15

What is the Pumping Lemma for formal languages and its proof?

Answer 15

??

Question 16

Prove that if L is a regular language then there is an NFA N with a single accept state such that L ( N ) = L. Fully justify your claim that the languages L ( N ) and L are equal.

Answer 16

??

Question 17

How do you convert from a language to a CFG?

Answer 17

??

Question 18

How do you convert from a language to a TM?

Answer 18

??

Question 19

What does it mean for a set of languages to be closed under union?

Answer 19

??

Question 20

Why is the collection of Turing-recognisable languages is closed under union?

Answer 20

??

Question 21

What is EXPTIME?

Answer 21

The set of decision problems that can be solved by a deterministic Turing machine within exponential asymptotic time.

Question 22

What is NEXPTIME?

Answer 22

The set of decision problems that can be solved by a non-deterministic Turing machine within exponential asymptotic time.

Question 23

How can you solve a recurrence relation?

Answer 23

??

Question 24

How do you convert from a language to a CFG?

Answer 24

??

Question 25

How do you prove a language to be regular?

Answer 25

??

Question 26

How do you prove a language to be irregular?

Answer 26

??

Question 27

How do you determine whether a language is context-free?

Answer 27

??

Question 28

What is the complement of a language?

Answer 28

For a language X ⊆ Σ* then the complement of X, denoted X̄, is the language of all words in Σ* that are not in X.

So X is the language built from all of the words of the alphabet Σ, and the complement of X, X̄, is the language made of all remaining words in Σ* (all words built from the alphabet Σ) that are not in X.

Question 29

Is the complement of a regular language regular? Why?

Answer 29

??

Question 30

What is Rice’s theorem?

Answer 30

Let P be a nontrivial property of the languages recognised by Turing machines. Then the following language is undecidable:

LP = { | M satisfies P}.
That is, there is no algorithm to decide whether a TM satisfies P.

Question 31

How can you determine if it is decidable if a TM accepts a given language?

Answer 31

??

Question 32

How can you determine if it is decidable if an NFA accepts a given language?

Answer 32

??

Question 33

What are the relationships between NP, co-NP, P, NP-complete, PSPACE, and co-NEXP problems?

Answer 33

??

Question 34

How can you determine if a problem is in NP?

Answer 34

It is in NP if you can provide a certificate allowing the problem to be verified by a nondeterministic TM within polynomial asymptotic time complexity.