Describing a nondeterministic polynomial-time algorithm

Assignment Help Computer Engineering

Reference no: EM131748887

Homework

Q1. What would happen if someone discovered an NP-complete language L that was in P? Justify your answer.

Q2. Suppose we know that there is a polynomial-time reduction of a language L to SAT. What can we say about L? Justify your answer.

Q3. The game PEBBLES is played on a k × n chessboard. Initially each square of the chessboard has a black pebble, or a white pebble, or no pebble. You play the game by removing pebbles one at a time. You win the game if you can end up with a board in which each column contains only pebbles of a single color and each row contains at least one pebble.

(a) Show that the set of winnable PEBBLES games is in NP by describing a nondeterministic polynomial-time algorithm to determine whether a given PEBBLES board is winnable.

(b) Given a boolean expression E in 3-CNF with k clauses and n variables, construct the following k × n board: If literal x_i is in clause c_j, put a black pebble in column x_i, row c_j. If literal ¬x_iis in clause c_j, put a white pebble in column x_i, row c_j. Show that E is satisfiable if and only if this PEBBLES game is winnable. [See HMU, Section 10.3.1, p. 448, for a definition of 3-CNF.]

Q4. PAC-learning problem. Suppose we have a collection of 100 concepts. How many samples do we need to examine to find a true concept with an error of at most 0.1 and a probability of at least 95%?

Q5. Consider the lambda expression (λx. a x)((λy. b y) c).

(a) Identify all redexes in this expression.

(b) Evaluate this expression using normal order evaluation.

Q6. Let G be the function definition (λf. λx. f(f x)). Evaluate the lambda expression GG.

Reference no: EM131748887

Questions Cloud

Compare and contrast gilgamesh and rama as heroes : Compare and contrast Gilgamesh and Rama as heroes. How does each hero embody the values of his culture

Discuss christianity influenced medieval european states : Compare the ways that Christianity influenced Medieval European states and the way that Buddhism influenced

Describe that all transactions are cash transactions : Gunn Manufacturing Company experienced the following accounting events during its first year of operation. With the exception of the adjusting entries.

What are the weaknesses of this thesis statement : What are the weaknesses of this thesis statement, essay will cover the ethos, pathos, and logos of the CDC web page

Describing a nondeterministic polynomial-time algorithm : COMS W3261 CS Theory: Homework. Show that the set of winnable PEBBLES games is in NP by describing a nondeterministic polynomial-time algorithm

Design an interior setting from residential domestic waste : design an interior setting from residential domestic waste by using the methods of reuse, recycle and up-cycling which creates environment friendly atmosphere.

Evidence to convince readers that your idea is true : Explain an idea you've had while thinking about and researching your chosen topic, and use logic and evidence to convince readers that your idea

Determine the key challenges that police officers face : Determine the key challenges that police officers face when responding to this problem

Discuss significant influences on art works painting styles : Compare and contrast these two works and discuss significant influences on art works painting styles. Provide links to these works. Minimum: one page.

Reviews

len1748887

12/4/2017 1:21:54 AM

Each problem is worth 20 points. You can discuss problems with others but your answers must be in your own words. Late assignments cannot be accepted. What would happen if someone discovered an NP-complete language L that was in P? Justify your answer.

Write a Review

Required(*) Message

User Account

All Pages