Computability and Complexity

What are the characteristics of a problem?

1. a uniform class of questions of which the type of input and answer must be precisely definable

2. can be solved by providing a function or deciding whether a given element belongs to a set

3. the problem has a definite and finite answer representing the solution

What is an EP?

A procedure that results in a solution to a problem in a finite number of steps

What makes a problem computable?

a problem is computable iff the answer can be computed by carrying out a specific EP in P

What does the church-turing thesis state?

Any real-world computation can be translated into an equivalent computation using a Turing machine or by λ-calculus

What are the properties of an EP?

1. The procedure is set out as a finite number of exact instructions 2. It must produce the desired results in a finite number of steps 3. Must be carried out by a human unaided by machinary 4. The procedure must have no interaction from a human

What does the Halting Problem state

The halting problem asks the question of whether a program can detect whether there exists an infinite loop in their program

What is a decision problem?

one that can be solved with an algorithm that considers a given statement and answers "yes" or "no" according to whether the statement is universally valid"

What would the outcome be if an algorithm to the decision problem exists?

If it exists then proofs for mathematical statements could be automated

What is an undecidable problem?

an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer.

What is a semi-decidable problem

There exists an algorithm, that given an input, the algorithm can recognize if the input belongs to the set of valid inputs for the problem, but it may run indefinitely or fail to terminate if the input does not belong to the set. It's not guaranteed to halt on all inputs.

What is problem reduction?

finding a way to convert problem A to problem B, so that a solution to problem B can be used to solve problem A

Why is reduction important?

A reduction to problem A to problem B shows that problem B is at least as difficult to solve as problem A

What is the totality problem?

The totality problem is to decide whether an arbitrary program P halts on all inputs, if it does it computes a total function

What is the Proof Strategy for the Totality Problem?

1. Prove that the halting problem is reducible to the totality problem 2. For any program P and input D, we create another program Q that takens an arbitrary input L 3. Q runs P on D 4. Q halts on all inputs if and only if P halts on input D, which would be the solution to the halting problem If an algorithm can solve the totality problem it can be used to solve the halting problem. Since no algorithm can solve the halting problem, the totality problem must also be unsolvable

What is the equivalence problem?

The equivalence problem is to decide whether two programs are equivalent; that is they produce the same output for the same input

How do we prove that the equivalence problem is undecidable?

1. We prove that the totality problem is reducible to the equivalence problem. 2. . For any program P, we can construct a program T that takes any input D, runs P on that input, and outputs true if P halts on D. 3. Construct a program U that takes any input and outputs True 4. If an algorithm can tell us whether T and U are equivalent, it can tell us whether P halts on all inputs

A property of a program can be viewed as [...]

the set of programs that have that property, which is thus a decision problem

What is a function/non-trivial property of a program?

one that some programs have and some don't

What does Rice’s Theorem state?

Rice's Theorem says that any functional property of programs are undecidable

What does it mean to “Accept the Decision Procedure” with regards to dealing with undecidable problems

It may return false negatives. For example, type checking may return false negatives or require (some) type declarations or hints.

What does it mean to “Give up on Uniformity” with regards to dealing with undecidable problems

instead of doing program verification for all inputs, do program testing with some inputs, and make probabilistic arguments.

What does it mean to “Give up on Automation” with regards to dealing with undecidable problems

For example, in program verification, proof is assisted by the machine, but guided by a human.

What does it mean to “Simplify the Problem”

For example, instead of doing program verification on the full C programming language, work with a variant without pointers.

What are the four ways that we deal with undecidable problems?

1. Approximate the Decision Procedure

2. Give up on Uniformity

3 Give up on Automation

4. Simplify the problem

A system rules is said to be Turing complete if [...]

it can be used to simulate any Turing Machine

A program p consists of [...]

a list of labelled instructions s

Machine state consists of [...]

instructions and next store

A TM tape consits of [...]

