HiveBrain v1.2.0
Get Started
← Back to all entries
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$?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#140320, answer score: 4

Revisions (0)

No revisions yet.