Classical Defintions Flashcards
A function is computable if
given any input the computer provides the output within a finite amount of time
Edge decision problem
The input is a nondirected graph. The output is 1 if the number of edges in the graph is larger or equal than m, and it is 0 if the graph has a number of edges smaller than m.
Intuitively, what is the complexity of a function?
The complexity is the minimal amount of elementary operations that a computer needs to evaluate a function as a function of the input size n
Define a Boolean function
Define an m-valued Boolean function
Define a basis
A basis is a set of Boolean functions
De Morgan basis
AND, OR, NOT
Monotone basis
AND, OR
Define a logic circuit of n inputs
A logic circuit of n inputs is defined as a directed, acyclic graph
G = (V, E) for which each vertex v in V satisfies one of the following:
• v has indegree (fan-in) 0 and is called an input xi for some i in {1,2,…,n};
• v has in degree k > and is labelled with g in B , where g is a k-ary Boolean function and with an ordering on the incoming edges to v.
Axiom of Boolean Algebra: closure
There exists a domain Bn having at least two distinct element and two binary operations (and, or), such that if x and y are in Bn, so are (x and y) and (x or y)
Axiom of Boolean Algebra: identity elements
x or 0 = x
x and 1 = x
Axiom of Boolean Algebra: commutativity
x and y = y and x
x or y = y or x
Axiom of Boolean Algebra: distributivity
x or ( y and z ) = (x or y) and (x or z)
x and ( y or z ) = (x and y) or (x and z)
Axiom of Boolean algebra: complementation
If x is in B there exists x bar in b such that x and x bar is 0 and x or x bar is 1
x and 1 =
x
x or 0 =
x
x bar bar =
x
x or x =
x
x and x =
x
Theorem of Boolean algebra: associativity
x or ( y or z) = (x or y) or z = x or y or z
Theorem of Boolean algebra: de Morgan’s law
Write an expression for the XOR gate in terms of Boolean algebra
Define a complete basis
A basis B is complete if any Boolean function can be computed in an B-circuit
Define a min term
Prove that the de Morgan basis is complete
Define the size or complexity of a logic circuit
The size or complexity of a logic circuit S equals the number of its logic gates, and we denote this number by C(S)
Define the circuit complexity of a Boolean function
The circuit complexity CB (f ) of a Boolean function f with respect to a basis B is the smallest number of gates in a circuit over the basis B that computes f.
Define the depth of a logic circuit
The depth D(S) of a logic circuit S is the number of gates of the longest path of the circuit
Define the depth of a function
The depth DB(f) of a function f with respect to the basis B is the minimal depth of a logic circuit with respect to B that computes f.
Prove that if we have two complete bases one creates an upper bound on the depth and complexity of the other
Asymptotic notation: big O
Asymptotic notation: big Omega
Asymptotic notation: big Theta
Asymptotic notation: little o
Asymptotic notation: little omega
Fill in this table
Shannon’s claim
Graph colouring problem
given a nondirected graph and q colours. Can you colour the nodes of the graph so that no adjacent nodes have the same colour
Hamiltonian cycle problem
given a nondirected graph. Does it have a Hamiltonian cycle? A Hamiltonian cycle is a cycle that passes through each vertex exactly once.
Definition of a finite automaton
Accept conditions of a finite automaton
What does it mean for a finite automaton to recognise a language?
Definition of regular operations
Definition of regular expression
Define a regular language
A language described by a regular expression is called a regular language.
Theorem of regular
Theorem of regular languages
A language a regular language if and only if some finite automaton recognises it.
Define a non-deterministic finite automaton
Acceptance conditions for a non deterministic finite automaton
Compare a finite automaton and a Turing machine
The Turing machine is a generalisation of a finite automaton with the important difference that the automaton has an infinite tape on which it can write. This tape gives the machine a memory that it can use to perform more powerful computations than finite automata.
What are the 4 components of a Turing machine?
We define a single tape Turing machine. The components of a Turing machine are visualised in Fig. 12. These consists of (a) a tape, which acts like a computer memory; (b) a read-write tape head that moves along the tape and can read and write symbols; (c) a state control that functions as a ”microprocessor” that coordinates the processes on the machine; (d) a program that contains instructions on what the tape head should do, and is akin to a computer program.
What 3 things determine the state of a Turing machine at a given moment?
The state of the Turing machine at a given moment in time is determined by (a) the internal state of the state control; (b) the sequence of symbols that are present on the tape; (c) the position of the read-write tape-head. Every time instance, these three components are altered as determined by a line in the program, which constitute the elementary operations of this model of computation.
Define a Turing machine
How many Turing machines are there?
Since the sets constituting the states and the alphabets are finite, there exist a countable number of Turing machines
Non deterministic Turing machine
We define the Nondeterministic Turing ¡achine similarly as we defined the nondeterministic finite automaton. The transition function is replaced by a transition function of the form below denoting the different possible transitions. If one path of the computation halts
in the accept state, then the machine accepts the input.
Definition of a decider
We call a Turing Machine a decider if it halts on all inputs.
Definition of a Turing decidable language
We call a language Turing-decidable if some Turing machines decides it
Definition of a Turing recognisable language
We call a language Turing-recognisable if some Turing machines recognises it.
Chomsky hierarchy of languages
Definition of running time or time complexity of a Turing machine
Let M be a deterministic Turing machine that halts on all in- puts. The running time or time complexity of M is the function f : N -> N, where f(n) is the maximum number of steps that M uses on any input of length n.
Definition of time complexity class
Let t : N -> R+ be a function. The time complexity class TIME(t(n)) is the collection of languages that are decidable by an O(t(n)) time Turing machine.
Definition of class P
P is class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine
2 examples of languages in P
RELPRIME = {x, y|x and y are relatively prime}
Every regular language
Define the running time of a non deterministic Turing machine
Let M be a nondeterministic Turing machine that is a decider. The running time of M is the function f : N ->N, where f(n) is the maximum number of steps that M uses on any branch of its computation on any input of length n.
Define the nondeterministic time complexity class
The nondeterministic time complexity class NTIME(t(n)) is the collection of languages L that are decided by an O(t(n)) time nondeterministic Turing machine.
Define NP
A language is in NP if and only if it is decided by some nondeterministic polynomial time Turing machine
Examples of NP problems
the graph colouring problem
the Hamiltonian path problem
Isomorphism between binary numbers and integers
Explain the half adder and full adder circuits
The half adder has inputs A,B and outputs the direct sum (A + B) using XOR and the carry (A . B) using AND.
The full adder has inputs A,B and Cin (the carry-in) and has outputs the sum (A+B+Cin) and the carry (A.B) + (Cin.(A+B))
We use these to add multi-bit numbers, use the half adder on the least significant bits and use the carry there as the carry in for the first full adder on the next bits. Keep going until it’s done.
Write out the sums bitwise with the least significant bits at the end. If there is a carry out left over at the end add it to the front as it means there were not enough bits to represent the sum