an alphabet or blank symbol

What are the three Complexity Classes

Problems in LIN are solvable by linear algorithms Problems in P are solvable by polynomial algorithms Problems in EXP are solvable by exponential algorithms

A linear algorithm is likely to be [...]

feasible for all data sizes.

Many polynomial algorithms [...]

are feasible for practical input data sizes, but unfortunately many are not

An exponential algorithm is

infeasible for all but the smallest data sizes.

The “Big-O” notation is useful for indicating the

quality or complexity of an algorithm in terms of asymptotic worst-case runtime.

The extended church-turing thesis

All notions of computation can simulate each other up to a polynomial factor

Why are there doubts on whether the extended church-turing thesis is true?

a highly parallel computer may be able to efficiently compute what a sequential computer cannot.

What is sequential computing?

refers to the process where all the instructions are executed in a sequence

What does the The Sequential Computation Thesis (also called Cook’s Thesis) state?

all notions of sequential computation can simulate each other up to a polynomial factor

All sequential computers have related execution times which means that [...]

any algorithm which runs in polynomial time of one computer can run in polynomial time on any other.

What is parallel computation?

Parallel computing refers to the process of breaking down larger problems into smaller problems by multiple processors communicating via shared memory, the results of which are combined upon completion as part of an overall algorithm

What does the Cobham-Edmonds Thesis state?

Feasible problems are those exactly in P

The Cobham-Edmonds Thesis states that feasible problems are those exactly in P. However there is a problem as [...]

the timebound does not necessarily indicate feasibility EXP timebound does not indicate infeasibility and a P timebound does not indicate feasibility

What are some example problems that are known to be in P?

Fast Fourier Transform, Shortest path in a graph, Finding Maximum source flow to sink in a graph, Primality, Matrix Multiplication

What is Fast Fourier Transform?

Converts waves into a spectrum

What are the two operations that The Cooley-Turkey FFT performs ?

1. Decomposition of Signal: breaks down the original signal into smaller components. 2. calculates the frequency spectra by calculating the frequency components of each of these smaller signals

The Floyd-Worshall algorithm calculates [...]

the shortest path of a graph by comparing all possible paths through to a graph It has a time complexity of O(N³)

The Ford-Fulkerson algorithm finds [...]

the maximum flow through a network from source to sink The complexity of the algorithm is O(M x f) where M is the number of links and f is the maximum flow

Primality finds out [...]

whether a positive natural number k is prime

A simple primality test is to perform [...]

trial division which has a complexity of O(√2n)

The alternative primality test is [...]

AKS which has a complexity of O¹² but this can be reduced

matrix multiplication can be conducted in [...]

the naive way (O^3) or Strassen's algorithm which is O(N^2.80)

What are problems not known to be in P?

1. TSP 2. Bin-packing problem 3. Graph colouring Problem 4. Timetabling problem

What is TSP?

The travelling salesperson problem is to decide if a salesperson can complete a round trip of 𝑁 cities within a given mileage allowance, visiting each city exactly once?

What is the complexity of TSP?

Brute-force O(n!) Dynamic Programming is O(n² 2^(n-1))

What the Hamilton Cycle Problem?

The Hamilton cycle problem is to decide whether a round trip that visits each city exactly once is even possible.

What is the bin-packing problem?

The bin-packing problem is to decide if 𝑇 trucks, each of which can carry a maximum load 𝑊, can carry 𝑁 crates of different weights

What is the knapsack problem?

The knapsack problem is to pack a knapsack that can hold weight 𝑊 with items of different weights and values.

What is the Graph Colouring Problem?

to assign colours to each vertex of a graph 𝐺 such that no adjacent vertices get same colour. The aim is to minimize the number of colors while coloring a graph.

What is the Timetabling Problem?

The timetabling problem is to create a timetable so that given a list of modules, a list of students enrolled on those modules, and the timeslots available, no student has a clash.

