CS 456 third exam :)

Every subset of a regular language is regular.

False

Every language is enumerable.

True

If L is any P-time language, there is a reduction of the Boolean circuit problem (CVP) to L which can be computed in polylogarithmic time using polynomially many processors.

True

The intersection of any two RE languages is RE.

True

P-time = NC

Open

The context-free grammar equivalence problem is decidable.

False

The set of all positions of generalized checkers (N × N board for any N ) from which black can win is decidable.

True

Every function that can be mathematically defined is bounded by some recursive function.

False

There are uncountably many languages over the binary alphabet.

True

There are uncountably many RE languages over the binary alphabet.

False

If a language is both NP and co-NP, it must be P-time.

Open

There is a P-time algorithm which determines whether a given set of n positive integers has a subset whose total is n.

Open

If L1 is NP-complete and L2 is NP and there is a P-time reduction of L1 to L2, then L2 must be NP-complete.

True

Nick's Class is closed under intersection.

True

Every subset of any enumerable set is enumerable.

True

Every subset of any recursively enumerable language is recursively enumerable.

False

The computer language C++ has Turing power.

True

Binary numeral multiplication is N C.

True

There is an P-space algorithm which decides SAT.

True

Every dynamic program problem can be worked by polynomially many processors in poly-logarithmic time.

Open

If an abstract Pascal machine can perform a computation in polynomial time, there must be some Turing machine that can perform the same computation in polynomial time.

True

Let L be any undecidable RE language, and let ML be a machine which accepts L. For any string w ∈ M, let FL(w) be the number of steps ML executes, if its input is w. If w !∈ M, let FL(w) = 0. Now define TL(n) = {maxF(w) : w ∈ Σ∗ and |w| = n}. Then TL is recursive.

False

There is a polynomial time reduction of the subset sum problem to 2SAT.

Open

Every P-time dynamic programming problem has an NC reduction to CVP.

True

If a language L is accepted by a non-deterministic machine, then L must be accepted by some deterministice machine.

True

The language {a^n b^n c^n : n ≥ 0} is NC.

True

The set of all languages over the binary alphabet is countable.

False

No set is larger than IR, the set of real numbers.

False

The furniture mover's problem is known to be NP-complete. (Given a room with a door and given a collection of furniture that must be put into the room, can all the furniture be moved into the room through the door?)

Open

The context-free grammar equivalence problem is co-RE.

False

Let L = {(G1 , G2 )} : G1 and G2 are not equivalent. Then L is recursively enumerable.

True

The factoring problem for unary numerals is P-time.

True

The set of all binary numerals for prime numbers is in P-time.

True

If L is a recursively enumerable language, there must be a machine which enumerates L in canonical order.

False

The set of all positive real numbers is countable.

False

Let L be a recursive language over an alphabet Σ, and M a machine that decides L. For any n, let F(n) be the maximum number of steps M needs to decide whether a given string in Σ∗ of length n is in L. Then F must be recursive.

True

Let L be a recursively enumerable language over an alphabet Σ, and M a machine that accepts L. For any n, let G(n) be the maximum number of steps M needs to accept any string in L of length n. Then G must be recursive.

False

For any alphabet Σ, the set of all recursively enumerable languages over Σ is countable.

True

If L is a context-free language over the unary alphabet, then L must be regular.

True

The union of any two undecidable languages is undecidable.

False

co-P-time= P-time.

Open

Every finite language is decidable.

True

Every context-free language is in Nick's class.

True

2SAT is known to be NP-complete.

False (2SAT is P-time)

The complement of any P-time language is P-time.

True

The complement of any P-space language is P-space.

True

The jigsaw puzzle problem is known to be NP complete.

True

The jigsaw puzzle problem is known to be P-space complete.

False

The furniture mover's problem is known to be P-space complete.

True

The complement of any recursive language is recursive.

True

The complement of any undecidable language is undecidable.

True

Every undecidable language is either RE or co-RE.

False

For any infinite countable sets A and B, there is a 1-1 correspondence between A and B.

