Automata and Computability (A128)

Show that the function K (x) is not a computable function.

Automata and Computability

Show that, if P = NP then every language A  P except A = 0 and A = * is NP-complete. See attached for full problem description.

Automata and Computability

Describe the error in the following fallacious “proof” that P  NP. Consider an algorithm for SAT: “On input , try all possible assignments to the variables. Accept if any satisfy .” This algorithm clearly requires exponential time. Thus SAT has exponential time complexity. Therefore SAT is not in P. ...continues

Java Program - need to create GUI in three different steps

I have posted my JAVA inventory program so far. I need to do 3 more versions of this. I have been using JDK 1.5 to create my programs and will need help with the following versions using this same version. I put enough credits for all three problems as I feel the same person helping me along with this would be easiest, but I can ...continues

Java DVD Inventory Program - need to modify GUI to include more buttons and store items in dat file

Version 3 – Modify the inventory program to include and Add button, a Delete button, and a Modify button on the GUI. These buttons should allow the user to perform the corresponding actions on the item name, the number of units in stock, and the price of each unit. An item added to the inventory should have an item number one m ...continues

Automata and Computability

Show that any PSPACE-hard language is also NP-hard.

Automata and Computability (A136)

Show that ANFA is NL-complete.

Automata and Computability

Let A be the language of properly nested parentheses. For example, ( () ) and ( () ( () ) ) () are in A, but ) ( is not. Show that A is in L.

Automata and Computability

Let EQREX = {R,S | R and S are equivalent regular expressions}. Show that EQREX  PSPACE. See attached file for full problem description.

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.