Computational complexity Theory

Question 1

NP Stands for

Answer 1

Non Deterministic Polynomial Time

Question 2

P

Answer 2

A fundamental complexity class that contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time

Question 3

Tractable vs intractable

Answer 3

A problem that can be solved in theory (e.g. given large but finite resources, especially time), but for which in practice any solution takes too many resources to be useful, is known as an intractable problem.[14] Conversely, a problem that can be solved in practice is called a tractable problem, literally “a problem that can be handled”.

Question 4

Cobham’s thesis

Answer 4

asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P.[4] In modern terms, it identifies tractable problems with the complexity class P.

Question 5

Cobham’s thesis limitations

Answer 5

Obviously in practice not all exponentials are slow and not all polynomials are fast for reasonable values of n. E.g n^10000 is practically a lot slower than .000001^(.00001n)

Question 6

L

Answer 6

the class of problems decidable by a deterministic Turing Machine using a logarithmic amount of memory space

Question 7

L aka

Answer 7

LSpace or DLSpace

Question 8

NP

Answer 8

is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine; also can be thought of as the set of decision problems for which the problem instances, where the answer is “yes”, have proofs verifiable in polynomial time by a deterministic Turing machine

Question 9

Turing degree of a set

Answer 9

is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set.

Question 10

a Cook reduction

Answer 10

A Turing reduction in which the oracle machine runs in polynomial time

Question 11

How do we represent a decision problem?

Answer 11

is represented as a set A of natural numbers (or strings). An instance of the problem is an arbitrary natural number (or string). The solution to the instance is “YES” if the number (string) is in the set, and “NO” otherwise.

Question 12

Oracle machine

Answer 12

a Turing machine with a black box, called an oracle, which is able to solve certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used.

Question 13

Turing reduction

Answer 13

a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B.

Question 14

Nondeterministic Turing Machine

Answer 14

a Turing machine that may have a set of rules that prescribes more than one action for a given situation

Question 15

IP stands for

Answer 15

Interactive Polynomial Time

Question 16

IP

Answer 16

the class of problems solvable by an interactive proof system

Question 17

PSPACE

Answer 17

the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Note this is different from P.

Question 18

SAT stands for

Answer 18

the Boolean Satisfiability Problem

Question 19

example of a satisfiable boolean problem vs a nonsatisfiable one

Answer 19

“a AND NOT b” is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, “a AND NOT a” is unsatisfiable.

Question 20

NP completeness

Answer 20

A decision problem C is NP-complete if:

• 1) C is in NP, and
• 2) C is in NP-hard

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1.

Question 21

IP is equivalent to what class?

Answer 21

PSpace

Question 22

NP-Hard high level definition

Answer 22

a class of problems that are at least as hard as the hardest problems in NP

Question 23

How to show that a decision problem C is in NP?

Answer 23

by demonstrating that a candidate solution to C can be verified in polynomial time [on a non deterministic turing machine though, right?? Nah actually it doesn’t matter, bc even if It is in P, it’s still in NP]

Question 24

“Complete” refers to what?

Answer 24

the property of being able to simulate everything in the same complexity class.

Question 25

Formal definition of NP-hard

Answer 25

A decision problem C is in NP-hard if every problem in NP is reducible to C in polynomial time

Question 26

Difference between solving a decision problem and verifying the solution of a decision problem?

Answer 26

…

Question 27

What is the question of whether P=NP?

Answer 27

whether NP-complete problems can be solved in polynomial time on a deterministic Turing machine

Question 28

Turing reduction vs many-one reduction

Answer 28

Many-one reductions map instances of one problem to instances of another; Turing reductions compute the solution to one problem, assuming the other problem is easy to solve.

These reduction concepts differ in that Turing reducibility can make many calls to the oracle, and it can use that information either positively or negatively, but with many-one reducibility, you get just one call to the oracle, and you have to use that particular answer as the answer to your query.

Question 29

map reduction decidability theorem

Answer 29

if A <=m B and B is decidable, then A is decidable

Question 30

What does it mean when you say problem A reduces to problem B?

Answer 30

that there exists a computable function f such that for every string w in the set associated with A, f(w) is in the set associated with B

Question 31

What notation do you use to say A map reduces to B

Answer 31

A <=m B

Question 32

What is polynomial time reduction?

Answer 32

when problem A reduces to problem B, but the mapping function f is only computable in polynomial time by deterministic Turing machine

Question 33

even more formal definition of NP-hard

Answer 33

given a language A, A is in NP-hard if for all languages B in NP, B <=p A

Question 34

More formally speaking what are decision problems in computational complexity theory normally represented as?

Answer 34

Formal languages, where you are deciding if a string belongs in a language

Question 35

If any NP complete problem can be solved in polynomial time, then what?

Answer 35

Then every problem in NP has a polynomial time algorithm

Question 36

Why are NP problems able to be verified in polynomial time on a DTM, even though they cant be solved in polynomial time on a DTM?

Answer 36

This isn’t an exact proof, but in general you can verify solutions quicker than it takes to come up with a solution. E.g traveling salesman problem (you want to visit let’s say 100 cities with less than 1000 miles . Checking if a path visits 100 cities and is less than 1000 miles is easier than coming up with the correct path. Easier in terms of takes less operations

Question 37

DTM

Answer 37

Deterministic Turing machine