Explore BrainMass
Share

Explore BrainMass

    Automata and Computability

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com October 9, 2019, 7:16 pm ad1c9bdddf
    https://brainmass.com/computer-science/algorithms/automata-computability-113204

    Attachments

    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 ...

    Solution Summary

    The expert describes the error in a fallacious proof.

    $2.19