Scribd Logo
Upload

Welcome to Scribd!

  • 29 views

    Homework 2

    Uploaded by

    cock boy jr.
    This document contains 8 homework problems related to automata theory, computability, and complexity. The problems cover topics like space complexity classes, the game of Go-Moku, Savitch's theorem, log-space reductions and completeness, and reachability in directed graphs. The document provides definitions, statements, and explanations to help solve each problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Homework 2

    Uploaded by

    cock boy jr.
    29 views2 pages
    This document contains 8 homework problems related to automata theory, computability, and complexity. The problems cover topics like space complexity classes, the game of Go-Moku, Savitch's theorem, log-space reductions and completeness, and reachability in directed graphs. The document provides definitions, statements, and explanations to help solve each problem.

    Original Title

    homework 2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains 8 homework problems related to automata theory, computability, and complexity. The problems cover topics like space complexity classes, the game of Go-Moku, Savitch's theorem, log-space reductions and completeness, and reachability in directed graphs. The document provides definitions, statements, and explanations to help solve each problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    29 views2 pages

    Homework 2

    Uploaded by

    cock boy jr.
    This document contains 8 homework problems related to automata theory, computability, and complexity. The problems cover topics like space complexity classes, the game of Go-Moku, Savitch's theorem, log-space reductions and completeness, and reachability in directed graphs. The document provides definitions, statements, and explanations to help solve each problem.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    6.045J/18.

    400J: Automata, Computability and Complexity Nancy Lynch

    Homework 12.1 (Fake)


    Due: Never Elena Grigorescu

    Readings: Sipser, Chapter 8 (the whole chapter).

    Problem 1: (Sipser Exercise 8.1) Show that for any function f : N → N , where f (n) ≥ n,
    the space complexity class SPACE(f (n)) is the same whether you define the class by using the
    single-tape TM model or the two tape read-only TM model.
    Problem 2: (Sipser Problem 8.10) The Japanese game go-moku is played by two players, “X”
    and “O”, on a 19 × 19 grid. Players take turns placing markers, and the first player to achieve 5
    of his/her markers consecutively in a row, column, or diagonal, is the winner. Consider this game
    generalized to an n × n board. Let

    GM = {hP i| P is a position in generalized go-moku, where player “X” has a winning strategy}.

    By a position we mean a board with markers placed on it, such as may occur in the middle of a play
    of the game. Show that GM ∈ PSPACE.
    Problem 3: The proof of Savitch’s theorem, in Section 8.1, describes in general how one can
    simulate any f (n)-space-bounded nondeterministic Turing machine N with an f 2 (n)-space-bounded
    deterministic Turing machine M. The key is a recursive computation of the CANYIELD relation,
    which reuses space.
    Give a good upper bound on the running time of M on input w.
    Problem 4: (Sipser Problem 8.12) Show that TQBF restricted to formulas where the part
    following the quantifiers is in conjunctive normal form is still PSPACE-complete.
    Problem 5: (Sipser Problem 8.17) Let A be the language of properly nested parentheses. For
    example, (()) and (()(()))() are in A, but )( is not. Show that A is in L.
    Problem 6: Show:
    1. A ≤L B ⇒ Ā ≤L B̄.
    2. A ≤L B and B ∈ NL ⇒ A ∈ NL.
    3. A ≤L B and B ≤L C ⇒ A ≤L C.

    Problem 7: (Sipser 8.27) Recall that a directed graph is strongly connected if every two nodes
    are connected by a directed path in each direction. Let

    STRONGLY-CONNECTED = {hGi| G is a strongly connected graph}.

    Show that STRONGLY-CONNECTED is NL-complete.


    Problem 8: This problem uses the ideas in the proof of Theorem 8.27.
    Describe a nondeterministic log-space Turing machine M that decides the language

    L = {hG, s, m, ki| G is a directed graph, s is a node in G, m, k ∈ N, and exactly

    m nodes of G are reachable from s ∈ G by paths consisting of at most k edges}.

    12.1 (Fake)-1
    That is, if exactly m nodes are reachable from s ∈ G by paths of length at most k, than M
    must accept hG, s, m, ki on some computation path. On the other hand, if more or fewer than m
    nodes are reachable from s ∈ G by paths of length at most k, then M must reject hG, s, m, ki on all
    computation paths.
    Explain why M works correctly and why it works in log space.

    12.1 (Fake)-2

    You might also like