Computational complexity Theory Flashcards
NP Stands for
Non Deterministic Polynomial Time
P
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
Tractable vs intractable
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”.
Cobham’s thesis
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.
Cobham’s thesis limitations
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)
L
the class of problems decidable by a deterministic Turing Machine using a logarithmic amount of memory space
L aka
LSpace or DLSpace
NP
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
Turing degree of a set
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.
a Cook reduction
A Turing reduction in which the oracle machine runs in polynomial time
How do we represent a decision problem?
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.
Oracle machine
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.
Turing reduction
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.
Nondeterministic Turing Machine
a Turing machine that may have a set of rules that prescribes more than one action for a given situation
IP stands for
Interactive Polynomial Time
IP
the class of problems solvable by an interactive proof system
PSPACE
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.
SAT stands for
the Boolean Satisfiability Problem
example of a satisfiable boolean problem vs a nonsatisfiable one
“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.
NP completeness
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.
IP is equivalent to what class?
PSpace
NP-Hard high level definition
a class of problems that are at least as hard as the hardest problems in NP
How to show that a decision problem C is in NP?
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]
“Complete” refers to what?
the property of being able to simulate everything in the same complexity class.
Formal definition of NP-hard
A decision problem C is in NP-hard if every problem in NP is reducible to C in polynomial time
Difference between solving a decision problem and verifying the solution of a decision problem?
…
What is the question of whether P=NP?
whether NP-complete problems can be solved in polynomial time on a deterministic Turing machine
Turing reduction vs many-one reduction
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.
map reduction decidability theorem
if A <=m B and B is decidable, then A is decidable
What does it mean when you say problem A reduces to problem B?
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
What notation do you use to say A map reduces to B
A <=m B
What is polynomial time reduction?
when problem A reduces to problem B, but the mapping function f is only computable in polynomial time by deterministic Turing machine
even more formal definition of NP-hard
given a language A, A is in NP-hard if for all languages B in NP, B <=p A
More formally speaking what are decision problems in computational complexity theory normally represented as?
Formal languages, where you are deciding if a string belongs in a language
If any NP complete problem can be solved in polynomial time, then what?
Then every problem in NP has a polynomial time algorithm
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?
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
DTM
Deterministic Turing machine
