Purchase Solution

Automata and Computability

Not what you're looking for?

Ask Custom Question

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. Because SAT is in NP, it must be true that P is not equal to NP.

Attachments
Purchase this Solution

Solution Summary

The expert describes the error in a fallacious proof.

Solution Preview

Please see the attached file.

Problem 34

Problem:
Describe the error in the following fallacious "proof" that P  NP. Consider an algorithm for SAT: "On input , try all ...

Purchase this Solution


Free BrainMass Quizzes
Basic Networking Questions

This quiz consists of some basic networking questions.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Javscript Basics

Quiz on basics of javascript programming language.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.