# Automata and Computability

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 ad1c9bdddfhttps://brainmass.com/computer-science/algorithms/automata-computability-113204

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