patternMinor
Has it been shown or can we show that if $SAT \in P$ then SAT can't be in any complexity class C so that $C \subsetneq P$?
Viewed 0 times
satshowcananyshownbeenhasthatsubsetneqthen
Problem
I'm already guessing that the answer is no because we cannot know whether there is a class "in between" already known classes? Or can we?
I am very new to complexity theory.
Thanks for any answer in advance!
EDIT: Now that I think about it again, what I am asking is if SAT was in P, could we show that SAT could not be in any class less complex than P? Or could not be in any class that requires as much time complexity as P?
I am very new to complexity theory.
Thanks for any answer in advance!
EDIT: Now that I think about it again, what I am asking is if SAT was in P, could we show that SAT could not be in any class less complex than P? Or could not be in any class that requires as much time complexity as P?
Solution
SAT is NP-hard with respect to NC$^0$ reductions, and in particular, it is P-hard with respect to NC$^0$ reductions.
Now let $C$ be a complexity class which is closed under NC$^0$ reductions. If SAT is in $C$ then every problem in P can be reduced to $C$ using NC$^0$ reductions, and so belongs to $C$, implying that $C$ contains P.
Now let $C$ be a complexity class which is closed under NC$^0$ reductions. If SAT is in $C$ then every problem in P can be reduced to $C$ using NC$^0$ reductions, and so belongs to $C$, implying that $C$ contains P.
Context
StackExchange Computer Science Q#140320, answer score: 4
Revisions (0)
No revisions yet.