How can we make progress to solve these algorithms not in P?

To make progress, use algorithms that find solutions that are approximate, solutions that come quickly on average, solutions that are probably correct

Describe the complexity class NP

Is a class for which there are no known polynomial algorithms for finding solutions but there are polynomial algorithms for checking solutions

What is the formal definition for NP?

NP (Non-deterministic Polynomial Time) is the collection of decision problems that can be solved by a non-deterministic machine in polynomial time

What is the complexity class NP-Hard?

A decision problem H is NP-hard if every problem L in NP can be reduced to H in polynomial time

What are the properties of problems in NP-Hard?

Property 1: Hard problems do not have to be in NP and do not need to be a decision problem

Property 2: The NP-hard problems are at least as hard as the NP problems

Property 3: If there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in Polynomial time

What are NP-complete problems?

A decision problem H is NP-complete if H is a problem in NP and every problem L in NP can be reduced to H in polynomial time.

What are the properties of NP-complete problems?

Property 1: The problems in NP-complete are the hardest problems in NP

Property 2: if a (deterministic) polynomial algorithm can be found to solve any problem in NP-complete, every NP problem is solvable in polynomial time

What is the SAT problem?

to assign values to the variables of a boolean formula φ to make it true SAT problem is the first proved NP-complete problem SAT - satisfying assignment

What are some examples of NP-complete problems?

1: Clique 2: the string correction problem 3: the Rubik's cube problem 4: the subgraph isomorphism problem

What is the clique problem?

The clique problem is to find a fully-connected subgraph in a graph. It is NP-complete.

What is the string correction problem?

compute the shortest edit distance between one string and another. It is NP complete. Here we want to go change the string rain to be shine. We do this iteratively and replace r with s, a with h and then insert e to obtain SHINE

What is the Rubik's cube problem?

Is to compute the minimal unscrambling action needed to reset the cube however there are a stupid number of permutations thus it is NP complete 43,252,003,374,489,856,000 Permutations (Mamma Mia)

What is the subgraph isomorphism problem?

The subgraph isomorphism problem is to determine whether one graph 𝐺 contains a subgraph that is isomorphic to 𝐻. It is NP complete. isomorphic - similar in form and relations

What is the k-Clique problem?

the problem asks if there exists a k-clique (the k vertices are all mutually adjacent) in graph G

What is the approach to show that k-clique is NP-complete?

1. Design a method that reduces an instance of the 3SAT problem to an instance of the k-Clique problem

2. Show that the k-Clique problem is in NP

3. Show that if there exists a solution to the 3SAT problem if and only if there is a k-clique in the constructed graph G for the k-clique problem

What is 3SAT?

3SAT, or the Boolean satisfiability problem, is a problem that asks whether there is some combination of literals that make the formula to be true. Each clause must contain at least one literal which evaluates to be true

What is the first step of reducing an instance of the 3SAT problem to an instance of the k-Clique problem?

Let phi φ be an instance of the 3SAT problem

We reduce this boolean formula into an undirected graph G by grouping nodes in G into k groups of three nodes called triples

Each triple corresponds to one of the clauses in the formula

Each node within a triple correspond to a literal in the corresponding cause

What are some of the rules to construct the graph G in context of the 3SAT reduction?

No connections between nodes in the same triple

No connections between complementary nodes (i.e xₙ and ∼xₙ) cannot be connected

What is the second step of reducing an instance of the 3SAT problem to an instance of the k-Clique problem?

The second step is to show that the k-Clique problem is in NP class which can be verified if a subgraph of k vertices is a clique or not

What is the third step of reducing an instance of the 3SAT problem to Clique

Show that there is exists a solution to the 3SAT problem if and only if there is a k-clique in the constructed graph G for the k-Clique problem

What is the forward argument to show that a solution exists for the 3SAT problem?