True

A language L is recursively enumerable if and only if there is a machine which accepts L.

True

Every NP language is reducible to the independent set problem in polynomial time.

True

If a Boolean expression is satisfiable, there is a polynomial time proof that it is satisfiable.

True

If a language L is recursively enumerable, there is a proof that L is recursively enumerable.

False

If a language L is co-RE, there is a proof that L is co-RE

False

The Post correspondence problem is undecidable.

True

If L1 is NP-complete and L2 is NP, and there is a polynomial time reduction of L1 to L2, then L2 must be (blank).

NP-complete

The class of RE languages is generated by the class of (blank) grammars.

unrestricted (or general, or phase-structure)

A language is (blank) if and only if it is both RE and co-RE.

decidable (or recursive)

The class of push-down-automata accepts the class of (blank) languages.

context-free

The class of Turing machines accepts the class of (blank) languages.

recursively enumerable (RE)

A language L is (blank) if and only if there is a machine which enumerates L in canonical order.

decidable

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
SAT

T

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
2-SAT

F

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
3-SAT

T

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
4-SAT

T

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
Rush Hour

F

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
The Boolean circuit problem (CVP)

F

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
Integer factoring, using binary numerals.

F

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
Tiling, i.e., covering a big polygon exactly with the members of a set of smaller polygons.

T

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
Given a room with a door and some pieces of furniture, move them all into the room through the door.

F

(T if it is known to be NP-complete, F if it is not known to be NP-complete.)
Given a set of trucks, each with a given capacity, and given a set of items, can all the items fit into the trucks?

T

Give a definition of the class P-space.

The class of all languages L such that L is decided by a program whose available memory is a polynomial
function of the length of the input string.

Explain how it is possible to find the maximum of an array of n integers in O(log n) time using O(n/logn) processors. You don't need to draw a diagram, but it might help.

We assume that n = 2k for some k. Otherwise, pad the array with numbers smaller than the first number. For k steps, pair the items of the current array and pick the maximum of those two, resulting in a list half as long. Keep going until there is only one in the list: that will be the maximum of the original list. The number of processors needed in O(n), while the time complexity is O(k) = O(log n), hence the algorithm is N C.

(Which of the following conditions is true if and only if a real number x is recursive?)
a. There is a program which, given n, finds the nth digit after the decimal point of the decimal expansion of x.

T

(Which of the following conditions is true if and only if a real number x is recursive?)
There is a machine which, given any positive integer q, computes an integer p such that
p/q ≤ x < (p+1)/q

T

(Which of the following conditions is true if and only if a real number x is recursive?)
There is a polynomial P with integral coefficients such that P(x) = 0. (ex: 5x^3 − 2x^2 + 9x − 4 is polynomial w/ integral coefficients)

F

(Which of the following conditions is true if and only if a real number x is recursive?)
There is a mathematical definition of x.

F

Which of the above complexity classes is the smallest class which is known to contain SAT, the Boolean satisfiability problem?

NP

Which of the above complexity classes is the smallest class which is known to contain the connectivity
problem for graphs?

P-Time

Which of the above complexity classes is the smallest class which is known to contain the context-free
language membership problem?

NC

Which of the above complexity classes is the smallest class which is known to contain every sliding
block problem?

P-Time

Which of the above complexity classes is the smallest class which is known to contain integer matrix
multiplication?

NC

We say that a computer program is straight-line if no portion of the code can be executed more
than once. That implies that the code contains no loops or recursion, and no GOTO from one line
of the code to an earlier line. Which of the above complexity classes is the smallest class which
contains the problem of determining whether the output of a straight-line program is zero?

P-Time

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

Boolean Satisfiability

T

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

Subset sum problem

T

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

Generalized Checkers

F

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

TSP

T

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

Dominating set problem

T

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

Strong connectivity of directed graphs

F

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

C++ Program equivalence

F

Enter T if it is known to be N P-complete, F
if it is not known to be N P-complete.

Partition

T