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 the ...continues

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 descrip ...continues

Automata and Computability

A Boolean formula is a Boolean circuit wherein every gate has only one output wire. The same input variable may appear in multiple places of a Boolean formula. Prove that a language has a polynomial size family of formulas if it is in NC1. Ignore uniformity considerations. See attached file for full problem description.

Automata and Computability

Recall that NPSAT is the class of languages that are recognized by nondeterministic polynomial time Turing machines with an oracle for the satisfiability problem. Show that NPSAT = 2P. See attached file for full problem description.

Automata and Computability

Prove that, if A is a regular language, a family of family programs B1, B2, … exists wherein each Bn accepts exactly the strings in A of length n and is bounded in size by a constant times n. See attached file for full problem description.

Automata and Computability

Show that the problem of testing whether two branching programs compute the same function is solvable in polynomial time if and only if P = NP

Create an application that will allow the user to input a matrix of three columns and four rows

The input must be done though text boxes. By default, the array must have the following values: 5, 2, 3 8, 32, 1 4, 9, 10 17, 15, 12 The application will multiply the columns of the matrix (e.g., 5 * 8 * 4 * 17 = 2720) and subtract the rows (e.g., 5 – 2 – 3 = 0). Display the results for the multiplication of all colu ...continues

Develop a calculator that allows addition, subtraction, multiplication, division, tangent, square, sine, cosine, and absolute value.

The code will be in the VB.NET format with the project name under bxnguyen. This problem is similar to SGSG202828 with the additional information such as "Create numeric buttons for numbers input. Create “.” and “+/-“ buttons for real numbers and negative numbers input. " Develop a calculator that allows addition, subtra ...continues