Page 1 of 1
8. (10 pts) For each statement below, if the statement would definitely prove that P-NP. write "P=NP next to the stateme
Posted: Sat May 14, 2022 7:37 pm
by answerhappygod
- 8 10 Pts For Each Statement Below If The Statement Would Definitely Prove That P Np Write P Np Next To The Stateme 1 (21.41 KiB) Viewed 79 times
8. (10 pts) For each statement below, if the statement would definitely prove that P-NP. write "P=NP next to the statement. If the statement would definitely prove that PNP, write -P#NP" next to the statement. If the statement would not prove either tesult, write "neither". No explanation is necessary. . There is deterministic polynomial-time algorithm for SAT • There is a nondeterministic polynomial-time algorithm for SAT. • There is a language in NP that, for any integer k, cannot be decided in time On . For any integer k, there is a language in NP that cannot be decided in time O(n) • Every f(n)-time single-tape nondeterministic TM can be converted into a tintime single-tape TM. E