Purchase Solution

Proof by contradiction

Not what you're looking for?

Ask Custom Question

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 theorem, TIME(nk+1) contains a language which isn't in TIME(nk), which contradicts P  TIME(nk). Therefore P  NP.

See attached file for full problem description.

Attachments
Purchase this Solution
Solution Summary

Show the error in the following fallacious "proof" that P  NP.

Solution Preview

Please see the attachment for solution.

Problem 42

Show the error in the following fallacious "proof" that P  NP. Proof by contradiction. Assume that P = NP. Then SAT  P. So, ...

Purchase this Solution
Free BrainMass Quizzes
Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

C# variables and classes

This quiz contains questions about C# classes and variables.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Javscript Basics

Quiz on basics of javascript programming language.

C++ Operators

This quiz tests a student's knowledge about C++ operators.

View More Free Quizzes
Related BrainMass Solutions

  • Proof by Contradiction: 3n + 2 is Even, N is Even

    424425 Use the proof by contradiction method. Assume that n is a positive integer. Use the proof by contradiction method to prove and explain if 3n + 2 is an even integer then n is an even integer.

  • Integer Proofs by Contradiction

    So, by (*), we know that n is an odd integer. This is a contradiction, as n is even. We complete our proof. Integer proofs by contradiction are provided.

  • Proof methods

    c) proof by contradiction Proof. Suppose that x is even but x^2 is odd.

  • Proofs : Circles and Irrational Numbers

    Proof: (by contradiction) Suppose the radius of the circle is less than .

  • Simple Proof By Contradiction

    This completes the if and only if proof. We prove by contradiction that 3n+2 is even if and only if n is even.

  • Basic Proof by Contradiction of the Zero Product Property

    This solution shows a proof that if ab=0, then a=0 or b=0. Gives an introduction to proving things by contradiction.

  • Introduction to Proofs

    A proof by contra-positive. d. A proof by contradiction. e. A proof by Mathematical Induction. (Question is repeated in attachment) a. Proof that two sets are equal: I'll call the sets A and B.

  • Real Analysis

    Proof. We will prove it by contradiction. Suppose that there is no such elements in B. Namely, for every , there is such that . So we get i.e., a contradiction.

  • Proof of Fixed Point Theorem using Stokes Theorem and Analysis

    18931 Proof of Fixed Point Theorem using Stokes Theorem and Analysis Prove that if D is the closed disc |x|  1 in R2, then any map f 2 C2[D ! D] has a fixed point: f(x) = x. The proof is by contradiction, and uses Stokes theorem.

View More Related Solutions