Write a polynomial-time algorithm

Assignment Help Computer Engineering

Reference no: EM132104013

In this problem assume that P has just been proven equal to NP, and so you have a polynomial time algorithm A that decides 3-SAT; that is, it takes in a logical formula written in 3-SAT form ((x₁ V x₂ V-x₃) (-x₁V x₂ V x₃) and it tells you whether or not a satisfying assignment exists for that formula (you also have a million dollars because you solved P = NP, but that's a different story...)

So you have an algorithm A that tells you whether or not a satisfying solution exists for a logic formula, but you don't have one that tells you what exactly that satisfying solution is.

For this problem, write a polynomial-time algorithm that finds a satisfying solution to an instance of 3-SAT, given that you have a polynomial-time algorithm A you can run that tells you whether or not a solution exists to an instance of 3-SAT.

Reference no: EM132104013

Questions Cloud

Explain the graph theoretic relationship : Explain the difference between a conventional torus and folded torus.

Find the magnitude of the charges : In this case, the line breaks when the kinetic energy of the plane is 52.0 J. Find the magnitude of the charges.

Is it feasible for an attacker to derive m from h : Suppose h=H(m), where H is a cryptographic hash function. Is it feasible for an attacker to derive m from h?

What is the initial charge on object : What is the initial charge on each object, the answer to part (a) being the one with the greater (and positive) value?

Write a polynomial-time algorithm : Write a polynomial-time algorithm that finds a satisfying solution to an instance of 3-SAT, given that you have a polynomial-time algorithm.

Find the magnitude of the net torque applied to the rod : A long, thin rod (length = 6.0 m) lies along the x axis, with its midpoint at the origin. In a vacuum, a +5.0C point charge

What is the electric flux through the cubical surface : The magnitude of the field is 6180 N/C. What is the electric flux through the cubical surface.

Determine the magnitude of the electric field : Starting from rest, the object accelerates to a speed of 1.1 x 103 m/s in a time of 1.3 s. Determine the magnitude of the electric field.

Determine the total size of the cache in bits : In your cache, what will be the tags at the end of the sequence? Assume that cache is initially empty.

User Account

All Pages