6+7 definitions

Question 1

PSPACE

Answer 1

A problem belonds to PSPACE if and only if the amount of memory it takes to solve it grows polynomially with the input size

Question 2

3SAT

Answer 2

The decision problem of whether there is an interpretation that makes a 3CNF propositional logic formula true.

Question 3

Karp reduction

Answer 3

A polynomial-time reduction

Question 4

kCNF

Answer 4

a formula is in kCNF if each conjunct contains at most k literals.

Question 5

CNF

Answer 5

A formula in CNF consists of a conjunction of disjunctions apart from that which contains only one conjunct or that with one of more disjunctions with a single disjunct

Question 6

SAT

Answer 6

The decision problem of whether there is an interpretation that makes a propositional logic formula true

Question 7

NP complete

Answer 7

A problem that is in NP and is NP Hard

Question 8

NP Hard

Answer 8

A problem that is at least as hard as any problem in NP

Question 9

NP

Answer 9

A decision problem is in NP if for the inputs where the answer is 1, there exists a certificate that can be checked in polynomial time.

Question 10

TSP

Answer 10

Given a weighted complete graph, decide whether there is a cycle that passes through every node exactly once except for the start and end node as they are the same, an whose total weight is at most k. The TSP is always relative to a value for k.

Question 11

Intractable

Answer 11

A computable problem that does not have a polynomial-time solution

Question 12

lower bound

Answer 12

a proof that shows problem X requires at least x complexity

Question 13

upper bound

Answer 13

An algorithm that shows X requires at most x complexity

Question 14

P

Answer 14

The class of tractable problems - problems with polynomial-time solutions

Question 15

Tractable

Answer 15

Problems that can be solved by algorithms in polynomial time.

Question 16

Equivalence Problem

Answer 16

The problem of deciding whether two programs produce the exact same outputs for the same inputs. Th equivalence problem is non computable

Question 17

Totality Problem

Answer 17

The problem of deciding whether a program halts for all inputs. The totality problem is non computable

Question 18

Reduction

Answer 18

A reduction of one problem A to another problem B is a demonstration that a solution for problem B can be used to solve the original problem A. The demonstration involves an algo that transforms inputs of problem A into inputs of problem B, such that the outputs for problem B correspond with the outputs for problem A.

Question 19

DPNuc the uncomputable decision problem

Answer 19

returns 1 for an input i and if DPNuc(i) does not return 1, else 0

Question 20

Turing complete

Answer 20

If an algo can be used to simulate any other algo

Question 21

Halting problem

Answer 21

whether an algorithm halts for a given input. This is uncomputable and NP Hard

Question 22

Church-Turing thesis

Answer 22

Any algo can be represented by a Turing machine