Automata and Computability

An undirected graph is bipartite if its nodes may divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn’t contain a cycle that has an odd number of nodes. See attached file for full problem description.

Automata and Computability

Give a circuit that computes the parity function on three input variables and show how it computes on input 011. See attached file for full problem description.

Automata and Computability

Show the error in the following fallacious “proof” that P  NP. Proof by contradiction. Assume that P = NP. Then SAT  P. So, of some k, SAT  TIME(nk). Because every language in NP is polynomial time reducible to SAT, NP  TIME(nk). Therefore P  TIME(nk). But, by the time hierarchy theorem, TIME(nk+1) contains a language which isn’t in TIME(nk), which contradicts P  TIME(nk). Therefore P  NP. See attached file for full problem description.

Automata and Computability

Prove that an oracle C exists for which NPC  coNPC. See attached file for full problem description.

Automata and Computability

Recall that we may consider circuits that output strings over {0,1} by designating several output gates. Let addn: {0,1}2n{0,1}n+1 take the sum of two n bit binary integers and produce the n + 1 bit result. Show that we can compute the addn function with 0(n) size circuits. See attached file for full problem description.