7. TIME COMPLEXITY

Question 1

How do we compute the running time of an algorithm Ð

Answer 1

As a function of the length of the string representing the input and don’t consider any other parameters.

Question 2

What is asymptotic analysis?

Answer 2

One convenient form of estimation, where we seek to understand the running time of the algorithm when it is run on large inputs

Question 3

The asymptotic notation is also called

Answer 3

big-O notation

Question 4

Big-O notation has a companion called small-o notation. How does that work?

Answer 4

Big-O notation says that one function is asymptotically no more than another. To say that one func- tion is asymptotically less than another, we use small-o notation.

Question 5

Polynomial time algorithms are fast enough for many purposes, but exponential time algorithms are rarely useful. Why is that ?

Answer 5

For example, let n be 1000, the size of a reasonable input to an algorithm. In that case, n^3 is 1 billion, a large but manageable number, whereas 2^n is a number much larger than the number of atoms in the universe.

Question 6

Exponential time algorithms typically arise when we solve problems by exhaustively searching through a space of solutions, called ?

Answer 6

brute-force search.

Question 7

All reasonable deterministic computational models are ?

Answer 7

polynomially equivalent.

Question 8

What is P ?

Answer 8

P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine.

Question 9

The class P plays a central role in our theory and is important because

Answer 9

1. P is invariant for all models of computation that are polynomially equivalent to the deterministic single-tape Turing machine, and
2. P roughly corresponds to the class of problems that are realistically solv-
   able on a computer.

Question 10

A verifier for a language A is an algorithm V , where

Answer 10

A = {w| V accepts ⟨w, c⟩ for some string c}.
We measure the time of a verifier only in terms of the length of w, so a polynomial time verifier runs in polynomial time in the length of w. A language A is polynomially verifiable if it has a polynomial time verifier.

Question 11

What is a certificate, or proof, of membership in A ?

Answer 11

A verifier uses additional information, represented by the symbol c in Defini- tion 7.18, to verify that a string w is a member of A. This information is called a certificate, or proof, of membership in A.

Question 12

What is NP ?

Answer 12

NP is the class of languages that have polynomial time verifiers.

Question 13

The term NP comes from ?

Answer 13

nondeterministic polynomial time

Question 14

A language is in NP iff it is decided by some nondeterministic polynomial time
Turing machine.

Question 15

We define the nondeterministic time complexity class NTIME(t(n)) as

Answer 15

analogous to the deterministic time complexity class TIME(t(n)).

Question 16

P

Answer 16

the class of languages for which membership can be decided quickly

Question 17

NP

Answer 17

the class of languages for which membership can be verified quickly.

Question 18

The question of whether P = NP is one of the greatest unsolved problems in theoretical computer science and contemporary mathematics.

Question 19

what are NP-complete problems

Answer 19

Certain problems in NP whose individual complexity is related to that of the entire class. If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable.

Question 20

A Boolean formula is satisfiable if some assignment of 0s and 1s to the variables makes the formula evaluate to ?

Answer 20

1.

Question 21

A function f : Σ∗ −→ Σ∗ is a polynomial time computable function if some polynomial time Turing machine M exists that halts with just f (w) on its tape, when started on any input w.

Question 22

Language A is polynomial time mapping reducible,1or simply polynomial time reducible, to language B, written A ≤P B, if

Answer 22

a polynomial time computable function f : Σ∗ −→ Σ∗ exists, where for every w,
w ∈ A ⇐⇒ f ( w ) ∈ B .
The function f is called the polynomial time reduction of A to B.

Question 23

A language B is NP-complete if it satisfies two conditions:

Answer 23

1. B is in NP, and
2. every A in NP is polynomial time reducible to B.