If there is a solution for the 3SAT problem, then at least one literal in each clause is true. We select the corresponding node from each triple in G to form a subgraph of k vertices. Based on the construction of G, the subgraph must be a k-clique

What is the backward argument to show that a solution exists for the 3SAT problem?

Suppose there is a k clique in the graph G. It is known that each node in the k-clique is from one clause in the 3SAT problem. We set the corresponding k literals in the k clauses to be true. As a result we find a solution to the 3SAT problem

What is the P vs NP problem?

If it easy to check that a solution to a problem is correct is it also easy to solve the problem?

What is the argument for P ≠ NP

Many researchers have attempted to find polynomial algorithms for specific problems in NP in their area but all have failed which suggests that P ≠ NP

What is the argument for P == NP?

A few researchers believe that P == NP but that the algorithm required no-one can ever understand and thus find them

What is a misconception about parallel programming?

Running code on a parallel computer will make it run faster. One must think of parallel algorithms and implement them on parallel computers

Are some problems limited to having a significant speed up on a parallel computers?

While it is believed that there are inherently sequential problems that do not admit any significant speed up on a parallel machine, so far no problem has proved to be inherently sequential

How can parallel computations be used for matrix multiplication

Either the matrix multiplication can be decomposed into n submatrix multiplications where n submatrix multiplications can be performed by n computing processors or the matrix multiplication can be decomposed into 8 submatrix multiplications and can then be performed using 8 computing processes.

What is quicksort?

1. Select median as pivot from unsorted list

2. Divide the list into two sub lists - a low list (numbers smaller than pivot) and high list (numbers larger then pivot)

3. low list and high list recursively repeat the procedure to sort themselves out

What is the average and worst case complexity of sequential Quicksort?

Average asymptotic complexity of Quicksort is O(n log n) and the worst-case is O(n²)

What is parallel quicksort?

Each processor holds a segment of the unsorted list

At each iteration, each computing processor performs partial sorting with a given pivot, which leads to a local low list and a local high list

At each iteration all the local low list and high lists are globally arranged and redistributed across all computing processors for the next iteration

What are the problems with sequential computation of big data processing?

The computer processor has limited memory therefore the computation for the gradient needs to be performed sequentially each time for one subset of training samples. The DNN model θ is updated when the gradients for all samples are collected

How can we use parallel computation to help in BigData processing?

• N pairs for training samples are evenly divided into M portions. Each client carries one portion of the training data

• At each iteration k, each client computes the local gradient with the model θ_k

• The central processor collects gradients from all clients then updates the DNN model to obtain θ_k+1

Does using parallel computers mean that P == NP?

While parallel processors can “take care” of nondeterministic choices, it does not make P == NP because an arbitrary input size would require an arbitrary number of processors

What is the PRAM model?

Parallel Random Access Machine combines the synchronous computation model with the hierarchical memory model

What does the PRAM model consist of?

1. An unbounded number of processors

2. An unbounded global memory

3. A finite program

What does each processor of a PRAM model have?

1. A unique processor id

2. a program counter

3. An unbounded local memory

4. a flag indicating whether the processor is active or not

Why does DNA computing have enormous potential

1. Uses 1b times less energy than silicon computers

2. uses 1t times less space than silicon computers

3. It has the ability to self-assemble

4. It is easily available and cheap

What are the four operations on DNA

1. Synthesis

2. Separation

3. PCR (polymerase chain reaction)

4. Gel electrophoresis

What is the purpose of performing synthesis and how does it relate to computation?

Strands may be synthesised (created) by a machine that is supplied with the required sequences of bases. This can be used to represent entities of optimisation problems

What is separation with regards to DNA computing?

Strands may be separated by a machine that is supplied with a short sequence of bases that they contain.

What is PCR with regards to DNA computation?

PCR quickly amplifies DNA (makes it longer) by making copies of a specific region that lies between two known sequences. For the Hamilton path problem, PCR can be used to select trips with the proper city and end with the final city